管 理 运 筹 学 1
第十章 动态规划
§ 1 多阶段决策过程最优化问题举例
§ 2 基本概念、基本方程与最优化原理
§ 3 动态规划的应用 (1)
§ 4 动态规划的应用 (2)
管 理 运 筹 学 2
§ 1 多阶段决策过程最优化问题举例例 1 最短路径问题下图表示从起点 A到终点 E之间各点的距离 。 求 A到 E的最短路径 。
BA
CB
D
B
C
D
E
C
4
1
2
3
1
2
3
1
2
3
2
2
1
6
4
7
2
4 8
3
8
6
7
5
6
1
10
6
4?
3
7 5
1
管 理 运 筹 学 3
§ 1 多阶段决策过程最优化问题举例讨论：
1,以上求从 A到 E的最短路径问题,可以转化为四个性质完全相同,但规模较小的子问题,即分别从 Di,Ci,Bi,A到 E的最短路径问题 。
第四阶段：两个始点 D1和 D2,终点只有一个；
表 10-1
分析得知：从 D1和 D2到 E的最短路径唯一 。
阶段 4
本阶段始点
（状态）
本阶段各终点（决策） 到 E的最短距离 本阶段最优终点
（最优决策 ) E
D1
D2
10*
6
10
6
E
E
管 理 运 筹 学 4
第三阶段：有三个始点 C1,C2,C3，终点有 D1,D2，对始点和终点进行分析和讨论分别求 C1,C2,C3到 D1,D2 的最短路径问题：
表 10-2
分析得知：如果经过 C1,则最短路为 C1-D2-E；
如果经过 C2,则最短路为 C2-D2-E；
如果经过 C3，则最短路为 C3-D1-E。
§ 1 多阶段决策过程最优化问题举例阶段 3
本阶段始点
（状态）
本阶段各终点（决策） 到 E的最短距离 本阶段最优终点
（最优决策 ) D1 D2
C1
C2
C3
8+10=18
7+10=17
1+10=11
6+6=12
5+6=11
6+6=12
12
11
11
D2
D2
D1
管 理 运 筹 学 5
第二阶段：有 4个始点 B1,B2,B3,B4,终点有 C1,C2,C3。 对始点和终点进行分析和讨论分别求 B1,B2,B3,B4到 C1,C2,C3 的最短路径问题：
表 10-3
分析得知：如果经过 B1,则走 B1-C2-D2-E；
如果经过 B2,则走 B2-C3-D1-E；
如果经过 B3,则走 B3-C3-D1-E；
如果经过 B4,则走 B4-C3-D1-E。
§ 1 多阶段决策过程最优化问题举例阶段 2
本阶段始点
（状态）
本阶段各终点（决策） 到 E的最短距离本阶段最优终点（最优决策 ) C
1 C2 C3
B1
B2
B3
B4
2+12=14
4+12=16
4+12=16
7+12=19
1+11=12
7+11=18
8+11=19
5+11=16
6+11=17
2+11=13
3+11=14
1+11=12
12
13
14
12
C2
C3
C3
C3
管 理 运 筹 学 6
第一阶段：只有 1个始点 A，终点有 B1,B2,B3,B4 。对始点和终点进行分析和讨论分别求 A到 B1,B2,B3,B4的最短路径问题：
表 10-4
最后，可以得到：从 A到 E的最短路径为 A?B4? C3? D1?
E
§ 1 多阶段决策过程最优化问题举例阶段 1
本阶段始点 (状态 )
本阶段各终点（决策） 到 E的最短距离本阶段最优终点 (最优决策 )B
1 B2 B3 B4
A 4+12=16 3+13=16 3+14=17 2+12=14 14 B4
管 理 运 筹 学 7
以上计算过程及结果，可用图 2表示，可以看到，以上方法不仅得到了从 A到 D的最短路径，同时，也得到了从图中任一点到 E的最短路径。
以上过程,仅用了 22次加法,计算效率远高于穷举法 。
BA
CB
D
B
C
D
E
C
4
1
2
3
1
2
3
1
2
3
3
2
16
4
7
2
4 8
3
8
6
7
5
1
6
10
6
0
10
6
12
11
11
12
13
14
14
4B
12
7 5 1
2
§ 1 多阶段决策过程最优化问题举例管 理 运 筹 学 8
一,基本概念：
1,阶段 k：表示决策顺序的离散的量,阶段可以按时间或空间划分 。
2,状态 sk：能确定地表示决策过程当前特征的量 。 状态可以是数量,也可以是字符,数量状态可以是连续的,也可以是离散的 。
3,决策 xk：从某一状态向下一状态过渡时所做的选择 。 决策是所在状态的函数,记为 xk(sk)。
决策允许集合 Dk(sk)：在状态 sk下,允许采取决策的全体 。
4,策略 Pk,n(sk)：从第 k阶段开始到最后第 n阶段的决策序列,称 k
子策略 。 P1,n(s1)即为全过程策略 。
5,状态转移方程 sk+1=Tk(sk,xk)：某一状态以及该状态下的决策,
与下一状态之间的函数关系 。
§ 2 基本概念、基本方程与最优化原理管 理 运 筹 学 9
6,阶段指标函数 vk(sk,xk)：从状态 sk出发,选择决策 xk所产生的第
k阶段指标 。
过程指标函数 Vk,n(sk,xk,xk+1,…,xn)：从状态 sk出发,选择决策
xk,
xk+1,…,xn所产生的过程指标 。 动态规划要求过程指标具有可分离性,即 Vk,n(sk,xk,xk+1,…,xn) = vk(sk,xk)+Vk+1(sk+1,xk+1,…,xn)
称指标具有可加性,或 Vk,n(sk,xk,xk+1,…,xn) = vk(sk,xk)× Vk+1(sk+1,
xk+1,…,xn)称指标具有可乘性 。
二,基本方程：
最优指标函数 fk(sk)：从状态 sk出发,对所有的策略 Pk,n,过程指标 Vk,n的最优值,即
)},({)(,,
)(
nkknk
sDx
kk PsVsf opt
kkk?
§ 2 基本概念、基本方程与最优化原理管 理 运 筹 学 10
对于可加性指标函数,上式可以写为上式中,opt”表示,max”或,min”。 对于可乘性指标函数,上式可以写为以上式子称为动态规划最优指标的递推方程,是动态规划的基本方程 。
终端条件：为了使以上的递推方程有递推的起点,必须要设定最优指标的终端条件,一般最后一个状态 n+1下最优指标 fn+1(sn+1) = 0。
nksfxsvsf kkkkk
sDx
kk opt
kkk
,,2,1)}(),({)( 11
)(
nksfxsvsf kkkkk
sDx
kk opt
kkk
,,2,1)}(),({)( 11
)(
§ 2 基本概念、基本方程与最优化原理管 理 运 筹 学 11
§ 2 基本概念、基本方程与最优化原理用逆序法列表求解右例
k=n=5 时,f5(v10)＝ 0
)}(),({m in)( 55444)(44
444
sfxsvsf sDx
k=4，递推方程为
s4 D4(s4) s5 v4(s4,x4) v4(s4,x4)+f5(s5) f4(s4) 最优决策 x4*
v7 v7?v10 v10 5 5+0=5* 5 v7?v10
v8 v8?v10 v10 8 8+0＝ 8* 8 v8→ v10
v9 v9?v10 v10 4 4+0=4* 4 v9?v10
管 理 运 筹 学 12
§ 2 基本概念、基本方程与最优化原理
)}(),({m in)( 44333)(33
333
sfxsvsf sDx
k=3，递推方程为表 10-2
s3 D3(s3) s4 v3(s3,x3) v3(s3,x3)+f4(s4) f3(s3) 最优决策 x3*
v5
v5?v7
v5?v8
v5?v9
v7
v8
v9
2
8
6
2+5=7*
8+8=16
6+4=10
7 v5?v7
v6
v6?v7
v6?v8
v6?v9
v7
v8
v9
12
5
8
12+5=17
5+8=13
8+4=12*
12 v6?v9
管 理 运 筹 学 13
§ 2 基本概念、基本方程与最优化原理
k=2，递推方程为表 10-3
s2 D2(s2) s3 v2(s2,x2) v2(s2,x2)+f3(s3) f2(s2) 最优决策 x2*
v2
v2?v5
v2?v6
v5
v6
10
13
10+7=17*
13+12=25 17 v2?v5
v3
v3?v5
v3?v6
v5
v6
7
10
7+7=14*
10+12=22 14 v3?v5
v4
v4?v5
v4?v6
v5
v6
13
11
13+7=20*
11+12=23 20 v4?v5
)}(),({m in)( 33222)(22
222
sfxsvsf sDx
管 理 运 筹 学 14
§ 2 基本概念、基本方程与最优化原理
k=1，递推方程为表 10-4
)}(),({m in)( 22111)(11
111
sfxsvsf sDx
s1 D1(s1) s2 v1(s1,x1) v1(s1,x1)+f2(s2) f1(s1) 最优决策 x1*
v1
v1?v2
v1?v3
v1?v4
v2
v3
v4
2
8
5
2+17=19*
8+14=22
5+20=25
19 v1?v2
最优值是表 8-4中 f1(s1)的值，从 v1到 v10的最短路长为 19。最短路线从表 8-4到表 8-1回朔，查看最后一列最优决策，得到最短路径为：
v1?v2? v5?v7? v10
管 理 运 筹 学 15
三,最优化原理作为整个过程的最优策略具有如下性质：
不管在此最优策略上的某个状态以前的状态和决策如何,对该状态来说,以后的所有决策必定构成最优子策略 。 就是说,最优策略的任意子策略都是最优的 。
§ 2 基本概念、基本方程与最优化原理管 理 运 筹 学 16
一,资源分配问题例 2,某公司拟将某种设备 5台,分配给所属的甲,乙,丙三个工厂 。 各工厂获得此设备后,预测可创造的利润如表 10-5所示,
问这 5台设备应如何分配给这 3个工厂,使得所创造的总利润为最大？
表 10-5
盈利工厂设备台数甲 厂 乙 厂 丙 厂
0 0 0 0
1 3 5 4
2 7 10 6
3 9 11 11
4 12 11 12
5 13 11 12
§ 3 动态规划的应用 (1)
管 理 运 筹 学 17
解：将问题按工厂分为三个阶段,甲,乙,丙三个厂分别编号为 1,2,3厂 。 设
sk= 分配给第 k个厂至第 3个厂的设备台数 （ k=1,2、
3） 。
xk=分配给第 k个设备台数 。
已知 s1=5,
并有从 与 的定义,可知以下 我们从第三阶段开始计算 。
222223 ),( xsxsTs
ks kx
33 xs?
§ 3 动态规划的应用 (1)
111112 ),( xsxsTs
管 理 运 筹 学 18
第三阶段,
显然将 台设备都分配给第 3工厂时,
也就是 时,第 3阶段的指标值 （ 即第 3厂的盈利 ）
为最大,即由于第 3阶段是最后的阶段,故有其中 可取值为 0,1,2,3,4,5。 其数值计算见表 10－ 6。
)5,4,3,2,1,0( 33?ss
).,(),(m a x)( 33333333
3
ssrxsrsf x
3x
),(),(m a x 333333
3
ssrxsrx?
§ 3 动态规划的应用 (1)
33 xs?
管 理 运 筹 学 19
表 10－ 6
0 1 2 3 4 5
0 0 － － － － － 0 0
1 － 4 － － － － 4 1
2 － － 6 － － － 6 2
3 － － － 11 － － 11 3
4 － － － － 12 － 12 4
5 － － － － － 12 12 5
3x
3s
),( 333 xsr
)( 33 sf 3*x
§ 3 动态规划的应用 (1)
管 理 运 筹 学 20
其中 表示取 3子过程上最优指标值 时的决策,例如在表 10-6中可知当 =4时,有 有此时,即当 时,此时取
（ 把 4台设备分配给第 3厂 ） 是最优决策,此时阶段指标值
（ 盈利 ） 为 12,最优 3子过程最优指标值也为 12。
第二阶段：
当把 台设备分配给第 2工厂和第 3工厂时,则对每个 值,有一种最优分配方案,使最大盈利即最优 2子过程最优指标函数值为
3*x )( 33 sf 3x
3s ;12)4,4(3?r
,12)4(3?f 43*?x 43?s 43?x
)5,4,3,2,1,0( 22?ss
2s
)](),([m a x)( 3322222
2
sfxsrsf x
§ 3 动态规划的应用 (1)
管 理 运 筹 学 21
因为 上式也可写成其数值计算如表 10－ 7所示 。
表 10－ 7
,223 xss
0 1 2 3 4 5
0 － － － － － 0 0
1 0＋ 4 － － － － 5 1
2 0＋ 6 5＋ 4 － － － 10 2
3 0＋ 11 5＋ 6 11＋ 0 － － 14 2
4 0＋ 12 11＋ 4 11＋ 0 － 16 1,2
5 0＋ 12 5＋ 12 11＋ 6 11＋ 4 11＋ 0 21 2
2x
2s
)(),( 223222 xsfxsr )(
22 sf 2*x
00?
05?
010?
410?
115? 610?
1110?
)(),(m a x)( 22322222
2
xsfxsrsf x
§ 3 动态规划的应用 (1)
管 理 运 筹 学 22
其中在 的这一行里,当 时,
这里 从表 10－ 5中可知,把 1台设备交给乙厂所得盈利数即可,知,这里 从表 10－ 6查即可知 =11。 同样可知当 时,可知;
当 时,；当 时,；当 时,；由于,不可能分 2厂 5
台设备,故 时,栏空着不填 。 从这些数值中取得最大即得,即有 =16。 在此行中我们在取最大值的 上面加一横以示区别,也可知这时 的最优决策为 1或 2。
42?s 12?x
16115)3()1,4()14()1,4()(),( 3232223222 frfrxsfxsr
)1,4(2r
5)1,4(2?r )3()14( 33 ff
)3(3f )3(3f 22?x
16610)2()2,4()24()2,4()(),( 3232223222 frfrxsfxsr
02?x 12120)04()0,4( 32 fr 32x
411)34()3,4( 32 fr 42?x
11011)44()4,4( 32 fr 42?s
52?x )54()5,4( 32 fr
)4(2f )4(2f
)(),( 223222 xsfxsr
2x
§ 3 动态规划的应用 (1)
管 理 运 筹 学 23
第一阶段：
把 台设备分配给第 1,第 2,第 3厂时,最大盈利为 其中 可取值 0,1,2,3,4,5.
数值计算见表 10－ 8
表 10-8
然后按计算表格的顺序推算,可知最优分配方案有两个：
1.由于,根据,查表 10－ 7可知,再由,求得 。 即分配给甲厂 0台,乙厂 2台,丙厂 3台 。
2.由于,根据,查表 10－ 7可
)5( 11?ss
)],5(),5([m a x)5( 12111
1
xfxrf x 1x
0 1 2 3 4 5
5 3＋ 16 9+10 12+5 13+0 21 0,2
1x
1s
)5(),5( 1211 xfxr
210? 147?
)(1 xf 1*x
01*?x 5051*12 xss
22*?x 3252*23 xss 333* sx
21*?x 3251*12 xss
§ 3 动态规划的应用 (1)
管 理 运 筹 学 24
知,再由,求得,
即分配给甲厂 2台,乙厂 2台,丙厂 1台 。
这两种分配方案都能得到最高的总盈利 21万元 。
22*?x 1232*23 xss 133* sx
§ 3 动态规划的应用 (1)
管 理 运 筹 学 25
二,背包问题设有 n种物品,每一种物品数量无限 。 第 i种物品每件重量为 wi公斤,每件价值 ci元 。 现有一只可装载重量为 W公斤的背包,求各种物品应各取多少件放入背包,
使背包中物品的价值最高 。
这个问题可以用整数规划模型来描述 。 设 xi为第 i种物品装入背包的件数 （ i=1,2,…,n）,背包中物品的总价值为 z,则
Max z = c1x1+c2x2+… +cnxn
s.t,w1x1+w2x2+… +wnxn≤W
x1,x2,…,xn?0且为整数 。
§ 3 动态规划的应用 (1)
管 理 运 筹 学 26
下面用动态规划逆序解法求解它 。 设阶段变量 k：第 k次装载第 k种物品 （ k=1,2,…,n）
状态变量 sk：第 k次装载时背包还可以装载的重量；
决策变量 uk= xk：第 k次装载第 k种物品的件数；
决策允许集合,Dk(sk) = { xk | 0? xk?sk/wk,xk为整数 }；
状态转移方程,sk+1 = sk? wkxk；
阶段指标,vk = ckxk；
最优过程指标函数 fk(sk)：第 k到 n阶段容许装入物品的最大使用价值；
递推方程,fk(sk) = max {ckxk+fk+1(sk+1)}
= max {ckxk+fk+1(sk? wkxk)}；
x?Dk(sk)
终端条件,fn+1(sn+1) = 0。
§ 3 动态规划的应用 (1)
管 理 运 筹 学 27
例 3,某咨询公司有 10个工作日可以去处理四种类型的咨询项目,每种类型的咨询项目中待处理的客户数量,处理每个客户所需工作日数以及所获得的利润如表 10－ 9所示 。 显然该公司在 10天内不能处理完所有的客户,它可以自己挑选一些客户,
其余的请其他咨询公司去做,应如何选择客户使得在这 10个工作日中获利最大？
表 10－ 9
咨询项目类型待处理客户数处理每个客户所需工作日数处理每个客户所获利润
1
2
3
4
4
3
2
2
1
3
4
7
2
8
11
20
§ 3 动态规划的应用 (1)
管 理 运 筹 学 28
解：用动态规划来求解此题 。
我们把此问题分成四个阶段,第一阶段我们决策将处理多少个第一种咨询项目类型中的客户,第二阶段决策将处理多少个第二种咨询项目类型中的客户,第三阶段,第四阶段我们也将作出类似的决策 。 我们设
＝分配给第 k种咨询项目到第四种咨询项目的所有客户的总工作日 （ 第 k阶段的状态变量 ） 。
=在第 k种咨询项目中处理客户的数量 （ 第 k阶段的决策变量 ） 。
已知 ＝ 10
并有
kx
1s
,),( 111112 xsxsTs
ks
§ 3 动态规划的应用 (1)
管 理 运 筹 学 29
并从 与 的定义可知从第四阶段开始计算：
显然将 个工作日 尽可能分配给第四类咨询项目,即 时,第四阶段的指标值为最大,
其中,表示取不大于 的最大整数,符号 为取整符号,故有由于第四阶段是最后的阶段,故有
,3),( 222223 xsxsTs
.4),( 333334 xsxsTs
ks kx 44 7xs?
4s )10,,1,0( 4s
7/44 sx?
7/4s7/4s
).7/,(),(m a x 444444
4
ssrxsrx
),7/,(),(m a x)( 4444*4444
4
ssrxsrsf
x
§ 3 动态规划的应用 (1)
管 理 运 筹 学 30
因为 至多为 10,其数值计算见表 10－ 10。
表 10－ 10
4s
0 1
0 － 0 0
1 － 0 0
2 － 0 0
3 － 0 0
4 － 0 0
5 － 0 0
6 － 0 0
7 0 20 1
8 0 20 1
9 0 20 1
10 0 20 1
4x
4s
),( 444 xsr
)( 44 sf 4*x
0
0
0
0
0
0
0
20
20
20
20
§ 3 动态规划的应用 (1)
管 理 运 筹 学 31
第三阶段：
当把 个工作日分配给第四类和第三类咨询项目时,则对每个 值,都有一种最优分配方案,使其最大盈利即最优 3子过程最优指标函数值为因为因为 至多为 10,所以 的取值可为 0,1,2。其数值计算见表 10－ 11。
)10,,3,2,1,0( 33ss
3s
.)(),(m a x)( 4433333
3
sfxsrsf x
334 4 xss
.)4(),(m a x)( 33433333
3
xsfxsrsf x
3s 3x
§ 3 动态规划的应用 (1)
管 理 运 筹 学 32
表 10－ 11
0 1 2
0 － － 0 0
1 － － 0 0
2 － － 0 0
3 － － 0 0
4 0＋ 0 － 11 1
5 0＋ 0 － 11 1
6 0＋ 0 － 11 1
7 11+0 － 20 0
8 0＋ 20 11+0 22 2
9 0＋ 20 11+0 22 2
10 0＋ 20 11+0 22 2
3x
3s
)4(),( 334333 xsfxsr )(
33 sf 3*x
00?
00?
00?
200?
011?
011?
011?
022?
022?
022?
00?
§ 3 动态规划的应用 (1)
管 理 运 筹 学 33
第二阶段：
同样以每个 值都有一种最优分配方案,使其最大盈利即最优 2子过程最优指标函数值为：
因为,故有因为 至多为 10，所以 的取值为 0,1,2,3。其数值计算见表 10－ 12。
.)3(),(m a x)( 22322222
2
xsfxsrsf x
223 3 xss.)3(),(m a x)( 22322222
2
xsfxsrsf x
2s 2x
2s
§ 3 动态规划的应用 (1)
管 理 运 筹 学 34
§ 3 动态规划的应用 (1)
表 10-12
管 理 运 筹 学 35
第一阶段：
我们已知,又因为,同样有因为,故 可取值为 0,1,2,…,10。 其数值计算见表 10－ 13。 表 10－ 13
101?s
.)(),(m a x)( 11211111
1
xsfxsrsf x
112 xss
.)10(),10(m a x)10( 12111
1
xfxrf x
101?s 1x
§ 3 动态规划的应用 (1)
管 理 运 筹 学 36
从 表 10－ 13可知,从而得 ＝ 10
－ 0＝ 10,在表 10－ 12的 的这一行可知,由
,查表 10－ 11的 的这一行可知
,最后由,查表 10-10的 的这一行得,综上所述得最优解为：
此时最大盈利为 28。
现在我们不妨假设该咨询公司的工作计划有所改变,只有
8个工作日来处理这四类咨询项目,那么该咨询公司如何选择客户使得获利最大呢？ 我们不必从头开始重做这个问题,而只要在第一阶段上把 改成 8,重新计算就可得到结果,如表 10－
14所示,这是动态规划的一个好处 。
28)10(1?f 01*?x 1*2 10 xs
102?s 12*?x
73103 2*23 xss 73?s
03*?x 707
3*34 xss 74?s
14*?x 0,1,0 3*2*1* xxx
,14*?x
4s
§ 3 动态规划的应用 (1)
管 理 运 筹 学 37
表 10－ 14
如上一样可从表 10－ 14,10－ 12,10－ 11,10－ 10得到两组最优解如下：
它们的最优解 （ 即最大盈利 ） 都为 22。
一旦咨询的工作日不是减少而是增加,那么我们不仅要重新计算第一阶段,而且要在第二,第三,第四阶段的计算表上补上增加的工作日的新的信息,也可得到新的结果 。
3
0
4
2
)
4
3
2
1
x
x
x
x
1
0
0
1
)
4
*
3
*
2
*
1
*
x
x
x
x
§ 3 动态规划的应用 (1)
管 理 运 筹 学 38
实际上,背包问题我们也可以用整数规划来求解,如果背包携带物品重量的限制为 W公斤,这 N种物品中第 i种物品的重量为,价值为,第 i种物品的总数量的,我们可以设 表示携带第 i种物品的数量,则其数学模型为：
S.T.
且为整数 。
我们不妨用此模型去求解例 3,也一定得出同样的结果 。
iw ic in
ix
,m a x
1
N
i
ii xcf
0
),,2,1(
1
i
ii
N
i
ii
x
Ninx
Wxw
§ 3 动态规划的应用 (1)
管 理 运 筹 学 39
三,生产与存贮问题例 4,某公司为主要电力公司生产大型变压器,由于电力采取预订方式购买,所以该公司可以预测未来几个月的需求量 。 为确保需求,该公司为新的一年前四个月制定一项生产计划,这四个月的需求如表 10－ 15所示 。
生产成本随着生产数量而变化 。 调试费为 4,除了调度费用外,每月生产的头两台各花费为 2,后两台花费为 1。 最大生产能力每月为 4台,生产成本如表 10－ 16所示 。
表 10－ 15
§ 3 动态规划的应用 (1)
管 理 运 筹 学 40
表 10－ 16
每台变压器在仓库中由这个月存到下个月的储存费为 1，
仓库的最大储存能力为 3台,另外,知道在 1月 1日时仓库里存有一台变压器,要求在 4月 30日仓库的库存量为零 。 试问该公司应如何制定生产计划,使得四个月的生产成本和储存总费用最少？
解：我们按月份来划分阶段,第 i个月为第 i阶段,
（ i=1,2,3,4).
设 为第 k阶段期初库存量； k=1,2,3,4
ks
§ 3 动态规划的应用 (1)
管 理 运 筹 学 41
为第 k阶段生产量； k=1,2,3,4
为第 k阶段需求量； k=1,2,3,4,这已在表 10-15
中告诉我们 。
因为下个月的库存量等于上个月的库存量加上上个月的产量减去上个月的需求量,我们就得到了如下状态转移方程：
因为,故有因为,故有
kx
kd
,1112 dxss
11?s
,112 1 dxs
,2223 dxss
,3334 dxss
,4445 dxss
05?s
,4440 dxs
§ 3 动态规划的应用 (1)
管 理 运 筹 学 42
由于必须要满足需求,则有通过移项得到另一方面,第 k阶段的生产量 必不大于同期的生产能力
（ 4台 ）,也不大于第 k阶段至第四阶段的需求之和与第 k阶段期初库存量之差,否则第 k阶段的生产量就要超过从第 k阶段至第四阶段的总需求,故有以下我们从第四阶段开始计算：
从以上的状态转移方程 可知这样就有
),4,3,2,1(, kdxs kkk
kkk sdx
kx
4
4,)(m i n
ki
kik sdx
,0 444 dxs,3 4444 ssdx
)3,(),(m i n)( 44444444
4
ssrxsrsf
x
§ 3 动态规划的应用 (1)
管 理 运 筹 学 43
这里的阶段指标 可以分成两部分,即生产成本与储存费,即为由于第四阶段末要求库存为零,即有,
这样可得对于每个 的可行值,的值列于表 10－ 17。
表 10－ 17
),( nnn xsr
),()(),( nnnnnnnn xshxcxsr
001),( 444xsh
)3()3,()3()3,()( 444444444444 scsshscssrsf
4s )( 44 sf
§ 3 动态规划的应用 (1)
管 理 运 筹 学 44
表中当 时,可知第四阶段要生产台,从表 10－ 16可知总成本为 9,同样可以算出当 为 1,2,3时的情况,结果已列于表 10－ 17中 。
第三阶段：
此时有：
因为 以及 所以有例如,当第三阶段初库存量 时,生产量 为 2时,
则 所以生产成本为 8,第三阶段末库存为 2时,储存费为,而
04?s 33 44 sx
4s
)(1)(),()(),( 3333333333333 dxsxcxshxcxsr
,3334 dxss,13?d
)()1(1)(m in)( 443333)4,4m i n (133
333
sfxsxcsf sxs
)1()1(1)(m in 3343333)4,4m i n (1
333
xsfxsxcsxs
13?s 3x
2121333 dxs
221 ),2()()( 4333444 fdxsfsf
§ 3 动态规划的应用 (1)
管 理 运 筹 学 45
查 10－ 17表可知,这样可知,
填入表 10－ 18中 的栏内,其他结果如表 10－ 18所示,表 10－ 18
第二阶段：
因为 所以有
6)2(4?f,16628)2()2,1( 43 fr
2,1 33 xs
,,4 22232 dxssd
§ 3 动态规划的应用 (1)
管 理 运 筹 学 46
计算结果如表 10－ 19所示 。
表 10－ 19
)(),(m in)( 33222)4,8m i n (422
222
sfxsrsf sxs
)(),()(m in 3322222)4,8m i n (4
222
sfxshxcsxs
)()(1)(m in 222322222)4,8m i n (4
222
dxsfdxsxcsxs
)4()4(1)(m in 2232222)4,8m i n (4
222
xsfxsxcsxs
§ 3 动态规划的应用 (1)
管 理 运 筹 学 47
第一阶段：
因为 故有计算结果见表 10－ 20。
表 10－ 20
,,1,2 211111 sdxssd
)(),(m in)1()( 2211141111
1
sfxsrfsf x
)21()21(1)(m in 1211141
1
xfxxcx
§ 3 动态规划的应用 (1)
管 理 运 筹 学 48
利用递推关系可以从表 10－ 20,表 10－ 19,表 10－ 18和表 10－
17得到两组最优解：
这时有最低总成本 29。
0
4
4
1
)
4
3
2
1
x
x
x
x
3
0
4
2
)
4
3
2
1
x
x
x
x
§ 3 动态规划的应用 (1)
管 理 运 筹 学 49
§ 3 动态规划的应用 (1)
四、系统可靠性问题例 5.某科研项目组由三个小组用不同的手段分别研究，
它们失败的概率各为 0.40,0.60,0.80。为了减少三个小组都失败的可能性，现决定给三个小组中增派两名高级科学家，到各小组后，各小组科研项目失败概率如下表：
问如何分派科学家才能使三个小组都失败的概率（即科研项目最终失败的概率）最小？
高级科学家 小组
1 2 3
0 0.40 0.60 0.80
1 0.20 0.40 0.50
2 0.15 0.20 0.30
管 理 运 筹 学 50
§ 3 动态规划的应用 (1)
解：用逆序算法。设阶段：每个研究小组为一个阶段，且阶段 1 2 3
小组 1 2 3
决策变量
nx
：分配给第 n 小组的高级科学家数目，相应的失败概率为 P n(
nx
) ；
状态变量
ns
：在阶段 n 时可分配于阶段 n,n - 1,…,1 的高级科学家人数。
递推关系,
*
3f
(
3s
)=
33 sx
M i n
{
3P
(
3x
)}
*
nf
(
ns
)=
nsx
M i n
n
{
nP
(
nx
)? *
1?n
f (
ns
-
nx
) } n= 1,2
管 理 运 筹 学 51
§ 3 动态规划的应用 (1)
计算
当 n=3时，
当 n=2时，
s3 f3*(s3) x3*
0 0,80 0
1 0,50 1
2 0,30 2
x2
s2
f2(s2,x2)=P2(x2) ·f3*(s2-x2) f
2*(s2) x2*0 1 2
0 0,48 0,48 0
1 0,30 0,32 0,30 0
2 0,18 0,20 0,16 0,16 2
管 理 运 筹 学 52
§ 3 动态规划的应用 (1)
当 n=1时，
最优解为 x1*=1,x2*=0,x3*=1；科研项目最终失败的概率为 0.060。
x1
s1
f1(s1,x1)=P1(x1) ·f2*(s1-x1) f2*(s2) x2*
0 1 2
2 0,064 0,060 0,072 0,060 1
管 理 运 筹 学 53
§ 3 动态规划的应用 (2)
8.5.1求解线性规划模型
【 例 】 用动态规划方法求解下列线性规划
1 2 3
12
1 2 3
1 2 3
ma x 6 5 8
3 2 2 0
4 4 1 4
,,0
Z x x x
xx
x x x
x x x
【 解 】 首先将问题转化为动态规划模型阶段数为 3，决策变量为 xk，状态变量为第 k阶段初各约束条件右端常数的剩余值，用 s1k和 s2k表示，状态转移方程为
s1,k+1=s1k－ a1kxk,s2,k+1=s2k－ a2kxk
终端条件
4 1 4 2 4(,) 0f s s?
管 理 运 筹 学 54
§ 3 动态规划的应用 (2)
23
3 3 3 3( ) | 0 4i
sD s x x
3 2 3 3 2 3
*3 1 3 2 3 3 3 3 2 3 3 2 3
0 4 0 4(,) m a x m a x 8 2 4x s x sf s s c x x s x s
k=2时,决策变量 x2的允许集合
1 2 2 2
2 2 2 2 1 2 2 2
1 2 2 2
( ) | 0 m in,,2,4i ssD s x x a aaa
1 2 2 2
2 2 2 2( ) | 0 m i n,24i
ssD s x x
k=3时,决策变量 x3的允许集合
1 3 2 3
3 3 3 3 1 3 2 3
1 3 2 3
( ) | 0 m in,,0,4i ssD s x x a aaa
管 理 运 筹 学 55
§ 3 动态规划的应用 (2)
状态转移方程为
1 3 1 2 2 2 3 2 2 22,4s s x s s x
1 2 2 2 1 2 2 2
22
1 2 2 2
2
1 2 2 2
2
2 1 2 2 2 2 2 3 1 3 2 3 2 2 3
0 m in,0 m in,
2 4 2 4
2 2 2 2
0 m in,
24
2 2 2
0 m in,
24
*
2 2 2
(,) m a x (,) m a x 5 2
m a x 5 2 ( 4 )
m a x 2 3
20
s s s s
xx
ss
x
ss
x
f s s c x f s s x s
x s x
sx
sx
管 理 运 筹 学 56
§ 3 动态规划的应用 (2)
k＝ 1时，决策变量 x1的允许集合
1 1 2 1
1 1 1 1
1 1 2 1
11
( ) | 0 m in,
20
| 0 m in,1 4
3
i
ss
D s x x
aa
xx
状态转移方程
1 2 1 1 1 1
2 2 2 1 1 1
3 0 3
14
s s x x
s s x x
1
1
1
1 11 21 1 1 2 12 22
20
0 m in,14
3
11
20
0 m in,14
3
*
11
20
0 m in,14
3
(,) m a x (,)
m a x 6 2( 14 )
16 4 20
m a x 4 2 14
33
x
x
x
f s s c x f s s
xx
xx
231 1 2 2 2 2 1 3 2 3 32 0 2 0 2 2 2 2 1 1,0,1 4 -,0,0,,3 3 3 3 4 6sx s s x s s x
最优解,2 0 1 1 1 6 4
,0,,3 6 3XZ
管 理 运 筹 学 57
§ 3 动态规划的应用 (2)
求解非线性规划模型
【 例 】 用动态规划方法求解下列非线性规划
1 2 3
1 2 3
1 2 3
m a x
5 2 2 0
,,0
Z x x x
x x x
x x x
11()( ) m a x ( )
kkk k k k kx D s
f s x f s
【 解 】 阶段数为 3，决策变量为 xk，状态变量 sk为第 k阶段初约束条件右端常数的剩余值，状态转移方程为 sk+1=sk－ akxk，阶段指标是 xk，递推方程为管 理 运 筹 学 58
§ 3 动态规划的应用 (2)
终端条件
44( ) 1fs?
k＝ 3时，决策变量允许集合
33
3 3 3 3
3
( ) | 0 2ssD s x x a
递推方程
3
3
3
3
3 3 3 4 4
0
2
*33
33
0
2
( ) m a x ( )
m a x
22
s
x
s
x
f s x f s
ss
xx
管 理 运 筹 学 59
§ 3 动态规划的应用 (2)
k＝ 2时，决策变量允许集合
22
2 2 2 2
2
( ) | 0 5ssD s x x a
状态转移方程 s3=s2－ 5x2
递推方程
2
2
2
2
2
2
2 2 2 3 3
0
5
23
0
5
2* 2
2 2 2 2 2
0
5
( ) m a x ( )
1
m a x
2
11
m a x ( 5 )
2 4 0 1 0
s
x
s
x
s
x
f s x f s
xs
s
x s x s x
管 理 运 筹 学 60
§ 3 动态规划的应用 (2)
k＝ 1时，决策变量允许集合
1
1 1 1 1
1
( ) | 0 2 0sD s x x a
状态转移方程 s
2=20－ x1
递推方程
21
1
1
2
1 1 1 2 2 1 2
0 2 0 0 2 0
2
11
0 2 0
32
1 1 1
0 2 0
*
1
1
( ) m a x ( ) m a x
40
1
m a x ( 2 0 )
40
1
m a x 1 0
40
8 0 0 2 0
2 7 3
xx
x
x
f s x f s x s
xx
x x x
x
得到最优解 2 0 4 1 0 8 0 0,,,3 3 3 2 7TXZ
2
20
3
)(
)5
4
)(2
10
3
()(
102
40
3
)(
10
40
1
)(
11
1
11
1
2
11
1
2
1
3
11
xx
x
xx
xxx
xxxx
管 理 运 筹 学 61
§ 4 动态规划的应用 (2)*
一,连续 确定性动态规划对于状态变量和决策变量只取连续值，过程的演变方式为确定性时，这种动态规划问题就称为连续确定性动态规划问题。
管 理 运 筹 学 62
§ 4 动态规划的应用 (2)*
机器负荷分配问题例 1 一种机器能在高低两种不同的负荷状态下工作。设机器在高负荷下生产时，产量函数为 P1=8u1，其中 u1为在高负荷状态下生产的机器数目，年完好率为 a=0.7，即到年底有 70％的机器保持完好。在低负荷下生产时，产量函数为
P2=5u2，其中 u2为在低负荷状态下生产的机器数目，年完好率为 b=0.9。设开始生产时共有 1000台完好的机器，请问每年应该如何把完好机器分配给高、低两种负荷下生产，才能使得 5年内生产的产品总产量最高。
管 理 运 筹 学 63
§ 4 动态规划的应用 (2)*
解 建立动态规划模型：
分为 5个阶段，每个阶段为 1年。设状态变量 sk表示在第 k
阶段初拥有的完好机器数目； k=1,2,3,4,5。
决策变量 xk表示第 k阶段中分配给高负荷状态下生产的机器数目； k=1,2,3,4,5。显然 sk-xk为分配给低负荷状态下生产的机器数目。
状态转移方程为 sk+1=0.7xk+0.9(sk-xk)
阶段指标 rk(sk,xk)=8xk+5(sk-xk)
最优指标函数,其中 k=1,2,3,4,5。
f6(s6)=0。
)()58m a x)( 11 kkkkkkk sfxsxsf （kk sx0
管 理 运 筹 学 64
§ 4 动态规划的应用 (2)*
第 5阶段：
因为 f5(s5)是 x5的线性单调增函数，故有 x5* =s5，
于是有 f5(s5)=8s5。
第 4阶段：
)(2.126.13m a x
)](9.07.0[8)(58m a x
8)(58m a x
)()(58m a x)(
444
0
444444
0
5444
0
55444
0
44
44
44
44
44
xsx
xsxxsx
sxsx
sfxsxsf
sx
sx
sx
sx
管 理 运 筹 学 65
§ 4 动态规划的应用 (2)*
同样的,f4(s4)是 x4的线性单调增函数，有 x4*=s4,
f4(s4)=13.6s4。
对前几个阶段依次类推，可得
f3(s3)=17.5s3，
f2(s2)=20.75s2，
f1(s1)=23.72s1。
因为期初共有完好机器 1000台，故 s1=1000。有 f1(s1)=23.72s1
＝ 23720，即 5年最大的产量为 23720台。得最优解为,
，,。
这意味着前两年应把年初完好机器完全投入低负荷生产，
后三年应把年初完好机器完全投入高负荷生产。
0*1?x 0*2?x
3*3 sx? 4
*4 sx? 5*5 sx?
管 理 运 筹 学 66
§ 4 动态规划的应用 (2)*
下一步工作是确定每年初的状态，按照从前向后的顺序依次计算出每年年初完好的机器数目。已知 s1=1000,根据状态转移方程，有,
9 0 09.0)(9.07.0 1*11*12 sxsxs
8109.0)(9.07.0 2*22*23 sxsxs
5677.0)(9.07.0 3*33*34 sxsxs
3977.0)(9.07.0 4*44*45 sxsxs
管 理 运 筹 学 67
§ 4 动态规划的应用 (2)*
上面所讨论的最优策略过程，初始端状态
s1=1000台是固定的，终点状态 s6没有要求。这种情况下得到最优决策称为初始端固定终点自由的最优策略。
如果终点附加一定的条件，则问题就称为“终端固定问题”。例如，规定在第 5年度结束时仍要保持 500台机器完好（而不是 278台），应如何安排生产才能使得总产量最大？
下面来分析：
根据终点条件有可得
500)(9.07.0 5556 xsxs
2 5 0 05.4 55 sx
管 理 运 筹 学 68
§ 4 动态规划的应用 (2)*
显然，由于固定了终点的状态,x5的取值受到了约束。因此有类似的，
容易解得,f4(s4)=21.7s4-7500。
7 5 0 05.18
)2 5 0 05.4(5)2 5 0 05.4(8m a x)(
5
55555
s
ssssf
7 5 0 07.07.21m a x
7 5 0 05.18)(58m a x
)()(58m a x)(
44
0
5444
0
55444
0
44
44
44
44
xs
sxsx
sfxsxsf
sx
sx
sx
0*4?x
管 理 运 筹 学 69
§ 4 动态规划的应用 (2)*
依次类推，得
f3(s3)=24.5s3-7500
f2(s2)=27.1s2-7500
f1(s1)=29.4s1-7500
再采用顺序方法递推计算各年的状态，有
s1=1000，
0*1*2*3 xxx
9 0 09.0)(9.07.0 1*11*12 sxsxs
8 1 09.0)(9.07.0 2*22*23 sxsxs
7 2 97.0)(9.07.0 3*33*34 sxsxs
6567.0)(9.07.0 4*44*45 sxsxs
管 理 运 筹 学 70
§ 4 动态规划的应用 (2)*
可见，为了使终点完好的机器数量增加到 500
台，需要安排前四年中全部完好机器都要投入低负荷生产，且在第 5年，也只能全部投入高负荷。
相应的最优指标为
f1(s1)=29.4s1-7500＝ 21900。
可以看到，因为增加了附加条件，总产量 f1(s1)
要比终点自由情况下的产量要低。
管 理 运 筹 学 71
二、离散随机性动态规划随机型的动态规划是指状态的转移律是不确定的，即对给定的状态和决策，下一阶段的到达状态是具有确定概率分布的随机变量，这个概率分布由本阶段的状态和决策完全确定。随机型动态规划的基本结构如下图：
§ 4 动态规划的应用 (2)*
sk状态 xk
决策概率 k阶段的收益
p1
p2
pN
…
.
k+1阶段的状态 sk+1
c1
c2
cN
1
2
N
管 理 运 筹 学 72
§ 4 动态规划的应用 (2)*
图中 N表示第 k+1阶段可能的状态数,p1、
p2,… pN为给定状态 sk和决策 xk的前提下,可能达到下一个状态的概率 。 ci为从 k阶段状态 sk转移到
k+1 阶段状态为 i时的指标函数值 。
在随机性的动态规划问题中，由于下一阶段到达的状态和阶段的效益值不确定，只能根据各阶段的期望效益值进行优化。
管 理 运 筹 学 73
离散随机性动态规划例 2 某公司承担一种新产品研制任务，合同要求三个月内交出一件合格的样品，否则将索赔 2000
元。根据有经验的技术人员估计，试制品合格的概率为 0.4，每次试制一批的装配费为 200元，每件产品的制造成本为 100元。每次试制的周期为 1个月。
问该如何安排试制，每次生产多少件，才能使得期望费用最小？
管 理 运 筹 学 74
离散随机性动态规划解,把三次试制当作三个阶段（ k=1,2,3）,决策变量 xk表示第 k次生产的产品的件数；状态变量 sk
表示第 k次试制前是否已经生产出合格品，如果有合格品，则 sk=0；如果没有合格品，记 sk=1。最优函数 fk(sk)表示从状态 sk、决策 xk出发的第 k阶段以后的最小期望费用。故有 fk(0)＝ 0。
生产出一件合格品的概率为 0.4，所以生产 xk
件产品都不合格的概率为,至少有一件合格品的概率为 1-,故有状态转移方程为
kx6.0
k
k
x
k
x
k
sp
sp
6.01)0(
6.0)1(
1
1
kx6.0
管 理 运 筹 学 75
离散随机性动态规划用 C(xk)表示第 k阶段的费用，第 k阶段的费用包括制造成本和装配费用，故有根据状态转移方程以及 C(xk)，可得到
00
02)(
k
kk
k x
xxxC
)}1(6.0)0()6.01()({m i n)1( 11 kxkxkxk ffxcf kk
k
)}1(6.0)({m i n 1 kxkx fxc k
k
管 理 运 筹 学 76
离散随机性动态规划如果 3个月后没有试制出一件合格品,则要承担
2000元的罚金,因此有 f4(1)=20。
当 k=3时，计算如下表：
x3
s3
C(x3)+20×
f3(s3) x3*
0 1 2 3 4 5 6
0 0 — — — — — — 0 0
1 20 15 11.2 9.32 8.59 8.56 8.93 8.56 5
0.6 3x
管 理 运 筹 学 77
离散随机性动态规划当 k=2时，计算如下表：
x2
s2
C(x2)+8.56×
f2(s2) x2*
0 1 2 3 4
0 0 — — — — 0 0
1 8.56 8.14 7.08 6.85 7.11 6.85 3
0.6 2x
管 理 运 筹 学 78
离散随机性动态规划当 k=1时，有
x1
s1
C(x1)+6.85×
f1(s1) x1*
0 1 2 3
0 0 — — — 0 0
1 6.85 7.11 6.46 6.48 6.46 2
0.6 1x
管 理 运 筹 学 79
离散随机性动态规划上面三个表中并没有列出 xk取更大数值的情况,
因为可以证明以后的 C(xk)+ fk+1(1)的值是对 xk单调增加的 。
因此得到的最优策略是，在第 1个阶段试制 2件产品；如果都不合格，在第 2阶段试制 3件产品；如果仍都不合格，则在第 3个阶段试制 5件产品。该策略得到的最小的期望费用 6.46。
0.6 kx
管 理 运 筹 学 80
离散随机性动态规划随机采购问题例 3 某公司打算在 5周内采购一批原料,未来 5周内的原料的价格有三种,这些价格的出现概率可以估计,如下表 。 该部分由于生产需要,必须在 5周内采购这批原料 。 如果第一周价格很高,可以等到第 2周；同样的,第 2周如果仍对价格不满意,可以等到第 3周；类似地,未来几周都可能选择购买或者等待,但必须保证第 5周时采购了该原料 。 试问该选择哪种采购方案,才能使得采购费用最小？
价格 概率
450 0.25
470 0.35
500 0.40
管 理 运 筹 学 81
离散随机性动态规划解,建立动态规划。按照采购周期分为 5个阶段，将每周的价格看作该阶段的状态。假设状态变量 sk表示第 k周的实际价格，决策变量 xk表示第 k周是否采购的 0-1变量。如决定采购，则 xk=1；如选择等待，则 xk=0。用 skE表示第 k周等待，而在以后采取最优决策时采购价格的期望值。
根据定义，
动态规划基本方程如下：
)5 0 0(40.0)4 7 0(35.0)4 5 0(25.0)( 11111 kkkkkEk fffsEfs
},m i n {)( Ekkkk sssf?
管 理 运 筹 学 82
离散随机性动态规划第五阶段：
因为如果前 4周都没有买,那第 5周必须购买,因此有 f5(s5)=s5,即 f5(450)=450； f5(470)=470；
f5(500)=500。
第四阶段：
下面考虑第 4周的情况 。
如第 4周购买，则需花费 s4；如果不买，则必须在第 5周购买。在第 5周采购的费用的期望值为
477
50040.047035.045025.0
)500(40.0)470(35.0)450(25.0 5554
fffs E
管 理 运 筹 学 83
离散随机性动态规划于是,有故第 4周的最优决策为同理，考虑第 3周的最优决策。
}4 7 7,m i n {},m i n {)( 44444 ssssf E
5 0 0s4 7 7
4 7 0s4 7 0
4 5 0s4 5 0
)(
4
4
4
44
当当当
sf
5 0 0s0
4 7 04 5 0s1
x
4
4
4 当或当管 理 运 筹 学 84
离散随机性动态规划第三阶段：
如果第 3周采购，则需花费 s3；也要和第 3周后再采购的费用的期望值作比较。
于是,有故第 3周的最优决策为
8.467
47740.047035.045025.0
)500(40.0)470(35.0)450(25.0 4443
fffs E
}8.467,m i n {},m i n {)( 33333 ssssf E
500470s4 6 7,8
450s450)(
3
3
33 或当当sf
500470s0
450s1x
3
3
3 或当当管 理 运 筹 学 85
离散随机性动态规划第二阶段：
同理可得故第 2周的最优决策为
500470s4 6 3,3 5
450s450
)(
2
2
22 或当当
sf
500470s0
450s1
x
2
2
2 或当当管 理 运 筹 学 86
离散随机性动态规划第一阶段：
同理可得第 1周的最优决策为
5 0 04 7 0s4 6 0,0 1 2 5
4 5 0s4 5 0
)(
1
1
11 或当当
sf
500470s0
450s1
x
1
1
1 或当当管 理 运 筹 学 87
离散随机性动态规划由上可知,最优的采购策略为：在第 1,2,3
周的市场价格为 450时,应该立即采购,否则等待；
在第 4周时,若市场价格为 450或 470时,应该采购,
否则等待 。 若等到第五周,只能采购 。
第十章 动态规划
§ 1 多阶段决策过程最优化问题举例
§ 2 基本概念、基本方程与最优化原理
§ 3 动态规划的应用 (1)
§ 4 动态规划的应用 (2)
管 理 运 筹 学 2
§ 1 多阶段决策过程最优化问题举例例 1 最短路径问题下图表示从起点 A到终点 E之间各点的距离 。 求 A到 E的最短路径 。
BA
CB
D
B
C
D
E
C
4
1
2
3
1
2
3
1
2
3
2
2
1
6
4
7
2
4 8
3
8
6
7
5
6
1
10
6
4?
3
7 5
1
管 理 运 筹 学 3
§ 1 多阶段决策过程最优化问题举例讨论：
1,以上求从 A到 E的最短路径问题,可以转化为四个性质完全相同,但规模较小的子问题,即分别从 Di,Ci,Bi,A到 E的最短路径问题 。
第四阶段：两个始点 D1和 D2,终点只有一个；
表 10-1
分析得知：从 D1和 D2到 E的最短路径唯一 。
阶段 4
本阶段始点
（状态）
本阶段各终点（决策） 到 E的最短距离 本阶段最优终点
（最优决策 ) E
D1
D2
10*
6
10
6
E
E
管 理 运 筹 学 4
第三阶段：有三个始点 C1,C2,C3，终点有 D1,D2，对始点和终点进行分析和讨论分别求 C1,C2,C3到 D1,D2 的最短路径问题：
表 10-2
分析得知：如果经过 C1,则最短路为 C1-D2-E；
如果经过 C2,则最短路为 C2-D2-E；
如果经过 C3，则最短路为 C3-D1-E。
§ 1 多阶段决策过程最优化问题举例阶段 3
本阶段始点
（状态）
本阶段各终点（决策） 到 E的最短距离 本阶段最优终点
（最优决策 ) D1 D2
C1
C2
C3
8+10=18
7+10=17
1+10=11
6+6=12
5+6=11
6+6=12
12
11
11
D2
D2
D1
管 理 运 筹 学 5
第二阶段：有 4个始点 B1,B2,B3,B4,终点有 C1,C2,C3。 对始点和终点进行分析和讨论分别求 B1,B2,B3,B4到 C1,C2,C3 的最短路径问题：
表 10-3
分析得知：如果经过 B1,则走 B1-C2-D2-E；
如果经过 B2,则走 B2-C3-D1-E；
如果经过 B3,则走 B3-C3-D1-E；
如果经过 B4,则走 B4-C3-D1-E。
§ 1 多阶段决策过程最优化问题举例阶段 2
本阶段始点
（状态）
本阶段各终点（决策） 到 E的最短距离本阶段最优终点（最优决策 ) C
1 C2 C3
B1
B2
B3
B4
2+12=14
4+12=16
4+12=16
7+12=19
1+11=12
7+11=18
8+11=19
5+11=16
6+11=17
2+11=13
3+11=14
1+11=12
12
13
14
12
C2
C3
C3
C3
管 理 运 筹 学 6
第一阶段：只有 1个始点 A，终点有 B1,B2,B3,B4 。对始点和终点进行分析和讨论分别求 A到 B1,B2,B3,B4的最短路径问题：
表 10-4
最后，可以得到：从 A到 E的最短路径为 A?B4? C3? D1?
E
§ 1 多阶段决策过程最优化问题举例阶段 1
本阶段始点 (状态 )
本阶段各终点（决策） 到 E的最短距离本阶段最优终点 (最优决策 )B
1 B2 B3 B4
A 4+12=16 3+13=16 3+14=17 2+12=14 14 B4
管 理 运 筹 学 7
以上计算过程及结果，可用图 2表示，可以看到，以上方法不仅得到了从 A到 D的最短路径，同时，也得到了从图中任一点到 E的最短路径。
以上过程,仅用了 22次加法,计算效率远高于穷举法 。
BA
CB
D
B
C
D
E
C
4
1
2
3
1
2
3
1
2
3
3
2
16
4
7
2
4 8
3
8
6
7
5
1
6
10
6
0
10
6
12
11
11
12
13
14
14
4B
12
7 5 1
2
§ 1 多阶段决策过程最优化问题举例管 理 运 筹 学 8
一,基本概念：
1,阶段 k：表示决策顺序的离散的量,阶段可以按时间或空间划分 。
2,状态 sk：能确定地表示决策过程当前特征的量 。 状态可以是数量,也可以是字符,数量状态可以是连续的,也可以是离散的 。
3,决策 xk：从某一状态向下一状态过渡时所做的选择 。 决策是所在状态的函数,记为 xk(sk)。
决策允许集合 Dk(sk)：在状态 sk下,允许采取决策的全体 。
4,策略 Pk,n(sk)：从第 k阶段开始到最后第 n阶段的决策序列,称 k
子策略 。 P1,n(s1)即为全过程策略 。
5,状态转移方程 sk+1=Tk(sk,xk)：某一状态以及该状态下的决策,
与下一状态之间的函数关系 。
§ 2 基本概念、基本方程与最优化原理管 理 运 筹 学 9
6,阶段指标函数 vk(sk,xk)：从状态 sk出发,选择决策 xk所产生的第
k阶段指标 。
过程指标函数 Vk,n(sk,xk,xk+1,…,xn)：从状态 sk出发,选择决策
xk,
xk+1,…,xn所产生的过程指标 。 动态规划要求过程指标具有可分离性,即 Vk,n(sk,xk,xk+1,…,xn) = vk(sk,xk)+Vk+1(sk+1,xk+1,…,xn)
称指标具有可加性,或 Vk,n(sk,xk,xk+1,…,xn) = vk(sk,xk)× Vk+1(sk+1,
xk+1,…,xn)称指标具有可乘性 。
二,基本方程：
最优指标函数 fk(sk)：从状态 sk出发,对所有的策略 Pk,n,过程指标 Vk,n的最优值,即
)},({)(,,
)(
nkknk
sDx
kk PsVsf opt
kkk?
§ 2 基本概念、基本方程与最优化原理管 理 运 筹 学 10
对于可加性指标函数,上式可以写为上式中,opt”表示,max”或,min”。 对于可乘性指标函数,上式可以写为以上式子称为动态规划最优指标的递推方程,是动态规划的基本方程 。
终端条件：为了使以上的递推方程有递推的起点,必须要设定最优指标的终端条件,一般最后一个状态 n+1下最优指标 fn+1(sn+1) = 0。
nksfxsvsf kkkkk
sDx
kk opt
kkk
,,2,1)}(),({)( 11
)(
nksfxsvsf kkkkk
sDx
kk opt
kkk
,,2,1)}(),({)( 11
)(
§ 2 基本概念、基本方程与最优化原理管 理 运 筹 学 11
§ 2 基本概念、基本方程与最优化原理用逆序法列表求解右例
k=n=5 时,f5(v10)＝ 0
)}(),({m in)( 55444)(44
444
sfxsvsf sDx
k=4，递推方程为
s4 D4(s4) s5 v4(s4,x4) v4(s4,x4)+f5(s5) f4(s4) 最优决策 x4*
v7 v7?v10 v10 5 5+0=5* 5 v7?v10
v8 v8?v10 v10 8 8+0＝ 8* 8 v8→ v10
v9 v9?v10 v10 4 4+0=4* 4 v9?v10
管 理 运 筹 学 12
§ 2 基本概念、基本方程与最优化原理
)}(),({m in)( 44333)(33
333
sfxsvsf sDx
k=3，递推方程为表 10-2
s3 D3(s3) s4 v3(s3,x3) v3(s3,x3)+f4(s4) f3(s3) 最优决策 x3*
v5
v5?v7
v5?v8
v5?v9
v7
v8
v9
2
8
6
2+5=7*
8+8=16
6+4=10
7 v5?v7
v6
v6?v7
v6?v8
v6?v9
v7
v8
v9
12
5
8
12+5=17
5+8=13
8+4=12*
12 v6?v9
管 理 运 筹 学 13
§ 2 基本概念、基本方程与最优化原理
k=2，递推方程为表 10-3
s2 D2(s2) s3 v2(s2,x2) v2(s2,x2)+f3(s3) f2(s2) 最优决策 x2*
v2
v2?v5
v2?v6
v5
v6
10
13
10+7=17*
13+12=25 17 v2?v5
v3
v3?v5
v3?v6
v5
v6
7
10
7+7=14*
10+12=22 14 v3?v5
v4
v4?v5
v4?v6
v5
v6
13
11
13+7=20*
11+12=23 20 v4?v5
)}(),({m in)( 33222)(22
222
sfxsvsf sDx
管 理 运 筹 学 14
§ 2 基本概念、基本方程与最优化原理
k=1，递推方程为表 10-4
)}(),({m in)( 22111)(11
111
sfxsvsf sDx
s1 D1(s1) s2 v1(s1,x1) v1(s1,x1)+f2(s2) f1(s1) 最优决策 x1*
v1
v1?v2
v1?v3
v1?v4
v2
v3
v4
2
8
5
2+17=19*
8+14=22
5+20=25
19 v1?v2
最优值是表 8-4中 f1(s1)的值，从 v1到 v10的最短路长为 19。最短路线从表 8-4到表 8-1回朔，查看最后一列最优决策，得到最短路径为：
v1?v2? v5?v7? v10
管 理 运 筹 学 15
三,最优化原理作为整个过程的最优策略具有如下性质：
不管在此最优策略上的某个状态以前的状态和决策如何,对该状态来说,以后的所有决策必定构成最优子策略 。 就是说,最优策略的任意子策略都是最优的 。
§ 2 基本概念、基本方程与最优化原理管 理 运 筹 学 16
一,资源分配问题例 2,某公司拟将某种设备 5台,分配给所属的甲,乙,丙三个工厂 。 各工厂获得此设备后,预测可创造的利润如表 10-5所示,
问这 5台设备应如何分配给这 3个工厂,使得所创造的总利润为最大？
表 10-5
盈利工厂设备台数甲 厂 乙 厂 丙 厂
0 0 0 0
1 3 5 4
2 7 10 6
3 9 11 11
4 12 11 12
5 13 11 12
§ 3 动态规划的应用 (1)
管 理 运 筹 学 17
解：将问题按工厂分为三个阶段,甲,乙,丙三个厂分别编号为 1,2,3厂 。 设
sk= 分配给第 k个厂至第 3个厂的设备台数 （ k=1,2、
3） 。
xk=分配给第 k个设备台数 。
已知 s1=5,
并有从 与 的定义,可知以下 我们从第三阶段开始计算 。
222223 ),( xsxsTs
ks kx
33 xs?
§ 3 动态规划的应用 (1)
111112 ),( xsxsTs
管 理 运 筹 学 18
第三阶段,
显然将 台设备都分配给第 3工厂时,
也就是 时,第 3阶段的指标值 （ 即第 3厂的盈利 ）
为最大,即由于第 3阶段是最后的阶段,故有其中 可取值为 0,1,2,3,4,5。 其数值计算见表 10－ 6。
)5,4,3,2,1,0( 33?ss
).,(),(m a x)( 33333333
3
ssrxsrsf x
3x
),(),(m a x 333333
3
ssrxsrx?
§ 3 动态规划的应用 (1)
33 xs?
管 理 运 筹 学 19
表 10－ 6
0 1 2 3 4 5
0 0 － － － － － 0 0
1 － 4 － － － － 4 1
2 － － 6 － － － 6 2
3 － － － 11 － － 11 3
4 － － － － 12 － 12 4
5 － － － － － 12 12 5
3x
3s
),( 333 xsr
)( 33 sf 3*x
§ 3 动态规划的应用 (1)
管 理 运 筹 学 20
其中 表示取 3子过程上最优指标值 时的决策,例如在表 10-6中可知当 =4时,有 有此时,即当 时,此时取
（ 把 4台设备分配给第 3厂 ） 是最优决策,此时阶段指标值
（ 盈利 ） 为 12,最优 3子过程最优指标值也为 12。
第二阶段：
当把 台设备分配给第 2工厂和第 3工厂时,则对每个 值,有一种最优分配方案,使最大盈利即最优 2子过程最优指标函数值为
3*x )( 33 sf 3x
3s ;12)4,4(3?r
,12)4(3?f 43*?x 43?s 43?x
)5,4,3,2,1,0( 22?ss
2s
)](),([m a x)( 3322222
2
sfxsrsf x
§ 3 动态规划的应用 (1)
管 理 运 筹 学 21
因为 上式也可写成其数值计算如表 10－ 7所示 。
表 10－ 7
,223 xss
0 1 2 3 4 5
0 － － － － － 0 0
1 0＋ 4 － － － － 5 1
2 0＋ 6 5＋ 4 － － － 10 2
3 0＋ 11 5＋ 6 11＋ 0 － － 14 2
4 0＋ 12 11＋ 4 11＋ 0 － 16 1,2
5 0＋ 12 5＋ 12 11＋ 6 11＋ 4 11＋ 0 21 2
2x
2s
)(),( 223222 xsfxsr )(
22 sf 2*x
00?
05?
010?
410?
115? 610?
1110?
)(),(m a x)( 22322222
2
xsfxsrsf x
§ 3 动态规划的应用 (1)
管 理 运 筹 学 22
其中在 的这一行里,当 时,
这里 从表 10－ 5中可知,把 1台设备交给乙厂所得盈利数即可,知,这里 从表 10－ 6查即可知 =11。 同样可知当 时,可知;
当 时,；当 时,；当 时,；由于,不可能分 2厂 5
台设备,故 时,栏空着不填 。 从这些数值中取得最大即得,即有 =16。 在此行中我们在取最大值的 上面加一横以示区别,也可知这时 的最优决策为 1或 2。
42?s 12?x
16115)3()1,4()14()1,4()(),( 3232223222 frfrxsfxsr
)1,4(2r
5)1,4(2?r )3()14( 33 ff
)3(3f )3(3f 22?x
16610)2()2,4()24()2,4()(),( 3232223222 frfrxsfxsr
02?x 12120)04()0,4( 32 fr 32x
411)34()3,4( 32 fr 42?x
11011)44()4,4( 32 fr 42?s
52?x )54()5,4( 32 fr
)4(2f )4(2f
)(),( 223222 xsfxsr
2x
§ 3 动态规划的应用 (1)
管 理 运 筹 学 23
第一阶段：
把 台设备分配给第 1,第 2,第 3厂时,最大盈利为 其中 可取值 0,1,2,3,4,5.
数值计算见表 10－ 8
表 10-8
然后按计算表格的顺序推算,可知最优分配方案有两个：
1.由于,根据,查表 10－ 7可知,再由,求得 。 即分配给甲厂 0台,乙厂 2台,丙厂 3台 。
2.由于,根据,查表 10－ 7可
)5( 11?ss
)],5(),5([m a x)5( 12111
1
xfxrf x 1x
0 1 2 3 4 5
5 3＋ 16 9+10 12+5 13+0 21 0,2
1x
1s
)5(),5( 1211 xfxr
210? 147?
)(1 xf 1*x
01*?x 5051*12 xss
22*?x 3252*23 xss 333* sx
21*?x 3251*12 xss
§ 3 动态规划的应用 (1)
管 理 运 筹 学 24
知,再由,求得,
即分配给甲厂 2台,乙厂 2台,丙厂 1台 。
这两种分配方案都能得到最高的总盈利 21万元 。
22*?x 1232*23 xss 133* sx
§ 3 动态规划的应用 (1)
管 理 运 筹 学 25
二,背包问题设有 n种物品,每一种物品数量无限 。 第 i种物品每件重量为 wi公斤,每件价值 ci元 。 现有一只可装载重量为 W公斤的背包,求各种物品应各取多少件放入背包,
使背包中物品的价值最高 。
这个问题可以用整数规划模型来描述 。 设 xi为第 i种物品装入背包的件数 （ i=1,2,…,n）,背包中物品的总价值为 z,则
Max z = c1x1+c2x2+… +cnxn
s.t,w1x1+w2x2+… +wnxn≤W
x1,x2,…,xn?0且为整数 。
§ 3 动态规划的应用 (1)
管 理 运 筹 学 26
下面用动态规划逆序解法求解它 。 设阶段变量 k：第 k次装载第 k种物品 （ k=1,2,…,n）
状态变量 sk：第 k次装载时背包还可以装载的重量；
决策变量 uk= xk：第 k次装载第 k种物品的件数；
决策允许集合,Dk(sk) = { xk | 0? xk?sk/wk,xk为整数 }；
状态转移方程,sk+1 = sk? wkxk；
阶段指标,vk = ckxk；
最优过程指标函数 fk(sk)：第 k到 n阶段容许装入物品的最大使用价值；
递推方程,fk(sk) = max {ckxk+fk+1(sk+1)}
= max {ckxk+fk+1(sk? wkxk)}；
x?Dk(sk)
终端条件,fn+1(sn+1) = 0。
§ 3 动态规划的应用 (1)
管 理 运 筹 学 27
例 3,某咨询公司有 10个工作日可以去处理四种类型的咨询项目,每种类型的咨询项目中待处理的客户数量,处理每个客户所需工作日数以及所获得的利润如表 10－ 9所示 。 显然该公司在 10天内不能处理完所有的客户,它可以自己挑选一些客户,
其余的请其他咨询公司去做,应如何选择客户使得在这 10个工作日中获利最大？
表 10－ 9
咨询项目类型待处理客户数处理每个客户所需工作日数处理每个客户所获利润
1
2
3
4
4
3
2
2
1
3
4
7
2
8
11
20
§ 3 动态规划的应用 (1)
管 理 运 筹 学 28
解：用动态规划来求解此题 。
我们把此问题分成四个阶段,第一阶段我们决策将处理多少个第一种咨询项目类型中的客户,第二阶段决策将处理多少个第二种咨询项目类型中的客户,第三阶段,第四阶段我们也将作出类似的决策 。 我们设
＝分配给第 k种咨询项目到第四种咨询项目的所有客户的总工作日 （ 第 k阶段的状态变量 ） 。
=在第 k种咨询项目中处理客户的数量 （ 第 k阶段的决策变量 ） 。
已知 ＝ 10
并有
kx
1s
,),( 111112 xsxsTs
ks
§ 3 动态规划的应用 (1)
管 理 运 筹 学 29
并从 与 的定义可知从第四阶段开始计算：
显然将 个工作日 尽可能分配给第四类咨询项目,即 时,第四阶段的指标值为最大,
其中,表示取不大于 的最大整数,符号 为取整符号,故有由于第四阶段是最后的阶段,故有
,3),( 222223 xsxsTs
.4),( 333334 xsxsTs
ks kx 44 7xs?
4s )10,,1,0( 4s
7/44 sx?
7/4s7/4s
).7/,(),(m a x 444444
4
ssrxsrx
),7/,(),(m a x)( 4444*4444
4
ssrxsrsf
x
§ 3 动态规划的应用 (1)
管 理 运 筹 学 30
因为 至多为 10,其数值计算见表 10－ 10。
表 10－ 10
4s
0 1
0 － 0 0
1 － 0 0
2 － 0 0
3 － 0 0
4 － 0 0
5 － 0 0
6 － 0 0
7 0 20 1
8 0 20 1
9 0 20 1
10 0 20 1
4x
4s
),( 444 xsr
)( 44 sf 4*x
0
0
0
0
0
0
0
20
20
20
20
§ 3 动态规划的应用 (1)
管 理 运 筹 学 31
第三阶段：
当把 个工作日分配给第四类和第三类咨询项目时,则对每个 值,都有一种最优分配方案,使其最大盈利即最优 3子过程最优指标函数值为因为因为 至多为 10,所以 的取值可为 0,1,2。其数值计算见表 10－ 11。
)10,,3,2,1,0( 33ss
3s
.)(),(m a x)( 4433333
3
sfxsrsf x
334 4 xss
.)4(),(m a x)( 33433333
3
xsfxsrsf x
3s 3x
§ 3 动态规划的应用 (1)
管 理 运 筹 学 32
表 10－ 11
0 1 2
0 － － 0 0
1 － － 0 0
2 － － 0 0
3 － － 0 0
4 0＋ 0 － 11 1
5 0＋ 0 － 11 1
6 0＋ 0 － 11 1
7 11+0 － 20 0
8 0＋ 20 11+0 22 2
9 0＋ 20 11+0 22 2
10 0＋ 20 11+0 22 2
3x
3s
)4(),( 334333 xsfxsr )(
33 sf 3*x
00?
00?
00?
200?
011?
011?
011?
022?
022?
022?
00?
§ 3 动态规划的应用 (1)
管 理 运 筹 学 33
第二阶段：
同样以每个 值都有一种最优分配方案,使其最大盈利即最优 2子过程最优指标函数值为：
因为,故有因为 至多为 10，所以 的取值为 0,1,2,3。其数值计算见表 10－ 12。
.)3(),(m a x)( 22322222
2
xsfxsrsf x
223 3 xss.)3(),(m a x)( 22322222
2
xsfxsrsf x
2s 2x
2s
§ 3 动态规划的应用 (1)
管 理 运 筹 学 34
§ 3 动态规划的应用 (1)
表 10-12
管 理 运 筹 学 35
第一阶段：
我们已知,又因为,同样有因为,故 可取值为 0,1,2,…,10。 其数值计算见表 10－ 13。 表 10－ 13
101?s
.)(),(m a x)( 11211111
1
xsfxsrsf x
112 xss
.)10(),10(m a x)10( 12111
1
xfxrf x
101?s 1x
§ 3 动态规划的应用 (1)
管 理 运 筹 学 36
从 表 10－ 13可知,从而得 ＝ 10
－ 0＝ 10,在表 10－ 12的 的这一行可知,由
,查表 10－ 11的 的这一行可知
,最后由,查表 10-10的 的这一行得,综上所述得最优解为：
此时最大盈利为 28。
现在我们不妨假设该咨询公司的工作计划有所改变,只有
8个工作日来处理这四类咨询项目,那么该咨询公司如何选择客户使得获利最大呢？ 我们不必从头开始重做这个问题,而只要在第一阶段上把 改成 8,重新计算就可得到结果,如表 10－
14所示,这是动态规划的一个好处 。
28)10(1?f 01*?x 1*2 10 xs
102?s 12*?x
73103 2*23 xss 73?s
03*?x 707
3*34 xss 74?s
14*?x 0,1,0 3*2*1* xxx
,14*?x
4s
§ 3 动态规划的应用 (1)
管 理 运 筹 学 37
表 10－ 14
如上一样可从表 10－ 14,10－ 12,10－ 11,10－ 10得到两组最优解如下：
它们的最优解 （ 即最大盈利 ） 都为 22。
一旦咨询的工作日不是减少而是增加,那么我们不仅要重新计算第一阶段,而且要在第二,第三,第四阶段的计算表上补上增加的工作日的新的信息,也可得到新的结果 。
3
0
4
2
)
4
3
2
1
x
x
x
x
1
0
0
1
)
4
*
3
*
2
*
1
*
x
x
x
x
§ 3 动态规划的应用 (1)
管 理 运 筹 学 38
实际上,背包问题我们也可以用整数规划来求解,如果背包携带物品重量的限制为 W公斤,这 N种物品中第 i种物品的重量为,价值为,第 i种物品的总数量的,我们可以设 表示携带第 i种物品的数量,则其数学模型为：
S.T.
且为整数 。
我们不妨用此模型去求解例 3,也一定得出同样的结果 。
iw ic in
ix
,m a x
1
N
i
ii xcf
0
),,2,1(
1
i
ii
N
i
ii
x
Ninx
Wxw
§ 3 动态规划的应用 (1)
管 理 运 筹 学 39
三,生产与存贮问题例 4,某公司为主要电力公司生产大型变压器,由于电力采取预订方式购买,所以该公司可以预测未来几个月的需求量 。 为确保需求,该公司为新的一年前四个月制定一项生产计划,这四个月的需求如表 10－ 15所示 。
生产成本随着生产数量而变化 。 调试费为 4,除了调度费用外,每月生产的头两台各花费为 2,后两台花费为 1。 最大生产能力每月为 4台,生产成本如表 10－ 16所示 。
表 10－ 15
§ 3 动态规划的应用 (1)
管 理 运 筹 学 40
表 10－ 16
每台变压器在仓库中由这个月存到下个月的储存费为 1，
仓库的最大储存能力为 3台,另外,知道在 1月 1日时仓库里存有一台变压器,要求在 4月 30日仓库的库存量为零 。 试问该公司应如何制定生产计划,使得四个月的生产成本和储存总费用最少？
解：我们按月份来划分阶段,第 i个月为第 i阶段,
（ i=1,2,3,4).
设 为第 k阶段期初库存量； k=1,2,3,4
ks
§ 3 动态规划的应用 (1)
管 理 运 筹 学 41
为第 k阶段生产量； k=1,2,3,4
为第 k阶段需求量； k=1,2,3,4,这已在表 10-15
中告诉我们 。
因为下个月的库存量等于上个月的库存量加上上个月的产量减去上个月的需求量,我们就得到了如下状态转移方程：
因为,故有因为,故有
kx
kd
,1112 dxss
11?s
,112 1 dxs
,2223 dxss
,3334 dxss
,4445 dxss
05?s
,4440 dxs
§ 3 动态规划的应用 (1)
管 理 运 筹 学 42
由于必须要满足需求,则有通过移项得到另一方面,第 k阶段的生产量 必不大于同期的生产能力
（ 4台 ）,也不大于第 k阶段至第四阶段的需求之和与第 k阶段期初库存量之差,否则第 k阶段的生产量就要超过从第 k阶段至第四阶段的总需求,故有以下我们从第四阶段开始计算：
从以上的状态转移方程 可知这样就有
),4,3,2,1(, kdxs kkk
kkk sdx
kx
4
4,)(m i n
ki
kik sdx
,0 444 dxs,3 4444 ssdx
)3,(),(m i n)( 44444444
4
ssrxsrsf
x
§ 3 动态规划的应用 (1)
管 理 运 筹 学 43
这里的阶段指标 可以分成两部分,即生产成本与储存费,即为由于第四阶段末要求库存为零,即有,
这样可得对于每个 的可行值,的值列于表 10－ 17。
表 10－ 17
),( nnn xsr
),()(),( nnnnnnnn xshxcxsr
001),( 444xsh
)3()3,()3()3,()( 444444444444 scsshscssrsf
4s )( 44 sf
§ 3 动态规划的应用 (1)
管 理 运 筹 学 44
表中当 时,可知第四阶段要生产台,从表 10－ 16可知总成本为 9,同样可以算出当 为 1,2,3时的情况,结果已列于表 10－ 17中 。
第三阶段：
此时有：
因为 以及 所以有例如,当第三阶段初库存量 时,生产量 为 2时,
则 所以生产成本为 8,第三阶段末库存为 2时,储存费为,而
04?s 33 44 sx
4s
)(1)(),()(),( 3333333333333 dxsxcxshxcxsr
,3334 dxss,13?d
)()1(1)(m in)( 443333)4,4m i n (133
333
sfxsxcsf sxs
)1()1(1)(m in 3343333)4,4m i n (1
333
xsfxsxcsxs
13?s 3x
2121333 dxs
221 ),2()()( 4333444 fdxsfsf
§ 3 动态规划的应用 (1)
管 理 运 筹 学 45
查 10－ 17表可知,这样可知,
填入表 10－ 18中 的栏内,其他结果如表 10－ 18所示,表 10－ 18
第二阶段：
因为 所以有
6)2(4?f,16628)2()2,1( 43 fr
2,1 33 xs
,,4 22232 dxssd
§ 3 动态规划的应用 (1)
管 理 运 筹 学 46
计算结果如表 10－ 19所示 。
表 10－ 19
)(),(m in)( 33222)4,8m i n (422
222
sfxsrsf sxs
)(),()(m in 3322222)4,8m i n (4
222
sfxshxcsxs
)()(1)(m in 222322222)4,8m i n (4
222
dxsfdxsxcsxs
)4()4(1)(m in 2232222)4,8m i n (4
222
xsfxsxcsxs
§ 3 动态规划的应用 (1)
管 理 运 筹 学 47
第一阶段：
因为 故有计算结果见表 10－ 20。
表 10－ 20
,,1,2 211111 sdxssd
)(),(m in)1()( 2211141111
1
sfxsrfsf x
)21()21(1)(m in 1211141
1
xfxxcx
§ 3 动态规划的应用 (1)
管 理 运 筹 学 48
利用递推关系可以从表 10－ 20,表 10－ 19,表 10－ 18和表 10－
17得到两组最优解：
这时有最低总成本 29。
0
4
4
1
)
4
3
2
1
x
x
x
x
3
0
4
2
)
4
3
2
1
x
x
x
x
§ 3 动态规划的应用 (1)
管 理 运 筹 学 49
§ 3 动态规划的应用 (1)
四、系统可靠性问题例 5.某科研项目组由三个小组用不同的手段分别研究，
它们失败的概率各为 0.40,0.60,0.80。为了减少三个小组都失败的可能性，现决定给三个小组中增派两名高级科学家，到各小组后，各小组科研项目失败概率如下表：
问如何分派科学家才能使三个小组都失败的概率（即科研项目最终失败的概率）最小？
高级科学家 小组
1 2 3
0 0.40 0.60 0.80
1 0.20 0.40 0.50
2 0.15 0.20 0.30
管 理 运 筹 学 50
§ 3 动态规划的应用 (1)
解：用逆序算法。设阶段：每个研究小组为一个阶段，且阶段 1 2 3
小组 1 2 3
决策变量
nx
：分配给第 n 小组的高级科学家数目，相应的失败概率为 P n(
nx
) ；
状态变量
ns
：在阶段 n 时可分配于阶段 n,n - 1,…,1 的高级科学家人数。
递推关系,
*
3f
(
3s
)=
33 sx
M i n
{
3P
(
3x
)}
*
nf
(
ns
)=
nsx
M i n
n
{
nP
(
nx
)? *
1?n
f (
ns
-
nx
) } n= 1,2
管 理 运 筹 学 51
§ 3 动态规划的应用 (1)
计算
当 n=3时，
当 n=2时，
s3 f3*(s3) x3*
0 0,80 0
1 0,50 1
2 0,30 2
x2
s2
f2(s2,x2)=P2(x2) ·f3*(s2-x2) f
2*(s2) x2*0 1 2
0 0,48 0,48 0
1 0,30 0,32 0,30 0
2 0,18 0,20 0,16 0,16 2
管 理 运 筹 学 52
§ 3 动态规划的应用 (1)
当 n=1时，
最优解为 x1*=1,x2*=0,x3*=1；科研项目最终失败的概率为 0.060。
x1
s1
f1(s1,x1)=P1(x1) ·f2*(s1-x1) f2*(s2) x2*
0 1 2
2 0,064 0,060 0,072 0,060 1
管 理 运 筹 学 53
§ 3 动态规划的应用 (2)
8.5.1求解线性规划模型
【 例 】 用动态规划方法求解下列线性规划
1 2 3
12
1 2 3
1 2 3
ma x 6 5 8
3 2 2 0
4 4 1 4
,,0
Z x x x
xx
x x x
x x x
【 解 】 首先将问题转化为动态规划模型阶段数为 3，决策变量为 xk，状态变量为第 k阶段初各约束条件右端常数的剩余值，用 s1k和 s2k表示，状态转移方程为
s1,k+1=s1k－ a1kxk,s2,k+1=s2k－ a2kxk
终端条件
4 1 4 2 4(,) 0f s s?
管 理 运 筹 学 54
§ 3 动态规划的应用 (2)
23
3 3 3 3( ) | 0 4i
sD s x x
3 2 3 3 2 3
*3 1 3 2 3 3 3 3 2 3 3 2 3
0 4 0 4(,) m a x m a x 8 2 4x s x sf s s c x x s x s
k=2时,决策变量 x2的允许集合
1 2 2 2
2 2 2 2 1 2 2 2
1 2 2 2
( ) | 0 m in,,2,4i ssD s x x a aaa
1 2 2 2
2 2 2 2( ) | 0 m i n,24i
ssD s x x
k=3时,决策变量 x3的允许集合
1 3 2 3
3 3 3 3 1 3 2 3
1 3 2 3
( ) | 0 m in,,0,4i ssD s x x a aaa
管 理 运 筹 学 55
§ 3 动态规划的应用 (2)
状态转移方程为
1 3 1 2 2 2 3 2 2 22,4s s x s s x
1 2 2 2 1 2 2 2
22
1 2 2 2
2
1 2 2 2
2
2 1 2 2 2 2 2 3 1 3 2 3 2 2 3
0 m in,0 m in,
2 4 2 4
2 2 2 2
0 m in,
24
2 2 2
0 m in,
24
*
2 2 2
(,) m a x (,) m a x 5 2
m a x 5 2 ( 4 )
m a x 2 3
20
s s s s
xx
ss
x
ss
x
f s s c x f s s x s
x s x
sx
sx
管 理 运 筹 学 56
§ 3 动态规划的应用 (2)
k＝ 1时，决策变量 x1的允许集合
1 1 2 1
1 1 1 1
1 1 2 1
11
( ) | 0 m in,
20
| 0 m in,1 4
3
i
ss
D s x x
aa
xx
状态转移方程
1 2 1 1 1 1
2 2 2 1 1 1
3 0 3
14
s s x x
s s x x
1
1
1
1 11 21 1 1 2 12 22
20
0 m in,14
3
11
20
0 m in,14
3
*
11
20
0 m in,14
3
(,) m a x (,)
m a x 6 2( 14 )
16 4 20
m a x 4 2 14
33
x
x
x
f s s c x f s s
xx
xx
231 1 2 2 2 2 1 3 2 3 32 0 2 0 2 2 2 2 1 1,0,1 4 -,0,0,,3 3 3 3 4 6sx s s x s s x
最优解,2 0 1 1 1 6 4
,0,,3 6 3XZ
管 理 运 筹 学 57
§ 3 动态规划的应用 (2)
求解非线性规划模型
【 例 】 用动态规划方法求解下列非线性规划
1 2 3
1 2 3
1 2 3
m a x
5 2 2 0
,,0
Z x x x
x x x
x x x
11()( ) m a x ( )
kkk k k k kx D s
f s x f s
【 解 】 阶段数为 3，决策变量为 xk，状态变量 sk为第 k阶段初约束条件右端常数的剩余值，状态转移方程为 sk+1=sk－ akxk，阶段指标是 xk，递推方程为管 理 运 筹 学 58
§ 3 动态规划的应用 (2)
终端条件
44( ) 1fs?
k＝ 3时，决策变量允许集合
33
3 3 3 3
3
( ) | 0 2ssD s x x a
递推方程
3
3
3
3
3 3 3 4 4
0
2
*33
33
0
2
( ) m a x ( )
m a x
22
s
x
s
x
f s x f s
ss
xx
管 理 运 筹 学 59
§ 3 动态规划的应用 (2)
k＝ 2时，决策变量允许集合
22
2 2 2 2
2
( ) | 0 5ssD s x x a
状态转移方程 s3=s2－ 5x2
递推方程
2
2
2
2
2
2
2 2 2 3 3
0
5
23
0
5
2* 2
2 2 2 2 2
0
5
( ) m a x ( )
1
m a x
2
11
m a x ( 5 )
2 4 0 1 0
s
x
s
x
s
x
f s x f s
xs
s
x s x s x
管 理 运 筹 学 60
§ 3 动态规划的应用 (2)
k＝ 1时，决策变量允许集合
1
1 1 1 1
1
( ) | 0 2 0sD s x x a
状态转移方程 s
2=20－ x1
递推方程
21
1
1
2
1 1 1 2 2 1 2
0 2 0 0 2 0
2
11
0 2 0
32
1 1 1
0 2 0
*
1
1
( ) m a x ( ) m a x
40
1
m a x ( 2 0 )
40
1
m a x 1 0
40
8 0 0 2 0
2 7 3
xx
x
x
f s x f s x s
xx
x x x
x
得到最优解 2 0 4 1 0 8 0 0,,,3 3 3 2 7TXZ
2
20
3
)(
)5
4
)(2
10
3
()(
102
40
3
)(
10
40
1
)(
11
1
11
1
2
11
1
2
1
3
11
xx
x
xx
xxx
xxxx
管 理 运 筹 学 61
§ 4 动态规划的应用 (2)*
一,连续 确定性动态规划对于状态变量和决策变量只取连续值，过程的演变方式为确定性时，这种动态规划问题就称为连续确定性动态规划问题。
管 理 运 筹 学 62
§ 4 动态规划的应用 (2)*
机器负荷分配问题例 1 一种机器能在高低两种不同的负荷状态下工作。设机器在高负荷下生产时，产量函数为 P1=8u1，其中 u1为在高负荷状态下生产的机器数目，年完好率为 a=0.7，即到年底有 70％的机器保持完好。在低负荷下生产时，产量函数为
P2=5u2，其中 u2为在低负荷状态下生产的机器数目，年完好率为 b=0.9。设开始生产时共有 1000台完好的机器，请问每年应该如何把完好机器分配给高、低两种负荷下生产，才能使得 5年内生产的产品总产量最高。
管 理 运 筹 学 63
§ 4 动态规划的应用 (2)*
解 建立动态规划模型：
分为 5个阶段，每个阶段为 1年。设状态变量 sk表示在第 k
阶段初拥有的完好机器数目； k=1,2,3,4,5。
决策变量 xk表示第 k阶段中分配给高负荷状态下生产的机器数目； k=1,2,3,4,5。显然 sk-xk为分配给低负荷状态下生产的机器数目。
状态转移方程为 sk+1=0.7xk+0.9(sk-xk)
阶段指标 rk(sk,xk)=8xk+5(sk-xk)
最优指标函数,其中 k=1,2,3,4,5。
f6(s6)=0。
)()58m a x)( 11 kkkkkkk sfxsxsf （kk sx0
管 理 运 筹 学 64
§ 4 动态规划的应用 (2)*
第 5阶段：
因为 f5(s5)是 x5的线性单调增函数，故有 x5* =s5，
于是有 f5(s5)=8s5。
第 4阶段：
)(2.126.13m a x
)](9.07.0[8)(58m a x
8)(58m a x
)()(58m a x)(
444
0
444444
0
5444
0
55444
0
44
44
44
44
44
xsx
xsxxsx
sxsx
sfxsxsf
sx
sx
sx
sx
管 理 运 筹 学 65
§ 4 动态规划的应用 (2)*
同样的,f4(s4)是 x4的线性单调增函数，有 x4*=s4,
f4(s4)=13.6s4。
对前几个阶段依次类推，可得
f3(s3)=17.5s3，
f2(s2)=20.75s2，
f1(s1)=23.72s1。
因为期初共有完好机器 1000台，故 s1=1000。有 f1(s1)=23.72s1
＝ 23720，即 5年最大的产量为 23720台。得最优解为,
，,。
这意味着前两年应把年初完好机器完全投入低负荷生产，
后三年应把年初完好机器完全投入高负荷生产。
0*1?x 0*2?x
3*3 sx? 4
*4 sx? 5*5 sx?
管 理 运 筹 学 66
§ 4 动态规划的应用 (2)*
下一步工作是确定每年初的状态，按照从前向后的顺序依次计算出每年年初完好的机器数目。已知 s1=1000,根据状态转移方程，有,
9 0 09.0)(9.07.0 1*11*12 sxsxs
8109.0)(9.07.0 2*22*23 sxsxs
5677.0)(9.07.0 3*33*34 sxsxs
3977.0)(9.07.0 4*44*45 sxsxs
管 理 运 筹 学 67
§ 4 动态规划的应用 (2)*
上面所讨论的最优策略过程，初始端状态
s1=1000台是固定的，终点状态 s6没有要求。这种情况下得到最优决策称为初始端固定终点自由的最优策略。
如果终点附加一定的条件，则问题就称为“终端固定问题”。例如，规定在第 5年度结束时仍要保持 500台机器完好（而不是 278台），应如何安排生产才能使得总产量最大？
下面来分析：
根据终点条件有可得
500)(9.07.0 5556 xsxs
2 5 0 05.4 55 sx
管 理 运 筹 学 68
§ 4 动态规划的应用 (2)*
显然，由于固定了终点的状态,x5的取值受到了约束。因此有类似的，
容易解得,f4(s4)=21.7s4-7500。
7 5 0 05.18
)2 5 0 05.4(5)2 5 0 05.4(8m a x)(
5
55555
s
ssssf
7 5 0 07.07.21m a x
7 5 0 05.18)(58m a x
)()(58m a x)(
44
0
5444
0
55444
0
44
44
44
44
xs
sxsx
sfxsxsf
sx
sx
sx
0*4?x
管 理 运 筹 学 69
§ 4 动态规划的应用 (2)*
依次类推，得
f3(s3)=24.5s3-7500
f2(s2)=27.1s2-7500
f1(s1)=29.4s1-7500
再采用顺序方法递推计算各年的状态，有
s1=1000，
0*1*2*3 xxx
9 0 09.0)(9.07.0 1*11*12 sxsxs
8 1 09.0)(9.07.0 2*22*23 sxsxs
7 2 97.0)(9.07.0 3*33*34 sxsxs
6567.0)(9.07.0 4*44*45 sxsxs
管 理 运 筹 学 70
§ 4 动态规划的应用 (2)*
可见，为了使终点完好的机器数量增加到 500
台，需要安排前四年中全部完好机器都要投入低负荷生产，且在第 5年，也只能全部投入高负荷。
相应的最优指标为
f1(s1)=29.4s1-7500＝ 21900。
可以看到，因为增加了附加条件，总产量 f1(s1)
要比终点自由情况下的产量要低。
管 理 运 筹 学 71
二、离散随机性动态规划随机型的动态规划是指状态的转移律是不确定的，即对给定的状态和决策，下一阶段的到达状态是具有确定概率分布的随机变量，这个概率分布由本阶段的状态和决策完全确定。随机型动态规划的基本结构如下图：
§ 4 动态规划的应用 (2)*
sk状态 xk
决策概率 k阶段的收益
p1
p2
pN
…
.
k+1阶段的状态 sk+1
c1
c2
cN
1
2
N
管 理 运 筹 学 72
§ 4 动态规划的应用 (2)*
图中 N表示第 k+1阶段可能的状态数,p1、
p2,… pN为给定状态 sk和决策 xk的前提下,可能达到下一个状态的概率 。 ci为从 k阶段状态 sk转移到
k+1 阶段状态为 i时的指标函数值 。
在随机性的动态规划问题中，由于下一阶段到达的状态和阶段的效益值不确定，只能根据各阶段的期望效益值进行优化。
管 理 运 筹 学 73
离散随机性动态规划例 2 某公司承担一种新产品研制任务，合同要求三个月内交出一件合格的样品，否则将索赔 2000
元。根据有经验的技术人员估计，试制品合格的概率为 0.4，每次试制一批的装配费为 200元，每件产品的制造成本为 100元。每次试制的周期为 1个月。
问该如何安排试制，每次生产多少件，才能使得期望费用最小？
管 理 运 筹 学 74
离散随机性动态规划解,把三次试制当作三个阶段（ k=1,2,3）,决策变量 xk表示第 k次生产的产品的件数；状态变量 sk
表示第 k次试制前是否已经生产出合格品，如果有合格品，则 sk=0；如果没有合格品，记 sk=1。最优函数 fk(sk)表示从状态 sk、决策 xk出发的第 k阶段以后的最小期望费用。故有 fk(0)＝ 0。
生产出一件合格品的概率为 0.4，所以生产 xk
件产品都不合格的概率为,至少有一件合格品的概率为 1-,故有状态转移方程为
kx6.0
k
k
x
k
x
k
sp
sp
6.01)0(
6.0)1(
1
1
kx6.0
管 理 运 筹 学 75
离散随机性动态规划用 C(xk)表示第 k阶段的费用，第 k阶段的费用包括制造成本和装配费用，故有根据状态转移方程以及 C(xk)，可得到
00
02)(
k
kk
k x
xxxC
)}1(6.0)0()6.01()({m i n)1( 11 kxkxkxk ffxcf kk
k
)}1(6.0)({m i n 1 kxkx fxc k
k
管 理 运 筹 学 76
离散随机性动态规划如果 3个月后没有试制出一件合格品,则要承担
2000元的罚金,因此有 f4(1)=20。
当 k=3时，计算如下表：
x3
s3
C(x3)+20×
f3(s3) x3*
0 1 2 3 4 5 6
0 0 — — — — — — 0 0
1 20 15 11.2 9.32 8.59 8.56 8.93 8.56 5
0.6 3x
管 理 运 筹 学 77
离散随机性动态规划当 k=2时，计算如下表：
x2
s2
C(x2)+8.56×
f2(s2) x2*
0 1 2 3 4
0 0 — — — — 0 0
1 8.56 8.14 7.08 6.85 7.11 6.85 3
0.6 2x
管 理 运 筹 学 78
离散随机性动态规划当 k=1时，有
x1
s1
C(x1)+6.85×
f1(s1) x1*
0 1 2 3
0 0 — — — 0 0
1 6.85 7.11 6.46 6.48 6.46 2
0.6 1x
管 理 运 筹 学 79
离散随机性动态规划上面三个表中并没有列出 xk取更大数值的情况,
因为可以证明以后的 C(xk)+ fk+1(1)的值是对 xk单调增加的 。
因此得到的最优策略是，在第 1个阶段试制 2件产品；如果都不合格，在第 2阶段试制 3件产品；如果仍都不合格，则在第 3个阶段试制 5件产品。该策略得到的最小的期望费用 6.46。
0.6 kx
管 理 运 筹 学 80
离散随机性动态规划随机采购问题例 3 某公司打算在 5周内采购一批原料,未来 5周内的原料的价格有三种,这些价格的出现概率可以估计,如下表 。 该部分由于生产需要,必须在 5周内采购这批原料 。 如果第一周价格很高,可以等到第 2周；同样的,第 2周如果仍对价格不满意,可以等到第 3周；类似地,未来几周都可能选择购买或者等待,但必须保证第 5周时采购了该原料 。 试问该选择哪种采购方案,才能使得采购费用最小？
价格 概率
450 0.25
470 0.35
500 0.40
管 理 运 筹 学 81
离散随机性动态规划解,建立动态规划。按照采购周期分为 5个阶段，将每周的价格看作该阶段的状态。假设状态变量 sk表示第 k周的实际价格，决策变量 xk表示第 k周是否采购的 0-1变量。如决定采购，则 xk=1；如选择等待，则 xk=0。用 skE表示第 k周等待，而在以后采取最优决策时采购价格的期望值。
根据定义，
动态规划基本方程如下：
)5 0 0(40.0)4 7 0(35.0)4 5 0(25.0)( 11111 kkkkkEk fffsEfs
},m i n {)( Ekkkk sssf?
管 理 运 筹 学 82
离散随机性动态规划第五阶段：
因为如果前 4周都没有买,那第 5周必须购买,因此有 f5(s5)=s5,即 f5(450)=450； f5(470)=470；
f5(500)=500。
第四阶段：
下面考虑第 4周的情况 。
如第 4周购买，则需花费 s4；如果不买，则必须在第 5周购买。在第 5周采购的费用的期望值为
477
50040.047035.045025.0
)500(40.0)470(35.0)450(25.0 5554
fffs E
管 理 运 筹 学 83
离散随机性动态规划于是,有故第 4周的最优决策为同理，考虑第 3周的最优决策。
}4 7 7,m i n {},m i n {)( 44444 ssssf E
5 0 0s4 7 7
4 7 0s4 7 0
4 5 0s4 5 0
)(
4
4
4
44
当当当
sf
5 0 0s0
4 7 04 5 0s1
x
4
4
4 当或当管 理 运 筹 学 84
离散随机性动态规划第三阶段：
如果第 3周采购，则需花费 s3；也要和第 3周后再采购的费用的期望值作比较。
于是,有故第 3周的最优决策为
8.467
47740.047035.045025.0
)500(40.0)470(35.0)450(25.0 4443
fffs E
}8.467,m i n {},m i n {)( 33333 ssssf E
500470s4 6 7,8
450s450)(
3
3
33 或当当sf
500470s0
450s1x
3
3
3 或当当管 理 运 筹 学 85
离散随机性动态规划第二阶段：
同理可得故第 2周的最优决策为
500470s4 6 3,3 5
450s450
)(
2
2
22 或当当
sf
500470s0
450s1
x
2
2
2 或当当管 理 运 筹 学 86
离散随机性动态规划第一阶段：
同理可得第 1周的最优决策为
5 0 04 7 0s4 6 0,0 1 2 5
4 5 0s4 5 0
)(
1
1
11 或当当
sf
500470s0
450s1
x
1
1
1 或当当管 理 运 筹 学 87
离散随机性动态规划由上可知,最优的采购策略为：在第 1,2,3
周的市场价格为 450时,应该立即采购,否则等待；
在第 4周时,若市场价格为 450或 470时,应该采购,
否则等待 。 若等到第五周,只能采购 。
