第五节 动态规划
动态规划是运筹学的一个分支，它是解决多
阶段决策过程最优化的一种数学方法．大约产生
于 50年代,1951年美国数学家贝尔曼
(R,Bellman)等人，根据一类多阶段 决策问题的
特点，把多阶段决策问题变换为一系列互相联系
单阶段问题，然后逐个加以解决。与此同时，他
提出了解决这类问题的, 最优性原理,,研究了
许多实际问题，从而创建了解决最优化问题的一
种新的方法 —— 动态规划．他的名著, 动态规划,
于 1957年出版，该书是动态规划的第一本著作．
动态规划模型的分类，根据多阶段决策过程的时间参量是离散的还是连续
的变量；过程分为离散决策过程和连续决策过程．根据决策过程的演变是确定
性的还是随机性的，过程又可分为确定性决策过程和随机性决策过程．组合起
来就有离散确定性、离散随机性、连续确定性、连续随机性四种决策过程模
型．本部分主要研究离散决策过程，介绍动态规划的基本概念、理论和方法，
并通过几个典型的问题来说明它的应用，这些都是整个动态规划的基本内容．
离散
决策过程
连续
决策过程
根据多阶段决策过程的
时间参量
根据决策过程的
演变
确定性
决策过程
随机性
决策过程
离散确定性
决策过程
离散确定性
决策过程
连续确定性
决策过程 连续随机性 决策过程
引例 — — 有一批军用物资需要从 A 地调运到 E地，如下图所示，请求出一
条从 A 到 E 的一条线路，使总的运输距离最短。图中线条上的数字为距离。
A EB2 C2
B1
B3
C1
C3
D1
D2
4
3
5
8
10
12
14
18
1012
9
4
5
8
9
7
7
3
4
11
1 多阶段决策过程及实例
B 地 C 地 D 地 E 地A 地
在生产和科学实验中，有一类活动的过程，由于它的特殊性，可将过程分为若干个
互相联系的阶段，在它的每一个阶段都需要作出决策，才能使整个过程达到最好的活动
效果．因此，各个阶段决策的选取不是任意确定的，它依赖于当前面临的状态，又影响
到以后的决策。
A EB2 C2
B1
B3
C1
C3
D1
D2
4
3
5
8
10
12
14
18
1012
9
4
5
8
9
7
7
3
4
11
如果一个问题的过程可以化分为若干个互相联系的阶段，而且每个阶段都需要作出
决策，而且当每个阶段的决策都确定之后，整个问题也就确定了，那么，这个问题就叫
做一个多阶段决策问题。动态规划就是解决这类问题的一个重要的数学方法。
如上图所示的线路网络，求 A 到 E 点的最短路线问题是动态规划中一个较为直
观的典型例子．现通过讨论它的解法，来说明动态规划方法的基本思想，并阐述它的
基本概念。．
A EB2 C2
B1
B3
C1
C3
D1
D2
4
3
5
8
10
12
14
18
1012
9
4
5
8
9
7
7
3
4
11
如上图可知，从 A点到 E点可以分为 4个阶段．从 A到 B为第一阶段，从 B到 C为第二
阶段 … 从 D到 E为第四阶段
在第一阶段,A为起点，终点有 B1,B2,B3三个，因而这时走的路线有三个选择，
分别是走 B1,B2,B3。
如果选择走 B2的决策，则 B2就是第 一阶段在我们决策之下的结果．它既是第一阶段
路线的终点，又是第二阶段路线的始点。
在第二阶段，再从 B2点出发，对应于 B2点就有一个可供选择的终点集合 {C1,C2，
C3}；
如果选择由 B2走至 C2为第二阶段的决策，则 C2 就是第二阶段的终点，同时又是第三
阶段的始点．
同理递推下去，可看到：各个阶段的决策不同，调运的路线就不同．很明显，当某一
阶段的始点给定时，它直接影响着后面各阶段的行进路线和整个路线的长短，而后面各阶
段的路线的发展不受这点以前各阶段路线的影响．故此问题的要求是：在各个阶段选取一
A EB2 C2
B1
B3
C1
C3
D1
D2
4
3
5
8
10
12
14
18
1012
9
4
5
8
9
7
7
3
4
11
如何解决这个问题呢?
可以采取穷举法．即把由 A到 E所有可能的每一条路线的距 离都算出来，然后互相比
较找出最短者，相应地得出了最短路线．这样，由 A到 E一共有 3 X 3 X 2 X 1＝ 18条不同的
路线，比较这 18条不同的路线的距离值，才找出最短路线。
显然，这样作计算是相当繁的．如果当段数很多，各段的不同选择也很多时，这种解
法的计算将变得极其繁杂，甚至在电子计算机上计算都是不现实的．
A EB2 C2
B1
B3
C1
C3
D1
D2
4
3
5
8
10
12
14
18
1012
9
4
5
8
9
7
7
3
4
11
A EB2 C2
B1
B3
C1
C3
D1
D2
4
3
5
8
10
12
14
18
1012
9
4
5
8
9
7
7
3
4
11
12
0
4
3
5
14
14
16
17
19
2 用动态规划的方法来求解以上最短路问题
B 地 C 地 D 地 E 地A 地
（ 1）
顺序
解法
求解得到的结果内容丰富
（ 2）
逆序
解法
A EB2 C2
B1
B3
C1
C3
D1
D2
4
3
5
8
10
12
14
18
1012
9
4
5
8
9
7
7
3
4
11 0
B 地 C 地 D 地 E 地A 地
3
4
7
11
10
15
18
19
19
3 动态规划的基本概念
(1)阶段
把所给问题的过程，恰当地分为若干个相互联系的阶段，以便能按一定的次序去
求解．
阶段的划分，一般是根据时间和空间的 自然特征来划分。
描述阶段的变量称为阶段变量，常用 k 表示．如例 1可分为 4个阶段来求解,k＝ 1,2、
3,4。
A EB2 C2
B1
B3
C1
C3
D1
D2
4
3
5
8
1012
1418
1012
9
4
5
8
9
7
7
3
4
11
(2)状态
状态表示每个阶段开始所处的自然状
况或客观条件，它描述了研究问题过程
的状况，又称不可控因素．在例 1中，状
态就是某阶段的出发位置．它既是该阶
段某支路的起点，又是前一阶段某支路
的终点．通常一个阶段有若于个状态，
第一阶段有一个状态就是点 A,第二阶段
有两个状态，即点集合 {B1,B2},第 k
阶段的状态就是第 k是阶段所有始点的集
合．,
A EB2 C2
B1
B3
C1
C3
D1
D2
4
3
5
8
1012
1418
1012
9
4
5
8
9
7
7
3
4
11
3 动态规划的基本概念
描述过程状态的变量称为状态变量。
它可用一个数、一组数或一个向量 (多维
情形 )来描述．常用 xk 表示第受阶段的
状态变量．如在例 1中第三阶段有 3 个
状态，则状态变量 x3 可取 3个值，即
x3=c1,c2,c3。
可达状态集合
某个阶段的所有的状态所构成的集合，
称为可达状态集合。例如，第三阶段的所有
状态为 c1,c2,c3,则第三阶段的可达状态集
合成为点集合 { c1,c2,c3} 。 记为
x3={ c1,c2,c3 }。
A EB2 C2
B1
B3
C1
C3
D1
D2
4
3
5
8
1012
1418
1012
9
4
5
8
9
7
7
3
4
11
3 动态规划的基本概念
状态的基本特性 —— 无后效性（ 否则就不能成为动态规划里所讲的状态）
A EB2 C2
B1
B3
C1
C3
D1
D2
4
3
5
8
1012
1418
1012
9
4
5
8
9
7
7
3
4
11
如果某阶段状态给定后，则在这阶
段以后过程的发展不受这阶段以前各段
状态的影响．换句活说，过程的过去历
史只能通过当前的状态去影响它未来的
发展，当前的状态是以往历史的一个总
结．这个性质称为无后效性 (即马尔科
夫性 )．
前效性
相反，如果状态仅仅描述过程的
具体特征，并不满足无后效性的要求。
应适当地改变状态的规定方法，以达
到能使它满足无后效性的要求。才能
成为动态规划里所讲的状态。
例如，研究物体 (把它
看作一个质点 )受外力作用
后其空间运动的轨迹问
题．从描述轨迹这点着眼，
可以只选坐标位置 (xk,yk)
作为过程的状态，但这样不
能满足无后效性，因为即使
知道了外力的大小和方向，
仍无法确定物体受力后的运
动方向 和轨迹。
不具有后效性的例子
但是如果把位置 (xk，
yk)和速度 (vxk,vvk)都
作为过程的状态变量，就
可以确定物体运动下一步
的方向和轨迹，实现无后
效性的要求．
(3)决策
决策表示当过程处于某一阶段的某个状态时，可以作出不同
的决定 (或选择 )，从而确定下一阶段的状态，这种决定称为决策 。
A EB2 C2
B1
B3
C1
C3
D1
D2
4
3
5
8
1012
14
18
1012
9
4
5
8
9
7
7
3
4
11
3 动态规划的基本概念
决策变量 —— uk ( xk )
描述决策的变量，称为决策变量．它可用一个数、一组数或
一个向量来描述．
uk ( xk )
表示第 k 阶段当状态处于 xk 时的决策变量．它是状态变量的函数．
A EB2 C2
B1
B3
C1
C3
D1
D2
4
3
5
8
1012
1418
1012
9
4
5
8
9
7
7
3
4
11
3 动态规划的基本概念
允许决策 集合 —— Dk(xk)
在实际问题中，决策变量的取值往往限制在某一范围之内，此范围称为 允许决策
集合,
A EB2 C2
B1
B3
C1
C3
D1
D2
4
3
5
8
1012
1418
1012
9
4
5
8
9
7
7
3
4
11
Dk(xk)
表示第 k 阶段从状态 xk 出发的允许决策集合，显然 有 uk(xk)∈ Dk(xk)．
从状态 B1出发，就可作出三种不同的决策，其允许决策集合是 D2(B1)＝ {C1,C2，
C3},如果选取的点为 C2,则 C2是状态 Bl在决策 u2(B1) 作用下的一个新的状态，记作
u2(B1) ＝ C2．
3 动态规划的基本概念
A EB2 C2
B1
B3
C1
C3
D1
D2
4
3
5
8
1012
1418
1012
9
4
5
8
9
7
7
3
4
11
K 子过程策略
由过程的第 k阶段开始直到终止状态为止的过程，称为问题的后部子过程
(或称为 k子过程 )．
全过程的一个策略
当 k=1时，此决策函数序列称为全过程的一个策略，简称策略，记为 p1,n(x1),
3 动态规划的基本概念
3 动态规划的基本概念
允许策略集合
在实际问题中，可供选择的策略有一定的范围，此范围称为
允许策略集合，用 P表示,从允许决策集合中就能找出达到最优效
果的策略，它被称为最优策略。
A EB2 C2
B1
B3
C1
C3
D1
D2
4
3
5
8
1012
1418
1012
9
4
5
8
9
7
7
3
4
11
3 动态规划的基本概念
指标函数
使用不同的策略，其效果是不一样的，把衡量过程效果的好
坏的函数叫做指标函数。
Vkn=Vkn(xk,uk,xk+1,uk +1,…,xk+1) (k=1,2,…,n)
V是 value的缩写
A EB2 C2
B1
B3
C1
C3
D1
D2
4
3
5
8
1012
1418
1012
9
4
5
8
9
7
7
3
4
11
在这个函数里面，各个状态的取值是变化的不定的。
3 动态规划的基本概念
最优指标函数
对于不同的状态 xk,指标函数 Vkn有不同的最优值，这个最优
值可以表示为 xk的函数，称为最优指标函数，记为 f k ( x k )
A EB2 C2
B1
B3
C1
C3
D1
D2
4
3
5
8
1012
1418
1012
9
4
5
8
9
7
7
3
4
11
例如 f 2 ( B 2 )表示从第二阶段中的 B2状态到终点 E的 最短 距离。
例如 f 4 ( D 1 )表示从第四阶段中的 D 1 状态到终点 E的 最短 距离。
0 1 2 3
1 0 3 7 11
2 0 4 8 12
3 0 5 7 9
导弹数
战场
效益
战场 1 战场 2 战场 3
将问题分为三个阶段，第三阶段给战场 3分配导弹，第二阶段给战场 2和战场 3
分配导弹。第一阶段给战场 1,2,3分配导弹
第三阶段给战场 3分配导弹
第二阶段给战场 2和战场 3分配导弹
第一阶段给战场 1,2,3分配导弹
4 动态规划解
决问题的 一般
步骤
(1)首先确定阶
段变量 K,
K=1,2,3.
(2)确定各阶段的
状态 xk
战场 2 战场 3
0 1 2 3
1 0 3 7 11
2 0 4 8 12
3 0 5 7 9
导弹数
战场
效益
战场 1
(1)首先确定阶段变量 K, K=1,2,3.
(2)确定各阶段的状态 xk
(3)确定各阶段允许状态集合, X3可以取值多少呢？
X3表示分配给第三阶段（也就是第 3战场）的导弹数量。 x2表示分配给第二阶段（也就是第
2,3战场）的导弹数量。 X1表示分配给第一阶段（也就是第 1,2,.3战场）的导弹数量。
X3={0,1,2,3}
要满足无后效性,x3,x2,x1
(4)确定决策变量, 决策变量 uk(xk)表示的是当第 K阶段所处的状态为 xk时所作的决策。确定决策变量
(5)确定状态转移关系,
4 动态规划解决问题的 一般 步骤
略过
0 1 2 3
1 0 3 7 11
2 0 4 8 12
3 0 5 7 9
导弹数
战场
效益
战场 2 战场 3战场 1(1)首先确定阶段变量 K,
(2)首先各阶段的状态 xk
(3)确定各阶段允许状态集合,
(4)确定决策变量 uk(xk).
(5)确定状态转移关系,
x3
X3=0,1,2,3
u3(X3)
X2
X2=0,1,2,3
u2(X2)x
2-u2(x2)=x3
0 1 2 3
1 0 3 7 11
2 0 4 8 12
3 0 5 7 9
导弹数
战场
效益
(1)首先确定阶段变量 K,
(2)首先各阶段的状态 xk
(3)确定各阶段允许状态集合,
(4)确定决策变量 uk(xk).
(5)确定状态转移关系,
战场 2 战场 3战场 1
x3X2
X1
X1=0,1,2,3
u1(X1)x1-u1(x1)=x2
0 1 2 3
1 0 3 7 11
2 0 4 8 12
3 0 5 7 9
导弹数
战场
效益
(1)首先确定阶段变量 K,
(2)首先各阶段的状态 xk
(3)确定各阶段允许状态集合,
(4)确定决策变量 uk(xk).
(5)确定状态转移关系,
战场 2 战场 3战场 1
x3X2
X1
X1=0,1,2,3
u1(X1)
x1-u1(x1)=x2
xk+1 = xk-uk(xk)
X4=0
0 1 2 3
1 0 3 7 11
2 0 4 8 12
3 0 5 7 9
导弹数
战场
效益
战场 2 战场 3战场 1
x3
X3=0,1,2,3
u3(X3)
u3(0)=0 u3(1)=1
f3(0)=0 f3(1)=5
u3(2)=2
f3(2)=7
u3(3)=3
f3(3)=9
xk+1 = xk-uk(xk)
x2
X2=0,1,2,3
u2(X2)
设 uk(xk)为第 K个阶段所采取的决策
变量，也就是分配给第 K个战场的导弹数
量。
设 g(uk(xk) ) 为分配给第 K
个战场 uk(xk)的导弹所产生的效
益 。
设 f (x k) 为第 K阶段状
态为 (x k时，第 K阶段到最后
阶段所得到的最优效益 。
1）实际求解
0 1 2 3
1 0 3 7 11
2 0 4 8 12
3 0 5 7 9
导弹数
战场
效益
战场 2 战场 3战场 1
x3
X3=0,1,2,3
u3(X3)
u3(0)=0 u3(1)=1
f3(0)=0 f3(1)=5
u3(2)=2
f3(2)=7
u3(3)=3
f3(3)=9
xk+1 = xk-uk(xk)
x2
X2=0,1,2,3
f2(0)= g(u2(0) ) + f3(0) =0
f2(1)= g(u2(0) )+ f3(1) =5
g(u2(1) ) + f3(0) =4
max =5
f2(2)=
g(u2(0) ) + f3(2) =7
g(u2(1) ) + f3(1) =9
g(u2(2) ) + f3(0) =8
=9max
f2(3)=
g(u2(0) ) + f3(3) =9
g(u2(1) ) + f3(2)=11
g(u2(2) ) + f3(1) =13
g(u2(3) ) + f3(0) =12
max =13
u2(X2)
0 1 2 3
1 0 3 7 11
2 0 4 8 12
3 0 5 7 9
导弹数
战场
效益
战场 2 战场 3战场 1
x3
X3=0,1,2,3
u3(X3)
u3(0)=0 u3(1)=1
f3(0)=0 f3(1)=5
u3(2)=2
f3(2)=7
u3(3)=3
f3(3)=9
xk+1 = xk-uk(xk)
x2
X2=0,1,2,3
f2(0)= g(u2(0) ) + f3(0) =0
f2(1)= g(u2(0) )+ f3(1) =5
g(u2(1) ) + f3(0) =4
max =5
f2(2)=
g(u2(0) ) + f3(2) =7
g(u2(1) ) + f3(1) =9
g(u2(2) ) + f3(0) =8
=9max
f2(3)=
g(u2(0) ) + f3(3) =9
g(u2(1) ) + f3(2)=11
g(u2(2) ) + f3(1) =13
g(u2(3) ) + f3(0) =12
max =13
u2(X2)
0 1 2 3
1 0 3 7 11
2 0 4 8 12
3 0 5 7 9
导弹数
战场
效益
战场 2 战场 3战场 1
x3
X3=0,1,2,3
u3(X3)
u3(0)=0 u3(1)=1
f3(0)=0 f3(1)=5
u3(2)=2
f3(2)=7
u3(3)=3
f3(3)=9
x2
X2=0,1,2,3
xk+1 = xk-uk(xk)
f2(0)= g(u2(0) ) + f3(0) = 0
f2(1)= g(u2(0) ) + f3(1) =5
f2(2)= g(u2(1) ) + f3(1) =9
f2(3)= g(u2(2) ) + f3(1) =13
u2(0)f2(0) = 0 决策是, u3(0)
f2(1) = 5 u2(0)决策是, u3(1)
f2(2) = 9 u2(1)决策是, u3(1)
f2(3) = 13 u2(2)决策是, u3(1)
u2(X2)
0 1 2 3
1 0 3 7 11
2 0 4 8 12
3 0 5 7 9
导弹数
战场
效益
xk+1 = xk-uk(xk) 战场 2 战场 3战场 1
x3
X3=0,1,2,3
x2
X2=0,1,2,3
f2(0) u2(0)= 0 决策是, u3(0)
f2(1) = 5 u2(0)决策是, u3(1)
f2(2) = 9 u2(1)决策是, u3(1)
f2(3) = 13 u2(2)决策是, u3(1)
x1
X1=0,1,2,3
用不用再求 f1(0),f1 (1),f1 (2)了？
f1(3)=
g(u1(0) ) + f2 (3) = 13
g(u1(1) ) + f2 (2) = 12
g(u1(2) ) + f2 (1) = 12
g(u1(3) ) + f2 (0) = 11
max = 13
0 1 2 3
1 0 3 7 11
2 0 4 8 12
3 0 5 7 9
导弹数
战场
效益
xk+1 = xk-uk(xk) 战场 2 战场 3战场 1
x3
X3=0,1,2,3
x2
X2=0,1,2,3
f2(0) u2(0)= 0 决策是, u3(0)
f2(1) = 5 u2(0)决策是, u3(1)
f2(2) = 9 u2(1)决策是, u3(1)
f2(3) = 9 u2(2)决策是, u3(1)
x1
X1=0,1,2,3
f1(3)=
g(u1(0) ) + f2 (3) = 13
g(u1(1) ) + f2 (2) = 12
g(u1(2) ) + f2 (1) = 12
g(u1(3) ) + f2 (0) = 11
max = 13
0 1 2 3
1 0 3 7 11
2 0 4 8 12
3 0 5 7 9
导弹数
战场
效益
xk+1 = xk-uk(xk) 战场 2 战场 3战场 1
x3
X3=0,1,2,3
x2
X2=0,1,2,3
f2(0) u2(0)= 0 决策是, u3(0)
f2(1) = 5 u2(0)决策是, u3(1)
f2(2) = 9 u2(1)决策是, u3(1)
f2(3) = 9 u2(2)决策是, u3(1)
x1
X1=0,1,2,3
f1(3)=g(u1(0) ) + f2 (3) = 13
f1(3) = 13 u1(0)决策是, u2(2)
,u3(1)
动态规划的方法，在工程技术、企业管理、工农业生产及军事
等部门中都有广泛的应用，并且获得了显著的效果．在企业管理方
面，动态规划可以用来解决最优路径问题、资源分配问题、生产调
度问题、库存问题、装载问题、排序问题、设备更新问题、生产过
程最优控制问题等等，所以它是现代企业管理中的一种重要的决策
方法．许多问题用动态规划的方法去处理，常比线性规划或非线性
规划更有成效．特别对于离散性的问题，由于解析数学无法施展其
术，而动态规划的方法就成为非常有用的工具．应指出，动态规划
是求解某类问题的一种方法，是考察问题的一种途径，而不是一种
特殊算法 (如线性规划是一种算法 )．因而，它不象线性规划那样有
一个标准的数学表达式和明确定义的一组规则，而必须对具体问题
进行具体分析处理．因此，读者在学习时，除了要对基本概念和方
法正确理解外，应以丰富的想象力去建立模型，用创造性的技巧去
求解．
小 节
动态规划是运筹学的一个分支，它是解决多
阶段决策过程最优化的一种数学方法．大约产生
于 50年代,1951年美国数学家贝尔曼
(R,Bellman)等人，根据一类多阶段 决策问题的
特点，把多阶段决策问题变换为一系列互相联系
单阶段问题，然后逐个加以解决。与此同时，他
提出了解决这类问题的, 最优性原理,,研究了
许多实际问题，从而创建了解决最优化问题的一
种新的方法 —— 动态规划．他的名著, 动态规划,
于 1957年出版，该书是动态规划的第一本著作．
动态规划模型的分类，根据多阶段决策过程的时间参量是离散的还是连续
的变量；过程分为离散决策过程和连续决策过程．根据决策过程的演变是确定
性的还是随机性的，过程又可分为确定性决策过程和随机性决策过程．组合起
来就有离散确定性、离散随机性、连续确定性、连续随机性四种决策过程模
型．本部分主要研究离散决策过程，介绍动态规划的基本概念、理论和方法，
并通过几个典型的问题来说明它的应用，这些都是整个动态规划的基本内容．
离散
决策过程
连续
决策过程
根据多阶段决策过程的
时间参量
根据决策过程的
演变
确定性
决策过程
随机性
决策过程
离散确定性
决策过程
离散确定性
决策过程
连续确定性
决策过程 连续随机性 决策过程
引例 — — 有一批军用物资需要从 A 地调运到 E地，如下图所示，请求出一
条从 A 到 E 的一条线路，使总的运输距离最短。图中线条上的数字为距离。
A EB2 C2
B1
B3
C1
C3
D1
D2
4
3
5
8
10
12
14
18
1012
9
4
5
8
9
7
7
3
4
11
1 多阶段决策过程及实例
B 地 C 地 D 地 E 地A 地
在生产和科学实验中，有一类活动的过程，由于它的特殊性，可将过程分为若干个
互相联系的阶段，在它的每一个阶段都需要作出决策，才能使整个过程达到最好的活动
效果．因此，各个阶段决策的选取不是任意确定的，它依赖于当前面临的状态，又影响
到以后的决策。
A EB2 C2
B1
B3
C1
C3
D1
D2
4
3
5
8
10
12
14
18
1012
9
4
5
8
9
7
7
3
4
11
如果一个问题的过程可以化分为若干个互相联系的阶段，而且每个阶段都需要作出
决策，而且当每个阶段的决策都确定之后，整个问题也就确定了，那么，这个问题就叫
做一个多阶段决策问题。动态规划就是解决这类问题的一个重要的数学方法。
如上图所示的线路网络，求 A 到 E 点的最短路线问题是动态规划中一个较为直
观的典型例子．现通过讨论它的解法，来说明动态规划方法的基本思想，并阐述它的
基本概念。．
A EB2 C2
B1
B3
C1
C3
D1
D2
4
3
5
8
10
12
14
18
1012
9
4
5
8
9
7
7
3
4
11
如上图可知，从 A点到 E点可以分为 4个阶段．从 A到 B为第一阶段，从 B到 C为第二
阶段 … 从 D到 E为第四阶段
在第一阶段,A为起点，终点有 B1,B2,B3三个，因而这时走的路线有三个选择，
分别是走 B1,B2,B3。
如果选择走 B2的决策，则 B2就是第 一阶段在我们决策之下的结果．它既是第一阶段
路线的终点，又是第二阶段路线的始点。
在第二阶段，再从 B2点出发，对应于 B2点就有一个可供选择的终点集合 {C1,C2，
C3}；
如果选择由 B2走至 C2为第二阶段的决策，则 C2 就是第二阶段的终点，同时又是第三
阶段的始点．
同理递推下去，可看到：各个阶段的决策不同，调运的路线就不同．很明显，当某一
阶段的始点给定时，它直接影响着后面各阶段的行进路线和整个路线的长短，而后面各阶
段的路线的发展不受这点以前各阶段路线的影响．故此问题的要求是：在各个阶段选取一
A EB2 C2
B1
B3
C1
C3
D1
D2
4
3
5
8
10
12
14
18
1012
9
4
5
8
9
7
7
3
4
11
如何解决这个问题呢?
可以采取穷举法．即把由 A到 E所有可能的每一条路线的距 离都算出来，然后互相比
较找出最短者，相应地得出了最短路线．这样，由 A到 E一共有 3 X 3 X 2 X 1＝ 18条不同的
路线，比较这 18条不同的路线的距离值，才找出最短路线。
显然，这样作计算是相当繁的．如果当段数很多，各段的不同选择也很多时，这种解
法的计算将变得极其繁杂，甚至在电子计算机上计算都是不现实的．
A EB2 C2
B1
B3
C1
C3
D1
D2
4
3
5
8
10
12
14
18
1012
9
4
5
8
9
7
7
3
4
11
A EB2 C2
B1
B3
C1
C3
D1
D2
4
3
5
8
10
12
14
18
1012
9
4
5
8
9
7
7
3
4
11
12
0
4
3
5
14
14
16
17
19
2 用动态规划的方法来求解以上最短路问题
B 地 C 地 D 地 E 地A 地
（ 1）
顺序
解法
求解得到的结果内容丰富
（ 2）
逆序
解法
A EB2 C2
B1
B3
C1
C3
D1
D2
4
3
5
8
10
12
14
18
1012
9
4
5
8
9
7
7
3
4
11 0
B 地 C 地 D 地 E 地A 地
3
4
7
11
10
15
18
19
19
3 动态规划的基本概念
(1)阶段
把所给问题的过程，恰当地分为若干个相互联系的阶段，以便能按一定的次序去
求解．
阶段的划分，一般是根据时间和空间的 自然特征来划分。
描述阶段的变量称为阶段变量，常用 k 表示．如例 1可分为 4个阶段来求解,k＝ 1,2、
3,4。
A EB2 C2
B1
B3
C1
C3
D1
D2
4
3
5
8
1012
1418
1012
9
4
5
8
9
7
7
3
4
11
(2)状态
状态表示每个阶段开始所处的自然状
况或客观条件，它描述了研究问题过程
的状况，又称不可控因素．在例 1中，状
态就是某阶段的出发位置．它既是该阶
段某支路的起点，又是前一阶段某支路
的终点．通常一个阶段有若于个状态，
第一阶段有一个状态就是点 A,第二阶段
有两个状态，即点集合 {B1,B2},第 k
阶段的状态就是第 k是阶段所有始点的集
合．,
A EB2 C2
B1
B3
C1
C3
D1
D2
4
3
5
8
1012
1418
1012
9
4
5
8
9
7
7
3
4
11
3 动态规划的基本概念
描述过程状态的变量称为状态变量。
它可用一个数、一组数或一个向量 (多维
情形 )来描述．常用 xk 表示第受阶段的
状态变量．如在例 1中第三阶段有 3 个
状态，则状态变量 x3 可取 3个值，即
x3=c1,c2,c3。
可达状态集合
某个阶段的所有的状态所构成的集合，
称为可达状态集合。例如，第三阶段的所有
状态为 c1,c2,c3,则第三阶段的可达状态集
合成为点集合 { c1,c2,c3} 。 记为
x3={ c1,c2,c3 }。
A EB2 C2
B1
B3
C1
C3
D1
D2
4
3
5
8
1012
1418
1012
9
4
5
8
9
7
7
3
4
11
3 动态规划的基本概念
状态的基本特性 —— 无后效性（ 否则就不能成为动态规划里所讲的状态）
A EB2 C2
B1
B3
C1
C3
D1
D2
4
3
5
8
1012
1418
1012
9
4
5
8
9
7
7
3
4
11
如果某阶段状态给定后，则在这阶
段以后过程的发展不受这阶段以前各段
状态的影响．换句活说，过程的过去历
史只能通过当前的状态去影响它未来的
发展，当前的状态是以往历史的一个总
结．这个性质称为无后效性 (即马尔科
夫性 )．
前效性
相反，如果状态仅仅描述过程的
具体特征，并不满足无后效性的要求。
应适当地改变状态的规定方法，以达
到能使它满足无后效性的要求。才能
成为动态规划里所讲的状态。
例如，研究物体 (把它
看作一个质点 )受外力作用
后其空间运动的轨迹问
题．从描述轨迹这点着眼，
可以只选坐标位置 (xk,yk)
作为过程的状态，但这样不
能满足无后效性，因为即使
知道了外力的大小和方向，
仍无法确定物体受力后的运
动方向 和轨迹。
不具有后效性的例子
但是如果把位置 (xk，
yk)和速度 (vxk,vvk)都
作为过程的状态变量，就
可以确定物体运动下一步
的方向和轨迹，实现无后
效性的要求．
(3)决策
决策表示当过程处于某一阶段的某个状态时，可以作出不同
的决定 (或选择 )，从而确定下一阶段的状态，这种决定称为决策 。
A EB2 C2
B1
B3
C1
C3
D1
D2
4
3
5
8
1012
14
18
1012
9
4
5
8
9
7
7
3
4
11
3 动态规划的基本概念
决策变量 —— uk ( xk )
描述决策的变量，称为决策变量．它可用一个数、一组数或
一个向量来描述．
uk ( xk )
表示第 k 阶段当状态处于 xk 时的决策变量．它是状态变量的函数．
A EB2 C2
B1
B3
C1
C3
D1
D2
4
3
5
8
1012
1418
1012
9
4
5
8
9
7
7
3
4
11
3 动态规划的基本概念
允许决策 集合 —— Dk(xk)
在实际问题中，决策变量的取值往往限制在某一范围之内，此范围称为 允许决策
集合,
A EB2 C2
B1
B3
C1
C3
D1
D2
4
3
5
8
1012
1418
1012
9
4
5
8
9
7
7
3
4
11
Dk(xk)
表示第 k 阶段从状态 xk 出发的允许决策集合，显然 有 uk(xk)∈ Dk(xk)．
从状态 B1出发，就可作出三种不同的决策，其允许决策集合是 D2(B1)＝ {C1,C2，
C3},如果选取的点为 C2,则 C2是状态 Bl在决策 u2(B1) 作用下的一个新的状态，记作
u2(B1) ＝ C2．
3 动态规划的基本概念
A EB2 C2
B1
B3
C1
C3
D1
D2
4
3
5
8
1012
1418
1012
9
4
5
8
9
7
7
3
4
11
K 子过程策略
由过程的第 k阶段开始直到终止状态为止的过程，称为问题的后部子过程
(或称为 k子过程 )．
全过程的一个策略
当 k=1时，此决策函数序列称为全过程的一个策略，简称策略，记为 p1,n(x1),
3 动态规划的基本概念
3 动态规划的基本概念
允许策略集合
在实际问题中，可供选择的策略有一定的范围，此范围称为
允许策略集合，用 P表示,从允许决策集合中就能找出达到最优效
果的策略，它被称为最优策略。
A EB2 C2
B1
B3
C1
C3
D1
D2
4
3
5
8
1012
1418
1012
9
4
5
8
9
7
7
3
4
11
3 动态规划的基本概念
指标函数
使用不同的策略，其效果是不一样的，把衡量过程效果的好
坏的函数叫做指标函数。
Vkn=Vkn(xk,uk,xk+1,uk +1,…,xk+1) (k=1,2,…,n)
V是 value的缩写
A EB2 C2
B1
B3
C1
C3
D1
D2
4
3
5
8
1012
1418
1012
9
4
5
8
9
7
7
3
4
11
在这个函数里面，各个状态的取值是变化的不定的。
3 动态规划的基本概念
最优指标函数
对于不同的状态 xk,指标函数 Vkn有不同的最优值，这个最优
值可以表示为 xk的函数，称为最优指标函数，记为 f k ( x k )
A EB2 C2
B1
B3
C1
C3
D1
D2
4
3
5
8
1012
1418
1012
9
4
5
8
9
7
7
3
4
11
例如 f 2 ( B 2 )表示从第二阶段中的 B2状态到终点 E的 最短 距离。
例如 f 4 ( D 1 )表示从第四阶段中的 D 1 状态到终点 E的 最短 距离。
0 1 2 3
1 0 3 7 11
2 0 4 8 12
3 0 5 7 9
导弹数
战场
效益
战场 1 战场 2 战场 3
将问题分为三个阶段，第三阶段给战场 3分配导弹，第二阶段给战场 2和战场 3
分配导弹。第一阶段给战场 1,2,3分配导弹
第三阶段给战场 3分配导弹
第二阶段给战场 2和战场 3分配导弹
第一阶段给战场 1,2,3分配导弹
4 动态规划解
决问题的 一般
步骤
(1)首先确定阶
段变量 K,
K=1,2,3.
(2)确定各阶段的
状态 xk
战场 2 战场 3
0 1 2 3
1 0 3 7 11
2 0 4 8 12
3 0 5 7 9
导弹数
战场
效益
战场 1
(1)首先确定阶段变量 K, K=1,2,3.
(2)确定各阶段的状态 xk
(3)确定各阶段允许状态集合, X3可以取值多少呢？
X3表示分配给第三阶段（也就是第 3战场）的导弹数量。 x2表示分配给第二阶段（也就是第
2,3战场）的导弹数量。 X1表示分配给第一阶段（也就是第 1,2,.3战场）的导弹数量。
X3={0,1,2,3}
要满足无后效性,x3,x2,x1
(4)确定决策变量, 决策变量 uk(xk)表示的是当第 K阶段所处的状态为 xk时所作的决策。确定决策变量
(5)确定状态转移关系,
4 动态规划解决问题的 一般 步骤
略过
0 1 2 3
1 0 3 7 11
2 0 4 8 12
3 0 5 7 9
导弹数
战场
效益
战场 2 战场 3战场 1(1)首先确定阶段变量 K,
(2)首先各阶段的状态 xk
(3)确定各阶段允许状态集合,
(4)确定决策变量 uk(xk).
(5)确定状态转移关系,
x3
X3=0,1,2,3
u3(X3)
X2
X2=0,1,2,3
u2(X2)x
2-u2(x2)=x3
0 1 2 3
1 0 3 7 11
2 0 4 8 12
3 0 5 7 9
导弹数
战场
效益
(1)首先确定阶段变量 K,
(2)首先各阶段的状态 xk
(3)确定各阶段允许状态集合,
(4)确定决策变量 uk(xk).
(5)确定状态转移关系,
战场 2 战场 3战场 1
x3X2
X1
X1=0,1,2,3
u1(X1)x1-u1(x1)=x2
0 1 2 3
1 0 3 7 11
2 0 4 8 12
3 0 5 7 9
导弹数
战场
效益
(1)首先确定阶段变量 K,
(2)首先各阶段的状态 xk
(3)确定各阶段允许状态集合,
(4)确定决策变量 uk(xk).
(5)确定状态转移关系,
战场 2 战场 3战场 1
x3X2
X1
X1=0,1,2,3
u1(X1)
x1-u1(x1)=x2
xk+1 = xk-uk(xk)
X4=0
0 1 2 3
1 0 3 7 11
2 0 4 8 12
3 0 5 7 9
导弹数
战场
效益
战场 2 战场 3战场 1
x3
X3=0,1,2,3
u3(X3)
u3(0)=0 u3(1)=1
f3(0)=0 f3(1)=5
u3(2)=2
f3(2)=7
u3(3)=3
f3(3)=9
xk+1 = xk-uk(xk)
x2
X2=0,1,2,3
u2(X2)
设 uk(xk)为第 K个阶段所采取的决策
变量，也就是分配给第 K个战场的导弹数
量。
设 g(uk(xk) ) 为分配给第 K
个战场 uk(xk)的导弹所产生的效
益 。
设 f (x k) 为第 K阶段状
态为 (x k时，第 K阶段到最后
阶段所得到的最优效益 。
1）实际求解
0 1 2 3
1 0 3 7 11
2 0 4 8 12
3 0 5 7 9
导弹数
战场
效益
战场 2 战场 3战场 1
x3
X3=0,1,2,3
u3(X3)
u3(0)=0 u3(1)=1
f3(0)=0 f3(1)=5
u3(2)=2
f3(2)=7
u3(3)=3
f3(3)=9
xk+1 = xk-uk(xk)
x2
X2=0,1,2,3
f2(0)= g(u2(0) ) + f3(0) =0
f2(1)= g(u2(0) )+ f3(1) =5
g(u2(1) ) + f3(0) =4
max =5
f2(2)=
g(u2(0) ) + f3(2) =7
g(u2(1) ) + f3(1) =9
g(u2(2) ) + f3(0) =8
=9max
f2(3)=
g(u2(0) ) + f3(3) =9
g(u2(1) ) + f3(2)=11
g(u2(2) ) + f3(1) =13
g(u2(3) ) + f3(0) =12
max =13
u2(X2)
0 1 2 3
1 0 3 7 11
2 0 4 8 12
3 0 5 7 9
导弹数
战场
效益
战场 2 战场 3战场 1
x3
X3=0,1,2,3
u3(X3)
u3(0)=0 u3(1)=1
f3(0)=0 f3(1)=5
u3(2)=2
f3(2)=7
u3(3)=3
f3(3)=9
xk+1 = xk-uk(xk)
x2
X2=0,1,2,3
f2(0)= g(u2(0) ) + f3(0) =0
f2(1)= g(u2(0) )+ f3(1) =5
g(u2(1) ) + f3(0) =4
max =5
f2(2)=
g(u2(0) ) + f3(2) =7
g(u2(1) ) + f3(1) =9
g(u2(2) ) + f3(0) =8
=9max
f2(3)=
g(u2(0) ) + f3(3) =9
g(u2(1) ) + f3(2)=11
g(u2(2) ) + f3(1) =13
g(u2(3) ) + f3(0) =12
max =13
u2(X2)
0 1 2 3
1 0 3 7 11
2 0 4 8 12
3 0 5 7 9
导弹数
战场
效益
战场 2 战场 3战场 1
x3
X3=0,1,2,3
u3(X3)
u3(0)=0 u3(1)=1
f3(0)=0 f3(1)=5
u3(2)=2
f3(2)=7
u3(3)=3
f3(3)=9
x2
X2=0,1,2,3
xk+1 = xk-uk(xk)
f2(0)= g(u2(0) ) + f3(0) = 0
f2(1)= g(u2(0) ) + f3(1) =5
f2(2)= g(u2(1) ) + f3(1) =9
f2(3)= g(u2(2) ) + f3(1) =13
u2(0)f2(0) = 0 决策是, u3(0)
f2(1) = 5 u2(0)决策是, u3(1)
f2(2) = 9 u2(1)决策是, u3(1)
f2(3) = 13 u2(2)决策是, u3(1)
u2(X2)
0 1 2 3
1 0 3 7 11
2 0 4 8 12
3 0 5 7 9
导弹数
战场
效益
xk+1 = xk-uk(xk) 战场 2 战场 3战场 1
x3
X3=0,1,2,3
x2
X2=0,1,2,3
f2(0) u2(0)= 0 决策是, u3(0)
f2(1) = 5 u2(0)决策是, u3(1)
f2(2) = 9 u2(1)决策是, u3(1)
f2(3) = 13 u2(2)决策是, u3(1)
x1
X1=0,1,2,3
用不用再求 f1(0),f1 (1),f1 (2)了？
f1(3)=
g(u1(0) ) + f2 (3) = 13
g(u1(1) ) + f2 (2) = 12
g(u1(2) ) + f2 (1) = 12
g(u1(3) ) + f2 (0) = 11
max = 13
0 1 2 3
1 0 3 7 11
2 0 4 8 12
3 0 5 7 9
导弹数
战场
效益
xk+1 = xk-uk(xk) 战场 2 战场 3战场 1
x3
X3=0,1,2,3
x2
X2=0,1,2,3
f2(0) u2(0)= 0 决策是, u3(0)
f2(1) = 5 u2(0)决策是, u3(1)
f2(2) = 9 u2(1)决策是, u3(1)
f2(3) = 9 u2(2)决策是, u3(1)
x1
X1=0,1,2,3
f1(3)=
g(u1(0) ) + f2 (3) = 13
g(u1(1) ) + f2 (2) = 12
g(u1(2) ) + f2 (1) = 12
g(u1(3) ) + f2 (0) = 11
max = 13
0 1 2 3
1 0 3 7 11
2 0 4 8 12
3 0 5 7 9
导弹数
战场
效益
xk+1 = xk-uk(xk) 战场 2 战场 3战场 1
x3
X3=0,1,2,3
x2
X2=0,1,2,3
f2(0) u2(0)= 0 决策是, u3(0)
f2(1) = 5 u2(0)决策是, u3(1)
f2(2) = 9 u2(1)决策是, u3(1)
f2(3) = 9 u2(2)决策是, u3(1)
x1
X1=0,1,2,3
f1(3)=g(u1(0) ) + f2 (3) = 13
f1(3) = 13 u1(0)决策是, u2(2)
,u3(1)
动态规划的方法，在工程技术、企业管理、工农业生产及军事
等部门中都有广泛的应用，并且获得了显著的效果．在企业管理方
面，动态规划可以用来解决最优路径问题、资源分配问题、生产调
度问题、库存问题、装载问题、排序问题、设备更新问题、生产过
程最优控制问题等等，所以它是现代企业管理中的一种重要的决策
方法．许多问题用动态规划的方法去处理，常比线性规划或非线性
规划更有成效．特别对于离散性的问题，由于解析数学无法施展其
术，而动态规划的方法就成为非常有用的工具．应指出，动态规划
是求解某类问题的一种方法，是考察问题的一种途径，而不是一种
特殊算法 (如线性规划是一种算法 )．因而，它不象线性规划那样有
一个标准的数学表达式和明确定义的一组规则，而必须对具体问题
进行具体分析处理．因此，读者在学习时，除了要对基本概念和方
法正确理解外，应以丰富的想象力去建立模型，用创造性的技巧去
求解．
小 节
