第四章
动态规划问题
动态规划的概念与模型
静态决策 一次性决策
动态决策 多阶段决策
决策
x1 x2
Z
u输入 决策
输出
决策效应
第一月
x1 x2
r1
u1
第二月
x3
r2
u2
第三月
x4
r3
u3
多段决策过程
T1
x1 x2
r1
u1
T2
x3
r2
u2
Tk
xk xk+!
rk
uk
Tn
xn xn+1
rn
un
… …
n个决策子问题
K称为阶段变量
xk描述k阶段初的状态，称为状态变量
一般把输入状态称为该阶段的阶段状态。
uk的取值代表k阶段对第k子问题所进行的决策，称为k阶段的决策变量
rk为k阶段从状况xk出发,做决策uk之后的后果，称为k阶段的阶段效应。
具有无后效性的多段决策过程
Xk+1=Tk (xk, uk)
系统从k阶段往后的决策只与k阶段系统的状态xk有关,而与系
统以前的决策无关，则称为具有无后效性的多段决策过程。
T1
x1 x2
r1 (x1,
u1)
u1(x1)
T2
x3
r2 (x2
,u2)
u2 (x2)
Tk
xk xk+!
rk (xk,uk)
uk (xk)
Tn
xn xn+1… …
rn (xn,un)
un (xn)
K后部子过程
多段决策过程中从第k阶段到最终阶段的过程称为k-后部子过
程，简称k-子过程。
Tk
xk xk+!
rk (xk,uk)
uk (xk)
Tn
xn xn+1…
rn (xn,un)
un (xn)
动态规划模型
Opt表示求优
Xk是一个集合，表示k阶段
状态可能取值的范围，称为
状态可能集合。
Uk是一个集合，表示k阶段
决策可能取值的范围，称为
决策允许集合，一般来说对
于不同状态，可以作的决策
的范围是不同的。因此决策
允许集合一般写为Uk(xk)。
动态规划的建模
动态规划建模
①确定阶段与阶段变量
②明确状态变量和状态可能集合。
③确定决策变量和决策允许集合。
④确定状态转移方程。
⑤明确阶段效应和目标。
动态规划的建模
①确定阶段与阶段变量
阶段的划分一般是按照决策进行的时间或空间上的先后顺
序划分的，阶段数等于多段决策过程中从开始到结束所需
要作出决策的数目，阶段变量用k表示。
②明确状态变量和状态可能集合。
状态变量必须包含在给定的阶段上确定全部允许决策所需
要的信息。状态变量的确定决定了整个决策过程是不是具
有无后效性，因而也决定着能不能用动态规划方法来求解。
状态可能集是关于状态的约束条件，因此为了求解必须正
确地确定状态可能集。
动态规划的建模
③确定决策变量和决策允许集合。
与静态问题相同，决策变量应能够反映对问题所作的决策，
决策变量也应有其相应的约束条件，在建模时应明确决策
允许集合Uk(xk)。
④确定状态转移方程。
系统k阶段从状态xk出发作了决策uk(xk)之后的结果之一是
系统状态的转移，这一结果直接影响系统往后的决策过程，
因此必须明确状态的转移过程，即根据问题的内在关系，
明确xk+1=Tk(xk,uk)中的函数Tk（ ）。
动态规划的建模
⑤明确阶段效应和目标。
阶段效应rk(xk,uk)是在阶段k以xk出发作了决策uk之后所产
生的后果，必须明确rk与xk，uk的关系，才能构成目标函
数。目标函数是由阶段效应经过某种集结而得到的，如何
集结视具体问题而定，同时还应根据问题确定目标是求最
大还是最小。
由于在经济系统中的大多数情况下，目标的集结方法都是
求和，因此，在不作说明的情况下，往后的讨论都针对目
标为和的形式进行。
动态规划解的概念
多段决策过程中所要求解的是，从起始状态x1开始，进行
一系列的决策，使目标R达到最优
最优目标值 R*
最优策略
使得目标达到最优的决策序列。
最优路线
在采取最优策略时，系统从x1开始所经过的状态序列
求解动态规划模型
找到最优策略、最优路线和最优目标值。
动态规划最优性原理
多段决策过程的特点
每个阶段都要进行决策
相继进行的阶段决策构成的决策序列
前一阶段的终止状态又是后一阶段的初始状态
阶段最优决策不能只从本阶段的效应出发，必须通盘考虑，
整体规划。
阶段k的最优决策不应该只是本阶段效应的最优，而必须
是本阶段及其所有后续阶段的总体最优，即关于整个k后
部子过程的最优决策。
动态规划最优性原理
最优性原理
“最优策略具有的基本性质是：无论初始状态和初始决
策如何，对于前面决策所造成的某一状态而言，下余的决
策序列必构成最优策略”。
A
M
B
动态规划最优性原理
最优性原理的含意
最优策略的任何一部分子策略，也是相应初始状态的
最优策略。
每个最优策略只能由最优子策略构成。
显然，对于具有无后效性的多段决策过程而言，如果按照
k后部子过程最优的原则来求各阶段状态的最优决策，那
么这样构成的最优决策序列或策略一定具有最优性原理所
提示的性质。
贝尔曼函数
贝尔曼函数fk(xk)：
在阶段k从初始状态xk出发，执行最优决策序列或策
略，到达过程终点时，整个k-子过程中的目标函数取值，
称为条件最优目标函数，亦称贝尔曼函数。
条件最优策略
多段决策过程的任一阶段状态xk的最优策略
处于条件xk时的最优策略。
条件最优决策 构成条件最优策略的决策
贝尔曼函数
条件最优目标函数值fk(xk)
执行条件最优策略时的目标函数值
条件最优路线
执行条件最优策略时的阶段状态序列
贝尔曼函数
条件最优k-子策略
系统从xk出发，在k-后部子过程中的最优策略
k-子过程条件最优目标函数
fk(xk)是从xk出发系统在k-后部子过程中的最优目标值，
多段决策问题所求解的最优目标函数值
R*=f1(x1
*)
动态规划基本方程
fk(xk)与fk＋1(xk＋1)之间的递推关系
动态规划方法的依据是最优性原理
动态规划基本方程
设在阶段k的状态xk执行了任意选定决策uk后的状态是
xk+1=Tk(xk,uk)。这时k-后部子过程就缩小为k+1后部子过程。
根据最优性原理，对k+1后部子过程应采取最优策略，由
于无后效性，k后部子过程的目标函数值为
动态规划基本方程
动态规划基本方程
动态规划方法基本原理
动态规划方法基本原理
rk(xk, uk)和xk+1=Tk(xk, uk)都是已知的函数
求fk(xk)需要首先求关于xk的所有k+1段状态xk+1的fk+1(xk+1)
逆序地求出条件最优目标函数值集合和条件最优决策集合
状态xk+1是由前面阶段的状态决定的
用问题给定的初始条件，即可顺序地求出整个多段决策问题
的最优目标函数值、最优策略和最优路线。
动态规划问题求解的一般步骤
逆序地求出条件最优目标函数值集合和条件最优决策集合
k=n时，动态规划基本方程是
边界条件
k=n时的动态规划基本方程成为
动态规划问题求解的一般步骤
逆序地求出条件最优目标函数值集合和条件最优决策集合
k=n－1时，动态规划的基本方程是
所有的fn(xn)都已经求出，因此可以根据xn=Tn-1(xn-1,un-1)
就阶段n-1每个可能状态xn-1∈Xn-1求条件最优决策及相应
的条件最优目标函数值fn－1(xn－1)
动态规划问题求解的一般步骤
逆序地求出条件最优目标函数值集合和条件最优决策集合
k=1时，动态规划的基本方程是
所有的f2(x2)都已经求出，因此可以根据x2=T1(x1,u1)
就阶段1每个可能状态x1∈X1求条件最优决策及相应的条
件最优目标函数值f1(x1)
动态规划问题求解的一般步骤
逆序地求出条件最优目标函数值集合和条件最优决策集合
动态规划问题求解的一般步骤
顺序地求出最优目标值、最优策略和最优路线
若x1已知，则
阶段1的条件最优决策就是阶段1的关于整个过程的最优决
策
若x1未知
动态规划问题求解的一般步骤
顺序地求出最优目标值、最优策略和最优路线
动态规划四大要素、一个方程
五个关键因素 四大要素、一个方程：
①状态变量及其可能集合
②决策变量及其允许集合
③状态转移方程
④阶段效应
⑤动态规划基本方程：
动态规划应用举例----最短路问题
例 某旅行者希望从s地起到t地，其间的道路系统如图4－1
所示，图上圆圈表示途径的地方，称为节点，连结两地的
箭线表示道路，其上的数字表示该段道路长度，箭头表示
通行的方向。试求s到t的最短路。
a d
b e t
c f
s
9
7
5
7
8
4
5
6
4
6
5 4
7
图4--1
动态规划应用举例----最短路问题
a d
b e t
c f
s
9
7
5
7
8
4
5
6
4
6
5 4
7
第一阶段 第二阶段 第三阶段
划分阶段 k=1,2,3 代表三个阶段
动态规划应用举例----最短路问题
a d
b e t
c f
s
9
7
5
7
8
4
5
6
4
6
5 4
7
状态变量xk取为k阶段所在地，则有：
动态规划应用举例----最短路问题
a d
b e t
c f
s
9
7
5
7
8
4
5
6
4
6
5 4
7
k阶段决策是决定下一步走到哪里，uk(xk)取为下一步的所在点。
动态规划应用举例----最短路问题
逆序求条件最优目标函数集和条件最优决策集
由于第3阶段末已到达t，往后的距离自然是零，因此f4(t)=0
对3阶段所有可能的状态X3={d, e, f}计算f3( )如下
动态规划应用举例----最短路问题
逆序求条件最优目标函数集和条件最优决策集
也可以用表格方法计算如下
t/t F3() U3()
d
e
f
5+0
7+0
4+0
5
7
4
t
t
t
r3(x3,u3)+f4(x4) f3(x3) u3(x3)
动态规划应用举例----最短路问题
逆序求条件最优目标函数集和条件最优决策集
对2阶段所有可能的状态X2={a, b, c}计算f2( )如下
动态规划应用举例----最短路问题
逆序求条件最优目标函数集和条件最优决策集
对2阶段所有可能的状态X2={a, b, c}计算f2( )如下
动态规划应用举例----最短路问题
逆序求条件最优目标函数集和条件最优决策集
也可以用表格方法计算如下
d/d e/e f/f F2() U2()
a
b
c
7+5
5+5
4+5
6+7
5+7
4+4
6+4
8
10
9
f
d
d
f2(x2) u2(x2) r2(x2,u2)+f3(x3)
动态规划应用举例----最短短问题
逆序求条件最优目标函数集和条件最优决策集
对1阶段所有可能的状态X1={s}计算f1( )如下
a/a b/b c/c F2() U2()
s 9+8 8+10 7+9 16 f
动态规划应用举例----最短路问题
顺序求最优策略、最优路线和最优目标函数值
动态规划应用举例----最短路问题
