文档介绍：动态规划 (Dynamic Programming)
动态规划是1951年由美国数学家贝尔曼(Richard Bellman)提出,它是解决一类多阶段决策问题的优化方法,也是考察问题的一种途径,而不是一种算法(如LP单纯形法)。因此它不象LP那样有一个标准的数学表达式和明确定义的一组规则,而必须对具体问题进行具体分析处理。
动态规划方法是现代企业管理中的一种重要决策方法。如果一个问题可将其过程划分为若干个相互联系的阶段问题,且它的每一阶段都需进行决策,则这类问题均可用动态规划方法进行求解。
根据多阶段决策过程的时序和决策过程的演变,动态规划方法有以下四种类型:离散确定型、离散随机型、连续确定型和连续随机型。
1
1 动态规划的基本概念和最优化原理
一、引例(最短路问题)
假如上图是一个线路网络,两点之间连线上的数字表示两点间的距离(或费用),我们的问题是要将货物从A地运往E地,中间通过B、C、D三个区域,在区域内有多条路径可走,现求一条由A到E的线路,使总距离最短(或总费用最小)。
A
B1
B2
B3
C1
C2
C3
D1
D2
E
2
4
3
7
4
6
3
2
4
2
6
5
3
4
6
3
3
3
3
4
2
将该问题划分为4个阶段的决策问题,即第一阶段为从A到Bj(j=1,2,3),有三种决策方案可供选择;第二阶段为从Bj到Cj(j=1,2,3),也有三种方案可供选择;第三阶段为从Cj到Dj(j=1,2),有两种方案可供选择;第四阶段为从Dj到E,只有一种方案选择。如果用完全枚举法,则可供选择的路线有3×3×2×1=18(条),将其一一比较才可找出最短路线:
A→B1→C2→D3→E
其长度为12。
显然,这种方法是不经济的,特别是当阶段数很多,各阶段可供的选择也很多时,这种解法甚至在计算机上完成也是不现实的。
由于我们考虑的是从全局上解决求A到E的最短路问题,而不是就某一阶段解决最短路线,因此可考虑从最后一阶段开始计算,由后向前逐步推至A点:
3
第四阶段,由D1到E只有一条路线,其长度f4(D1)=3,
同理f4(D2)=4。
第三阶段,由Cj到Di分别均有两种选择,即
,决策点为D1
,决策点为D1
,决策点为D2
4
第二阶段,由Bj到Cj分别均有三种选择,即:
决策点为C2
决策点为C1或C2
决策点为C2
5
第一阶段,由A到B,有三种选择,即:
决策点为B3
f1(A)=15说明从A到E的最短距离为12,最短路线的确定可按计算顺序反推而得。即
A→B3→C2→D2→E
上述最短路线问题的计算过程,也可借助于图形直观的表示出来:
6
图中各点上方框的数,表示该点到E的最短距离。图中红箭线表示从A到E的最短路线。
从引例的求解过程可以得到以下启示:
①对一个问题是否用上述方法求解,其关键在于能否将问题转化为相互联系的决策过程相同的多个阶段决策问题。
A
B1
B2
B3
C1
C2
C3
D1
D2
E
2
4
3
7
4
6
3
2
4
2
6
5
3
4
6
3
3
3
3
4
3
4
6
7
6
9
9
11
12
7
所谓多阶段决策问题是:把一个问题看作是一个前后关联具有链状结构的多阶段过程,也称为序贯决策过程。如下图所示:
②在处理各阶段决策的选取上,不仅只依赖于当前面临的状态,而且还要注意对以后的发展。即是从全局考虑解决局部(阶段)的问题。
③各阶段选取的决策,一般与“时序”有关,决策依赖于当前的状态,又随即引起状态的转移,整个决策序列就是在变化的状态中产生出来,故有“动态”含义。因此,把这种方法称为动态规划方法。
④决策过程是与阶段发展过程逆向而行。
8
二、多阶段决策问题的典型例子:
企业在生产过程中,由于需求是随着时间变化的因素,因此企业为了获得全年最佳经济效益,就要在整个生产过程中逐月或逐季的根据库存和需求决定生产计划。
某种机器,可以在高、低两种负荷下生产。高负荷下生产的产量多,但每生产一个阶段后机器的完好率低;低负荷下生产时的情况则相反。现在需要安排该种机器在多个阶段内的生产,问应该如何决定各阶段中机器的使用,使整个计划期内的总产量最大。
某台设备,例如汽车,刚买来时故障少,耗油低,出车时间长,处理价值和经济效益高。随着使用时间的增加则变为故障多,耗油高,维修费用增加,经济效益差。使用时间愈长,处理价值也愈低。另外,每次更新都要付出更新费用。因此,应当如何决定设备的使用年限,使总的效益最佳。
9
三、动态规划方法的特点
优点:①许多问题用动态规划研究求解比线性