4-2 动态规划的
基本概念和模型
一、基本概念
DP中描述多段决策过程的基本概念主要有：
?阶段和阶段变量；
?状态和状态变量；
?决策、决策变量和决策序列；
?状态转移方程；
?阶段效应和目标函数等。
1,阶段和阶段变量
把所研究的多段决策过程恰当地划分为若干
个 相互独立又相互联系的部分, 每一个部分
就称为一个 阶段 。 事实上一个阶段也就是需
要作出一个决策的子问题部分 。 通常阶段是
按照过程进行的时间和空间上的先后顺序划
分的, 并用 阶段变量 k表示 。 阶段数等于多段
决策过程中从开始到结束所需要作出决策的
数目, 划分阶段的目的是便于求解 。
2,状态和状态变量
状态 是描述系统状况所必须的信息 。 一
般定义为某一个 阶段的初始点, 初始位置
或初始情况 。 状态变量必须包含在给定的
阶段上确定全部允许决策所需要的信息,
阶段 k的状态表示为 xk。 比如：在最短路问
题中, 状态就是网络中的各个节点 。
状态变量的取值有一定的允许范围，
称为 状态可能集 。状态可能集可以是
一个离散取值的集合，也可以是一个
连续的区间，视所给问题而定。
状态可能集是关于状态的约束条件。
状态可能集用相应阶段状态 xk的大写
字母 Xk表示，其中 xk?Xk
3,决策、决策变量和决策序列
决策 就是决策者从本阶段出发对下一阶
段状态的 选择 。
多段决策过程的发展是用各个阶段的状
态演变来描述的。因为用状态描述的过程具
有 无后效性,因此在进行阶段决策时,只须
根据当前的状态而无须考虑过去的历史 。在
阶段 k如果给出了决策变量 uk随状态变量 xk
变化的函数，称为决策函数，表示为 uk(xk)。
决策变量的允许取值范围，称为 允许决策
集合 。允许决策集合是决策的约束条件。 uk
的允许决策集合表示为 Uk,uk?Uk 。 Uk要根据
相应的状态可能集 Xk并结合具体问题来确定。
? ?n21 u,,u,u ?
决策序列就叫策略 。策略有 全过程策略
和 k-子策略 之分。全过程策略是整个 n段决
策过程中依次进行的 n个阶段决策构成的决
策序列，简称策略，表示为：
从阶段 k到阶段 n依次进行的阶段决策构
成的决策序列称为 k-子策略,表示为：
? ?n1kk u,,u,u ??
当 k=1时,k-子策略就是全过程策略。
在 n段决策问题中，各阶段的状态可能集
和决策允许集确定了决策的允许范围。
特别，过程的初始状态不同，决策和策略
也就不同，即策略是初始状态的函数。
4,状态转移方程
状态转移方程表示从阶段 k到阶段 k+1
的状态转移规律的表达式 。
多阶段过程的发展就是用阶段状态的
相继演变来描述的 。 对具有无后效性的多
段决策过程, 系统由从阶段 k到阶段 k+1的
状态转移方程表示为：
))(xu,(xTx kkkk1k ??
意即阶段的状态完全由阶段的状态和决
策确定, 与系统过去的状态 x1,x2,…,xk-1及
其决策 u1(x1),u2(x2),…,uk-1(xk-1)无关 。
Tk( xk,uk)称为 变换函数 或 变换算子 。变换
函数可以分为确定型和随机型两种类型，据
此形成确定型动态规划和随机型动态规划。
问,状态转移方程是否一定是数学意义上
的方程？
5,阶段效应和目标函数
多段决策过程中, 在阶段 k的状态 xk执行
决策 uk, 不仅带来系统状态的转移, 而且也
必然带来对目标函数的影响 。 阶段效应就是
执行阶段决策时所带来的目标函数的增量 。
在具有无后效性的多段决策过程中，阶
段效应完全由阶段 k的状态 xk和决策 uk决定，
与阶段以前的状态和决策无关，表示为
)u,(xr kkk
多阶段决策过程关于 目标函数的总
效应是由各阶段的阶段效应累积形成 。
适于动态规划求解的问题的目标, 必
需具有 关于阶段效应的可分离形式,
递推性和对于变元 RK+1的严格单调性 。
k-子过程的目标函数可以表示为,
)u,(xr)u,(xr)u,(xr
)u,x,,u,x,u,R ( xR
nnn1k1k1`kkkk
nn1k1kkkk
????
?
???
??
?
?
今后要讨论的主要就是这种形式的目标函数 。
其中 表示某种运算, 可以是加, 减, 乘,
除, 开方等 。 经济管理领域中最常见的目标
函数取阶段效应之和的形式, 即：
?
?
?
?? ??
n
ki
iiinn1k1kkkk )u,(xr)u,x,,u,x,u,R ( xR ?
二、多阶段决策过程的数学模型
（ DP的建模）
1,构模条件：
? 一个大前提,恰当地划分问题的阶段,
把问题化为多阶段决策过程；
? 四个条件 (详见下页）
? 一个方程 —— 动态规划基本方程
（ DP基本方程）
四 个 条 件
（ 1）正确地选择状态变量：
–能描述过程的演变特征；
-满足无后效性 —— 指系统从某个阶段往
后的发展，完全由本阶段所处的状态及
其往后的决策决定，与系统以前的状态
和决策无关。即过程 过去的历史只能通
过当前的状态去影响未来的发展,当前
状态是未来过程的初始状态。
?一个例子：负指数分布具有无记忆性
P{?>s+t| ?>s}=P{?>t}=e-μt
– 可知性 — 各阶段状态变量的值直接或间
接均为已知 。
（ 2）能确定决策变量及各阶段的允许决策
集合；
（ 3）能写出状态转移方程；
（ 4）能根据题意列出阶段效应和目标函数；
在明确四个条件 （ 或称四个要素 ） 的基础上,
写出动态规划基本方程 。 DP模型的数学表达式一
般形式,
式中 opt指最优化, 根据具体问题要求取 max或
min。
?
?
?
?
?
?
?
?
?
?
?
??
?
?
nk
Uu
Xx
uxTx
ts
uxrRo p t
kk
kk
kkkk
kkk
n
k
uu
n
?
?
,2,1
),(
..
),(
1
1
,
1
具体的 DP模型 包括：
四个条件和一个方程 （ 动态规划基本
方程 ） 的全体 。
问：动态规划模型由哪些部分构成？
2,求解要求：
? ?*n*2*1 u,,u,u ?
? (逆序 )求出 最优策略, 即最优决策序列；
其中,;~1),,(
1 nkuxTx kkkk ?? ??? ?
? ?* 1n*k*2*1 x,,x,x,x ??
?(顺序 )求出 最优路线, 即执行最优策略时
的最优状态序列：
?
?
?
n
1k
*
k
*
kk
* )u,(xrR
?求出 最优目标函数值,
三,DP基本方程
?
?
?
n
ki
iii
u~u
kk )u,(xropt)(xf
nk
n)~1(k ?
)( kk xf
kx
1.Bellman函数 （ 最优指数函数 ） 亦称 条件最
优目标函数 。
该 函数是为了便于应用最优性原理, 建立
动态规划基本方程所定义的 辅助函数,
是在阶段 K从初始状态 出发, 执行最优决策
序列或策略到达过程终点时的目标函数取值 。
对于目标函数是阶段效应之和的多段决策过
程而言,
为了将关于多段决策过程的任一阶段
状态 的最优策略和最终的最优策略相
区别, 称前者为 条件最优策略, 意即相
对于状态 时的最优策略 。 构成条件最
优策略的决策称为 条件最优决策 。 阶段 k
处于状态 的 条 件 最 优 决 策 表 示
为, 简记为, 相应的条件最优
策略表示为,
kx
? ?'n' 1k'k u,,u,u ??
kx
kx
)(' kk xu 'ku
执行条件最优策略时的阶段状态序列称
为 条件最优路线, 表示为
条件最优目标函数值 亦称执行条件最优
策略时的目标函数值, 因此
? ?' 1n'n' 1k'k x,x,x,x ?? ?
.n~1k),u,(xTx 'k'kk' 1k ???其中,
?
?
n
ki
'
iii )u,(xr
?)(xf kk
2,最优化原理
最优策略 具有的 基本性质 是,无论初始状
态和初始决策如何, 对于前面决策所造成的
某一状态而言, 下余的决策序列必构成最优
策略 。
示意图解释,
M B
A
3,DP基本方程
包括 主体部分 和 边界条件 两个部分 。 特别, 当
目标函数为阶段效应求和形式时, 基本方程为
? ?
)1,1,(
0)(
)(),()(
11
11
???
??
?
?
?
?
??
??
??
nnk
xf
xfuxrxf
nn
kkkkk
u
kk o p t
k
? ?
?
?
?
?
?
?
?
?
????
?
??
??
?
?
0)(
1,2,,1)(),(
),()(
11
11
nn
kkkkk
n
ki
iiikk
xf
nkxfuxrO p t
uxro p txf
?
四、动态规划的分类
动态规划的表现形式随多段决策过程的特点
不同而不同, 据此可将动态规划作以下分类：
1,按决策的特性分
a,时间多段决策过程
b,空间多段决策过程
2,按允许决策集合的连续或不连续分
a,连续多段决策过程
b,离散多段决策过程
3.按构成决策序列的决策数目有限或无限分
a,有限多段决策过程
b,无限多段决策过程
4,按状态变化的确定或随机性分
a,确定型多段决策过程
b,随机性多段决策过程
5,按决策序列与时间起点的关系分
a,定常 (与时间起点无关 )多段决策过程
b,非定常多段决策过程
实际的多段决策问题, 常常归结
为它们的各种复合情况 。
今后只限于 定常的, 确定性的,
有限的多段决策过程 的讨论 。
以 最短路问题 为例
熟悉有关的五组概念
3 9
4 8
4 4 7 5
3 4 1 2
1 1 6 3
6 5
阶段 1 2 3 4
h
g
t
a d
b
c f
e
s
②决策变量选为终止位置,? ?cbavu,,11 ?? ； ? ?fedv,,2 ?
③ ),(1 kkk uxx ??? ； )(! kkk xux ??
④
),(
kkk
uxr
执行从 k
x
k
u
所付出的代价（距离、费用等）
目标函数 ? ??
? ??
???
4
1
4
1
4
1
),(),(
k k
kkk
k
kkkk
jiduxCrR
阶段 —— 从起点到终点可以划分为 4个阶段；
① ? ?sx ?1 ； ? ?cbax,,2 ? ； ? ?fedx,,3 ? ； ? ?ghx,4 ? ； ? ?tx ?5
基本概念和模型
一、基本概念
DP中描述多段决策过程的基本概念主要有：
?阶段和阶段变量；
?状态和状态变量；
?决策、决策变量和决策序列；
?状态转移方程；
?阶段效应和目标函数等。
1,阶段和阶段变量
把所研究的多段决策过程恰当地划分为若干
个 相互独立又相互联系的部分, 每一个部分
就称为一个 阶段 。 事实上一个阶段也就是需
要作出一个决策的子问题部分 。 通常阶段是
按照过程进行的时间和空间上的先后顺序划
分的, 并用 阶段变量 k表示 。 阶段数等于多段
决策过程中从开始到结束所需要作出决策的
数目, 划分阶段的目的是便于求解 。
2,状态和状态变量
状态 是描述系统状况所必须的信息 。 一
般定义为某一个 阶段的初始点, 初始位置
或初始情况 。 状态变量必须包含在给定的
阶段上确定全部允许决策所需要的信息,
阶段 k的状态表示为 xk。 比如：在最短路问
题中, 状态就是网络中的各个节点 。
状态变量的取值有一定的允许范围，
称为 状态可能集 。状态可能集可以是
一个离散取值的集合，也可以是一个
连续的区间，视所给问题而定。
状态可能集是关于状态的约束条件。
状态可能集用相应阶段状态 xk的大写
字母 Xk表示，其中 xk?Xk
3,决策、决策变量和决策序列
决策 就是决策者从本阶段出发对下一阶
段状态的 选择 。
多段决策过程的发展是用各个阶段的状
态演变来描述的。因为用状态描述的过程具
有 无后效性,因此在进行阶段决策时,只须
根据当前的状态而无须考虑过去的历史 。在
阶段 k如果给出了决策变量 uk随状态变量 xk
变化的函数，称为决策函数，表示为 uk(xk)。
决策变量的允许取值范围，称为 允许决策
集合 。允许决策集合是决策的约束条件。 uk
的允许决策集合表示为 Uk,uk?Uk 。 Uk要根据
相应的状态可能集 Xk并结合具体问题来确定。
? ?n21 u,,u,u ?
决策序列就叫策略 。策略有 全过程策略
和 k-子策略 之分。全过程策略是整个 n段决
策过程中依次进行的 n个阶段决策构成的决
策序列，简称策略，表示为：
从阶段 k到阶段 n依次进行的阶段决策构
成的决策序列称为 k-子策略,表示为：
? ?n1kk u,,u,u ??
当 k=1时,k-子策略就是全过程策略。
在 n段决策问题中，各阶段的状态可能集
和决策允许集确定了决策的允许范围。
特别，过程的初始状态不同，决策和策略
也就不同，即策略是初始状态的函数。
4,状态转移方程
状态转移方程表示从阶段 k到阶段 k+1
的状态转移规律的表达式 。
多阶段过程的发展就是用阶段状态的
相继演变来描述的 。 对具有无后效性的多
段决策过程, 系统由从阶段 k到阶段 k+1的
状态转移方程表示为：
))(xu,(xTx kkkk1k ??
意即阶段的状态完全由阶段的状态和决
策确定, 与系统过去的状态 x1,x2,…,xk-1及
其决策 u1(x1),u2(x2),…,uk-1(xk-1)无关 。
Tk( xk,uk)称为 变换函数 或 变换算子 。变换
函数可以分为确定型和随机型两种类型，据
此形成确定型动态规划和随机型动态规划。
问,状态转移方程是否一定是数学意义上
的方程？
5,阶段效应和目标函数
多段决策过程中, 在阶段 k的状态 xk执行
决策 uk, 不仅带来系统状态的转移, 而且也
必然带来对目标函数的影响 。 阶段效应就是
执行阶段决策时所带来的目标函数的增量 。
在具有无后效性的多段决策过程中，阶
段效应完全由阶段 k的状态 xk和决策 uk决定，
与阶段以前的状态和决策无关，表示为
)u,(xr kkk
多阶段决策过程关于 目标函数的总
效应是由各阶段的阶段效应累积形成 。
适于动态规划求解的问题的目标, 必
需具有 关于阶段效应的可分离形式,
递推性和对于变元 RK+1的严格单调性 。
k-子过程的目标函数可以表示为,
)u,(xr)u,(xr)u,(xr
)u,x,,u,x,u,R ( xR
nnn1k1k1`kkkk
nn1k1kkkk
????
?
???
??
?
?
今后要讨论的主要就是这种形式的目标函数 。
其中 表示某种运算, 可以是加, 减, 乘,
除, 开方等 。 经济管理领域中最常见的目标
函数取阶段效应之和的形式, 即：
?
?
?
?? ??
n
ki
iiinn1k1kkkk )u,(xr)u,x,,u,x,u,R ( xR ?
二、多阶段决策过程的数学模型
（ DP的建模）
1,构模条件：
? 一个大前提,恰当地划分问题的阶段,
把问题化为多阶段决策过程；
? 四个条件 (详见下页）
? 一个方程 —— 动态规划基本方程
（ DP基本方程）
四 个 条 件
（ 1）正确地选择状态变量：
–能描述过程的演变特征；
-满足无后效性 —— 指系统从某个阶段往
后的发展，完全由本阶段所处的状态及
其往后的决策决定，与系统以前的状态
和决策无关。即过程 过去的历史只能通
过当前的状态去影响未来的发展,当前
状态是未来过程的初始状态。
?一个例子：负指数分布具有无记忆性
P{?>s+t| ?>s}=P{?>t}=e-μt
– 可知性 — 各阶段状态变量的值直接或间
接均为已知 。
（ 2）能确定决策变量及各阶段的允许决策
集合；
（ 3）能写出状态转移方程；
（ 4）能根据题意列出阶段效应和目标函数；
在明确四个条件 （ 或称四个要素 ） 的基础上,
写出动态规划基本方程 。 DP模型的数学表达式一
般形式,
式中 opt指最优化, 根据具体问题要求取 max或
min。
?
?
?
?
?
?
?
?
?
?
?
??
?
?
nk
Uu
Xx
uxTx
ts
uxrRo p t
kk
kk
kkkk
kkk
n
k
uu
n
?
?
,2,1
),(
..
),(
1
1
,
1
具体的 DP模型 包括：
四个条件和一个方程 （ 动态规划基本
方程 ） 的全体 。
问：动态规划模型由哪些部分构成？
2,求解要求：
? ?*n*2*1 u,,u,u ?
? (逆序 )求出 最优策略, 即最优决策序列；
其中,;~1),,(
1 nkuxTx kkkk ?? ??? ?
? ?* 1n*k*2*1 x,,x,x,x ??
?(顺序 )求出 最优路线, 即执行最优策略时
的最优状态序列：
?
?
?
n
1k
*
k
*
kk
* )u,(xrR
?求出 最优目标函数值,
三,DP基本方程
?
?
?
n
ki
iii
u~u
kk )u,(xropt)(xf
nk
n)~1(k ?
)( kk xf
kx
1.Bellman函数 （ 最优指数函数 ） 亦称 条件最
优目标函数 。
该 函数是为了便于应用最优性原理, 建立
动态规划基本方程所定义的 辅助函数,
是在阶段 K从初始状态 出发, 执行最优决策
序列或策略到达过程终点时的目标函数取值 。
对于目标函数是阶段效应之和的多段决策过
程而言,
为了将关于多段决策过程的任一阶段
状态 的最优策略和最终的最优策略相
区别, 称前者为 条件最优策略, 意即相
对于状态 时的最优策略 。 构成条件最
优策略的决策称为 条件最优决策 。 阶段 k
处于状态 的 条 件 最 优 决 策 表 示
为, 简记为, 相应的条件最优
策略表示为,
kx
? ?'n' 1k'k u,,u,u ??
kx
kx
)(' kk xu 'ku
执行条件最优策略时的阶段状态序列称
为 条件最优路线, 表示为
条件最优目标函数值 亦称执行条件最优
策略时的目标函数值, 因此
? ?' 1n'n' 1k'k x,x,x,x ?? ?
.n~1k),u,(xTx 'k'kk' 1k ???其中,
?
?
n
ki
'
iii )u,(xr
?)(xf kk
2,最优化原理
最优策略 具有的 基本性质 是,无论初始状
态和初始决策如何, 对于前面决策所造成的
某一状态而言, 下余的决策序列必构成最优
策略 。
示意图解释,
M B
A
3,DP基本方程
包括 主体部分 和 边界条件 两个部分 。 特别, 当
目标函数为阶段效应求和形式时, 基本方程为
? ?
)1,1,(
0)(
)(),()(
11
11
???
??
?
?
?
?
??
??
??
nnk
xf
xfuxrxf
nn
kkkkk
u
kk o p t
k
? ?
?
?
?
?
?
?
?
?
????
?
??
??
?
?
0)(
1,2,,1)(),(
),()(
11
11
nn
kkkkk
n
ki
iiikk
xf
nkxfuxrO p t
uxro p txf
?
四、动态规划的分类
动态规划的表现形式随多段决策过程的特点
不同而不同, 据此可将动态规划作以下分类：
1,按决策的特性分
a,时间多段决策过程
b,空间多段决策过程
2,按允许决策集合的连续或不连续分
a,连续多段决策过程
b,离散多段决策过程
3.按构成决策序列的决策数目有限或无限分
a,有限多段决策过程
b,无限多段决策过程
4,按状态变化的确定或随机性分
a,确定型多段决策过程
b,随机性多段决策过程
5,按决策序列与时间起点的关系分
a,定常 (与时间起点无关 )多段决策过程
b,非定常多段决策过程
实际的多段决策问题, 常常归结
为它们的各种复合情况 。
今后只限于 定常的, 确定性的,
有限的多段决策过程 的讨论 。
以 最短路问题 为例
熟悉有关的五组概念
3 9
4 8
4 4 7 5
3 4 1 2
1 1 6 3
6 5
阶段 1 2 3 4
h
g
t
a d
b
c f
e
s
②决策变量选为终止位置,? ?cbavu,,11 ?? ； ? ?fedv,,2 ?
③ ),(1 kkk uxx ??? ； )(! kkk xux ??
④
),(
kkk
uxr
执行从 k
x
k
u
所付出的代价（距离、费用等）
目标函数 ? ??
? ??
???
4
1
4
1
4
1
),(),(
k k
kkk
k
kkkk
jiduxCrR
阶段 —— 从起点到终点可以划分为 4个阶段；
① ? ?sx ?1 ； ? ?cbax,,2 ? ； ? ?fedx,,3 ? ； ? ?ghx,4 ? ； ? ?tx ?5
