文档介绍：第七章动态规划
动态规划问题和基本概念
动态规划的基本原理
动态规划的应用
引言
动态规划与多阶段决策:
多阶段决策是指这样一类特殊的活动过程
,
它们可以按时间顺序分
解成若干相互联系的阶段
,
每个阶段都要作出决策
,
全部过程的决策是
一个决策序列
,
所以多阶段决策问题又称为序贯决策问题。
多阶段决策的目标
是要达到整个活动过程的总体效果最优
,
所以多
阶段决策又叫做过程最优化。
所谓
动态规划,
就是解决多阶段决策和过程最优化问题的一
种规划方法。
最短路问题
设A地的某一企业要把一批货物由A地运到E城销售, 其间
要经过八个城市,各城市间的交通路线及距离如下图所示, 问应
选择什么路线才能使总的距离最短?
动态规划问题和基本概念
例中,路线图(共18条路线,3×3×2×1=18)
枚举法:
例中,路线图(共18条路线,3×3×2×1=18)
为解决这个最短路径问题,首先给出几个定义。
1)、阶段
(stage)
将所给问题的过程,按时间或空间特征分解成若干相互联系的段落,
以便按次序求解就形成了阶段
,
阶段变量常用字母
K
来表示
。如例

有四个阶段,
K
就等于
1,2,3,4
。第一阶段共有
3
条路线即
(A,B1), (A,B2)
和
(A,B3)
,
第二阶段有
9
条路线,第
3
阶段有
6
条路线
,
第
4
阶段有
2
条
路线。
1
2
3
4
2)、
状态
(
state)
各阶段开始时的出发点称作状态。
描述各阶段状态的变量,称作状态变量,用sk 表示。
在例

中,第一阶段的状态为
A
,第二阶段的状态为城市
B1,B2
和
B3。
所以状态变量
S1
的集合
S1={A}
,
S2
的集合是
S2={B1,B2,B3},
依次有
S3={C1,C2,C3}, S4={D1,D2}
。
1
2
3
4
3)、
决策(Decision )
当各阶段的状态确定以后,就可以做出不同的决定或选择,从而确
定下一阶段的状态,这种决定就是决策,表示决策的变量称为决策变量。
常
用
k
X
(
k
s
)
表示第
K
阶段当状态为
k
s
时的决策变量
,
,即S2=B1,可选择走C1或C2,C3 ,如果我们选择,从C2走,则此时的决策变量可表示x2(B1)=C2。
1
2
3
4
4)、策略( Policy)
在各阶段决策确定以后,整个问题的决策序列就构成了一个策略,
用P1n(s1)表示。
,但最优策略只有一个。
1
2
3
4
5)、目标函数

用于衡量所选定策略优劣的数量指标称作目标函数。一个n阶段的决策过程,从1到n 叫作问题的原过程。
目标函数的最优值称为最优目标函数,最优目标函数记为fk(sk),它表示从第K阶段的状态Sk出发采用的最优策略。
当K=1时, f1(s1 )就是从初始状态S1到全过程结束的整体最优目标函数。
,
,目标函数就是距离。如在第2阶段,状态为B2时,f2 (B2)则表示从B2到E的最短距离。本问题的总目标是求f 1(A), 即从A到E的最短距离。
1
2
3
4