文档介绍：信息系刘康泽
动态规划
动态规划是解决多阶段决策过程最优化问题的一种方法。()首先提出的。它可以把一个 n 维最优化问题转化为 n 个一维最优化问题来求解。
一个决策问题,往往可以分解成若干个相互联系,又相对独立的阶段,对于每一个阶段,存在着很多方案可供选择,我们要对每个阶段作出一个决策。
各阶段之间有密切的联系,某一个阶段的不同决策,将会对其它阶段的决策产生重大的影响,某个阶段局部的较优方案,未必是整个问题的最好方案,某个阶段局部的不好方案,也未必是整个问题的不好方案。
我们目标是:寻找整个问题,即所有阶段总体的一个最优方案,这就是动态规划所要讨论的问题。
一、多阶段决策问题
由于决策问题被划分为若干个相互联系的阶段,在任一阶段都有若干种方案可供选择,选择哪一个方案需要作出决策,这样就形成一个决策序列,通常称为一种策略。不同的策略就产生不同的效果,在所有可能的策略当中,选择一个效果最好的最优策略,就是解决多阶段决策问题的主要目的。
例1 (投资问题)一家公司有三个工厂,每个厂都需要进行扩建。公司用于扩建的资金总共为 7百万元。各个厂的投资方案及扩建后预期可获得的利润如表所示(单位:百万元)。现在公司要确定对各厂投资多少才能使公司的总利润达到最大。
在这个问题中,因为每个厂都有几种投资方案,所以要对每个作出一项决策,总共要作出三个决策。同时,这三个厂的总投资不能超过 7 万元。如果把每个厂看成是一个阶段,这就是一个多阶段的决策问题。
方案一
方案二
方案三
方案四
投资额
利润
投资额
利润
投资额
利润
投资额
利润
一厂
0
0
1
5
2
8
3
10
二厂
0
0
1
3
3
9
4
11
三厂
0
0
2
7
3
11
4
13
例2、(货船装载问题)有四种货物准备装到一艘货船上,
第i ( i=1,2,3,4 )种货物的单位重量是wi (单位:吨),其单位价值是vi (单位:千元),如表所示。
i
wi
vi
1
2
4
2
1
2
3
4
7
4
3
5
假定这艘货船的总载重量是100吨,现在要确定这四种货物应各装几箱才能使装载货物的总价值达到最大。
在这个问题中,因为对每一种货物要确定装载的箱数,也就是要作出一项决策,所以总共要作出四个决策。同时,各种货物的总重量不能超过10吨。如果把每一种货物看成是一个阶段,这也是一个多阶段的决策问题。
例3 (最短路程问题)从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
在这个问题中,从A到 B 1 , B2 , B3中的哪一个点要作出一项决策,从B 1 , B2 , B3某点到 C 1 , C2 , C3 中的哪一个点又要作出一项决策等等。所以总共要作出四个决策。因此, 我们可以把整个路程分为A,B ( 包括B 1 ,B2 , B3) , C ( 包括C 1 , C2 , C3 ) , D (包括D1和D2),E 四个阶段。这又是一个多阶段的决策问题。
二、动态规划的基本思想
用动态规划求解多阶段决策问题,需要依次地为每一个阶段作出最优决策,而每个阶段的最优决策应该是包含本阶段和所有以前各阶段在内的最优决策,也就是到本阶段为止,包含以前各阶段在内的最优总决策。因此,在确定了最后一个阶段的决策之后,整个问题的最优决策序列也就随之产生。这就是用动态规划解多阶段决策问题的基本思想。
以上面的例3来说明动态规划解决问题的思想。
设:Sk----第k阶段的起点(状态变量)
dk(x, y) -----第k阶段的顶点 x 到顶点 y 的“距离”;
fk(Sk) ------第k阶段从顶点Sk到终点的最短“路”。
最短路线的重要持性就是:如果最短路线在第k站通过点Pk 。则由点Pk出发到达终点的这条路线,对于从点Pk 出发到达终点的所有可能选择的不同路经来说,必定也是最短路线。例如,在最短路线问题中,如果找到了A到G的最短路:
则应该是由Dl 出发到G点的所有可能不同线路中的最短路线。
最短路线这一特性,启发我们找最短路线的方法: 先从最后一段开始,用由后向前逐步递推的方法,求出各点到G点的最短路线,最后求得由A点到G点的最短路线。所以, 动态规划的常用的方法是从