动态规划习题
第 七 章
动态规划
规划问题得最终目得就就是确定各决策变量得取值,以使目标函数达到极大或极小。在线性规划与非线性规划中,决策变量都就是以集合得形式被一次性处理得;然而,有时我们也会面对决策变量需分期、分批处理得多阶段决策问题。所谓 多阶段决策问题就是指这样一类活动过程:它可以分解为若干个互相联系得阶段,在每一阶段分别对应着一组可供选取得决策集合;即构成过程得每个阶段都需要进行一次决策得决策问题。将各个阶段得决策综合起来构成一个决策序列,称为一个策略。显然,由于各个阶段选取得决策不同,对应整个过程可以有一系列不同得策略。当过程采取某个具体策略时,相应可以得到一个确定得效果,采取不同得策略,就会得到不同得效果。多阶段得决策问题,就就是要在所有可能采取得策略中选取一个最优得策略,以便得到最佳得效果。
动态规划(dy n ami c
pro g ramming)同前面介绍过得各种优化方法不同,它不就是一种算法,而就是考察问题得一种途径。动态规划就是一种求解多阶段决策问题得系统技术,可以说它横跨整个规划领域(线性规划与非线性规划)。当然,由于动态规划不就是一种特定得算法,因而它不象线性规划那样有一个标准得数学表达式与明确定义得一组规则,动态规划必须对具体问题进行具体得分析处理。在多阶段决策问题中,有些问题对阶段得划分具有明显得时序性,动态规划得“动态”二字也由此而得名。动态规划得主要创始人就是美国数学家贝尔曼(Bel l ma n )。20 世纪 40 年代末 50 年代初,当时在兰德公司(Rand Cor p orati o n)从事研究工作得贝尔曼首先提出了动态规划得概念。1957 年贝尔曼发表了数篇研究论文,并出版了她得第一部著作《动态规划》。该著作成为了当时唯一得进一步研究与应用动态规划得理论源泉。1961 年贝尔曼出版了她得第二部著作,并于 1962年同杜瑞佛思( D reyfu s )合作出版了第三部著作。在贝尔曼及其助手们致力于发展与推广这一技术得同时,其她一些学者也对动态规划得发展做出了重大得贡献,其中最值得一提得就是爱尔思(A r i s )与梅特顿(Mitten)。爱尔思先后于 1961 年与 1964 年出版了两部关于动态规划得著作,并于 1964 年同尼母霍思尔(Ne m hauser)、威尔德(Wild)一道创建了处理分枝、循环性多阶段决策系统得一般性理论。梅特顿提出了许多对动态规划后来发展有着重要意义得基础性观点,并且对明晰动态规划路径得数学性质做出了巨大得贡献。
动态规划在工程技术、经济管理等社会各个领域都有着广泛得应用,并且获得了显著得效果。在经济管理方面,动态规划可以用来解决最优路径问题、资源分配问题、生产调度问题、库存管理问题、排序问题、设备更新问题以及生产过程最优控制问题等,就是经济管理中一种重要得决策技术。许多规划问题用动态规划得方法来处理,常比线性规划或非线性规划更有效。特别就是对于离散得问题,由于解析数学无法发挥作用,动态规划便成为了一种非常有用得工具。
动态规划可以按照决策过程得演变就是否确定分为 确定性动态规划与 随机性动态规划;也可以按照决策变量得取值就是否连续分为 连续性动态规划与 离散性动态规划。本教材主要介绍动态规划得基本概念、理论与方法,并通过典型得案例说明这些理论与方法得应用。
§7 7 、 1
动态规划得基本理论 1.1 多阶段决策过程得数学描述 有这样一类活动过程,其整个过程可分为若干相互联系得阶段,每一阶段都要作出相应得决策,以使整个过程达到最佳得活动效果。任何一个阶段( stage ,即决策点)都就是由输入( input )、决策( decision )、状态转移律( transformation function )与输出( output )构成得,如图 7-1(a)所示。其中输入与输出也称为状态( state ),输入称为输入状态,输出称为输出状态。
输
出 输
入 决
策 阶
段 状态转移 S n+1
S n
d n
Stage n g n
= r(S n ,d n )
图 7-1 由于每一阶段都有一个决策,所以每一阶段都应存在一个衡量决策效益大小得指标函数,这一指标函数称为 阶段指标函数,用 g n 表示。显然 g n 就是状态变量 S n 与决策变量 d n 得函数,即 g n = r ( S n , d n ),如图 7-1(b)所示。显然,输出就是输入与决策得函数,即:
(7-1) 式(7-1)即为状态转移律。在由 N 个阶段构成得过程里,前一个阶段得输出即为后一个阶段得输入。
1.2 动态规划得基本概念
动态规划得数学描述离不开它得一些基本概念与符号,因此有必要在介绍多阶段决策过程得数学描述得基础上,系统地介绍动态规划得一些基本概念。
1. 阶段( stage )
阶段就是过程中需要做出决策得决策点。描述阶段得变量称为阶段变量,常用 k 来表示。阶段得划分一般就是根据时间与空间得自然特征来进行得,但要便于将问题得过程转化为多阶段决策得过程。对于具有 N 个阶段得决策过程,其阶段变量 k =1,2,„, N 。
2. 状态( state ) 状态表示每个阶段开始所处得自然状况或客观条件,它描述了研究问题过程得状况。状态既反映前面各阶段系列决策得结局,又就是本阶段决策得一个出发点与依据;它就是各阶段信息得传递点与结合点。各阶段得状态通常用状态变量 S k 来加以描述。作为状态应具有这样得性质:如果某阶段状态给定后,则该阶段以后过程得发展不受此阶段以前各阶段状态得影响。换句话说,过程得历史只能通过当前得状态来影响未来,当前得状态就是以往历史得一个总结。这个性质称为 无后效性( the future is independent of the past )或 健忘性( the process is forgetful )。
3. 决策( decision )
决策就是指决策者在所面临得若干个方案中做出得选择。决策变量 d k 表示第 k 阶段得决策。决策变量 d k 得取值会受到状态 S k 得某种限制,用 D k ( S k )表示第 k 阶段状态为 S k 时决策变量允许得取值范围,称为 允许决策集合,因而有 d k ( S k ) D k ( S k )。
4. 状态转移律( transformation function ) 状态转移律就是确定由一个状态到另一状态演变过程得方程,这种演变得对应关系记为 S k+1
= T k ( S k
, d k )。
5. 策略( policy )与子策略( sub-policy )
由所有阶段决策所组成得一个决策序列称为一个策略,具有 N 个阶段得动态规划问题得策略可表示为:
从某一阶段开始到过程终点为止得一个决策子序列,称为 过程子策略或 子策略。从第 k个阶段起得一个子策略可表示为:
6. 指标函数 指标函数有 阶段指标函数与 过程指标函数之分。阶段指标函数就是对应某一阶段决策得效率度量,用 g k = r ( S k , d k )来表示;过程指标函数就是用来衡量所实现过程优劣得数量指标,就是定义在全过程(策略)或后续子过程(子策略)上得一个数量函数,从第 k 个阶段起得一个子策略所对应得过程指标函数常用 G k,N 来表示,即:
构成动态规划得过程指标函数,应具有可分性并满足递推关系;即:
这里得表示某种运算,最常见得运算关系有如下二种: (1)
过程指标函数就是其所包含得各阶段指标函数得“与”,即:
于就是
(2)
过程指标函数就是其所包含得各阶段指标函数得“积”,即:
于就是
7. 最优指标函数 从第个阶段起得 最优子策略所对应得过程指标函数称为最优指标函数,可以用式(7-2)加以表示:
(7-2)
其中“ opt ”就是最优化“ optimization ”得缩写,可根据题意取最大“ max ”或最小“ min ”。在不同得问题中,指标函数得含义可能就是不同得,它可能就是距离、利润、成本、产量或资源量等。
1.3 动态规划得数学模型
动态规划得数学模型除包括式(7-2)外,还包括阶段得划分、各阶段得状态变量与决策变量得选取、允许决策集合与状态转移律得确定等。
如何获得最优指标函数呢?一个阶段得决策过程,具有如下一些特性: (1)
刚好有个决策点; (2 2 )
对阶段而言,除了其所处得状态与所选择得决策外,再没有任何其它因素影响决策得最优性了;
(3 3 )
阶段仅影响阶段得决策,这一影响就是通过来实现得;
(4 4 )
贝尔曼( Bellman )最优化原理:在最优策略得任意一阶段上,无论过去得状态与决策如何,对过去决策所形成得当前状态而言,余下得诸决策必须构成最优子策略。
根据贝尔曼( Bellman )最优化原理,可以将式(7-2)表示为递推最优指标函数关系式(7-3)或式(7-4):
(7-3)
(7-4)
利用式(7-3)与式(7-4)可表示出最后一个阶段(第 N 个阶段,即 k=N )得最优指标函数:
(7-5)
(7-6) 其中称为 边界条件。一般情况下,第阶段得输出状态已经不再影响本过程得策略,即式(7-5)中得边界条件,式(7-6)中得边界条件;但当问题第阶段得输出状态对本过程得策略产生某种影响时,边界条件就要根据问题得具体情况取适当得值,这一情况将在后续例题中加以反映。
已知边界条件,利用式(7-3)或式(7-4)即可求得最后一个阶段得最优指标函数;有了,继续利用式(7-3)或式(7-4)即可求得最后两个阶段得最优指标函数;有了,进一步又可以求得最后三个阶段得最优指标函数;反复递推下去,最终即可求得全过程个阶段得最优指标函数,从而使问题得到解决。由于上述最优指标函数得构建就是按阶段得逆序从后向前进行得,所以也称为动态规划得 逆序算法。
通过上述分析可以瞧出,任何一个多阶段决策过程得最优化问题,都可以用非线性规划(特殊得可以用线性规划)模型来描述;因此,从原则上讲,一般也可以用非线性规划(或线性规划)得方法来求解。那么利用动态规划求解多阶段决策过程有什么优越性、又有什么局
限性呢? 动态规划得优点: 第一, , 求解更容易、效率更高。动态规划方法就是一种逐步改善法,它把原问题化成一系列结构相似得最优化子问题,而每个子问题得变量个数比原问题少得多,约束集合也简单得多,故较易于确定最优解。
第二, , 解得信息更丰富。非线性规划(或线性规划)得方法就是对问题得整体进行一次性求解得,因此只能得到全过程得解;而动态规划方法就是将过程分解成多个阶段进行求解得,因此不仅可以得到全过程得解,同时还可以得到所有子过程得解。
动态规划得缺点: 第一,没有一个统一得标准模型。由于实际问题不同,其动态规划模型也就各有差异,模型构建存在一定困难。
第二, , 应用条件苛刻。由于构造动态规划模型状态变量必须满足“无后效性”条件,这一条件不仅依赖于状态转移律,还依赖于允许决策集合与指标函数得结构,不少实际问题在取其自然特征作为状态变量时并不满足这一条件,这就降低了动态规划得通用性。
第三, ,” 状态变量存在“维数障碍”。最优指标函数就是状态变量得函数,当状态变量得维数增加时,最优指标函数得计算量将成指数倍增长;因此,无论就是手工计算还就是电算“维数障碍”都就是无法完全克服得。
§7 7 、2
确定性动态规划问题
确定性动态规划问题即阶段得输出状态完全由其输入状态与决策所决定得动态规划问题。确定性动态规划解决得问题可能包含经济管理得方方面面,可以就是最短路线问题,可以就是资源配置问题,也可以就是其她得规划优化问题。最短路线问题直观、具体地演示了动态规划得基本概念与基本步骤;因此,让我们首先来分析一下最短路线问题。
2- -1 1 最短路线问题
[ [例 例 7 7- - 1] 美国黑金石油公司( The Black Gold Petroleum pany )最近在阿拉斯加( Alaska )得北斯洛波( North Slope )发现了大得石油储量。为了大规模开发这一油田,首先必须建立相应得输运网络,使北斯洛波生产得原油能运至美国得 3 个装运港之一。在 油田得集输站(结点 C )与 装运港(结点 P 1 、 P 2 、 P 3 )之间需要若干个中间站,中间站之间得联通情况如图 7-2 所示,图中线段上得数字代表两站之间得距离(单位:10千米)。试确定一最佳得输运线路,使原油得输送距离最短。
解:最短路线有一个重要性质,即如果由起点 A 经过 B 点与 C 点到达终点 D 就是一条最短路线,则由 B 点经 C 点到达终点 D 一定就是 B 到 D 得最短路(贝尔曼最优化原理)。此性质用反证法很容易证明,因为如果不就是这样,则从 B 点到 D 点有另一条距离更短得路线存在,不妨假设为 B—P—D ;从而可知路线 A—B—P—D 比原路线 A—B—C—D 距离短,这与原路线A—B—C—D 就是最短路线相矛盾,性质得证。
根据最短路线得这一性质,寻找最短路线得方法就就是从最后阶段开始,由后向前逐步递推求出各点到终点得最短路线,最后求得由始点到终点得最短路;即动态规划得方法就是从终点逐段向始点方向寻找最短路线得一种方法。按照动态规划得方法,将此过程划分为 4个阶段,即阶段变量;取过程在各阶段所处得位置为状态变量,按逆序算法求解。
当时: 由结点 M 31 到达目得地有两条路线可以选择,即选择 P 1 或 P 2 ;故:
选择 P 2
由结点 M 32 到达目得地有三条路线可以选择,即选择 P 1 、 P 2 或 P 3 ;故:
选择 P P 2 2
由结点 M 33 到达目得地也有三条路线可以选择,即选择 P 1 、 P 2 或 P 3 ;故:
选择 P P 3 3
C P 3
P 2
P 1
M 11
M 12
M 21
M 22
M 23
M 31
M 32
M 33
M 34
10 12 8 6 9 11 10 7 6 9 7 5 11 4 6 8 6 4 3 7 7 6 5 3 4
由结点 M 34 到达目得地有两条路线可以选择,即选择 P 2 或 P 3 ;故:
选择 P 2
当时:
由结点 M 21 到达下一阶段有三条路线可以选择,即选择 M 31 、 M 32 或 M 33 ;故:
选择 M 32
由结点 M 22 到达下一阶段也有三条路线可以选择,即选择 M 31 、 M 32 或 M 33 ;故:
选择 M M 32 或 M M 33
由结点 M 23 到达下一阶段也有三条路线可以选择,即选择 M 32 、 M 33 或 M 34 ;故:
选择 M 33 或 M 34
当时: 由结点 M 11 到达下一阶段有两条路线可以选择,即选择 M 21 或 M 22 ;故:
选择 M 2 2 2
由结点 M 12 到达下一阶段也有两条路线可以选择,即选择 M 22 或 M 23 ;故:
选择 M 22
当时:
由结点 C 到达下一阶段有两条路线可以选择,即选择 M 11 或 M 12 ;故:
选择 M 1 1 1
从而通过顺序(计算得反顺序)追踪(黑体标示)可以得到两条最佳得输运线路: C C — M M 11 —M M 2 2 2 — M 32 — P P 2 2 ; C C — M 11 — M 22 — M 33 — P P 3 3 。最短得输送距离就是 280 千米。
2- -2 2 资源分配问题
所谓资源分配问题,就就是将一定数量得一种或若干种资源(如原材料、机器设备、资金、劳动力等)恰当地分配给若干个使用者,以使资源得到最有效地利用。设有 m 种资源,总量分别为 b b i i ( i
= 1,2,, m ),用于生产 n n 种产品,若用 x x ij 代表用于生产第 j j 种产品得第 i i种资源得数量( j
= 1,2,, n ),则生产第 j j 种产品得收益就是其所获得得各种资源数量得函数,即 g j
= f ( x 1j , x 2j ,,
x mj )。由于总收益就是 n n 种产品收益得与,此问题可用如下静态模型加以描述:
若 x x ij j 就是连续变量,当 g j
= f ( x 1j , x 2j ,,
x mj )就是线性函数时,该模型就是线性规划模型;当 g j
= f ( x 1j , x 2j ,,
x mj )就是非线性函数时,该模型就是非线性规划模型。若 x x ij就是离散变量或(与) g j
= f ( x 1j , x 2j ,,
x mj )就是离散函数时,此模型用线性规划或非线性规划来求解都将就是非常麻烦得。然而在此情况下,由于这类问题得特殊结构,可以将它瞧成为一个多阶段决策问题,并利用动态规划得递推关系来求解。
本教材只考虑一维资源得分配问题,设状态变量 S k 表示分配于从第 k 个阶段至过程最终(第 N 个阶段)得资源数量,即第 k 个阶段初资源得拥有量;决策变量 x k 表示第 k 个阶段资源得分配量。于就是有状态转移律:
允许决策集合:
最优指标函数(动态规划得逆序递推关系式):
利用这一递推关系式,最后求得得即为所求问题得最大总收益,下面来瞧一个具体得例
子。
[ [例 例 7 7- - 2] 某公司拟将 500 万元得资本投入所属得甲、乙、丙三个工厂进行技术改造,各工厂获得投资后年利润将有相应得增长,增长额如表 7-1 所示。试确定 500 万元资本得分配方案,以使公司总得年利润增长额最大。
表7-1 投资额 100万元 200 万元 300 万元 400万元 500 万元 甲 3
乙 5
10 丙 4
0 解:将问题按工厂分为 三个阶段,设 状态变量()代表从第个工厂到第 3 个工厂得投资额,决策变量代表第个工厂得投资额。于就是有 状态转移率、 允许决策集合与递推关系式:
当时: :
于就是有表 7-2,表中表示第三个阶段得最优决策。
表 7-2
( 单位:百万元 )
0
1 2 3 4 5
0 1 2 3 4 5
0 0、4 0、6 1、1 1、2 1、2 当时: :
于就是有表 7-3。
表 7-3
( 单位:百万元 )
x 2
S 2
g 2 (x 2 )+f 3 (s 2 - x 2 )
0 1 2 3 4 5 0 0+0
0 0 1 0+0、4 0、5+0
0、5 1 2 0+0、6 0、5+0、4 1、0+0
1、0 2 3 0+1、1 0、5+0、6 1、0+0、4 1、1+0
1、4 2 4 0+1、2 0、5+1、1 1、0+0、6 1、1+0、4 1、1+0
1、6 1,2 5 0+1、2 0、5+1、2 1、0+1、1 1、1+0、6 1、1+0、4 1、1+0 2、1 2 当时: :
于就是有表 7-4。
表 7-4 x 1
S 1
g 1 (x 1 )+f 2 (s 1 – x 1 )
0 1 2 3 4 5 5 0+2、1 0、3+1、6 0、7+1、4 0、9+1、0 1、2+0、5 1、3+0 2、1 0,2
然后按计算表格得顺序反推算,可知最优分配方案有两个:(1)甲工厂投资200万元,乙工厂投资 200 万元,丙工厂投资 100 万元;(2)甲工厂没有投资,乙工厂投资 200 万元,丙工厂投资 300 万元。按最优分配方案分配投资(资源),年利润将增长210万元。
这个例于就是决策变量取离散值得一类分配问题,在实际问题中,相类似得问题还有销售店得布局(分配)问题、设备或人力资源得分配问题等。在资源分配问题中,还有一种决策变量为连续变量得资源分配问题,请见例 7-3。
[例 7 7- -3 3 ]
机器负荷分配问题。某种机器可在高低两种不同得负荷下进行生产,设机器在高负荷下生产得产量(件)函数为,其中为投入高负荷生产得机器数量,年度完好率(年底得完好设备数等于年初完好设备数得70%);在低负荷下生产得产量(件)函数为,其中为投入低负荷生产得机器数量,年度完好率。假定开始生产时完好得机器数量为 1000 台,试问每年应如何安排机器在高、低负荷下得生产,才能使 5 年生产得产品总量最多? 解:设 阶段表示年度(); 状态变量为第年度初拥有得完好机器数量(同时也就是第年度末时得完好机器数量)。
决策变量为第年度分配高负荷下生产得机器数量,于就是为该年度分配在低负荷下生产得机器数量。这里得与均为连续变量,它们得非整数值可以这样理解:如就表示一台机器在第年度中正常工作时间只占全部时间得 60%;就表示一台机器在第年度中只有 30%得工作时间在高负荷下运转。
状态转移方程为: k k k k k k k k kx S x S x x S x S 2 . 0 9 . 0 ) ( 9 . 0 7 . 0 ) (1
允许决策集合:
设 阶段指标为第年度得产量,则:
过程指标就是阶段指标得与,即:
令 最优值函数表示从资源量出发,采取最优子策略所生产得产品总量,因而有逆推关系式:
边界条件。
当时: :
因就是关于得单调递增函数,故取,相应有。
当时:
因就是关于得单调递增函数,故取,相应有;依次类推,可求得: 当时: :, 当时: :, 当时: :,
计算结果表明最优策略为:,,,,;即前两年将全部设备都投入低负荷生产,后三年将全部设备都投入高负荷生产,这样可以使 5 年得总产量最大,最大产量就是 23700 件。
有了上述最优策略,各阶段得状态也就随之确定了,即按阶段顺序计算出各年年初得完好设备数量。
上面所讨论得过程始端状态就是固定得,而终端状态就是自由得,实现得目标函数就是
5 年得总产量最高。如果在终端也附加上一定得约束条件,如规定在第 5 年结束时,完好得机器数量不低于350台(上面得例子只有 278 台),问应如何安排生产,才能在满足这一终端要求得情况下使产量最高呢? 解:
阶段表示年度(); 状态变量为第年度初拥有得完好机器数量; 决策变量为第年度分配高负荷下生产得机器数量; 状态转移方程为: k k k k k k k k kx S x S x x S x S 2 . 0 9 . 0 ) ( 9 . 0 7 . 0 ) (1
终端约束:
允许决策集合: : “加”第阶段得终端递推条件
对于,考虑终端递推条件有:
同理其她各阶段得允许决策集合可在过程指标函数得递推中产生。
设 阶段指标:
过程指标:
最优值 函数:
边界条件。
当时: :
因就是关于得单调递增函数,故取,相应有:
即:
, 当时: :
由可得,又因就是关于得单调递减函数,故取,相应有:
, 当时: :
由可得,又因就是关于得单调递减函数,故取,相应有:
由于,所以就是恒成立得,即。
,
当时: :
因就是关于得单调递减函数,而得取值并不对有下界得约束,故取,相应有: , 当时:
因就是关于得单调递减函数,故取,相应有:
, 计算结果表明最优策略为: (1)第 1 年将全部设备都投入低负荷生产。
,,
(2)第 2 年将全部设备都投入低负荷生产。
,,
(3)第 3 年将台完好设备投入高负荷生产,将剩余得台完好设备投入低负荷生产。
(4)第4年将台完好设备均投入高负荷生产,将剩余得 1 台完好设备均投入低负荷生产。
(5)第 5 年将,即将台完好设备均投入高负荷生产。
2 2- -3 3 存贮控制问题
由于供给与需求在时间上存在差异,需要在供给与需求之间构建存贮环节以平衡这种差异。存贮物资需要付出资本占用费与保管费等,过多得物资储备意味着浪费;而过少得储备又会影响需求造成缺货损失。存贮控制问题就就是要在平衡双方得矛盾中,寻找最佳得采购批量与存贮量,以期达到最佳得经济效果。
例 [例 7 7- - 4 ] 某鞋店销售一种雪地防潮鞋,以往得销售经历表明,此种鞋得销售季节就是从 10 月 1 日至 3 月31 日。下个销售季节各月得需求预测值如表 7-5 所示。
表 7-5
( 单位:双 ) 月份 10 11 12 1 2 3 需求 4
该鞋店得此种鞋完全从外部生产商进货,进货价每双4美元。进货批量得基本单位就是箱,每箱10 双。由于存贮空间得限制,每次进货不超过 5 箱。对应不同得订货批量,进价享受一定得数量折扣,具体数值如表 7-6 所示。
表 7-6 进货批量 1 箱 2 箱 3箱 4 箱 5 箱 数量折扣 4% 5% 10% 20% 25% 假设需求就是按一定速度均匀发生得,订货不需时间,但订货只能在月初办理一次,每次订货得采购费(与采购数量无关)为 10 美元。月存贮费按每月月底鞋得存量计,每双 0、2美元。由于订货不需时间,所以销售季节外得其她月份得存贮量为“0”。试确定最佳得进货
方案,以使总得销售费用最小。
解:阶段:将销售季节 6 个月中得每一个月作为一个阶段,即; 状态变量:第阶段得状态变量代表第个月初鞋得存量; 决策变量:决策变量代表第个月得采购批量; 状态转移律:(就是第个月得需求量); 边界条件:,; 阶段指标函数:代表第个月所发生得全部费用,即与采购数量无关得 采购费、与采购数量成正比得 购置费与 存贮费。其中: ;; 最优指标函数:最优指标函数具有如下递推形式
当时( ( 3月) ): 表 7-7 S 6
0 10 20 x 6
20 10 0 f 6 ( S 6 )
86 48 0 当时( ( 2月) ):
表 7-8 x 5 S 5
0
204
1
0 142 2
122 30 86 98 90
0 86 40 50 52
0 50 50 4
0 4 当时(1 1 月) ): 表 7-9 x 4 S 4
2 1
0、40 282 2
52 20 250 3
30 218 10 212 4
1
5
76 152
0 144 6
32
0 126 当时 (1 2月) ): 表 7-10 x 3 S 3
0 414 1
84 50 384 2
62 332 50 332
3
42 310 314 0 302 4
9
当时1 (11 月) ): 表 7-11 x 2 S 2
68 50 468 1
46 452 40 446 当时0 (10 月) ): 表7-12 x 1 S 1
6 利用状态转移律,按上述计算得逆序可推算出最优策略:10 月份采购4箱(40 双),11月份采购 5 箱(50 双),12 月份不采购,1 月份采购 4 箱(40双),2 月份采购5箱(50 双),3月份不采购;最小得销售费用为 606 美元。
2-4 4 用动态规划求解非线性规划问题
非线性规划问题得求解(在第六章中已讨论)就是非常困难得;然而,对于有些非线性规划问题,如果转化为用动态规划来求解将就是十分方便得。
[ [例 例 7 7 - 5] 用动态规划求解
解:阶段:将问题得变量数作为阶段,即; 决策变量:决策变量; 状态变量:状态变量代表第阶段得约束右端项,即从到占有得份额; 状态转移律:; 边界条件:,; 允许决策集合 :
当时: :
当时: :
设,于就是 令,可得或 又因,所以:
,就是得极小值点 ,就是得极大值点 于就是:
当时: :
同上可得:
由,有 由,有
于就是得到最优解,最优值。
习题: :
1. 某公司打算向它得三个营业区增设 6 个销售店,每个营业区至少增设1个。各营业区每年增加得利润与增设得销售店个数有关,具体关系如表1所示。试规划各营业区应增设销售店得个数,以使公司总利润增加额最大。
表 1 增设销售店个数 营业区 A
营业区 B
营业区 C
1 100(万元) 120(万元) 150(万元)
2 160 150 165 3 190 170 175 4 200 180 190 2. 某工厂有 100 台机器,拟分 4 个周期使用,在每一周期有两种生产任务,据经验把机器投入第一种生产任务,则在一个周期中将有六分之一得机器报废,投入第二种生产任务,则有十分之一得机器报废。如果投入第一种生产任务每台机器可收益 1 万元,投入第二种生产任务每台机器可收益 0、5 万元。问怎样分配机器在 4 个周期内得使用才能使总收益最大? 3. 某公司生产一种产品,估计该产品在未来四个月得销售量分别为300、400、350 与250件。生产该产品每批得固定费用为 600 元,每件得变动费用为 5 元,存储费用为每件每月2元。假定第一个月月初得库存为 100 件,第四个月月底得存货为 50件。试求该公司在这四个月内得最优生产计划。
- 范文大全
- 职场知识
- 精美散文
- 名著
- 讲坛
- 诗歌
- 礼仪知识
-
超星尔雅学习通《对话大国工匠致敬劳动模范》题库附答案
超星尔雅学习通《对话大国工匠致敬劳动模范》题库附答案 1、历史只会眷顾坚定者、奋进者、搏击者,而不会
【入党申请书】 日期:2021-05-12
-
对于政治生态考核整改工作方案
本文系作者原创投稿,仅供学习参考,请勿照搬照抄! 关于政治生态考核整改工作的方案 为做好推进风清气正
【经济工作】 日期:2020-06-05
-
大学生学习2024年两会精神心得感悟
大学生学习2024年两会精神心得感悟过去一年,是全面贯彻二十大精神的开局之年,中国共产党带领全国各族人民,付出艰辛努力,换来重大成
【心得体会】 日期:2024-03-07
-
中国传统故事英文版 中国古代故事英文版
历史学科蕴含着许多丰富的、生动的、有趣的素材,每一个历史事件、历史人物都有相关的、动人的历史小故事,都能给人以启迪。你对中国古代的故事了解多少呢?下面是小编为您...
【调查报告】 日期:2019-05-22
-
基尔霍夫定律验证实验报告
基尔霍夫定律的验证的实验报告本文关键词:基尔,定律,霍夫,验证,实验基尔霍夫定律的验证的实验报告本文
【思想宣传】 日期:2021-03-08
-
中小学党建工作实施意见
中小学党建设工作实施意见中小学校担负着培养德智体美全面发展的社会主义建设者和接班人的重要使命。加强中
【爱国演讲】 日期:2020-09-22
-
地藏经诵读仪规(完整版)
地藏经诵读仪规(完整版) 恭请文: 恭请大慈大悲大愿地藏王菩萨、护法诸天菩萨慈悲加持护念弟子***能
【个人简历】 日期:2021-03-31
-
小学党建工作制度
小学党建工作制度33篇 党建工作责任制度 1 党支部年初制定全年党建工作计划,将目标任务分解到有关部
【思想学习】 日期:2021-02-10
-
青年学生学习全国人大十四届二次会议心得感想16篇
青年学生学习全国人大十四届二次会议心得感想16篇报告中提到政府在经济调控、消费政策、基础设施和制造业投资、房地产调控以及地方债务
【心得体会】 日期:2024-03-07
-
材料力学考题
材料力学考题本文关键词:材料力学,考题材料力学考题本文简介:材料力学1、简易起重设备中,AC杆由两根
【入党申请书】 日期:2021-03-06
-
执行信息公开网
执行信息公开网 执行信息公开网 执行信息公开网: zhi*ing (点击下图可直接进行访问) 全国
【职场知识】 日期:2020-07-03
-
大学教师毕业设计指导记录4篇
大学教师毕业设计指导记录4篇 毕业设计是指工、农、林科高等学校和中等专业学校学生毕业前夕总结性的独立作业。是实践性教学最后一
【职场知识】 日期:2022-05-11
-
年国家开放大学电大电子商务单选题题库
单选: 1、EDI是指A、电子商务B、电子数据交换C、电子交易 D、移动数据交换 答案: B 2、电
【职场知识】 日期:2020-06-05
-
“以学生为中心”的教学原则
以学生为中心的教学原则教师在开展以学生为中心的教学实践中,必须谨记学习目标不再是知识的获得,能力要比知识更重要。以下是蒲公英阅读网
【职场知识】 日期:2023-01-05
-
有机磷酸酯类中毒及其解救(实验报告范文)
有机磷酸酯类中毒及其解救XXX、XXX一、实验目的1 观察有机磷酸酯类农药敌百虫中毒时的症状。 2
【职场知识】 日期:2020-08-30
-
组工干部学习谈治国理政第三卷《共建创新包容开放型世界经济》心得体会
组工干部学习谈治国理政第三卷《共建创新包容的开放型世界经济》心得体会 《习近平谈治国理政》第三卷第七
【职场知识】 日期:2020-09-22
-
心理健康黑板报_心理健康黑板报图片
虽然工作上难免压力,但是只要正视压力,一切就不会太辛苦。下面就随小编看看心理健康黑板报内容,希望喜欢哦。 心理健康黑板报图片欣赏 心理健康黑板报图片1 心理健...
【职场知识】 日期:2020-02-26
-
2021教育基础知识试题(附答案)
2021教育基础知识精选试题(附答案) 1、主张恢复西方传统教育核心价值,反对“进步教育
【职场知识】 日期:2021-03-17
-
男一分钟仰卧起坐标准表
表表11--13 男生一分钟仰卧起坐、引体向上单项评分表(单位:次) 等级 单项 得分 三年级 四年
【职场知识】 日期:2021-05-08
-
发展党员工作部门联审征求意见表
发展党员工作部门联审征求意见表发展对象姓 名 性别 出生年月 身份证号 现工作单位及职务 家庭住址
【职场知识】 日期:2020-09-22
-
唐代诗人李昂个人信息
唐代诗人李昂个人信息 导读:我根据大家的需要整理了一份关于《唐代诗人李昂个人信息》的内容,具体内容:
【古典文学】 日期:2020-11-07
-
[关于中秋的朗诵诗词] 关于爱国的朗诵诗词
中秋,热闹的街头树起了灯彩,舞起了火龙。你知道多少关于中秋的朗诵诗词?下面小编为你整理了几篇关于中秋的朗诵诗词,希望对你有帮助。 关于中秋的朗诵诗词一 中秋佳节...
【古典文学】 日期:2019-06-06
-
叠加原理实验报告
一、实验目的1、通过实验来验证线性电路中的叠加原理以及其适用范围。 2、学习直流仪器仪表的测试方法。
【古典文学】 日期:2020-11-12
-
输血查对制度
输血查对制度依据卫生部《临床输血技术规范》的要求,制订抽血交叉配备查对制度、取血查对制度、输血查对制
【古典文学】 日期:2020-09-24
-
大气唯美黑板报【国庆节大气黑板报】
日本在投降的那一天,再也没有昔日的嚣张,我们中国的屈辱得到洗刷。下面就随小编看看国庆节大气黑板报内容,希望喜欢哦。 国庆节大气黑板报图片欣赏 国庆节大气黑板报...
【古典文学】 日期:2019-05-05
-
【二人旅游英语情景对话】 二人英语对话2分钟旅游
随着国内外旅游业市场的不断扩大,旅游英语人才成为社会的紧缺人才。小编精心收集了二人旅游英语情景对话,供大家欣赏学习! 二人旅游英语情景对话1 A:Itsmyfirsttimeto...
【古典文学】 日期:2020-02-29
-
怎样认识世界处于百年未有之大变局
怎样认识世界处于百年未有之大变局 首先,“大变局”是对国际格局发生巨大变迁的
【古典文学】 日期:2020-10-28
-
2021公安专业知识考试练习题(附答案)
2021公安专业知识考试练习题(附答案) 1 甲地公安机关接到群众举报,在当天举行的大型娱乐活动中,
【古典文学】 日期:2021-01-29
-
乳糖检测方法
附录A(规范性附录) 乳糖的测定A 1原理牛乳或乳粉样液经沉淀剂澄清后,样液中的乳糖在苯酚、氢氧化钠
【古典文学】 日期:2020-12-08
-
[合作与成功的故事]团队合作成功的案例
学会合作,合作是一种深刻后的美丽,因为一滴水只有融入大海,才能够激起美丽的浪花。关于合作你了解吗?以下是小编分享的合作与成功的故事,一起来和小编看看吧。 合作与成...
【古典文学】 日期:2020-02-27
-
时尚女装店面装修效果图|韩式女装店面装修
在服装店的设计之中,我们要将多变、创新、品牌自身的定位与发展趋势相结合,用一种可持续的设计方式呈现出来,以便更加适应不断更新的展示主体。下面小编就为大家解开时尚女装店...
【中国文学】 日期:2019-05-16
-
2021年超星尔雅学习通《辩论与修养》章节测试试题(共183题附答案)
2021年超星尔雅学习通《辩论与修养》章节测试试题(共183题附答案)1、辩论的目的不是单纯获得某种
【中国文学】 日期:2021-05-12
-
天地人格最佳搭配起名技巧|天地人格的五行怎么算
天地有阴有阳,物体刚柔表里,而数字则有一个诱导力,那么你知道怎么计算天地人格来取名吗?今天小编为你整理了天地人格最佳搭配起名技巧,一起来看看用天地人格取名的方法有哪些...
【中国文学】 日期:2019-06-06
-
信息技术重要性
信息技术的重要性 信息技术与课程整合将带来课程内容的革新,信息技术的高速发展,要求传统的课程必须适应
【中国文学】 日期:2021-02-11
-
2022年当前世界下中国面临国际形势论文范本
和平与发展仍然是当今时代的主题。谋和平、求合作、促发展是各国人民的共同愿望。为了大家学习方便,下面是小编为大家整理的当前世界下中国面临的国际形势论文范文内容,以供参...
【中国文学】 日期:2022-03-31
-
【世界上最大的半岛】阿拉伯半岛
你知道世界上最大的半岛是什么吗?下面由小编来介绍一下。 阿拉伯半岛的简介 阿拉伯半岛(阿拉伯文:)位于亚洲,是世界上最大的半岛。沙特阿拉伯、也门、阿曼、阿拉伯联合...
【中国文学】 日期:2019-05-24
-
古代人物漫画女生唯美图片欣赏 漫画人物图片女孩唯美
中国漫画始于清末民初,而平面设计虽然其名称是在改革开放以后确立的,但设计活动却自古就有,二者的相互影响是本文的主要讨论范围。小编整理了唯美古代女生人物漫画,欢迎阅读!...
【中国文学】 日期:2020-03-19
-
雪天安全行车注意事项_雪天安全行车提示语
维护城市交通秩序,争做河源文明市民。你们想看看雪天安全行车提示语有哪些吗?以下是小编推荐雪天安全行车提示语给大家,欢迎大家阅读! 安全行车温馨提示语【经典篇】 1...
【中国文学】 日期:2020-03-15
-
2021年5月时事政治热点(国内+国际)
2021年年5月时事政治热点(国内+国际)国内部分 1 55月月66日,由商务部和海南省人民政府共同
【中国文学】 日期:2021-06-10
-
关于通过努力获得成功的故事:靠自己努力成功的例子
努力,是成功的一半。人生道路上难免会遇到挫折,但我们不应后退,应向理想之路奋勇前进。关于名人努力成功的故事你了解吗?以下是小编分享的关于通过努力获得成功的故事,一起...
【中国文学】 日期:2020-03-03
-
改革开放大事记简表(改革开放新时期1978-2012年)
改革开放大事记简表 (1978-2012年) 时间1978年12月18日至22日地点北京事件党的十一
【外国名著】 日期:2021-06-17
-
山东省生产经营单位安全生产主体责任规定(303号令)
山东省生产经营单位安全生产主体责任规定(2013年2月2日山东省人民政府令第260号公布根据2016
【外国名著】 日期:2020-10-22
-
大学生音乐欣赏论文 大学音乐鉴赏论文3000
今天小编就为你介绍关于大学生音乐欣赏论文,下面是!小编给你搜集了相关资料!希望可以能帮助到大家。 大学生音乐欣赏论文—第一篇 音乐是生活不可缺少的一部分,学会欣...
【外国名著】 日期:2019-05-27
-
材料力学金属扭转实验报告
材料力学金属扭转实验报告 【实验目的】 1、验证扭转变形公式,测定低碳钢的切变模量G。;测定低碳钢和
【外国名著】 日期:2020-11-27
-
长豆角家常做法怎么做好吃营养 炒豆角的家常做法
豆角在我们日常生活中是很常见的食材,可能我们只知道它含有优质蛋白和维生素,其实它还有其他的营养价值。它也是可以和很多食材做搭配的。下面小编为大家整理了长豆角的做法...
【外国名著】 日期:2020-02-26
-
(新版)就业知识竞赛题库及答案解析
(新版)就业知识竞赛题库(全真题库) 一、单选题1 (单选):在职业生涯规划工具中,组织在展开员工职
【外国名著】 日期:2021-07-21
-
植物装饰画黑白图片欣赏|荷花装饰画黑白图片
装饰画是一种装饰性艺术,是装饰性和创造性相结合的艺术设计形式。小编整理了植物装饰画黑白,欢迎阅读! 植物装饰画黑白图片展示 植物装饰画黑白图片1 植物装饰画黑白...
【外国名著】 日期:2019-05-31
-
坚定不移全面从严管党治警研讨发言稿
坚定不移全面从严管党治警研讨发言稿政治建警、从严治警是党在新时代的建警治警方针。一年前的全国公安工作
【外国名著】 日期:2020-09-18
-
白烛葵的花语:白烛葵的不死幻想症
白烛葵,花名,花语为“不感兴趣”。现又指《知音漫客》上连载漫画《极度分裂》里主要角色之一。下面小编为你整理了白烛葵的花语。欢迎阅读。 白烛葵的花语:不感兴趣 ...
【外国名著】 日期:2019-05-11
-
把脉人力资源管理的风向标 什么是风向标
把脉人力资源管理的风向标 外部经营环境的巨大变化,不可避免地给身处其中的企业及其经营管理带来新的、深刻的变化和挑战:市场需求在明显萎缩;而买方市场中,客户要求
【外国名著】 日期:2019-09-04
-
梧桐花的花语|梧桐花的功效与作用
梧桐花为梧桐科植物梧桐的花,植物形态详梧桐子条。今天小编为你整理了梧桐花的花语,欢迎阅读。 梧桐花的花语是:情窦初开 在春季里晚开的花朵,有着恬淡的气息。 ...
【寓言童话】 日期:2020-03-03
-
西部计划笔试题库(99题含答案)
西部计划笔试题库(99题含答案) 1 第十三届全国人大三次会议表决通过了《中华人民共和国民法典》,自
【寓言童话】 日期:2021-06-16
-
大学生音乐欣赏论文 大学音乐鉴赏论文3000
今天小编就为你介绍关于大学生音乐欣赏论文,下面是!小编给你搜集了相关资料!希望可以能帮助到大家。 大学生音乐欣赏论文—第一篇 音乐是生活不可缺少的一部分,学会欣...
【寓言童话】 日期:2020-03-12
-
年学生资助诚信教育主题活动方案
各二级学院(部): 为深入贯彻落实习近平总书记关于教育的重要论述,落实立德树人根本任务,增强当代大学
【寓言童话】 日期:2020-06-21
-
油管、套管规格尺寸对照表
API油管规格及尺寸 公称尺寸(in) 不加厚外径(mm) 不加厚内径(mm) 加厚外径(mm) 加
【寓言童话】 日期:2020-08-31
-
主题教育调查研究工作方案2篇
主题教育调查研究工作方案1根据省、市、县开展“不忘初心、牢记使命”主题教育工
【寓言童话】 日期:2021-03-19
-
惊悚鬼故事50字 令人惊悚的故事
这些惊悚故事在短短的篇幅和时间之内让您感受到故事里传达出来的恐怖感,令你感到害怕。下面就是小编给大家整理的令人惊悚的故事,希望对你有用! 令人惊悚的故事篇1:学校...
【寓言童话】 日期:2019-05-13
-
【古代男生漫画图片大全】男生漫画头像
漫画和动画组成了动漫产业的两大支柱。然而,与动画相比,漫画在业界和学界皆相对冷清。小编整理了古代男生漫画,欢迎阅读! 古代男生漫画图片展示 古代男生漫画图片1 ...
【寓言童话】 日期:2019-05-27
-
读《李光耀观天下》有感_李光耀观天下txt在线读
务实与真诚 ——读《李光耀观天下》有感 原创:雁过留声ly 购于北大,在出差的飞机和高铁上读完,这本《李光耀观天下》给予我很多启示。严格地说,这本书没有详
【寓言童话】 日期:2019-05-05
-
北京最好吃的自助餐厅 北京高档自助餐排名
自助餐简直就是拯救大胃王的最佳饮食!没有之一!世界上没有什么事情是吃一顿自助餐解决不了的,如果有,那就吃两顿!下面小编给大家推荐北京几家好吃的自助餐。 北京最好吃的...
【寓言童话】 日期:2020-02-25
-
学生高考动员演讲稿
学生高考动员演讲稿3篇高考动员演讲稿11 老师们、同学们: 大家下午好!漫漫高考长征路已经进入尾声了
【百家讲坛】 日期:2021-09-22
-
企业安全演讲稿2021
最新企业安全的演讲稿5篇 演讲稿是作为在特定的情境中供口语表达使用的文稿。在充满活力,日益开放的今天
【百家讲坛】 日期:2021-09-22
-
XX镇扶贫项目实施专项整治工作总结_1
XX镇扶贫项目实施专项整治工作总结 为深入贯彻精准扶贫精准脱贫基本方略,认真落实党中央、国务院,省委
【百家讲坛】 日期:2021-09-22
-
对乡镇领导班子干部成员批评意见例文
对乡镇领导班子干部成员的批评看法范文 一、对党委书记XXX同志的批评看法〔3条〕 1、与干部交流偏少
【百家讲坛】 日期:2021-09-22
-
群英乡扶贫资金项目芬坡村祖埇村生产道路硬化工程绩效自评报告
群英乡扶贫资金项目((芬坡村祖埇村生产道路硬化工程))绩效自评报告 一、基本情况(一)群英乡扶贫资金
【百家讲坛】 日期:2021-09-22
-
党委书记警示教育大会上讲话2021汇编
党委书记在警示教育大会上的讲话55篇汇编 党委书记在警示教育大会上的讲话(一) 同志们: 根据省州委
【百家讲坛】 日期:2021-09-22
-
对于2021年召开巡视整改专题民主生活会对照检查材料
关于12021年召开巡视整改专题民主生活会对照检查材料 按照中央巡视组要求和省、市、区委统一部署,区
【百家讲坛】 日期:2021-08-14
-
消防安全知识培训试题.doc
消防安全知识培训试题姓名: 部门班组: 成绩: 一:填空题,每空4分,共44分。 1、灭火剂是通过隔
【百家讲坛】 日期:2021-08-14
-
涉疫重点人员“五包一”居家隔离医学观察工作流程
涉疫重点人员“五包一”居家隔离医学观察工作流程 目前,全球疫情仍处于大流行状
【百家讲坛】 日期:2021-08-14
-
疫情防控致全体师生员工及家长一封信
疫情防控致全体师生员工及家长的一封信 各位师生员工及全体家长朋友: 暑假已至,近期我省部分地方发现确
【百家讲坛】 日期:2021-08-14