10运筹学-动态规划.ppt

动态规划
动态规划问题实例
动态规划的基本概念与原理
动态规划应用举例
引言
动态规划是解决多阶段决策过程最优化的一种方法。该方法
是由美国数学家贝尔曼(R. E. Bellman)等人在20世纪50年代
初提出的。并成功地解决了生产管理、工程技术等方面的许
多问题,从而建立了运筹学的一个新的分支,即动态规划。
Bellman在1957年出版了《Dynamic Programming》一书,是
动态规划领域中的第一本著作。
§1 动态规划问题实例
例1 给定一个线路网络,
A
B1
B2
C1
C2
C3
C4
D1
D2
D3
E1
E2
F
4
5
2
3
6
8
7
7
5
8
4
5
3
4
8
4
3
5
6
2
3
1
4
3
要从A向F铺设一条输油管道,
各点间连线上的数字表示距离,问应选择什么路线,可使总
距离最短?
动态规划是解决多阶段决策问题的一种方法。所谓多阶段
决策问题是指这样的决策问题:其过程可分为若干个相互联
系的阶段,每一阶段都对应着一组可供选择的决策,每一决
策的选定即依赖于当前面临的状态,又影响以后总体的效果。
A
B
C
D
E
状态A
状态B
状态C
状态D
状态E
状态F
决策A
决策D
决策E
当每一阶段的决策选定以后,就构成一个决策序列,称为一个
决策B
决策C
策略,它对应着一个确定的效果。多阶段决策问题就是寻找使
此效果最好的策略。
§2 动态规划的基本概念与原理
一。基本概念
阶段:是指问题需要做出决策的步数。阶段总数常记为n,相
应的是n个阶段的决策问题。阶段的序号常记为k,称为阶段
变量,k=1,2, …,n. k即可以是顺序编号也可以是逆序编号,
常用顺序编号。
状态:各阶段开始时的客观条件,第k阶段的状态常用状态
变量表示,状态变量取值的集合称为状态集合,用
表示。
例如,例1中,
A
B1
B2
C1
C2
C3
C4
D1
D2
D3
E1
E2
F
4
5
2
3
6
8
7
7
5
8
4
5
3
4
8
4
3
5
6
2
3
1
4
3
第1阶段
第2阶段
第3阶段
第4阶段
第5阶段
状态
1
状态
2
状态
3
状态
4
状态
5
状态
6
决策:是指从某阶段的某个状态出发,在若干个不同方案中
做出的选择。表示决策的变量,称为决策变量,用表示
例如: 表示走到C阶段,当处于C2 路口时,下一
步奔D1.
时的允许决策集合记为,例如:
状态转移方程:是从上一阶段的某一状态值转变为下一阶段
某一状态值的转移规律,用
表示。
决策变量允许的取值范围称为允许决策集合,第k阶段状态为
指标函数:分阶段指标函数和过程指标函数。阶段指标函数
是指第k阶段从状态出发,采取决策时的效益,用
表示。而过程指标函数从第k阶段的某状态出发,
采取子策略
时所得到的阶段效益之和:
最优指标函数:表示从第k阶段状态为时采用最佳策略
到过程终止时的最佳效益。记为
其中 opt 可根据具体情况取max 或min。
基本方程:此为逐段递推求和的依据,一般为:
式中opt 可根据题意取 max 或 min.
例如,例1的基本方程为:
最优性原理:无论过去的状态和决策如何,从眼下直到最后
的诸决策必构成最优子策略。
动态规划应用举例
例1 最短路线问题
A
B1
B2
C1
C2
C3
C4
D1
D2
D3
E1
E2
F
4
5
2
3
6
8
7
7
5
8
4
5
3
4
8
4
3
5
6
2
3
1
4
3