文档介绍：第十章动态规划
§1 多阶段决策过程最优化问题举例
§2 基本概念、基本方程与最优化原理
§3 动态规划的应用(1)
§4 动态规划的应用(2)
1
第十章动态规划
动态规划:解决多阶段决策过程最优化问题
解决思路:多阶段单阶段
解决的具体问题:最短路径、装载问题、库存、资源分配、生产过程最优化等问题、
决策过程
确定性决策过程
随机性决策过程
离散决策过程
连续决策过程
离散确定性决策过程
连续随机性决策过程
连续确定性决策过程
离散随机性决策过程
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 多阶段决策过程最优化问题举例
讨论:
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
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
4
第三阶段:有三个始点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
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
5
第二阶段:有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
6
第一阶段:只有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
7
以上计算过程及结果,可用图2表示,可以看到,以上方法不仅
得到了从A到D的最短路径,同时,也得到了从图中任一点到E的最
短路径。