第一节 动态规划的基本概念与方法一、多阶段决策问题
1,时间阶段的例子（机器负荷问题）
某厂有 1000台机器，现需作一个五年计划，
以决定每年安排多少台机器投入高负荷生产（产量大但损耗也大）可使五年的总产量最大。
1 2 3 4 5S1=1000
x1 x2 x5x4x3
s5
v1 v2 v3 v4 v5
s2 s3 s4
2,空间阶段的例子（最短路问题）
如图为一线路网络。现要从 A点铺设一条管道到 E点，图中两点间连线上数字表示两点间距离。现需选一条由 A到 E的铺管线路，使总距离最短。
A E
B1
B2
B3
C1
C2
C3
D1
D2
2 9
5
3
12
25
1
56
4
6
8
10
13
12
11
14
10
阶段 1 阶段 2 阶段 3 阶段 4
二、基本概念与方程
1.基本概念阶段 —— 分步求解的过程，用阶段变量 k表示,k=1,…,n
状态 —— 每阶段初可能的情形或位置，用状态变量 Sk表示。
按状态的取值是离散或连续，将动态规划问题分为离散型和连续型。
决策 —— 每阶段状态确定后的抉择，即从该状态演变到下阶段某状态的选择，用决策变量 xk表示。
状态转移 —— 由 Sk转变为 Sk+1的规律，记 Sk+1=T(Sk,xk)。
策略 —— 由各阶段决策组成的序列，记 P1n={x1,…,xn}，
称 Pkn={xk,…,xn}为阶段 k至 n的后部子策略。
阶段指标 —— 每阶段选定决策 xk后所产生的效益，记
vk= vk(Sk,xk)。
指标函数 —— 各阶段的总效益，记相应于 Pkn的指标函数为 vkn= vkn(Sk,Pkn )。 其中最优的称最优指标函数，记 fk = fk（ Sk ） =opt vkn。
问题：动态规划的最优解和最优值各是什么？
—— 最优解：最优策略 P1n,
最优值：最优指标 f1。
2.基本原理与基本方程
（ 1）基本原理
。有和允许状态
（对任何是最优策略定理：
1111
11
1
,
)1),,(
fvo p tfs
nkkxxP?
略。子过程来说必为最优策至点的为起对于以），子策略（则对任何是最优策略，最优性原理）：若推论（
nk
sPnkk
PB e l l m a n
1
1
以最短路为例说明
（ 2）基本方程根据最优性原理，可建立从后向前逆推求解的递推公式 —— 基本方程：
,1,0,
1
1
nkf
fvo p tf
动态规划求解的一般步骤：
- 确定过程的分段，构造状态变量；
- 设置决策变量，写出状态转移；
- 列出阶段指标和指标函数；
- 写出基本方程，由此逐段递推求解。
三、求解方法
1,离散型（用表格方式求解）
例 1 用动态规划方法求解前面的最短路问题。
A E
B1
B2
B3
C1
C2
C3
D1
D2
2 9
5
312
251
56
4
6
8
10
13
12
11
14
10
A E
B1
B2
B3
C1
C2
C3
D1
D2
2 9
5
312
251
56
4
6
8
10
13
12
11
14
10
解：设阶段 k=1,2,3,4依次表示 4个阶段选路的过程；
状态 sk表示 k阶段初可能处的位置；
决策 xk表示 k阶段初可能选择的路；
阶段指标 vk表示 k阶段与所选择的路段相应的路长；
指标函数 vk4 = 表示 k至 4阶段的总路长；?
v
,14,0,5
1
kf
fvM i nf kkk递推公式：
A E
B1
B2
B3
C1
C2
C3
D1
D2
2 9
5
312
251
56
4
6
8
10
13
12
11
14
10
4
k Sk xk vk vkn=vk+fk+1 fk?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
C1
C2
C3
9
3
5
6
10
8
29
53
25
56
210
58
8
7
12
C1D1E
C2D2E
C3D2E
k Sk xk vk vkn=vk+fk+1 fk?P
A E
B1
B2
B3
C1
C2
C3
D1
D2
2 9
5
312
251
56
4
6
8
10
13
12
11
14
10
2
B1
B2
B3
2
1
C
C
14
12
714
812
20 B
1C1D1E
C
C
C
4
10
6
124
710
86
14 B2C1D1E
C
C
C
11
12
13
1211
712
813
19 B3C2D2E
k Sk xk vk vkn=vk+fk+1 fk?P
A E
B1
B2
B3
C1
C2
C3
D1
D2
2 9
5
312
251
56
4
6
8
10
13
12
11
14
10
1 A
3
2
1
B
B
B
1
5
2
191
5
202
14 19 AB2C1D1E
P*14=AB2C1D1E
f1 = 19
（最短路）
（最短距）
2,连续型（用公式递推求解）
例 2 用动态规划方法求解前面的机器负荷问题。
某种机器可以在高、低两种负荷下进行生产。
高负荷年产量 8，年完好率 0.7；低负荷年产量 5，
年完好率 0.9。现有完好机器 1000台，需制定一个 5
年计划，以决定每年安排多少台机器投入高、低负荷生产，使 5年的总产量最大。
解：设阶段 k=1,…,5表示第 k年安排机器的过程；
状态 sk表示第 k年初的完好机器台数；
决策 xk表示第 k年投入高负荷的机器台数；则投入低负荷的台数为 sk-xk ；
状态转移 sk+1=0.7xk+0.9(sk-xk)；
阶段指标 vk=8xk+5(sk-xk)表示第 k年的产量；
指标函数 vkn= 表示第 k至 5年的总产量；?
5 v
,15,0,6
1
kf
fvM a xf递推公式：
550
55506505
53
)5(85
55
5555
sxM a x
xsxM a xfvM a xfk
，当投入高负荷。年初将全部完好机器都即第 5,8,sfsx
440
444440
544405404
1 2,21,4
))0,9 (8 ( 0,753
8)5(84
44
44
4444
sxM a x
xsxsxM a x
sxsxM a xfvM a xfk
，当投入高负荷。年初将全部完好机器都即第 4,1 3,6,4444 sfsx
330
333304303
1 7,2 40,2 8
)0,21 3,6 ( 0,9533
33
3333
sxM a x
xssxM a xfvM a xfk
，当投入高负荷。年初将全部完好机器都即第 3,1 7,5 2,3333 sfsx
220
222203202
2 0,
)0,25 2 ( 0,917532
22
2222
x.sM a x
xs.sxM a xfvM a xfk
508
，当投入低负荷。年初将全部完好机器都即第 20,2 0,8,222 sfx
110
111102101
2 3,7
)0,2( 0,92053
11
1111
x.sM a x
xs.sxM a xfvM a xfk
1612
81
，当投入低负荷。年初将全部完好机器都即第 1,2 3,7 20,111 sfx
5年的最大总产量为 23,72× 1000=23720。
1,时间阶段的例子（机器负荷问题）
某厂有 1000台机器，现需作一个五年计划，
以决定每年安排多少台机器投入高负荷生产（产量大但损耗也大）可使五年的总产量最大。
1 2 3 4 5S1=1000
x1 x2 x5x4x3
s5
v1 v2 v3 v4 v5
s2 s3 s4
2,空间阶段的例子（最短路问题）
如图为一线路网络。现要从 A点铺设一条管道到 E点，图中两点间连线上数字表示两点间距离。现需选一条由 A到 E的铺管线路，使总距离最短。
A E
B1
B2
B3
C1
C2
C3
D1
D2
2 9
5
3
12
25
1
56
4
6
8
10
13
12
11
14
10
阶段 1 阶段 2 阶段 3 阶段 4
二、基本概念与方程
1.基本概念阶段 —— 分步求解的过程，用阶段变量 k表示,k=1,…,n
状态 —— 每阶段初可能的情形或位置，用状态变量 Sk表示。
按状态的取值是离散或连续，将动态规划问题分为离散型和连续型。
决策 —— 每阶段状态确定后的抉择，即从该状态演变到下阶段某状态的选择，用决策变量 xk表示。
状态转移 —— 由 Sk转变为 Sk+1的规律，记 Sk+1=T(Sk,xk)。
策略 —— 由各阶段决策组成的序列，记 P1n={x1,…,xn}，
称 Pkn={xk,…,xn}为阶段 k至 n的后部子策略。
阶段指标 —— 每阶段选定决策 xk后所产生的效益，记
vk= vk(Sk,xk)。
指标函数 —— 各阶段的总效益，记相应于 Pkn的指标函数为 vkn= vkn(Sk,Pkn )。 其中最优的称最优指标函数，记 fk = fk（ Sk ） =opt vkn。
问题：动态规划的最优解和最优值各是什么？
—— 最优解：最优策略 P1n,
最优值：最优指标 f1。
2.基本原理与基本方程
（ 1）基本原理
。有和允许状态
（对任何是最优策略定理：
1111
11
1
,
)1),,(
fvo p tfs
nkkxxP?
略。子过程来说必为最优策至点的为起对于以），子策略（则对任何是最优策略，最优性原理）：若推论（
nk
sPnkk
PB e l l m a n
1
1
以最短路为例说明
（ 2）基本方程根据最优性原理，可建立从后向前逆推求解的递推公式 —— 基本方程：
,1,0,
1
1
nkf
fvo p tf
动态规划求解的一般步骤：
- 确定过程的分段，构造状态变量；
- 设置决策变量，写出状态转移；
- 列出阶段指标和指标函数；
- 写出基本方程，由此逐段递推求解。
三、求解方法
1,离散型（用表格方式求解）
例 1 用动态规划方法求解前面的最短路问题。
A E
B1
B2
B3
C1
C2
C3
D1
D2
2 9
5
312
251
56
4
6
8
10
13
12
11
14
10
A E
B1
B2
B3
C1
C2
C3
D1
D2
2 9
5
312
251
56
4
6
8
10
13
12
11
14
10
解：设阶段 k=1,2,3,4依次表示 4个阶段选路的过程；
状态 sk表示 k阶段初可能处的位置；
决策 xk表示 k阶段初可能选择的路；
阶段指标 vk表示 k阶段与所选择的路段相应的路长；
指标函数 vk4 = 表示 k至 4阶段的总路长；?
v
,14,0,5
1
kf
fvM i nf kkk递推公式：
A E
B1
B2
B3
C1
C2
C3
D1
D2
2 9
5
312
251
56
4
6
8
10
13
12
11
14
10
4
k Sk xk vk vkn=vk+fk+1 fk?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
C1
C2
C3
9
3
5
6
10
8
29
53
25
56
210
58
8
7
12
C1D1E
C2D2E
C3D2E
k Sk xk vk vkn=vk+fk+1 fk?P
A E
B1
B2
B3
C1
C2
C3
D1
D2
2 9
5
312
251
56
4
6
8
10
13
12
11
14
10
2
B1
B2
B3
2
1
C
C
14
12
714
812
20 B
1C1D1E
C
C
C
4
10
6
124
710
86
14 B2C1D1E
C
C
C
11
12
13
1211
712
813
19 B3C2D2E
k Sk xk vk vkn=vk+fk+1 fk?P
A E
B1
B2
B3
C1
C2
C3
D1
D2
2 9
5
312
251
56
4
6
8
10
13
12
11
14
10
1 A
3
2
1
B
B
B
1
5
2
191
5
202
14 19 AB2C1D1E
P*14=AB2C1D1E
f1 = 19
（最短路）
（最短距）
2,连续型（用公式递推求解）
例 2 用动态规划方法求解前面的机器负荷问题。
某种机器可以在高、低两种负荷下进行生产。
高负荷年产量 8，年完好率 0.7；低负荷年产量 5，
年完好率 0.9。现有完好机器 1000台，需制定一个 5
年计划，以决定每年安排多少台机器投入高、低负荷生产，使 5年的总产量最大。
解：设阶段 k=1,…,5表示第 k年安排机器的过程；
状态 sk表示第 k年初的完好机器台数；
决策 xk表示第 k年投入高负荷的机器台数；则投入低负荷的台数为 sk-xk ；
状态转移 sk+1=0.7xk+0.9(sk-xk)；
阶段指标 vk=8xk+5(sk-xk)表示第 k年的产量；
指标函数 vkn= 表示第 k至 5年的总产量；?
5 v
,15,0,6
1
kf
fvM a xf递推公式：
550
55506505
53
)5(85
55
5555
sxM a x
xsxM a xfvM a xfk
，当投入高负荷。年初将全部完好机器都即第 5,8,sfsx
440
444440
544405404
1 2,21,4
))0,9 (8 ( 0,753
8)5(84
44
44
4444
sxM a x
xsxsxM a x
sxsxM a xfvM a xfk
，当投入高负荷。年初将全部完好机器都即第 4,1 3,6,4444 sfsx
330
333304303
1 7,2 40,2 8
)0,21 3,6 ( 0,9533
33
3333
sxM a x
xssxM a xfvM a xfk
，当投入高负荷。年初将全部完好机器都即第 3,1 7,5 2,3333 sfsx
220
222203202
2 0,
)0,25 2 ( 0,917532
22
2222
x.sM a x
xs.sxM a xfvM a xfk
508
，当投入低负荷。年初将全部完好机器都即第 20,2 0,8,222 sfx
110
111102101
2 3,7
)0,2( 0,92053
11
1111
x.sM a x
xs.sxM a xfvM a xfk
1612
81
，当投入低负荷。年初将全部完好机器都即第 1,2 3,7 20,111 sfx
5年的最大总产量为 23,72× 1000=23720。
