§ 1.5 动态规划动态规划是一类多阶段决策过程的最优化方法。
基本方法是：按阶段把一个大问题化成一系列相互有联系的子问题，建立相应的递推公式，解一系列的子问题，最后求得整个问题的最优解。
例 最短路问题一、动态规划的基本概念和基本方法
E
1B
2D
1D
A
3B
2B
3C
2C
1C
2
4
3
7
46
3 2
4
4 1
5
1
4
6
3
3 3
3
4
7
11
7
8
4
6
3
4
011
1 2 3 4阶段从 A到 E的路有,)(181233 条
求 A到 E的最短路。
4 5 7 8 9 10 12 13
1,概念
阶段,根据时间或空间划分。
状态,某阶段 出发的位置。
既是某支路本阶段的起点，又是前一阶段的终点。
本例 按 空间 分成 4个阶段本例 4个阶段的 状态集,
},{A },,,{ 321 BBB },,,{ 321 CCC },,{ 21 DD
状态变量 sk,描述状态的变量。
As 的取值：1
3212,,BBBs 的取值：
3213,,CCCs 的取值：
214,DDs 的取值：
#
决策,从给定状态到下一阶段某状态的选择。
决策变量 xk=xk(sk),描述决策的变量。
如,;2,)( 11 路程为BAx?,4,)( 21 路程为BAx?
有,};,,{ 3211 BBBxX
};,,{ 3212 CCCx2X
};,{ 213 DDx3X
}.{4 Ex4X
容许决策集合
状态转移方程,描述状态转移规律的函数关系
),(1 kkk xsTs
策略,决策序列
21 ; BABA本例可记为
24
如,})(,)(,)(,)({ 1412321211 EDxDCxCBxBAx
})(,)(,)(,)({ 1411312221 EDxDCxCBxBAx
本例共有 18个策略，欲从中选出 最优策略 (路长最短者 )。
k 子策略,策略中，从 第 k个 决策开始 到最后一个决策所成之子序列。
如,})(,)(,)({ 14113122 EDxDCxCBx
})(,)({ 14113 EDxDCx
报酬函数,一决策对应的“费用”，记为
),( kkk xsv
如,4))(,( 21212 CBxBv 的路程）（,21 CB?
25
目标（指标）函数,衡量策略好坏的函数。
从 出发到 终点 的目标函数记为：ks
nkxxsv nkkkn,,2,1),,,,(
视 为确定状态,是变化的。ks nk xx,,?
从 出发到终点的 最优目标值,ks
),,,()(
,,nkkknxxkk
xxsvoptsf
nk
m a x )m i n( 或为opt
nk,,2,1
例中,)(1 Af? 为 A 到 E 的最短路程，
相应的策略为所求的最优策略 — 最短路。
)( kk sf? 对应的策略为 到终点最优子策略。ks
26
2,最优化原理例中：有最优策略
})(,)(,)(,)({ 1411312221 EDxDCxCBxBAx
即 }{ 112 EDCBA
11)(1 Af— A到 E的最短路，路长为子策略,}{ 112 EDCB
— B2到 E的最短路，路长为 7)( 22 Bf
}{ 11 EDC
— C1到 E的最短路，路长为 4)( 13 Cf
……
27
#
最优策略有 性质 — 最优化原理：
无论过去的状态和决策如何，对某确定的状态，
余下的决策必须构成最优子策略 。
或，对某状态而言，该状态到终点的最优策略只与后面的选择有关，与前面的选择无关 。
或,已知现在，将来与过去无关 。
即 后部子问题 的最优策略是 父问题 的 最优子策略 。
28
#
利用该原理得寻优方法：
A E问题：
子问题：
行进方向寻优方向先求出“最小子问题”中，各状态到 E的最优子策略，
将问题化成一系列 相互有联系的 子问题，
再求出“次小子问题”中（第 3阶段），各状态到
E的最优子策略，如此向前推进，而每次都利用 后部子问题 中已得到的最优子策略。
如：已得 C1到 E的最优子策略,}{ 11 EDC
在求 B2到 E的最佳走法时，如果该阶段取 12 CB?
29
则后面的最佳走法是：
即得最优子策略,EDC 11 }{ 2?B
}{ 11 EDC
在第 1阶段，若取,则得 A到 E的最佳走法：2BA?
EDCB 112?A{ }
如果是,则利用 B1到 E的最佳走法得：1BA?
EDCB 221?A{ }
EDCB 111?A{ }或
减少了计算量,即不必再验证后面走法的最优性；
丰富了结果,即得从任何一点出发到终点的最短路。
210
3,动态规划的数学模型根据最优化原理，可得 从 出发到终点的 最优目标值,ks
),,,()(
,,nkkknxxkk
xxsvoptsf
nk
) },(),({ 11
kkkkk
Xx
sfxsvopt
kk
)(0)( 11 规定 nn sf
1,2,,1, nnk
),(,1 kkk xsTs其中例中,1,2,3,4?k )},(),({m in)( 11 kkkkkXxkk sfxsvsf
kk
)(0)(5 规定 Ef
的路程。到为 1),(?kkkkk ssxsv
211
最短路问题的解 （列表）
第 4阶段,)(
554 sfv
E
4x
4s
2
1
D
D
)( 44 sf4x
ED?1
ED?2
第 3阶段,)( 443 sfv
1D 2D
3
2
1
C
C
C
31?
3x
3s
)( 33 sf3x
44?
36? 43?
33? 43?
4
7
6
11 DC?
22 DC?
13 DC?
3
4
3
4
212
第 2阶段：
)( 332 sfv
321 CCC
3
2
1
B
B
B2x
2s )( 22 sf
2x
47? 74? 66?
43? 72? 64?
44? 71? 65?
11
7
8
2111 CBCB 或
12 CB?
2313 CBCB 或第 1阶段：
)( 221 sfv
321 BBB
)( 11 sf1x1x
1s
A 112? 74? 83? 11 32 BABA 或最优策略,2BA? 1C? 1D? E?
3BA? 1C? 1D? E?
3BA? 2C? 2D? E?
路长：
11)(1 Af
213
二、应用根据问题的特点，确定：阶段、状态变量、决策变量、
状态转移方程、目标函数递推公式。
例 （例 1.7） （ 生产存储问题 ）用动态规划方法求解。
解 假设与例 1.7同
4
3
2
1
76
80
72
70
60
120
70
60
月份 单位成本 ic (元 ) 销售量 id (件 )
按月份分 4个阶段；；决策变量月产量为第 )(kx k
（状态变量）；
月初库存量为第 ks k
);(1 状态转移方程kkkk dxss
);(2),( 报酬函数kkkkkk sxcxsv
（ 1）,建模模型：
) },(2{m in)( 1 kkkkkkkXxkk dxsfsxcsf
kk
1,2,3,4?k
0)( 55 sf 1?ks
（ 2）,求解
K=4,)}(276{m i n)( 554444
44
sfsxsf Xx
}276{m in 44
44
sxXx
的表达式。欲求 )(),( kkkkk sfsxx
:4X求
44455,0 dsxss由
}60|{ 4444 sxxX得故得,44 60 sx
)( 44 sf? 47445 60 s 44 276 sx
关于 x4的线性函数欲求 Xk,可利用 状态转移方程 和 约束条件,求出 xk满足的等式或不等式。
K=3:
)}(280{m in)( 33343333
33
dxsfsxsf Xx
)]}(74456 0[280{m in 33333
33
dxssxXx
4s
}134 40726{m in 33
33
sxXx
求 X3,?)(?)( 333 sxs即求
,3334 dxss
50)1207060(10030 4 s
333 1 7 01 2 0 sxs
,1 0 00 3 x?又
}1 7 0,1 0 0m i n {}1 2 0,0m a x { 333 sxs
70)7060(1 0 020 3 s?又
,12012050 3 s 170170100 3 s
100120 33 xs
X3的增函数从而得,33 1 2 0 sx
)( 33 sf? 1 3 4 4 0726 33 sx 37814160 s
故 }100120|{ 3333 xsxX
K=2,)}(272{m i n)(
22232222 22 dxsfsxsf Xx
1 0 02x
222 7619020)( ssf
}1 9 6 2 0766{m in 22
22
sxXx
}10070|{ 2222 xsxX可得
K=1,)}(270{m i n)( 11121111
11
dxsfsxsf Xx
}2 35 80746{m in 11
22
sxXx
求 X1:
由 0,401000,1121112 sdsdxss
得 10 060 1 x
}10060|{ 112 xxX
,1001x
)( 11 sf? 2 35 80071 006 22980?
,01s 1 0 01x
1112 dxss,40? 0 02x
,702223 dxss 50120 33 s
,03334 dxss 6060 44 sx
总费用,)(22980)( 11 元 sf
利用状态转移方程及 的表达式，按 k=1,2,3,4的顺序求最优策略。 (d1==60,d2=70,d3=120,d4=60)
)( kk sx?
（ 3）灵敏度分析如,2月份的库存损失了 20件（即 s2=20），则
2— 4 月份的最优生产计划如下：
)(100 222 无关与 sxx
,5070100202223 dxss
,70120 33 sx
,03334 dxss 6060 44 sx
费用增加：
)70781 4 1 6 0()50781 4 1 6 0()70()50( 33 ff
)(15 60 元?
又如,2月份出现 10件废品（ x2=90,s3=60），类似可求 3,4月份的最优生产计划。
注,
(1)当目标函数是线性函数或二次函数等简单函数时，
容易求出 的表达式，否则可求数值解。)( kk sf?
（ 2）当 取少数离散值时，可列表计算。如上例中还要求每 10个产品为一批地生产，则,
的可能取值为 0,10,20,…,100这些离散值。
kx
kx ks
＃
2,一维资源分配问题
a — 资源总量
— 第 k个使用者的效益)( kk xg
数学规划模型：
njx
axxxts
xgz
j
n
n
k
kk
,,2,1,0
.
)(m a x
21
1
总效益化为动态规划模型：
xk— 分配给第 k个使用者的资源量关键 求：阶段，状态变量，决策变量，状态转移方程。
阶段 — 将资源分配给一个使用者视为一个阶段，
决策变量,xk— 分配给第 k个使用者的资源量状态变量,sk— 前 k-1个使用者分配后的 剩余量即 nn
n
ki
ik xsasxs
,,1
状态转移方程,kkk xss 1 )(
1
k
n
ki
i
n
ki
i xxx
1x 2x kx 1?kx nx
使用者,1 2 k 1?k n
资源量：
1?ks
ks
as?1
状态变量：
允许决策集合,}0|{ kkkk sxxX
报酬函数,)(),( kkkkk xgxsv?
动态规划模型：
1,2,,1,)()(m a x)( 10 nkxsfxgsf kkkkksxkk
kk
)(m a x)( 0 nnsxnn xgsf
nn
)( nn sg?
1?ks
效益函数一般是增函数注,若原目标函数为连乘积
n
k
kk xgopt
1
)(
则动态规划目标函数为：
)()()( 11
kkkkXxkk sfxgoptsf
kk
例 （ P.41）
如何分配 2万元补加研制费，
使三种新产品 都不成功 的概率最小。有关数据如表。
30.020.015.02
50.040.020.01
80.060.040.00
CBA
产品研制费不 成 功 概 率解 建立非线性规划模型种产品的补加费分配给第 kx k
种新产品不成功的概率万元后，第分得 kxxp kkk )(
假定研制是 独立 进行的，即有
P(A,B,C均不成功 )
= P(A不成功 ) ·P(A不成功 ) ·P(A不成功 )
则得非线性规划模型：
且为整数0,,
2.
)()()(m i n
321
321
332211
xxx
xxxts
xpxpxpz
转化为动态规划模型：
状态变量：
种新产品的补加费，至第为分配给第 3
)3,2,1(
3
k
kxs
ki
ik
状态转移方程,2),2,1( 11 skxss kkk
则 1,2),()({m in)( 1 kxsfxpsf kkkkkXxkk
kk
)(m in)( 3333
33
xpsf Xx )( 33 sp?
允许决策集合,}0|{ 且为整数kkkk sxxX
))(( 的减函数是 kkk xxp?
kk sx0
330 sx
1?ks
基本方法是：按阶段把一个大问题化成一系列相互有联系的子问题，建立相应的递推公式，解一系列的子问题，最后求得整个问题的最优解。
例 最短路问题一、动态规划的基本概念和基本方法
E
1B
2D
1D
A
3B
2B
3C
2C
1C
2
4
3
7
46
3 2
4
4 1
5
1
4
6
3
3 3
3
4
7
11
7
8
4
6
3
4
011
1 2 3 4阶段从 A到 E的路有,)(181233 条
求 A到 E的最短路。
4 5 7 8 9 10 12 13
1,概念
阶段,根据时间或空间划分。
状态,某阶段 出发的位置。
既是某支路本阶段的起点，又是前一阶段的终点。
本例 按 空间 分成 4个阶段本例 4个阶段的 状态集,
},{A },,,{ 321 BBB },,,{ 321 CCC },,{ 21 DD
状态变量 sk,描述状态的变量。
As 的取值：1
3212,,BBBs 的取值：
3213,,CCCs 的取值：
214,DDs 的取值：
#
决策,从给定状态到下一阶段某状态的选择。
决策变量 xk=xk(sk),描述决策的变量。
如,;2,)( 11 路程为BAx?,4,)( 21 路程为BAx?
有,};,,{ 3211 BBBxX
};,,{ 3212 CCCx2X
};,{ 213 DDx3X
}.{4 Ex4X
容许决策集合
状态转移方程,描述状态转移规律的函数关系
),(1 kkk xsTs
策略,决策序列
21 ; BABA本例可记为
24
如,})(,)(,)(,)({ 1412321211 EDxDCxCBxBAx
})(,)(,)(,)({ 1411312221 EDxDCxCBxBAx
本例共有 18个策略，欲从中选出 最优策略 (路长最短者 )。
k 子策略,策略中，从 第 k个 决策开始 到最后一个决策所成之子序列。
如,})(,)(,)({ 14113122 EDxDCxCBx
})(,)({ 14113 EDxDCx
报酬函数,一决策对应的“费用”，记为
),( kkk xsv
如,4))(,( 21212 CBxBv 的路程）（,21 CB?
25
目标（指标）函数,衡量策略好坏的函数。
从 出发到 终点 的目标函数记为：ks
nkxxsv nkkkn,,2,1),,,,(
视 为确定状态,是变化的。ks nk xx,,?
从 出发到终点的 最优目标值,ks
),,,()(
,,nkkknxxkk
xxsvoptsf
nk
m a x )m i n( 或为opt
nk,,2,1
例中,)(1 Af? 为 A 到 E 的最短路程，
相应的策略为所求的最优策略 — 最短路。
)( kk sf? 对应的策略为 到终点最优子策略。ks
26
2,最优化原理例中：有最优策略
})(,)(,)(,)({ 1411312221 EDxDCxCBxBAx
即 }{ 112 EDCBA
11)(1 Af— A到 E的最短路，路长为子策略,}{ 112 EDCB
— B2到 E的最短路，路长为 7)( 22 Bf
}{ 11 EDC
— C1到 E的最短路，路长为 4)( 13 Cf
……
27
#
最优策略有 性质 — 最优化原理：
无论过去的状态和决策如何，对某确定的状态，
余下的决策必须构成最优子策略 。
或，对某状态而言，该状态到终点的最优策略只与后面的选择有关，与前面的选择无关 。
或,已知现在，将来与过去无关 。
即 后部子问题 的最优策略是 父问题 的 最优子策略 。
28
#
利用该原理得寻优方法：
A E问题：
子问题：
行进方向寻优方向先求出“最小子问题”中，各状态到 E的最优子策略，
将问题化成一系列 相互有联系的 子问题，
再求出“次小子问题”中（第 3阶段），各状态到
E的最优子策略，如此向前推进，而每次都利用 后部子问题 中已得到的最优子策略。
如：已得 C1到 E的最优子策略,}{ 11 EDC
在求 B2到 E的最佳走法时，如果该阶段取 12 CB?
29
则后面的最佳走法是：
即得最优子策略,EDC 11 }{ 2?B
}{ 11 EDC
在第 1阶段，若取,则得 A到 E的最佳走法：2BA?
EDCB 112?A{ }
如果是,则利用 B1到 E的最佳走法得：1BA?
EDCB 221?A{ }
EDCB 111?A{ }或
减少了计算量,即不必再验证后面走法的最优性；
丰富了结果,即得从任何一点出发到终点的最短路。
210
3,动态规划的数学模型根据最优化原理，可得 从 出发到终点的 最优目标值,ks
),,,()(
,,nkkknxxkk
xxsvoptsf
nk
) },(),({ 11
kkkkk
Xx
sfxsvopt
kk
)(0)( 11 规定 nn sf
1,2,,1, nnk
),(,1 kkk xsTs其中例中,1,2,3,4?k )},(),({m in)( 11 kkkkkXxkk sfxsvsf
kk
)(0)(5 规定 Ef
的路程。到为 1),(?kkkkk ssxsv
211
最短路问题的解 （列表）
第 4阶段,)(
554 sfv
E
4x
4s
2
1
D
D
)( 44 sf4x
ED?1
ED?2
第 3阶段,)( 443 sfv
1D 2D
3
2
1
C
C
C
31?
3x
3s
)( 33 sf3x
44?
36? 43?
33? 43?
4
7
6
11 DC?
22 DC?
13 DC?
3
4
3
4
212
第 2阶段：
)( 332 sfv
321 CCC
3
2
1
B
B
B2x
2s )( 22 sf
2x
47? 74? 66?
43? 72? 64?
44? 71? 65?
11
7
8
2111 CBCB 或
12 CB?
2313 CBCB 或第 1阶段：
)( 221 sfv
321 BBB
)( 11 sf1x1x
1s
A 112? 74? 83? 11 32 BABA 或最优策略,2BA? 1C? 1D? E?
3BA? 1C? 1D? E?
3BA? 2C? 2D? E?
路长：
11)(1 Af
213
二、应用根据问题的特点，确定：阶段、状态变量、决策变量、
状态转移方程、目标函数递推公式。
例 （例 1.7） （ 生产存储问题 ）用动态规划方法求解。
解 假设与例 1.7同
4
3
2
1
76
80
72
70
60
120
70
60
月份 单位成本 ic (元 ) 销售量 id (件 )
按月份分 4个阶段；；决策变量月产量为第 )(kx k
（状态变量）；
月初库存量为第 ks k
);(1 状态转移方程kkkk dxss
);(2),( 报酬函数kkkkkk sxcxsv
（ 1）,建模模型：
) },(2{m in)( 1 kkkkkkkXxkk dxsfsxcsf
kk
1,2,3,4?k
0)( 55 sf 1?ks
（ 2）,求解
K=4,)}(276{m i n)( 554444
44
sfsxsf Xx
}276{m in 44
44
sxXx
的表达式。欲求 )(),( kkkkk sfsxx
:4X求
44455,0 dsxss由
}60|{ 4444 sxxX得故得,44 60 sx
)( 44 sf? 47445 60 s 44 276 sx
关于 x4的线性函数欲求 Xk,可利用 状态转移方程 和 约束条件,求出 xk满足的等式或不等式。
K=3:
)}(280{m in)( 33343333
33
dxsfsxsf Xx
)]}(74456 0[280{m in 33333
33
dxssxXx
4s
}134 40726{m in 33
33
sxXx
求 X3,?)(?)( 333 sxs即求
,3334 dxss
50)1207060(10030 4 s
333 1 7 01 2 0 sxs
,1 0 00 3 x?又
}1 7 0,1 0 0m i n {}1 2 0,0m a x { 333 sxs
70)7060(1 0 020 3 s?又
,12012050 3 s 170170100 3 s
100120 33 xs
X3的增函数从而得,33 1 2 0 sx
)( 33 sf? 1 3 4 4 0726 33 sx 37814160 s
故 }100120|{ 3333 xsxX
K=2,)}(272{m i n)(
22232222 22 dxsfsxsf Xx
1 0 02x
222 7619020)( ssf
}1 9 6 2 0766{m in 22
22
sxXx
}10070|{ 2222 xsxX可得
K=1,)}(270{m i n)( 11121111
11
dxsfsxsf Xx
}2 35 80746{m in 11
22
sxXx
求 X1:
由 0,401000,1121112 sdsdxss
得 10 060 1 x
}10060|{ 112 xxX
,1001x
)( 11 sf? 2 35 80071 006 22980?
,01s 1 0 01x
1112 dxss,40? 0 02x
,702223 dxss 50120 33 s
,03334 dxss 6060 44 sx
总费用,)(22980)( 11 元 sf
利用状态转移方程及 的表达式，按 k=1,2,3,4的顺序求最优策略。 (d1==60,d2=70,d3=120,d4=60)
)( kk sx?
（ 3）灵敏度分析如,2月份的库存损失了 20件（即 s2=20），则
2— 4 月份的最优生产计划如下：
)(100 222 无关与 sxx
,5070100202223 dxss
,70120 33 sx
,03334 dxss 6060 44 sx
费用增加：
)70781 4 1 6 0()50781 4 1 6 0()70()50( 33 ff
)(15 60 元?
又如,2月份出现 10件废品（ x2=90,s3=60），类似可求 3,4月份的最优生产计划。
注,
(1)当目标函数是线性函数或二次函数等简单函数时，
容易求出 的表达式，否则可求数值解。)( kk sf?
（ 2）当 取少数离散值时，可列表计算。如上例中还要求每 10个产品为一批地生产，则,
的可能取值为 0,10,20,…,100这些离散值。
kx
kx ks
＃
2,一维资源分配问题
a — 资源总量
— 第 k个使用者的效益)( kk xg
数学规划模型：
njx
axxxts
xgz
j
n
n
k
kk
,,2,1,0
.
)(m a x
21
1
总效益化为动态规划模型：
xk— 分配给第 k个使用者的资源量关键 求：阶段，状态变量，决策变量，状态转移方程。
阶段 — 将资源分配给一个使用者视为一个阶段，
决策变量,xk— 分配给第 k个使用者的资源量状态变量,sk— 前 k-1个使用者分配后的 剩余量即 nn
n
ki
ik xsasxs
,,1
状态转移方程,kkk xss 1 )(
1
k
n
ki
i
n
ki
i xxx
1x 2x kx 1?kx nx
使用者,1 2 k 1?k n
资源量：
1?ks
ks
as?1
状态变量：
允许决策集合,}0|{ kkkk sxxX
报酬函数,)(),( kkkkk xgxsv?
动态规划模型：
1,2,,1,)()(m a x)( 10 nkxsfxgsf kkkkksxkk
kk
)(m a x)( 0 nnsxnn xgsf
nn
)( nn sg?
1?ks
效益函数一般是增函数注,若原目标函数为连乘积
n
k
kk xgopt
1
)(
则动态规划目标函数为：
)()()( 11
kkkkXxkk sfxgoptsf
kk
例 （ P.41）
如何分配 2万元补加研制费，
使三种新产品 都不成功 的概率最小。有关数据如表。
30.020.015.02
50.040.020.01
80.060.040.00
CBA
产品研制费不 成 功 概 率解 建立非线性规划模型种产品的补加费分配给第 kx k
种新产品不成功的概率万元后，第分得 kxxp kkk )(
假定研制是 独立 进行的，即有
P(A,B,C均不成功 )
= P(A不成功 ) ·P(A不成功 ) ·P(A不成功 )
则得非线性规划模型：
且为整数0,,
2.
)()()(m i n
321
321
332211
xxx
xxxts
xpxpxpz
转化为动态规划模型：
状态变量：
种新产品的补加费，至第为分配给第 3
)3,2,1(
3
k
kxs
ki
ik
状态转移方程,2),2,1( 11 skxss kkk
则 1,2),()({m in)( 1 kxsfxpsf kkkkkXxkk
kk
)(m in)( 3333
33
xpsf Xx )( 33 sp?
允许决策集合,}0|{ 且为整数kkkk sxxX
))(( 的减函数是 kkk xxp?
kk sx0
330 sx
1?ks
