文档介绍：第三部分动态规划
所谓多阶段决策问题是有这样一类决策过程,它可以划分为若干个相互联系的阶段,在任一阶段都有若干种方案可供选择,选择哪一种方案需要作出决策,这样就形成一个决策序列,通常称为一种策略。不同的策略就产生不同的效果,在所有可能的策略当中,选择一个效果最好的最优策略,就是解决多阶段决策问题的主要目的。下面通过例子来说明。
第一节动态规划模型
一、多阶段决策过程及实例
1
例1:(最短路问题)设从A地到E地要铺设一条管道,其中要经过若干个中间点(如图)。图中两点之间连线上的数字表示两地间的距离。现在要选择一条铺设管道的路线,使总长度最短。
2
5
1
12
14
10
6
10
4
13
11
12
3
9
6
5
8
10
5
2
C1
C3
D1
A
B1
B3
B2
D2
E
C2
2
在这个问题中,从A到B1 ,B2 , B3中的哪一个点要作出一项决策,从B1,B2 , B3某点到 C1,C2,C3 中的哪一个点又要作出一项决策等等。所以总共要作出四个决策。因此,我们可以把整个路程分为A,B ( 包括B1,B2 , B3), C (包括C1, C2 , C3),D(包括D1和D2),E四个阶段。这就是一个多阶段的决策问题。
用动态规划求解多阶段决策问题,是把整个问题划分为若干阶段后,依次地为每一个阶段作出最优决策,而每个阶段的最优决策应该是包含本阶段和以后所有各阶段在内的最优决策。因此,在确定了第一个阶段的决策之后,整个问题的最优决策序列也就随之产生。这就是用动态规划解多阶段决策问题的基本思想。
3
以上面的例1来说明动态规划解决问题的思想。设:
Sk—第k阶段的起点(状态变量)
d(x, y) —第k阶段的从状态x 到状态y 的“距离”;
fk(sk) —第k阶段从状态Sk出发到终点E的“最短路”。
最短路线的重要特征是:如果最短路线在第k阶段通过点Pk。则由点Pk出发到达终点的这条路线,对于从点Pk出发到达终点的所有可能选择的不同路线来说,必定也是最短路线。
4
例如在最短路问题中,如果找到了从A到E的最短路:
则C2→D1→E应该是由C2 出发到E点的所有可能不同线路中的最短路线。
最短路线这一特性,启发我们找最短路线的方法:那就是从最后一段开始,用由后向前逐步递推的方法,求出各点到E点的最短路线,最后求得由A点到E点的最短路线。所以动态规划的常用的方法是从终点逐段向始点方向寻找“最短路线”。如图所示:
行进方向
起点
终点
动态规划寻优途径
5
下面按上述思想,将例1从最后一段开始计算,由后向前逐步推移至A点。
2
5
1
12
14
10
6
10
4
13
11
12
3
9
6
5
8
10
5
2
C1
C3
D1
A
B1
B3
B2
D2
E
C2
f5(E)=0
设想有k= 5, f5(E)= 0 。
6
2
5
1
12
14
10
6
10
4
13
11
12
3
9
6
5
8
10
5
2
C1
C3
D1
A
B1
B3
B2
D2
E
C2
f4(D2)=2
f5(E)=0
f4(D1)=5
K=4时:
7
2
5
1
12
14
10
6
10
4
13
11
12
3
9
6
5
8
10
5
2
C1
C3
D1
A
B1
B3
B2
D2
E
C2
f4(D2)=2
f5(E)=0
f4(D1)=5
K=3时:
8
2
5
1
12
14
10
6
10
4
13
11
12
3
9
6
5
8
10
5
2
C1
C3
D1
A
B1
B3
B2
D2
E
C2
f4(D2)=2
f5(E)=0
f3(C3)=12
f4(D1)=5
f3(C2)=7
f3(C1)=8
K=2时:
9
2
5
1
12
14
10
6
10
4
13
11
12
3
9
6
5
8
10
5
2
C1
C3
D1
A
B1
B3
B2
D2
E
C2
f4(D2)=2
f5(E)=0
f3(C3)=12
f4(D1)=5
f2(B3)=19
f3(C2)=7
f3(C1)=8
f1(A)=19
f2(B2)=14
f2(B1)=20
K=1时:
10