运筹学动态规划.ppt

文档介绍：1
第十章动态规划
§1 多阶段决策过程最优化问题举例
§2 基本概念、基本方程与最优化原理
§3 动态规划的应用(1)
§4 动态规划的应用(2)
2
§1 多阶段决策过程最优化问题举例
例1 最短路径问题
下图表示从起点A到终点E之间各点的距离。求A到E的最
短路径。
B
A
C
B
D
B
C
D
E
C
4
1
2
3
1
2
3
1
2
3
2
2
1
6
4
7
2
4
8
3
8
6
7
5
6
1
10
6
3
7
5
1
3
§1 多阶段决策过程最优化问题举例
用穷举法的计算量:
如果从A到E的站点有k个,除A、E之外每站有3个位置则
总共有3k-1×2条路径;
计算各路径长度总共要进行(k+1) 3k-1×2次加法以及3k-
1×2-1次比较。随着 k 的值增加时,需要进行的加法和比较的
次数将迅速增加;
例如当 k=20时,加法次数为 ×1015 次,
比较 ×1014 次。若用1亿次/秒的计算机计算
需要约508天。
4
§1 多阶段决策过程最优化问题举例
讨论:
1、以上求从A到E的最短路径问题,可以转化为四个性质完全相
同,但规模较小的子问题,即分别从Di 、Ci、Bi、A到E的最短路
径问题。
第四阶段:两个始点D1和D2,终点只有一个;
表10-1
分析得知:从D1和D2到E的最短路径唯一。
阶段4
本阶段始点
(状态)
本阶段各终点(决策)
到E的最短距离
本阶段最优终点
(最优决策)
E
D1
D2
10*
6
10
6
E
E
5
第三阶段:有三个始点C1,C2,C3,终点有D1,D2,对始点
和终点进行分析和讨论分别求C1,C2,C3到D1,D2 的最短路
径问题:
表10-2
分析得知:如果经过C1,则最短路为C1-D2-E;
如果经过C2,则最短路为C2-D2-E;
如果经过C3,则最短路为C3-D1-E。
§1 多阶段决策过程最优化问题举例
阶段3
本阶段始点
(状态)
本阶段各终点(决策)
到E的最短距离
本阶段最优终点
(最优决策)
D1
D2
C1
C2
C3
8+10=18
7+10=17
1+10=11
6+6=12
5+6=11
6+6=12
12
11
11
D2
D2
D1
6
第二阶段:有4个始点B1,B2,B3,B4,终点有C1,C2,C3。对始点和终点进行分
析和讨论分别求B1,B2,B3,B4到C1,C2,C3 的最短路径问题:
表10-3
分析得知:如果经过B1,则走B1-C2-D2-E;
如果经过B2,则走B2-C3-D1-E;
如果经过B3,则走B3-C3-D1-E;
如果经过B4,则走B4-C3-D1-E。
§1 多阶段决策过程最优化问题举例
阶段2
本阶段始点
(状态)
本阶段各终点(决策)
到E的最短距离
本阶段最优终点(最优决策)
C1
C2
C3
B1
B2
B3
B4
2+12=14
4+12=16
4+12=16
7+12=19
1+11=12
7+11=18
8+11=19
5+11=16
6+11=17
2+11=13
3+11=14
1+11=12
12
13
14
12
C2
C3
C3
C3
7
第一阶段:只有1个始点A,终点有B1,B2,B3,B4 。对始点和终
点进行分析和讨论分别求A到B1,B2,B3,B4的最短路径问题:
表10-4
最后,可以得到:从A到E的最短路径为A B4 C3 D1 E
§1 多阶段决策过程最优化问题举例
阶段1
本阶段始点(状态)
本阶段各终点(决策)
到E的最短距离
本阶段最优终点(最优决策)
B1
B2
B3
B4
A
4+12=16
3+13=16
3+14=17
2+12=14
12
C2
8
以上计算过程及结果,可用图2表示,可以看到,以上方法不仅
得到了从A到D的最短路径,同时,也得到了从图中任一点到E的最
短路径。

以上过程,仅用了22次加法,计算效率远高于穷举法。
B
A
C
B
D
B
C
D
E
C
4
1
2
3
1
2
3
1
2
3
3
2
1
6
4
7
2
4
8
3
8
6
7
5
1
6
10
6
0
10
6
12
11
11
12
13
14
14
12