第二章 动态规划
（Dynamic Programming）
2.1 动态规划的基本概念与方法
2.2 动态规划应用举例
http://www.tju.edu.cn
第二章动态规划
2.1 动态规划的基本概念与方法一、多阶段决策问题举例
1,时间阶段例子(生产负荷问题) 某种机器可以在高、低两种负荷下进行生产。高负荷年产量
8，年完好率0.7；低负荷年产量5，年完好率0.9。
现有完好机器1000台，需制定一个5年计划，以决定每年安排多少台机器投入高、低负荷生产，
使5年的总产量最大。
123
45
S
1
=1000
x
1
x
2
x
5
x
4
x
3
s
5
v
1
v
2
v
3
v
4
v
5
s
2
s
3
s
4
http://www.tju.edu.cn
第二章动态规划
2.空间阶段的例子（最短路问题） 如图为一线路网络。现要从A点铺设一条管道到E点，图中两点间连线上数字表示两点间距离。现需选一条由A到E的铺管线路，使总距离最短。
A
E
B
1
B
2
B
3
C
1
C
2
C
3
D
1
D
2
29
5
3
12
2
5
1
5
6
4
6
8
10
13
12
11
14
10
阶段1 阶段2 阶段3 阶段4
http://www.tju.edu.cn
第二章动态规划二、基本概念与方程
1、基本概念阶段 ——分步求解的过程，用阶段变量 k表示，
k=1,…,n
状态 ——每阶段初可能的情形或位置，用状态变量
S
k
表示。 动态规划中的状态应具有无后效性。
决策 ——每阶段状态确定后的抉择，即从该状态演变到下阶段某状态的选择，用决策变量 x
k
表示。
http://www.tju.edu.cn
第二章动态规划状态转移 ——由 S
k
转变为 S
k+1
的规律，记 S
k+1
=T(S
k，
x
k
)。
策略 ——由各阶段决策组成的序列，记 P
1n
={x
1,…，
x
n
}，
称 P
kn
={x
k,…，
x
n
}为阶段 k至 n的后部子策略。
阶段指标 ——每阶段选定决策 x
k
后所产生的效益，记
v
k
= v
k
(S
k，
x
k
)。
指标函数 ——各阶段的总效益，记相应于 P
kn
的指标函数为 v
kn
= v
kn
(S
k，
P
kn
)。
其中最优的称 最优指标函数,记 f
k
= f
k
（ S
k
）=opt v
kn
。
http://www.tju.edu.cn
第二章动态规划问题：动态规划的最优解和最优值各是什么？
——最优解：最优策略 P
1n
，
最优值：最优指标 f
1
。
http://www.tju.edu.cn
第二章动态规划
（1）基本原理
{}。有和允许状态
（对任何是最优策略定理：
1111
11
1
,
)1),,(
+

+=
<<?=
kk
p
nn
fvoptfs
nkkxxP
k
"
略。子过程来说必为最优策至点的为起对于以），子策略（则对任何是最优策略，最优性原理）：若推论（
nk
sPnkk
PBellman
kkn
n

<<1
1
2、基本方程
http://www.tju.edu.cn
第二章动态规划
（2）基本方程根据最优性原理，可建立从后向前逆推求解的递推公式——基本方程：
{ }
==
+=
+
+
,1,0,
1
1
"nkf
fvoptf
n
kk
x
k
k
以最短路为例说明
http://www.tju.edu.cn
第二章动态规划动态规划求解的一般步骤：
?确定过程的分段，构造状态变量；
?设置决策变量，写出状态转移；
?列出阶段指标和指标函数；
?写出基本方程，由此逐段递推求解。
http://www.tju.edu.cn
第二章动态规划三、求解方法
1.离散型（用表格方式求解）
例1 用动态规划方法求解前面的最短路问题
A
E
B
1
B
2
B
3
C
1
C
2
C
3
D
1
D
2
29
5
3
12
2
5
1
5
6
4
6
8
10
13
12
11
14
10
http://www.tju.edu.cn
第二章动态规划解：设阶段 k=1，2，3，4依次表示4个阶段选路的过程；
状态 s
k
表示 k阶段初可能处的位置；
决策 x
k
表示 k阶段初可能选择的路；
阶段指标 v
k
表示 k阶段与所选择的路段相应的路长；
指标函数 表示 k至4阶段的总路长；
4
4ki
ik
vv
=
=
∑
{ }
1
5
0,4,,1
kkk
fMinvf
fk
+
=+
=="
递推公式：
http://www.tju.edu.cn
第二章动态规划
4
kS
k
x
k
v
k
v
kn
=v
k
+f
k+1
f
k
kn
P
2
1
D
D
E
E
02
05
+
+
2
5
2
5
ED
ED
2
1
3
2
1
D
D
2
1
D
D
2
1
D
D
C
1
C
2
C
3
9
3
5
6
10
8
29
53
+
+
25
56
+
+
210
58
+
+
8
7
1
2
C
1
D
1
E
C
2
D
2
E
C
3
D
2
E
http://www.tju.edu.cn
第二章动态规划
kS
k
x
k
v
k
v
kn
=v
k
+f
k+1
f
k
kn
P
2
B
1
B
2
B
3
2
1
C
C
14
12
714
812
+
+
20
B
1
C
1
D
1
E
3
2
1
C
C
C
4
10
6
124
710
86
+
+
+
14
B
2
C
1
D
1
E
3
2
1
C
C
C
11
12
13
1211
712
813
+
+
+
19
B
3
C
2
D
2
E
http://www.tju.edu.cn
第二章动态规划
kS
k
x
k
v
k
v
kn
=v
k
+f
k+1
f
k
kn
P
1 A
3
2
1
B
B
B
1
5
2
191
5
202
+
+
+
14
19 AB
2
C
1
D
1
E
P*
14
=
AB
2
C
1
D
1
E
（最短路）
（最短距）f
1
= 19
http://www.tju.edu.cn
第二章动态规划
A
E
B
1
B
2
B
3
C
1
C
2
C
3
D
1
D
2
29
5
3
12
2
5
1
5
6
4
6
8
10
13
12
11
14
10
P*
14
=
AB
2
C
1
D
1
E
（最短路）
（最短距）
f
1
= 19
http://www.tju.edu.cn
第二章动态规划例2用动态规划方法求解前面的机器负荷问题某种机器可以在高、低两种负荷下进行生产。
高负荷年产量8，年完好率0.7；低负荷年产量5，年完好率0.9。现有完好机器1000台，
需制定一个5年计划，以决定每年安排多少台机器投入高、低负荷生产，使5年的总产量最大。
2.连续型（用公式递推求解）
http://www.tju.edu.cn
第二章动态规划解：设阶段 k=1,…，5表示第 k年安排机器的过程；
状态 s
k
表示第 k年初的完好机器台数；
决策 x
k
表示第 k年投入高负荷的机器台数；则投入低负荷的台数为 s
k
-x
k；
状态转移 s
k+1
=0.7x
k
+0.9(s
k
-x
k
)；
阶段指标：
指标函数：
=
=+=
+
0
1,,5}{max
6
1
f
kfVf
kkk
"
基本方程：
∑
=
=
5
5
ki
ik
VV
V
k
=8x
k
+5(S
k
-x
k
) ；
http://www.tju.edu.cn
第二章动态规划
K=5
}{max
655
fVf +=
)}(58{max
555
0
55
xSx
Sx
+=
≤≤
}53{max
55
0
55
Sx
Sx
+=
≤≤
5555
8,SfSx ==∴
K=4
}{max
544
fVf +=
}8)(58{max
5444
0
44
SxSx
Sx
+?+=
≤≤
4444
6.13,SfSx ==∴
)]}(9.07.0[853{max
44444
0
44
xSxSx
Sx
+++=
≤≤
}2.124.1{max
44
0
44
Sx
Sx
+=
≤≤
http://www.tju.edu.cn
第二章动态规划同理：
K=3
}{max
433
fVf +=
}24.1728.0{max
33
0
33
Sx
Sx
+=
≤≤
3333
52.17,SfSx ==∴
K=2
}{max
322
fVf +=
}8.205.0{max
22
0
22
Sx
Sx
+?=
≤≤
222
8.20,0 Sfx ==∴
K=1
}{max
211
fVf +=
}72.2316.1{max
11
0
11
Sx
Sx
+?=
≤≤
2372072.23,0
111
===∴
Sfx
http://www.tju.edu.cn
第二章动态规划故最优计划为：
年份
12345
高负荷
0 0 810 567 397
低负荷
1000 900 0 0 0
总产量,23720
http://www.tju.edu.cn
第二章动态规划
2.2 动态规划应用举例一、资源分配问题
1,问题的一般提法设有某种资源，总数量为 a，用于生产 n种产品；
若分配数量 x
i
用于生产第 i种产品，其收益为
g
i
(x
i
)。问应如何分配，可使总收益最大？
http://www.tju.edu.cn
第二章动态规划
2,数学规划模型
i
xi种产品的资源数量为设分配给第决策变量,
∑
=
=
n
i
ii
xgMaxz
1
)( 目标函数：
=≥
=
∑
=
nix
ax
i
n
i
i
,,1,0
1
"
约束条件：
模型的特点
——变量分离。
http://www.tju.edu.cn
第二章动态规划
3.用动态规划方法求解阶段k
状态s
k
决策x
k
=1,…,n表示把资源分配给第 k种产品的过程；
表示在给第 k种产品分配之前还剩有的资源量；
表示分配给第 k种产品的资源量；
状态转移s
k+1
= s
k
-x
k；
阶段指标v
k
指标函数v
kn；
∑
=
=
=
n
ki
ii
kk
xg
xg
)(
)(
12
S
1
=a
x
1
x
2
g
1
(x
1
)g
2
(x
2
)
n
x
n
s
n
g
n
(x
n
)
s
2
s
3
...
http://www.tju.edu.cn
第二章动态规划
{ }
==
+=
+
+
,1,0,
1
1
"nkf
fvMaxf
n
kk
x
k
k
基本方程
http://www.tju.edu.cn
第二章动态规划例3 某公司拟将某种高效设备5台分配给所属甲、
乙、丙3厂。各厂获此设备后可产生的效益如下表。问应如何分配，可使所产生的总效益最大？
效益厂设备台数甲乙丙
0 0 0 0
1 3 5 4
2 7 10 6
3 9 11 11
4 12 11 12
5 13 11 12
http://www.tju.edu.cn
第二章动态规划解：
阶段k
状态s
k
决策x
k
=1,2,3依次表示把设备分配给甲、乙、丙厂的过程表示在第k阶段初还剩有的可分台数；
表示第k阶段分配的设备台数；
状态转移s
k+1
= s
k
-x
k；
阶段指标v
k
指标函数v
k3；阶段分配后产生的效益表示第
∑
=
=
3
k
)(
i
ii
xv
k
{ }
==
+=
+
,1,0,
1
23
4
kf
fvMaxf
kk
x
k
k
基本方程
http://www.tju.edu.cn
第二章动态规划效益厂设备台数甲乙丙
0 0 0 0
1 3 5 4
2 7 10 6
3 9 11 11
4 12 11 12
5 13 11 12
kS
k
x
k
v
k
v
k
+f
k+1
f
k
kn
P
3
0
1
2
3
4
5
0
1
2
3
4
5
0
4
6
11
12
12
0+0
4+0
6+0
11+0
12+0
12+0
0
4
6
11
12
12
0
1
2
3
4
5
kS
k
x
k
v
k
v
k
+f
k+1
f
k
kn
P
0
1
2
3
4
5
2
0 0 0+0 0 0-0
0 0 0+4
1 5 5+0
5 1-0
0 0 0+6
1 5 5+4
2 10 10+0
10 2-0
0 0 0+11
1 5 5+6
2 10 10+4
3 11 11+0
14 2-1
0 0 0+12
1 5 5+11
2 10 10+6
3 11 11+4
4 11 11+0
16 1-3
2-2
0 0 0+12
1 5 5+12
2 10 10+11
3 11 11+6
4 11 11+4
5 11 11+0
21 2-3
http://www.tju.edu.cn
第二章动态规划
kS
k
x
k
v
k
v
k
+f
k+1
f
k
kn
P
1
5
0
1
2
3
4
5
0
3
7
9
12
13
0+21
3+16
7+14
9+10
12+5
13+0
21 0-2-3
2-2-1
最优策略：P*
13
为0-2-3或2-2-1，
即分给甲厂0台、分给乙厂2台、分给丙厂3台，
或分给甲厂2台、分给乙厂2台、分给丙厂1台。
最优值：f
1
=21。
可见，最优解可以是不唯一的，但最优值是唯一的。
http://www.tju.edu.cn
第二章动态规划资源分配问题的应用很广泛，例如：
1.某学生正在备考4门功课，还剩7天时间，每门功课至少复习1天。若他已估计出各门功课的复习天数与能提高的分数之间的关系，问他应怎样安排复习时间可使总的分数提高最多？
2.背包问题：旅行者携带的背包中能装的物品重量为a，现他要从n种物品中挑选若干数量装入背包，问他应如何挑选可使所带的物品总价值最大？
http://www.tju.edu.cn
第二章动态规划二、复合系统工作可靠性问题
1、问题描述,设某工作系统由 n个部件串接而成，为提高系统的可靠性，在每个部件上装有备用件。已知部件 i上装有 x
i
个备用件时，其正常工作的概率为 p
i
(x
i
)；每个部件 i的备用件重量为 w
i
，系统要求总重量不超过 W。问应如何安排备用件可使系统可靠性最高？
串接:
12
http://www.tju.edu.cn
第二章动态规划
2,数学规划模型个备用件个部件安排设给第决策变量：
i
xi
)(
1
ii
n
i
xpMaxz
=
∏=目标函数：
≤
∑
=
为非负整数约束条件：
i
n
i
ii
x
Wxw
1
模型的特点
——变量分离。
3.用动态规划方法求解
12
S
1
=W
x
1
x
2
p
1
(x
1
) p
2
(x
2
)
n
x
n
s
n
p
n
(x
n
)
s
2
s
3
...
http://www.tju.edu.cn
第二章动态规划
3,用动态规划法求解阶段：
第k-n部件的容许总重量
k=1,…,n；表示给第k部件安排备用件的过程；
状态S
k
：
决策x
k
：
第k部件安排的备用件个数；
状态转移方程,S
k+1
= S
k
-W
k
x
k；
阶段指标,指标函数：
=
=?=
+
+
1
1,,}{max
1
1
n
kkk
f
nkfVf"
基本方程：
∏
=
=
n
ki
ikn
VV
V
k
= P
k
(x
k
)；
http://www.tju.edu.cn
第二章动态规划三、设备更新问题某运输公司购进一批卡车投入运营，公司每年初需对卡车作出更新或继续使用的决定。假设第 k年中,r
k
(t
k
)表示车龄为 t
k
的车使用一年的收入，
u
k
(t
k
)表示车龄为 t
k
的车使用一年的维修费用，
c
k
(t
k
)表示车龄为 t
k
的车更新成新车的费用。现公司需制定一个10年计划，以决定如何安排使10年的总收入最大。
http://www.tju.edu.cn
第二章动态规划
12
S
1
=？
x
1
x
2
10
x
10
s
1
0
v
1
v
2
v
10
s
2
…
http://www.tju.edu.cn
第二章动态规划阶段k
状态s
k
决策x
k
= 1,…,10表示第 k年的决策过程；
= t
k
表示第 k年的车龄；
=
年不更新，第年更新第
k
k
0
1,
状态转移t
k+1
= t
k
+1(1-x
k
)
阶段指标v
k
指标函数v
kn
= r
k
[t
k
] - u
k
[t
k
] - c
k
(t
k
)(1-x
k
)(1-x
k
) x
k；
∑
=
=
10
ki
i
v
{}
{ }
==
+=
+
∈
,110,0,
11
1
"kf
fvMaxf
kk
x
k
k
1,0
基本方程
P209页例
9.6
http://www.tju.edu.cn
第二章动态规划四、其他——随机型问题举例某瓷厂接受订制一个瓷瓶的任务。瓷瓶用电炉烧制。
据技术分析估计，每个瓷瓶出炉后的合格率为0.5，
各瓶合格与否相互独立（即一炉如装有 n个瓷瓶，那么出炉后都不合的概率为0.5
n
）。制造一个瓷瓶的原料费为100元，烧一炉的费用为300元。现因厂中条件限制最多只能烧3炉，每炉最多装4个瓷瓶。若3
炉的瓷瓶无1个合格，则因不能履行合同而被罚款
1600元。试用动态规划方法确定一种生产方案（即每炉该装几个瓷瓶），使总的期望成本为最小。