?管理与人文学院 忻展红
1999,4
第五章 动态规划
不要过河拆桥
2
动态规划 Dynamic programming
? 五十年代贝尔曼 (B,E,Bellman)为代表的研究成果
? 属于现代控制理论的一部分
? 以长远利益为目标的一系列决策
? 最优化原理，可归结为一个递推公式
5.1 动态规划的最优化原理及其算法
5.1.1 求解多阶段决策过程的方法
例 5.1.1 最短路问题
H
L
O
B
I
E
C
A F
JD
G
K
N
P
M
4
3
5
2 3
5
2
3
4
4
7
7
1
1 3
4
2 2
2
5 4
8 1
2
3
决策树法
A
C
E
H
I
I
F
J
I
F
D
G
J
J
K
可以枚举出 20条路径，其中最短的路径长度为 16
4
例 5.1.1 最短路问题
? 表现为明显的阶段性
? 一条从 A 到 B 的最短路径
中的任何一段都是最短的
H
L
O
B
I
E
C
A F
JD
G
K
N
P
M
4
3
5
2 3
5
2
3
4
4
7
7
1
1 3
4
2 2
2
5 4
8 1
2
16
12
14
0
2
1
4
5
7
10
8
6
7
11
8
9
2 13456 阶段最优性原理
“最优策略的一部分也是最优的”
每步的决策只与相邻阶段状态有关，
而与如何达到这一状态无关
??
?
?
??
?
?
?
?
?
DAD
CAC
A
i
Sd
Sd
S
BiS
m i n则有
径的长度
点的最短路点到表示由设
?因此我们可以从 B向回搜索最短路
?标记法
?如何找出最短路径
5
5.1.2 动态规划的基本概念及递推公式
? 状态 (每阶段初始的出发点 )
– 最短路问题中，各个节点就是状态
– 生产库存问题中，库存量是状态
– 物资分配问题中，剩余的物资量是状态
? 控制变量 (决策变量 )
– 最短路问题中，走哪条路
– 生产库存问题中，各阶段的产品生产量
– 物资分配问题中，分配给每个地区的物资量
? 阶段的 编号 与递推的 方向
– 一般采用反向递推，所以阶段的编号也是逆向的
– 当然也可以正向递推
6
动态规划的步骤
1、确定问题的阶段和编号
2、确定状态变量
– 用 Sk 表示第 k 阶段的状态变量及其值
3、确定决策变量
– 用 xk 表示第 k 阶段的决策变量，并以 xk*表示该阶段的最优
决策
4、状态转移方程
sk-1= g(sk,xk) 反向编号 sk+1= g(sk,xk) 正向编号
5、直接效果
– 直接一步转移的效果 dk(sk,xk)
6、总效果函数
– 指某阶段某状态下到终端状态的总效果，它是一个递推公式
)),(),,((),( 111 ? ???? kkkkkkkkkk xsfxsdhxsf
7
动态规划的步骤
– hk 是一般表达形式，求当前阶段当前状态下的阶段最优
总效果
(1) 如最短路问题，是累加形式，此时有
终端的边际效果一般为 f0(s0,x0)=0
(2)如串联系统可靠性问题，是连乘形式，此时有
终端的边际效果一般为 f0(s0,x0)=1
从第 1阶段开始，利用边际效果和边界条件，可以递推到最后
阶段
8
5.2 动态规划模型举例
5.2.1 产品生产计划安排问题
例 1 某工厂生产某种产品的月生产能力为 10件，已知今后四个月
的产品成本及销售量如表所示。如果本月产量超过销售量时，可
以存储起来备以后各月销售，一件产品的月存储费为 2元，试安
排月生产计划并做到：
1、保证满足每月的销售量，并规定计划期初和期末库存为零；
2、在生产能力允许范围内，安排每月生产量计划使产品总成本
(即生产费用加存储费 )最低。
9
例 1 产品生产计划安排
? 设 xk为第 k阶段生产量，则有直接成本
dk(sk,xk)= ck xk+2sk
? 状态转移公式为
sk-1= sk+ xk- yk
? 总成本递推公式
第一阶段, (即第 4月份 )
由边界条件和状态转移方程 s0=s1+x1?y1= s1+x1?6=0 得
s1+x1= 6 或 x1= 6?s1?0
估计 第一阶段，即第 4月份初库存的可能 状态：
0? s1 ? 30?6?7?12=5,所以,s1 ?[0,5]
10
第一阶段最优决策表
s
1 x 1
?
f
1
( s
1
,x
1
?
)
0 6 456
1 5 382
2 4 308
3 3 234
4 2 160
5 1 86
第二阶段,最大可能库存量 7 件
由状态转移方程,s1=s2+x2?12?0 及
x2?10，可知 s2?[2,7],min x2=5
由阶段效果递推公式有：
f2(2,10)=d2(2,10)+f1*(0,6)
=2?2+80?10+456=1260
得第二 阶段最优决策表，如下
s
2
x
2
5 6 7 8 9 10 x
2
* f
2
( s
2
,x
2
*)
2 1 2 6 0 * 10 1 2 6 0
3 1 1 8 2 * 1 1 8 8 9 1 1 8 2
4 1 1 0 4 * 1 1 1 0 1 1 1 6 8 1 1 0 4
5 1 0 2 6 * 1 0 3 2 1 0 3 8 1 0 4 4 7 1 0 2 6
6 9 4 8 * 954 960 966 972 6 948
7 8 7 0 * 876 882 888 894 900 5 870
s
1
=0 s
1
=1 s
1
=2 s
1
=3 s
1
=4 s
1
=5
11
第二阶段最优决策表
s
3
x 3 5 6 7 8 9 10 x 3 * f 3 ( s 3,x 3 *)
0 1 9 0 8 1 9 0 2 * 10 1 9 0 2
1 1 8 3 8 1 8 3 2 1 8 2 6 * 10 1 8 2 6
2 1 7 6 8 1 7 6 2 1 7 5 6 1 7 5 0 * 10 1 7 5 0
3 1 6 9 8 1 6 9 2 1 6 8 6 1 6 8 0 1 6 7 4 * 10 1 6 7 4
4 1 6 2 8 1 6 2 2 1 6 1 6 1 6 1 0 1 6 0 4 1 5 9 8 * 10 1 5 9 8
s
2
=2 s
2
=3 s
2
=4 s
2
=5 s
2
=6 s
2
=7
第三阶段,最大可能库存量 4 件
由状态转移方程,s2=s3+x3?7?2 及
x3?10，可知 s3?[0,4],min x3=5
由阶段效果递推公式有：
f3(1,10)=d3(1,10)+f2*(4,8)
=2?1+72?10+1104=1826
得第三 阶段最优决策表，如下
s
2
x
2
* f
2
( s
2
,x
2
*)
2 10 1 2 6 0
3 9 1 1 8 2
4 8 1 1 0 4
5 7 1 0 2 6
6 6 948
7 5 870
12
第三阶段最优决策表 第四阶段,初始库存量 s4=0
由状态转移方程,s3=s4+x4?6?0
可知 x4?6,由阶段效果递推公式有：
f4(0,6)=d4(0,6)+f3*(0,10)
=70?6+1902=2322
得第四 阶段最优决策表，如下
回
溯
得
此
表
13
例 2 生产 –库存管理问题 (连续变量 )
设某厂计划全年生产某种产品 A。其四个季度的订货量分别为 600
公斤,700公斤,500公斤和 1200公斤。已知生产产品 A的生产费
用与产品的平方成正比，系数为 0.005。厂内有仓库可存放产品，
存储费为每公斤每季度 1元。求最佳的生产安排使年总成本最小。
解,四个季度为四个阶段，采用阶段编号与季度顺序一致。
设 sk 为第 k季初的库存量，则边界条件为 s1=s5=0
设 xk 为第 k季的 生产 量,设 yk为第 k季的订货量；
sk, xk, yk 都取实数，状态转移方程为 sk+1=sk+xk - yk
仍采用反向递推，但注意阶段编号是正向的
目标函数为
?
?
?? 4
1
2
,,,1
)005.0(m i n)(
4321 i
iixxxx sxxf
14
例 2 生产 –库存管理问题 (连续变量 )
第一步, (第四季度 ) 总效果 f4(s4,x4)=0.005 x42+s4
由边界条件有,s5= s4 + x4 – y4=0，解得,x4*=1200 – s4
将 x4*代入 f4(s4,x4)得：
f4*(s4)=0.005(1200 – s4)2+s4=7200 –11 s4+0.005 s42
第二步, (第三、四季度 ) 总效果 f3(s3,x3)=0.005 x32+s3+ f4*(s4)
将 s4= s3 + x3 – 500 代入 f3(s3,x3) 得：
15
例 2 生产 –库存管理问题 (连续变量 )
第三步, (第二、三、四季度 ) 总效果
f2(s2,x2)=0.005 x22+s2+ f3*(s3)
将 s3= s2 + x2 ?700 代入 f2(s2,x2) 得：
注意,阶段最优总效果仅是当前状态的函数，与其后的决
策无关
16
例 2 生产 –库存管理问题 (连续变量 )
第四步, (第一、二、三、四季度 ) 总效果
f1(s1,x1)=0.005 x12+s1+ f2*(s2)
将 s2= s1 + x1 – 600= x1 – 600 代入 f1(s1,x1) 得：
由此 回溯,得最优生产 –库存方案
x1*=600,s2*=0； x2*=700,s3*=0； x3*=800,s4*=300；
x4*=900。
17
5.2.2 资源分配问题
例 3 某公司有 9个推销员在全国三个不同市场推销货物，这三个市
场里推销人员数与收益的关系如下表，试作出使总收益最大的分
配方案。
?
?
? 3
1,,
3 )(ma x)(
321 i
ixxx xdxf
解,设分配人员的顺序为市场 1,2,3，采用反向阶段编号。
设 sk 为第 k阶段尚未分配的人员数，边界条件为 s3=9
设 xk 为第 k阶段分配的推销人员数； 仍采用反向递推，
状态转移方程为 sk–1=sk – xk
目标函数为
18
例 3 第一阶段：给第三市场分配
s1 有 0~9种可能，第一阶段最优决策表如下：
为什么与 例 1的第一阶段的表有差别？
因为不存在边界条件 s0=0
19
例 3 第二阶段：给第二市场分配
s2 有 0~9种可能，第二阶段最优决策表如下：
20
例 3 第三阶段：给第一市场分配
由边界条件 s3=9，第三阶段最优决策表如下：
x 3
s 3 0 1 2 3 4 5 6 7 8 9 x 3 * f 3 *
9 2 1 1 213 218 217 215 208 206 202 201 200 2 218
得决策过程,x3*=2,x2*=0,x1*=7,f3*=218
即 市场 1 分配 2人，市场 2 不分配,市场 3 分配 7人
最优解与分配的顺序有关吗？
21
5.2.2 资源分配问题
例 4 项目选择问题
某工厂预计明年有 A,B,C,D四个新
建项目，每个项目的投资额 wk及其投
资后的收益 vk如右表所示。投资总额
为 30万元，问如何选择项目才能使总
收益最大。
? 上述问题的静态规划模型如下：
? 这是一类 0-1规划问题
? 该问题是经典的 旅行背包问题
(Knapsack)
? 该问题是 NP-complete?
?
?
?
?
?
?
?
?
?
?
?
?
项入选
项未入选
1
0
30
)(m a x
k
k
x
xw
xvxf
k
k
kk
k
kk
22
例 4 项目选择问题
解,设项目选择的顺序为 A,B,C,D;
1、阶段 k=1,2,3,4 分别对应 D,C,B,A项目的选择过程
2、第 k 阶段的状态 sk，代表第 k 阶段初尚未分配的投资额
3、第 k 阶段的决策变量 xk,，代表第 k 阶段分配的投资额
4、状态转移方程为 sk–1= sk– wk xk
5、直接效益 dk(sk,xk)= vk 或 0
6、总效益递推公式
该问题的难点在于各阶段的状态的确定，当阶段增加时，状
态数成指数增长。下面利用决策树来确定各阶段的可能状态。
23
24
例 4 第一阶段 (项目 D)的选择过程
? s1<8 时, x1只能取 0； w1=8,v1=5
s
1
x
1
d
1
( s
1
,x
1
) s
0
= s
1
- w
1
x
1
f
0
( s
0
,x
0
*) f
1
( s
1
,x
1
*) 条件
0 0 3 0 0
3
? ? ?
x
4
= x
2
=1
x
3
=0
0 0 5 0 0
5
? ? ?
x
4
= x
3
=1
x
2
=0
0 0 8 0
8
1 5 0 0 5
x
3
= x
2
=1
x
4
=0
0 0 15 0
15
1 5 7 0 5
x
3
= x
2
=0
x
4
=1
0 0 18 0
18
1 5 10 0 5
x
4
= x
3
=0
x
2
=1
0 0 20 0
20
1 5 12 0 5
x
4
= x
2
=0
x
3
=1
0 0 30 0
30
1 5 22 0 5
x
4
= x
3
= x
2
=0
25
例 4 第二阶段 (项目 C)的选择过程
26
w 3 = 1 0 v 3 =8
s 3 x 3 d 3 ( s 3,x 3 ) s 2 = s 3 - w 3 x 3 f 2 ( s 2,x 2 *) f 3 ( s 3,x 3 *) 条件
0 0 15 9 9*
15
1 8 5 0 8
x 4 =1
0 0 30 14 14
30
1 8 20 14 22 *
x 4 = 0项目 决策 投资额 直接收益 v
k
A x 4 =0 0 0
B x 3 =1 10 8
C x 2 =1 12 9
D x 1 =1 8 5
总额 30 22
例 4 第三阶段 (项目 B)的选择过程
w 4 = 1 5 v 4 = 1 2
s 4 x 4 d 4 ( s 4,x 4 ) s 3 = s 4 - w 4 x 4 f 3 ( s 3,x 3 *) f 4 ( s 4,x 4 *) 条件
0 0 3 0 22 22*
3 0 1 12 15 9 21
第四阶段 (项目 A)的选择过程
27
5.2.3 串联系统可靠性问题
例 5 有 A,B,C 三部机器串联生产某种产品，由于工艺技术问题，产品
常出现次品。统计结果表明，机器 A,B,C 产生次品的概率分别为
pA=30%,PB=40%,PC=20%,而产品必须经过三部机器顺序加工才能
完成。为了降低产品的次品率，决定拨款 5 万元进行技术改造，以
便最大限度地提高产品的成品率指标。现提出如下四种改进方案：
方案 1,不拨款，机器保持原状；
方案 2,加装监视设备，每部机器需款 1 万元；
方案 3,加装设备，每部机器需款 2 万元；
方案 4,同时加装监视及控制设备，每部机器需款 3 万元；
采用各方案后，各部机器的次品率如下表。
A B C
不拨款 3 0 % 4 0 % 2 0 %
拨款 1 万元 2 0 % 3 0 % 1 0 %
拨款 2 万元 1 0 % 2 0 % 1 0 %
拨款 3 万元 5% 1 0 % 6%
28
例 5 串联机器可靠性问题
解,为三台机器分配改造拨款，设拨款顺序为 A,B,C，阶段序号反
向编号为 k，即第一阶段计算给机器 C 拨款的效果。
设 sk 为第 k 阶段剩余款，则边界条件为 s3=5；
设 xk 为第 k 阶段的 拨款额 ；
状态转移方程为 sk-1=sk-xk；
目标函数为 max R=(1-PA)(1-PB)(1-PC)
仍采用反向递推
第一阶段,对机器 C 拨款的效果
R1(s1,x1)=d1(s1,x1)? R0(s0,x0)= d1(s1,x1)
x
1
s
1
0 1 2 3 x
1
* R
1
( s
1
,x
1
*)
0 0, 8 0 0, 8
1 0, 8 0, 9 1 0, 9
2 0, 8 0, 9 0, 9 1,2 0, 9
3 0, 8 0, 9 0, 9 0, 9 4 3 0, 9 4
4 0, 8 0, 9 0, 9 0, 9 4 3 0, 9 4
5 0, 8 0, 9 0, 9 0, 9 4 3 0, 9 4
29
第二阶段最优决策表 第二阶段,对机器 B,C 拨款
的效果
由于机器 A 最多只需 3 万元，
故 s2 ? 2
递推公式：
R2(s2,x2)=d2(s2,x2)? R1(s1,x1*)
例,R2(3,2)=d2(3,2)?
R1(1,1)=(1-0.2) ?0.9=0.72
得 第二阶段最优决策表
x
1
s
1
x
1
* R
1
( s
1
,x
1
*)
0 0 0, 8
1 1 0, 9
2 1,2 0, 9
3 3 0, 9 4
4 3 0, 9 4
5 3 0, 9 4
x 2
s 2
0 1 2 3 x 2 * R 2
( s 2,x 2 *)
2 0, 5 4 0, 6 3 0, 6 4 2 0, 6 4
3 0, 5 6 4 0, 6 3 0, 7 2 0, 7 2 2,3 0, 7 2
4 0, 5 6 4 0, 6 5 8 0, 7 2 0, 8 1 3 0, 8 1
5 0, 5 6 4 0, 6 5 8 0, 7 5 2 0, 8 1 3 0, 8 1
30
第二阶段最优决策表 第三阶段,对机器 A,B,C 拨
款的效果
边界条件,s3 = 5
递推公式：
R3(s3,x3)=d3(s3,x3)? R2(s2,x2*)
例,R3(5,3)=d3(5,3)?
R2(2,2)=(1-0.05) ?0.64=0.608
得 第三阶段最优决策表
x 2
s 2
x 2 * R 2
( s 2,x 2 *)
2 2 0, 6 4
3 2,3 0, 7 2
4 3 0, 8 1
5 3 0, 8 1
s 3 x 3 0 1 2 3 x 3 * R 3 ( s 3,x 3 *)
5 0, 5 6 7 0, 6 4 8 0, 6 4 8 0, 6 0 8 1,2 0, 6 4 8
回溯, 有多组最优解 。
I,x3=1,x2=3,x1=1,R3=0.8 ?0.9 ?0.9=0.648
II,x3=2,x2=2,x1=1,R3= 0.9?0.8?0.9=0.648
III,x3=2,x2=3,x1=0,R3= 0.9?0.9?0.8 =0.648
31
例 6 用动态规划解非线性规划
解, 这是一个资源分配问题。设分配次序为 x1,x2,x3，阶段正向
编号，但逆向递推，由约束条件可得边界条件 s1=27,s4=0。
第三阶段：（给 x3分配）
?
?
?
?
???
???
0,,
27
)(m ax
321
321
321
xxx
xxx
xxxxf
333 )( xxf ?
由边界条件和状态转移方程有,s4=s3?x3=0，即 x3*= s3；
因此有，
33*3 )( ssf ?
第二阶段：（给 x2分配） )(),(
3*32222 sfxxsf ??
由状态转移方程有,s3=s2?x2，代入上式得，
22222
22222
222222
2)(,2,
02121
),(
ssfsx
xsxxf
xsxxsf
??
??????
???
??解得
32
例 6 用动态规划解非线性规划
第一阶段：（给 x1分配）
212*21111 2)(),( sxsfxxsf ????
由状态转移方程有,s2=s1?x1=27 ?x1,代入上式得，
9,
9)(,9,
0254121
)27(2),(
321
111
1111
11111
???
??
??????
???
???
??
xxx
sfx
xxxf
xxxsf
回溯得
解得
33
动态规划总结
? 二大类：生产 -库存问题；资源分配问题
?
?
?
?
?
?
??
?
?
?
???
?
?
连续型
离散型
状态和控制变量
累乘
累加
目标函数
状态转移公式
资源分配问题二
连续型
离散型
状态和控制变量
状态转移公式
库存问题生产一
,
-,
1
1
kkk
kkkk
xss
yxss
1999,4
第五章 动态规划
不要过河拆桥
2
动态规划 Dynamic programming
? 五十年代贝尔曼 (B,E,Bellman)为代表的研究成果
? 属于现代控制理论的一部分
? 以长远利益为目标的一系列决策
? 最优化原理，可归结为一个递推公式
5.1 动态规划的最优化原理及其算法
5.1.1 求解多阶段决策过程的方法
例 5.1.1 最短路问题
H
L
O
B
I
E
C
A F
JD
G
K
N
P
M
4
3
5
2 3
5
2
3
4
4
7
7
1
1 3
4
2 2
2
5 4
8 1
2
3
决策树法
A
C
E
H
I
I
F
J
I
F
D
G
J
J
K
可以枚举出 20条路径，其中最短的路径长度为 16
4
例 5.1.1 最短路问题
? 表现为明显的阶段性
? 一条从 A 到 B 的最短路径
中的任何一段都是最短的
H
L
O
B
I
E
C
A F
JD
G
K
N
P
M
4
3
5
2 3
5
2
3
4
4
7
7
1
1 3
4
2 2
2
5 4
8 1
2
16
12
14
0
2
1
4
5
7
10
8
6
7
11
8
9
2 13456 阶段最优性原理
“最优策略的一部分也是最优的”
每步的决策只与相邻阶段状态有关，
而与如何达到这一状态无关
??
?
?
??
?
?
?
?
?
DAD
CAC
A
i
Sd
Sd
S
BiS
m i n则有
径的长度
点的最短路点到表示由设
?因此我们可以从 B向回搜索最短路
?标记法
?如何找出最短路径
5
5.1.2 动态规划的基本概念及递推公式
? 状态 (每阶段初始的出发点 )
– 最短路问题中，各个节点就是状态
– 生产库存问题中，库存量是状态
– 物资分配问题中，剩余的物资量是状态
? 控制变量 (决策变量 )
– 最短路问题中，走哪条路
– 生产库存问题中，各阶段的产品生产量
– 物资分配问题中，分配给每个地区的物资量
? 阶段的 编号 与递推的 方向
– 一般采用反向递推，所以阶段的编号也是逆向的
– 当然也可以正向递推
6
动态规划的步骤
1、确定问题的阶段和编号
2、确定状态变量
– 用 Sk 表示第 k 阶段的状态变量及其值
3、确定决策变量
– 用 xk 表示第 k 阶段的决策变量，并以 xk*表示该阶段的最优
决策
4、状态转移方程
sk-1= g(sk,xk) 反向编号 sk+1= g(sk,xk) 正向编号
5、直接效果
– 直接一步转移的效果 dk(sk,xk)
6、总效果函数
– 指某阶段某状态下到终端状态的总效果，它是一个递推公式
)),(),,((),( 111 ? ???? kkkkkkkkkk xsfxsdhxsf
7
动态规划的步骤
– hk 是一般表达形式，求当前阶段当前状态下的阶段最优
总效果
(1) 如最短路问题，是累加形式，此时有
终端的边际效果一般为 f0(s0,x0)=0
(2)如串联系统可靠性问题，是连乘形式，此时有
终端的边际效果一般为 f0(s0,x0)=1
从第 1阶段开始，利用边际效果和边界条件，可以递推到最后
阶段
8
5.2 动态规划模型举例
5.2.1 产品生产计划安排问题
例 1 某工厂生产某种产品的月生产能力为 10件，已知今后四个月
的产品成本及销售量如表所示。如果本月产量超过销售量时，可
以存储起来备以后各月销售，一件产品的月存储费为 2元，试安
排月生产计划并做到：
1、保证满足每月的销售量，并规定计划期初和期末库存为零；
2、在生产能力允许范围内，安排每月生产量计划使产品总成本
(即生产费用加存储费 )最低。
9
例 1 产品生产计划安排
? 设 xk为第 k阶段生产量，则有直接成本
dk(sk,xk)= ck xk+2sk
? 状态转移公式为
sk-1= sk+ xk- yk
? 总成本递推公式
第一阶段, (即第 4月份 )
由边界条件和状态转移方程 s0=s1+x1?y1= s1+x1?6=0 得
s1+x1= 6 或 x1= 6?s1?0
估计 第一阶段，即第 4月份初库存的可能 状态：
0? s1 ? 30?6?7?12=5,所以,s1 ?[0,5]
10
第一阶段最优决策表
s
1 x 1
?
f
1
( s
1
,x
1
?
)
0 6 456
1 5 382
2 4 308
3 3 234
4 2 160
5 1 86
第二阶段,最大可能库存量 7 件
由状态转移方程,s1=s2+x2?12?0 及
x2?10，可知 s2?[2,7],min x2=5
由阶段效果递推公式有：
f2(2,10)=d2(2,10)+f1*(0,6)
=2?2+80?10+456=1260
得第二 阶段最优决策表，如下
s
2
x
2
5 6 7 8 9 10 x
2
* f
2
( s
2
,x
2
*)
2 1 2 6 0 * 10 1 2 6 0
3 1 1 8 2 * 1 1 8 8 9 1 1 8 2
4 1 1 0 4 * 1 1 1 0 1 1 1 6 8 1 1 0 4
5 1 0 2 6 * 1 0 3 2 1 0 3 8 1 0 4 4 7 1 0 2 6
6 9 4 8 * 954 960 966 972 6 948
7 8 7 0 * 876 882 888 894 900 5 870
s
1
=0 s
1
=1 s
1
=2 s
1
=3 s
1
=4 s
1
=5
11
第二阶段最优决策表
s
3
x 3 5 6 7 8 9 10 x 3 * f 3 ( s 3,x 3 *)
0 1 9 0 8 1 9 0 2 * 10 1 9 0 2
1 1 8 3 8 1 8 3 2 1 8 2 6 * 10 1 8 2 6
2 1 7 6 8 1 7 6 2 1 7 5 6 1 7 5 0 * 10 1 7 5 0
3 1 6 9 8 1 6 9 2 1 6 8 6 1 6 8 0 1 6 7 4 * 10 1 6 7 4
4 1 6 2 8 1 6 2 2 1 6 1 6 1 6 1 0 1 6 0 4 1 5 9 8 * 10 1 5 9 8
s
2
=2 s
2
=3 s
2
=4 s
2
=5 s
2
=6 s
2
=7
第三阶段,最大可能库存量 4 件
由状态转移方程,s2=s3+x3?7?2 及
x3?10，可知 s3?[0,4],min x3=5
由阶段效果递推公式有：
f3(1,10)=d3(1,10)+f2*(4,8)
=2?1+72?10+1104=1826
得第三 阶段最优决策表，如下
s
2
x
2
* f
2
( s
2
,x
2
*)
2 10 1 2 6 0
3 9 1 1 8 2
4 8 1 1 0 4
5 7 1 0 2 6
6 6 948
7 5 870
12
第三阶段最优决策表 第四阶段,初始库存量 s4=0
由状态转移方程,s3=s4+x4?6?0
可知 x4?6,由阶段效果递推公式有：
f4(0,6)=d4(0,6)+f3*(0,10)
=70?6+1902=2322
得第四 阶段最优决策表，如下
回
溯
得
此
表
13
例 2 生产 –库存管理问题 (连续变量 )
设某厂计划全年生产某种产品 A。其四个季度的订货量分别为 600
公斤,700公斤,500公斤和 1200公斤。已知生产产品 A的生产费
用与产品的平方成正比，系数为 0.005。厂内有仓库可存放产品，
存储费为每公斤每季度 1元。求最佳的生产安排使年总成本最小。
解,四个季度为四个阶段，采用阶段编号与季度顺序一致。
设 sk 为第 k季初的库存量，则边界条件为 s1=s5=0
设 xk 为第 k季的 生产 量,设 yk为第 k季的订货量；
sk, xk, yk 都取实数，状态转移方程为 sk+1=sk+xk - yk
仍采用反向递推，但注意阶段编号是正向的
目标函数为
?
?
?? 4
1
2
,,,1
)005.0(m i n)(
4321 i
iixxxx sxxf
14
例 2 生产 –库存管理问题 (连续变量 )
第一步, (第四季度 ) 总效果 f4(s4,x4)=0.005 x42+s4
由边界条件有,s5= s4 + x4 – y4=0，解得,x4*=1200 – s4
将 x4*代入 f4(s4,x4)得：
f4*(s4)=0.005(1200 – s4)2+s4=7200 –11 s4+0.005 s42
第二步, (第三、四季度 ) 总效果 f3(s3,x3)=0.005 x32+s3+ f4*(s4)
将 s4= s3 + x3 – 500 代入 f3(s3,x3) 得：
15
例 2 生产 –库存管理问题 (连续变量 )
第三步, (第二、三、四季度 ) 总效果
f2(s2,x2)=0.005 x22+s2+ f3*(s3)
将 s3= s2 + x2 ?700 代入 f2(s2,x2) 得：
注意,阶段最优总效果仅是当前状态的函数，与其后的决
策无关
16
例 2 生产 –库存管理问题 (连续变量 )
第四步, (第一、二、三、四季度 ) 总效果
f1(s1,x1)=0.005 x12+s1+ f2*(s2)
将 s2= s1 + x1 – 600= x1 – 600 代入 f1(s1,x1) 得：
由此 回溯,得最优生产 –库存方案
x1*=600,s2*=0； x2*=700,s3*=0； x3*=800,s4*=300；
x4*=900。
17
5.2.2 资源分配问题
例 3 某公司有 9个推销员在全国三个不同市场推销货物，这三个市
场里推销人员数与收益的关系如下表，试作出使总收益最大的分
配方案。
?
?
? 3
1,,
3 )(ma x)(
321 i
ixxx xdxf
解,设分配人员的顺序为市场 1,2,3，采用反向阶段编号。
设 sk 为第 k阶段尚未分配的人员数，边界条件为 s3=9
设 xk 为第 k阶段分配的推销人员数； 仍采用反向递推，
状态转移方程为 sk–1=sk – xk
目标函数为
18
例 3 第一阶段：给第三市场分配
s1 有 0~9种可能，第一阶段最优决策表如下：
为什么与 例 1的第一阶段的表有差别？
因为不存在边界条件 s0=0
19
例 3 第二阶段：给第二市场分配
s2 有 0~9种可能，第二阶段最优决策表如下：
20
例 3 第三阶段：给第一市场分配
由边界条件 s3=9，第三阶段最优决策表如下：
x 3
s 3 0 1 2 3 4 5 6 7 8 9 x 3 * f 3 *
9 2 1 1 213 218 217 215 208 206 202 201 200 2 218
得决策过程,x3*=2,x2*=0,x1*=7,f3*=218
即 市场 1 分配 2人，市场 2 不分配,市场 3 分配 7人
最优解与分配的顺序有关吗？
21
5.2.2 资源分配问题
例 4 项目选择问题
某工厂预计明年有 A,B,C,D四个新
建项目，每个项目的投资额 wk及其投
资后的收益 vk如右表所示。投资总额
为 30万元，问如何选择项目才能使总
收益最大。
? 上述问题的静态规划模型如下：
? 这是一类 0-1规划问题
? 该问题是经典的 旅行背包问题
(Knapsack)
? 该问题是 NP-complete?
?
?
?
?
?
?
?
?
?
?
?
?
项入选
项未入选
1
0
30
)(m a x
k
k
x
xw
xvxf
k
k
kk
k
kk
22
例 4 项目选择问题
解,设项目选择的顺序为 A,B,C,D;
1、阶段 k=1,2,3,4 分别对应 D,C,B,A项目的选择过程
2、第 k 阶段的状态 sk，代表第 k 阶段初尚未分配的投资额
3、第 k 阶段的决策变量 xk,，代表第 k 阶段分配的投资额
4、状态转移方程为 sk–1= sk– wk xk
5、直接效益 dk(sk,xk)= vk 或 0
6、总效益递推公式
该问题的难点在于各阶段的状态的确定，当阶段增加时，状
态数成指数增长。下面利用决策树来确定各阶段的可能状态。
23
24
例 4 第一阶段 (项目 D)的选择过程
? s1<8 时, x1只能取 0； w1=8,v1=5
s
1
x
1
d
1
( s
1
,x
1
) s
0
= s
1
- w
1
x
1
f
0
( s
0
,x
0
*) f
1
( s
1
,x
1
*) 条件
0 0 3 0 0
3
? ? ?
x
4
= x
2
=1
x
3
=0
0 0 5 0 0
5
? ? ?
x
4
= x
3
=1
x
2
=0
0 0 8 0
8
1 5 0 0 5
x
3
= x
2
=1
x
4
=0
0 0 15 0
15
1 5 7 0 5
x
3
= x
2
=0
x
4
=1
0 0 18 0
18
1 5 10 0 5
x
4
= x
3
=0
x
2
=1
0 0 20 0
20
1 5 12 0 5
x
4
= x
2
=0
x
3
=1
0 0 30 0
30
1 5 22 0 5
x
4
= x
3
= x
2
=0
25
例 4 第二阶段 (项目 C)的选择过程
26
w 3 = 1 0 v 3 =8
s 3 x 3 d 3 ( s 3,x 3 ) s 2 = s 3 - w 3 x 3 f 2 ( s 2,x 2 *) f 3 ( s 3,x 3 *) 条件
0 0 15 9 9*
15
1 8 5 0 8
x 4 =1
0 0 30 14 14
30
1 8 20 14 22 *
x 4 = 0项目 决策 投资额 直接收益 v
k
A x 4 =0 0 0
B x 3 =1 10 8
C x 2 =1 12 9
D x 1 =1 8 5
总额 30 22
例 4 第三阶段 (项目 B)的选择过程
w 4 = 1 5 v 4 = 1 2
s 4 x 4 d 4 ( s 4,x 4 ) s 3 = s 4 - w 4 x 4 f 3 ( s 3,x 3 *) f 4 ( s 4,x 4 *) 条件
0 0 3 0 22 22*
3 0 1 12 15 9 21
第四阶段 (项目 A)的选择过程
27
5.2.3 串联系统可靠性问题
例 5 有 A,B,C 三部机器串联生产某种产品，由于工艺技术问题，产品
常出现次品。统计结果表明，机器 A,B,C 产生次品的概率分别为
pA=30%,PB=40%,PC=20%,而产品必须经过三部机器顺序加工才能
完成。为了降低产品的次品率，决定拨款 5 万元进行技术改造，以
便最大限度地提高产品的成品率指标。现提出如下四种改进方案：
方案 1,不拨款，机器保持原状；
方案 2,加装监视设备，每部机器需款 1 万元；
方案 3,加装设备，每部机器需款 2 万元；
方案 4,同时加装监视及控制设备，每部机器需款 3 万元；
采用各方案后，各部机器的次品率如下表。
A B C
不拨款 3 0 % 4 0 % 2 0 %
拨款 1 万元 2 0 % 3 0 % 1 0 %
拨款 2 万元 1 0 % 2 0 % 1 0 %
拨款 3 万元 5% 1 0 % 6%
28
例 5 串联机器可靠性问题
解,为三台机器分配改造拨款，设拨款顺序为 A,B,C，阶段序号反
向编号为 k，即第一阶段计算给机器 C 拨款的效果。
设 sk 为第 k 阶段剩余款，则边界条件为 s3=5；
设 xk 为第 k 阶段的 拨款额 ；
状态转移方程为 sk-1=sk-xk；
目标函数为 max R=(1-PA)(1-PB)(1-PC)
仍采用反向递推
第一阶段,对机器 C 拨款的效果
R1(s1,x1)=d1(s1,x1)? R0(s0,x0)= d1(s1,x1)
x
1
s
1
0 1 2 3 x
1
* R
1
( s
1
,x
1
*)
0 0, 8 0 0, 8
1 0, 8 0, 9 1 0, 9
2 0, 8 0, 9 0, 9 1,2 0, 9
3 0, 8 0, 9 0, 9 0, 9 4 3 0, 9 4
4 0, 8 0, 9 0, 9 0, 9 4 3 0, 9 4
5 0, 8 0, 9 0, 9 0, 9 4 3 0, 9 4
29
第二阶段最优决策表 第二阶段,对机器 B,C 拨款
的效果
由于机器 A 最多只需 3 万元，
故 s2 ? 2
递推公式：
R2(s2,x2)=d2(s2,x2)? R1(s1,x1*)
例,R2(3,2)=d2(3,2)?
R1(1,1)=(1-0.2) ?0.9=0.72
得 第二阶段最优决策表
x
1
s
1
x
1
* R
1
( s
1
,x
1
*)
0 0 0, 8
1 1 0, 9
2 1,2 0, 9
3 3 0, 9 4
4 3 0, 9 4
5 3 0, 9 4
x 2
s 2
0 1 2 3 x 2 * R 2
( s 2,x 2 *)
2 0, 5 4 0, 6 3 0, 6 4 2 0, 6 4
3 0, 5 6 4 0, 6 3 0, 7 2 0, 7 2 2,3 0, 7 2
4 0, 5 6 4 0, 6 5 8 0, 7 2 0, 8 1 3 0, 8 1
5 0, 5 6 4 0, 6 5 8 0, 7 5 2 0, 8 1 3 0, 8 1
30
第二阶段最优决策表 第三阶段,对机器 A,B,C 拨
款的效果
边界条件,s3 = 5
递推公式：
R3(s3,x3)=d3(s3,x3)? R2(s2,x2*)
例,R3(5,3)=d3(5,3)?
R2(2,2)=(1-0.05) ?0.64=0.608
得 第三阶段最优决策表
x 2
s 2
x 2 * R 2
( s 2,x 2 *)
2 2 0, 6 4
3 2,3 0, 7 2
4 3 0, 8 1
5 3 0, 8 1
s 3 x 3 0 1 2 3 x 3 * R 3 ( s 3,x 3 *)
5 0, 5 6 7 0, 6 4 8 0, 6 4 8 0, 6 0 8 1,2 0, 6 4 8
回溯, 有多组最优解 。
I,x3=1,x2=3,x1=1,R3=0.8 ?0.9 ?0.9=0.648
II,x3=2,x2=2,x1=1,R3= 0.9?0.8?0.9=0.648
III,x3=2,x2=3,x1=0,R3= 0.9?0.9?0.8 =0.648
31
例 6 用动态规划解非线性规划
解, 这是一个资源分配问题。设分配次序为 x1,x2,x3，阶段正向
编号，但逆向递推，由约束条件可得边界条件 s1=27,s4=0。
第三阶段：（给 x3分配）
?
?
?
?
???
???
0,,
27
)(m ax
321
321
321
xxx
xxx
xxxxf
333 )( xxf ?
由边界条件和状态转移方程有,s4=s3?x3=0，即 x3*= s3；
因此有，
33*3 )( ssf ?
第二阶段：（给 x2分配） )(),(
3*32222 sfxxsf ??
由状态转移方程有,s3=s2?x2，代入上式得，
22222
22222
222222
2)(,2,
02121
),(
ssfsx
xsxxf
xsxxsf
??
??????
???
??解得
32
例 6 用动态规划解非线性规划
第一阶段：（给 x1分配）
212*21111 2)(),( sxsfxxsf ????
由状态转移方程有,s2=s1?x1=27 ?x1,代入上式得，
9,
9)(,9,
0254121
)27(2),(
321
111
1111
11111
???
??
??????
???
???
??
xxx
sfx
xxxf
xxxsf
回溯得
解得
33
动态规划总结
? 二大类：生产 -库存问题；资源分配问题
?
?
?
?
?
?
??
?
?
?
???
?
?
连续型
离散型
状态和控制变量
累乘
累加
目标函数
状态转移公式
资源分配问题二
连续型
离散型
状态和控制变量
状态转移公式
库存问题生产一
,
-,
1
1
kkk
kkkk
xss
yxss
