文档介绍：第六章动态规划 Dynamic Programming
Slide 1
《运筹学》第二章线性规划在工商管理中的应用
多阶段决策过程最优化问题:有一些活动,它在时间或空间上可以分成若干个阶段,需要对每个阶段进行决策(有若干个方案可供选择),使得活动的整体效果最好。
每个阶段的决策都不是可以任意确定的,它依赖于当前的状况,同时,它的决策结果又影响到以后的决策。组成了一个决策序列。
这样的决策过程是在变化的过程中产生的,故有动态的含义。处理它的方法称为动态规划的方法。
方法:多阶段问题转化成一系列互相联系的较容易的单阶段问题。
1
2
n
……..
状态
决策
状态
决策
决策
状态
状态
状态
2
《运筹学》第六章动态规划
第一节动态规划的基本思想和方法
一、多阶段决策过程最优化问题举例
P169 :最短路线问题(P176)
从A点到E点可分成4个阶段。以A为起点,终点有三个B1、B2、B3,有三个选择。若选择B2,则B2为第一阶段决策的结果。同时它又是第二阶段的开始状态。当每个阶段做出决策的结果,直接影响到后面的选择和决策的结果。
最短路线有一个重要特性:
如果从起点A经过C2点和D1点到达终点E是一条最短的路线,则由C2 点经过D1 点到达E点的这条子路线,是由C2 点出发到达E点所有路线中的最短路线。
寻找最短路线的方法,从最后一段开始,由后向前逐步推进,找出各点到E点的最短路线,最后就能确定一条从A点到E点的最短路线。
3
《运筹学》第六章动态规划
阶段 4
本阶段始点(状态)
本阶段各终点(决策)
到E点的最短距离
本阶段最优终点
(最优决策)
E
D1
4
4
E
D2
3
3
E
4
《运筹学》第六章动态规划
阶段 3
本阶段始点(状态)
本阶段各终点(决策)
到E点的最短距离
本阶段最优终点
(最优决策)
D1
D2
C1
3+4=7
5+3=8
7
D1
C2
4+4=8
3+3=6
6
D2
C3
6+4=10
9+3=12
10
D1
5
《运筹学》第六章动态规划
阶段2
本阶段始点(状态)
本阶段各终点(决策)
到E点的最短距离
本阶段最优终点
(最优决策)
C1
C2
C3
B1
7+7=14
6+6=12
12
C2
B2
9+7=16
5+6=11
2+10=12
11
C2
B3
3+6=9
8+10=18
9
C2
6
《运筹学》第六章动态规划
阶段 1
本阶段始点(状态)
本阶段各终点(决策)
到E点的最短距离
本阶段最优终点
(最优决策)
B1
B2 B3
A
3+12=15
5+11 7+9
=16 =16
15
B1
最短线路:A→B1 →C2 →D2 →E,总长度为15。
7
《运筹学》第六章动态规划
作业例1:如图给定一个线路网络,两点之间连线上的数字表示两点间的距离(或费用)。试求一条从A到G的铺管线路,使总距离最短(或总费用最小)。
A
C1
E3
E2
E1
F2
F1
G
D3
D2
D1
C4
C3
C2
B2
B1
5
3
1
3
6
6
8
2
2
3
5
4
8
7
6
5
3
3
3
1
2
5
2
6
6
3
8
4
3
3
8
《运筹学》第六章动态规划
阶段 6
本阶段始点(状态)
本阶段各终点(决策)
到G点的最短距离
本阶段最优终点
(最优决策)
G
F1
4
4
G
F2
3
3
G
9
《运筹学》第六章动态规划
阶段 5
本阶段始点(状态)
本阶段各终点(决策)
到G点的最短距离
本阶段最优终点
(最优决策)
F1
F2
E1
3+4=7
5+3=8
7
F1
E2
5+4=9
2+3=5
5
F2
E3
6+4=10
6+3=9
9
F2
10
《运筹学》第六章动态规划