第五章 动态规划
动态规划是运筹学的一个重要分支，它
是从 1951年开始，由美国人贝尔曼 (R.Belman)
为首的一个学派发展起来的。动态规划在经
济、管理、军事、工程技术等方面都有广泛
应用。
动态规划是解决 多阶段决策过程 的最
优化问题的一种方法。
所谓 多阶段决策过程 是指这样一类决策过
程：它是把一个复杂问题按时间（或空间）分
成若干个阶段，每个阶段都需要作出决策，以
便得到过程的最优结局。
由于在每个阶段采取的决策是与时间有关
的而且与前一阶段采取的决策如何 ，不但与该
阶段的经济效果有关，还影响以后各阶段的经
济效果，可见这类多阶段决策问题是一个动态
的问题。因此，处理的方法称为 动态规划方法 。
动态规划也可以处理一些本来与时间
没有关系的静态模型 ， 只要人为 地 引入 “时
间 ”因素 ， 分成时段 ， 就可以把它看作是多阶
段的动态模型，用动态规划方法去处理。
动态规划对于解决多阶段决策问题的
效果是明显的，但也有一定的 局限性 。
首先，它没有统一的处理方法，必须根
据问题的各种性质并结合一定的技巧来处
理；
另外当变量的维数增大时，总的计算量
及存储量急剧增大。由于计算机的存储量及
计算速度的限制 ，目前的计算机仍不能用动
态规划方法来解决较大规模的问题，这就是
所谓的 “维数障碍 ”。
§1 动态规划的基本概念
1.1 多阶段决策问题
在研究社会经济、经营管理和工程技术
领域内的有关问题中，有一类特殊形式的动
态决策问题 —多阶段决策问题 。 在多阶段决
策过程中，系统的动态过程可以按照时间进
程分为相互联系而又相互区别的各个阶段，
在每个阶段都要进行决策。系统在每个阶段
存在许多不同的状态，在某个时点的状态 往
往要依某种形式受到过去某些决策的影响，
而系统的当前状态和决策又会影响系统过
程今后的发展。因而在寻求多阶段决策问题
的最优解时，重要的是不能仅仅从眼前的局
部利益出发进行决策，而需要从系统所经过
的整个事件的总效应出发，有预见性地进行
动态决策，找到不同时点的最优决策及整个
过程的最优策略。
下面举例说明什么是多阶段决策问题。
例 1（最短路线问题） 在线路网络图中，从 A至 E
有一批货物需要调运。图上所标数字为各节点之间
的运输距离，为使总运费最少，必须找出一条由 A
至 E总里程最短的路线。
为了找到由 A 至 E的最短线路，可以将该问
题分为 A B C D E? ? ? ? 4个阶段，在每个阶段
都要作出决策，即在 A 点需决策下一步到 1B 还是
到 2B 或 3B ；同样，若到达第二阶段某个状态，比如
1B ，需决定走向 1C 还是 2C ；以此类推，可以看出：
各个阶段的决策不同，由 A 至 E 的路线就不同，
当从某个阶段的某个状态出发作出一个决策，则这
个状态不仅影响下一个阶段的距离，而且直接影响
后面各阶段的行进线路。所以这类问题要求在各个
阶段选择一个恰当的决策，使这些决策序列所决定
的一条路线对应的总路程最短。
例 2（带回收的资源分配问题）
某厂新购某种机床 125台。据估计，这种设
备 5年后将被其它设备所代替。此机床如在
高负荷状态下工作，年损坏率为 1/2，年利润
为 10万元；如在低负荷状态下工作，年损坏
率为 1/5，年利润为 6 万元。问应如何安排
这些机床的生产负荷，才能使 5年内获得的
利润最大？
本问题具有时间的次序性，在五年计划的每一
年都要作出关于这些机床生产负荷的决策，并且一
旦作出决策，不仅影响本年利润的多少，而且影响
到下一年初完好机床数，从而 影响以后各年的利润。
所以在每年初作出决策时，必须将当年的利润和以
后各年利润结合起来，统筹考虑。
与上面的例 1、例 2类似的多阶段决策问题还
有资源分配、生产存贮、可靠性、背包、设备更新
问题等等。
1.2 动态规划的基 本概念
1.阶段
动态规划问题通常都具有时间或空间
上的次序性，因此求解这类问题时，首先要
将问题按一定的次序划分成若干相互联系
的阶段，以便能按一定次序去求解。如例 1，
可以按空间次序划分为 A B C D E? ? ? ?4个
阶段，而例 2，按照时间次序可分成 5个阶
段。
2.状态
在多阶段决策过程中，每阶段都需要作出
决策，而决策时根据系统所处情况决定的。状
态是描述系统情况所必需的信息。如例 1 中每
阶段的出发点位置就是状态，例 2 中每年初拥
有的完好机床数是作出机床负荷安排的根据，
所以年初完好机床 数是状态。一般地，状态可
以用一个变量来描述，称为状态变量。记第 k
阶段的状态变量为 , 1 , 2 , ,kx k n?.
3.决策
多阶段决策过程的发展是用各阶段的
状态演变来描述的，阶段决策就是决策者从
本阶段某状态 出发对下一阶段状态所作出
的选择。描述决策的变量称为决策变量，当
第 k阶段的状态确定之后，可能作出的决策
要受到这一状态的影响。这就是说决策变量
ku 还是状态变量 kx 的函数，因此，又可将第
k阶段 kx 状态下的决策变量记为 ()kkux.
在实际问题中，决策变量的取值往往限
制在某一范围之内，此范围称为允许决策变
量集合，记作 ()kkDu.如例 2中取高负荷运行
的机床 数 ku 为决策变量，则 0 kkux??（ kx 是
k阶段初完好机床数）为允许决策变量集合。
4.状态转移方程
在多阶段决策过程中，如果给定了 k阶
段的状态变量 kx 和决策变量 ku ，则第 1k? 阶
段的状态变量 1kx? 也会随之而确定。也就是
说 1kx? 是 kx 和 ku 的函数，这种关系可记为
1 ( , )k k kx T x u? ?
称之为状态转移方程。
5.策略
在一个多阶段决策过程中，如果各个阶
段的决策变量 ( ) ( 1 , 2 , , )kku x k n?都已确定，
则整个过程也就完全确定。称决策序列
? ?1 1 2 2( ) , ( ) , , ( )nnu x u x u x为该过程的一个策
略。从阶段 k到阶段 n的决策序列称为子策
略， 表示成 ? ?11( ) , ( ) , , ( )k k k k n nu x u x u x??。如例
1 中，选取一线路 1 2 2A B C D E? ? ? ?就是一
个策略：
? ?1 1 2 1 2 3 2 2 4 2( ) , ( ) , ( ) , ( )u A B u B C u C D u D E? ? ? ?
由于每一阶段都有若干个可能的状态和多
种不同的决策，因而一个多阶段决策的实际问
题存在许多策略可供选择，称其中能够满足预
期目标的策略为最优策略。例 1中存在 12条不
同线路，其中 2 1 2A B C D E? ? ? ?是最短线路。
6.指标函数
用来衡量过程优劣的数量指标，称为指标
函数。在阶段 k 的 kx 状态下执行决策 ku ，不仅
带来系统状态的转移，而且也必然对目标函数
给予影响，阶段效应就是执行阶段决策时给目
标函数的影响。
多阶段决策过程关于目标函数的总效应是
各阶段的阶段效应累积形成的。常见的全过程
目标函数有以下两种形式：
（ 1）全过程的目标函数等于各阶段目标函数的
和，即 1 1 1 2 2 2( , ) ( , ) ( , )n n nR r x u r x u r x u? ? ? ?
（ 2）全过程的目标函数等于各阶段目标函数的
积，即 1 1 1 2 2 2( , ) ( , ) ( , )n n nR r x u r x u r x u? ? ? ?
指标函数的最优值，称为 最优函数值 。一般，
11()fx表示从第 1 阶段 1x 状态出发至第 n 阶段
（最后阶段）的最优指标函数， ()kkfx表示从第
k 阶段 kx 状态出发至第 n 阶段的最优指标函数
( 1 , 2 , , )kn? .
§2 动态规划的最优性原理
多阶段决策过程的特点是每个阶段都要进
行决策，具有 n个阶段的决策过程的策略是由
n 个 相继进行的阶段决策构成的决策序列。由
于前阶段的终止状态又是后一阶段的初始状态，
因此确定阶段最优决策不能只从本阶段的效应
出发，必须通盘考虑整体规划。 就是说，阶段 k
的最优决策不应只是本阶段的最优，而必须是
本阶段及其所有后续阶段的总体最优，即关于
整个后部子过程的最优决策。
对此，贝尔曼在深入研究的基础上，针对
具有无后效性的多阶段决策过程的特点，提出
了著名的多阶段决策的最优性原理 ： “整个过程
的最优策略具有这样的性质：即无论 过程 过去
的状态和决策如何，对前面的决策 所形成的状
态而言 ， 余下的诸决策必须构成最优策略 。 ”
简而 言之，最优性原理的含意就是： 最优
策略的任何一部分子策略也必须是最优的。
如例 1， 2 1 2A B C D E? ? ? ?是由 A到 E
的最短路线，我们在该路线上任取一点 1C ，
按照最优性原理 12C D E??应该是 1C 到 E的
最短路。很容易用反证法证明这一结论的正
确性，从而说明最优性原理的正确性。
按最优性原理，可以将例 1 分成
A B C D E? ? ? ?4个阶段，由后向前逐步求
出各点到 E 的最短线路，直至求出 A 至 E
的最短线路。（ 逆序法 ）
以例 1为例。（如图）
4K ? 时，出发点为 1 2 3D D D， ，，记
4 ( ) ( 1 , 2 , 3 )if D i ?为 iD到 E的最短距离； 4 ()iuD表
示从状态 iD出发采取的决策。
显然：
4 1 4 1( ) 7 , ( )f D u D E??；
4 2 4 2( ) 8 , ( )f D u D E；
4 3 4 3( ) 6 , ( )f D u D E??
3K ? 时，出发点为 1 2 3C C C， ，
? ?3 1 1 1 4 1 1 2 4 2( ) m in ( ) ( ) , ( ) ( )f C d C D f D d C D f D? ? ?
??m in 4 7 , 2 8 1 0? ? ? ?
所以 3 1 2()u C D?
? ?3 2 2 2 4 2 2 3 4 3( ) m in ( ) ( ) , ( ) ( )f C d C D f D d C D f D? ? ?
??m in 5 8 , 7 6 1 3? ? ? ?
所以 3 2 2()u C D?或 3D
? ?3 3 3 2 4 2 3 3 4 3( ) m in ( ) ( ) , ( ) ( )f C d C D f D d C D f D? ? ?
??m in 1 0 8 , 9 6 1 5? ? ? ?
所以 3 3 3()u C D?
2K ? 时，出发点为 1 2 3B B B， ，
? ?2 1 1 1 3 1 1 2 3 2( ) m in ( ) ( ) , ( ) ( )f B d B C f C d B C f C? ? ?
??m in 6 1 0 , 4 1 3 1 6? ? ? ?
所以 2 1 1()u B C?
? ?2 2 2 1 3 1 2 3 3 3( ) m in ( ) ( ) , ( ) ( )f B d B C f C d B C f C? ? ?
??m in 3 1 0 , 1 1 5 1 3? ? ? ?
所以 2 2 1()u B C?
? ?2 3 3 2 3 2 3 3 3 3( ) m in ( ) ( ) , ( ) ( )f B d B C f C d B C f C? ? ?
??m in 8 1 3 , 4 1 5 1 9? ? ? ?
所以 2 3 3()u B C?
1K ? 时，出发点只有 A
1 2 1
1 2 2 2
3 2 3
( ) ( ) 4 16
( ) m in ( ) ( ) m in 5 13 18
3 19( ) ( )
d A B f B
f A d A B f B
d A B f B
? ?? ?
??
? ? ? ? ???
?? ??
??
所以 12()u A B?
由 1 ( ) 1 8fA ?，可知从起点 A 到终点 E 的
最短距离是 18。 为了找出最短线路，再按计算
顺序反推回去，可求出最优决策序列，即由
12()u A B?， 2 2 1()u B C?， 3 1 2()u C D?， 42()u D E?
组成最优策略，也就是最短路线为：
2 1 2A B C D E? ? ? ?
从上面的例子不难看出，对于最短路线问
题，有如下的递推关系（函数方程）： ? ?
1
11
( ) m in ( , ( ) ) ( ( , ) )
( ) 0 ( , 1 , , 1 )
k k k k k k k k
nn
f x d x u x f T x u
f x k n n
?
??
? ??
? ? ? ?
?
一般情况下，多阶段决策问题存在下面的
递推关系：
? ?1
11
( ) ( , ( ) ) ( ( , ) )
( )
( ) ( , 1 , , 1 )
k k k k k k k k k
k k k
nn
f x o p t r x u x f T x u
u D u
f x C k n n
?
??
??
?
? ? ?
这里
( , ( ) )k k k kr x u x是第 k 阶段采用 ()kkux决策产
生的阶段效应；
11()nnf x C?? ?是边界条件；
“? ”大多数情况下是 “+ ”， 也可能是 “? ”。
称上述递推关系为 动态规划的基本方程 ，
这个方程 是 最优化原理的具体表达形式。
§3 建立动态规划模型的步骤
“最优化原理 ”是动态规划的核心 ， 所有动
态规划问题的递推关系都是根据这个原理建立
起来的，并且根据递推关系依次计算，最终可
求得动态规划问题的解。
一般来说，利用动态规划求解实际问题需
先建立问题的动态模型， 具体步骤 如下：
1、将问题按时间或空间次序划分成若干阶
段。有些问题不具有时空次序，也可以人为地
引进时空次序，划分阶段。
2、正确选择状态变量 kx ，这一步是形成动
态模型的关键，状态变量是动态规划模型中最
重要的参数。一般来说，状态变量应具有以下
三个特征：
（ 1）要能够用来描述决策过程的演变特征。
（ 2）要满足无 后效性。即如果某阶段状态已给定
后，则以后过程的进展不受以前各状态的影响。也
就是说，过去的历史只通过当前的状态去影响未来
的发展。
（ 3）递推性。即由 k阶段的状态变量 kx 及决策变
量 ku 可以计算出 1k? 阶段的状态 变量 1kx? .
3、确定决策变量 ku 及允许决策变量集合
()kkDu .
4、根据状态变量之间的递推关系，写出状
态转移方程： 1 ( , ( ) )k k k kx T x u x? ? .
5、建立指标函数。一般用 ( , )k k kr x u描写阶
段效应 , ()kkfx表示 kn? 阶段的最优子策略函数 .
6、建立动态规划基本方程：
? ?1
11
( ) ( , ( ) ) ( ( , ) )
( )
( ) ( , 1 , , 1 )
k k k k k k k k k
k k k
nn
f x o p t r x u x f T x u
u D u
f x C k n n
?
??
??
?
? ? ?
以上是建立动态规划模型的过程，这个过
程是正确求解动态规划的基础。
在动态规划基本方程中， ( , )k k kr x u，
1 ( , )k k kx T x u? ? 都是已知函数，最优子策略
()kkfx与 + 1 + 1()kkfx之间是递推关系，要求出
()kkfx及 ()kkux，需要先求出 + 1 + 1()kkfx，这就决
定了应用动态规划基本方程求最优策略总是逆
着阶段的顺序进行的。 由后向前逐步计算，最
终可以算出全过程的最优策略函数值及最优策
略。
另一方面，由于 1k? 阶段的状态
k + 1 ( , )kkx T x u? 是由前面的状态 kx 和决策 ku 所
形成的，在计算 + 1 + 1()kkfx时还不能具体确定 1kx?
的值。所以， 这就要求必须就 1k? 阶段的各个
可能状态计算 + 1 + 1()kkfx，因此动态规划方法不
但能求出整个问题的最优策略和最优目标值，
而且还能求出决策过程中所有可能状态的最优
策略及最优目标值。
下面就按上述步骤求解例 2.
例 2（带回收的资源分配问题） 某厂新购某种机
床 125台。据估计，这种设备 5年后将被其它
设备所代替。此机床如在高负荷状态下工作，
年损坏率为 1/2，年利润为 10万元；如在低负
荷状态下工作，年损坏率为 1/5，年利润为 6万
元。问应如何安排这些机床的生产负荷，才能
使 5年内获得的利润最大？
解： 以年为阶段， 1 , 2 , 3 , 4 , 5k ?
取 k 年初完好的机床数为状态变量 kx ，以
k年初投入高负荷运行的机床数为决策变量 ku ，
则低负荷运行机床数是 kkxu? ，于是状态转移
方程为：
1 1 / 2 4 / 5 ( ) 0 . 8 0 . 3k k k k k kx u x u x u? ? ? ? ? ?
以利润为目标函数，则 k年利润为：
1 0 6 ( ) 4 6k k k k ku x u u x? ? ? ?
记 ()kkfx为 k 年至 5 年末最大总利润，则动
态规划基本方程为：
? ?1
66
( ) m a x 4 6 ( 0 .8 0 .3 )
( ) 0 ( 5 , 4 , 3 , 2 , 1 )
k k k k k k kf x u x f x u
f x k
?? ? ? ? ??
???
以上是建立动态模型的过程，下面具体求解。
注意动态规划基本方程为： ? ?
1( ) m a x 4 6 ( 0 .8 0 .3 )
0
k k k k k k k
kk
f x u x f x u
ux
?? ? ? ?
??
所以，当 5k? 时，有 ? ?
5 5 5 5 6 6 5
55
( ) m a x 4 6 ( ) 1 0
0
f x u x f x x
ux
? ? ? ?
??
55ux?
当 4k? 时，有 ? ?
4 4 4 4 5 4 4 4
44
( ) m a x 4 6 ( 0 .8 0 .3 ) 1 5
0
f x u x f x u x
ux
? ? ? ? ?
??
44ux?
当 3k? 时，有 ? ?
3 3 3 3 4 3 3 3
33
( ) m a x 4 6 ( 0 .8 0 .3 ) 1 8
0
f x u x f x u x
ux
? ? ? ? ?
??
3 0u ?
当 2k? 时，有 ? ?
2 2 2 2 3 2 2 2
22
( ) m a x 4 6 ( 0 .8 0 .3 ) 2 0 .4
0
f x u x f x u x
ux
? ? ? ? ?
??
2 0u ?
当 1k? 时，有 ? ?
1 1 1 1 2 1 1 1
11
( ) m a x 4 6 ( 0 .8 0 .3 ) 2 2 .3 2
0
f x u x f x u x
ux
? ? ? ? ?
??
1 0u ?
所以利润为： 2 2 .3 2 1 2 5 2 7 9 0??（万元）
再按与计算过程相反的顺序推回去，可得最优计划
如下表所示：
年份 完好机床数 高负荷机床数 低负荷机床数
第一年 125 0 125
第二年 100 0 100
第三年 80 0 80
第四年 64 64 0
第五年 32 32 0
|
|
