运筹学之动态规划(new2009).ppt

1、动态规划,Dynamic programming,驿站马车问题,19世纪中叶，密苏里州的一个寻宝者决定去加州西部淘金。旅程需要乘坐驿站马车，途径那些有遭遇强盗袭击的危险的无人乡村。虽然他的出发点和目的地已定，但他有相当多的选择从哪个州中穿过。下图显示了可能路线，每个州都用字母表示，旅行方向在图中是从左到右的。因此从他的出发点A州（密苏里州）到目的地J州（加利福尼亚州），就需要4个阶段（驿站马车行驶）。 于是，淘金者决定购买保险，每条路线的保单成本并不一样，淘金者决定选一条保单费用最便宜的路线。（每段保单的费用也如图所示）,A,F,C,D,G,I,J,H,E,B,2,4,3,7,4,6,3,2,

2、4,4,1,5,1,4,6,3,3,3,3,4,驿站马车问题,驿站马车问题,考虑：寻找每个连续阶段费用最省的方案？ A B F I J(13) 另一条A D F I J(11) 解决方案：找出所有路线（18条) 动态规划：从原问题的很小的一个部分开始，给这个较小的问题寻找最优解，然后逐渐扩大问题，从前面的问题中找出目前最优解，然后取得全部问题的最优解。 从小问题开始，假设淘金者几乎完成了他的旅行，只剩下最后一个阶段了。然后依次重复，通过每次增加一个阶段来不断来扩大问题。,建模,令决策变量xn（n=1，2，3，4）为阶段n（要进行的n段驿站马车运行）的直接目的地。这样选择路线是AX1 X2 X3

3、 X4,其中X4=J。保单成本用cij表示。 设fn（s，xn）为剩余阶段整体最优成本，已知淘金者在s州，准备开始第n阶段并选择xn作为直接目的地。 最小化fn（s，xn），并设f*（s）为相应的fn（s，xn）的最小值。 f*（s）=Min fn（s，xn）= fn（s，x*），其中 fn（s，xn）=中间成本（阶段n）+最小未来成本（阶段n+1至终点）= csx +f*n+1（xn）。 而csx 的值由当前州（i=s)和直接目的地（j=xn）中的cij已给出。所以在第四阶段末将达到最终目的地J州，所以f*5（J）=0,求解,N=4 当淘金者只有一步要走时，他后来的路线完全由他目前所在的州（

4、H or J）和最终目的x4=J所决定。,N=3,淘金者还有2步走，假设淘金者在F州，他必须往下走到H州或J州，直接成本分别是CFH=6和Cfi=3。假设他选H州，他到达之后，最小额外成本是f*4（H)=3,所以这个决策成本是6+3=9.如果他选的是I州，全部成本是3+4=7，所以，最优选择是后者，x*3=I 同样，在其他两个可能有两步要走要走的州s=E和s=G开始，有类此计算。,N=3,N=2,此时，淘金者有三步要走，这里 f2(s,x2)=csx2+f*3(x2) 假设淘金者正在C州，他接着必须走到E州、F州或G州，直接成本是cCE=3,cCF=2或cCG=4，到达之后，第三阶段最小成本如

5、n=3的表，分别为 x2=E: f2(C,E)=cCE+f*3(E)=3+4=7 x2=F: f2(C,F)=cCF+f*3(F)=2+7=9 x2=G: f2(C,G)=cCG+f*3(G)=4+6=10 显然，C到终点最小成本是f*2(C)=7,直接目的应为x*2=E 同理从B或D开始计算，有类似计算,N=2,N=1,淘金者走第一步的问题包含了全部要走的4个阶段。但目前只有一个可能开始的周s=A. x1=B: f1(A,B)=cAB+f*3(B)=2+11=13 x1=C: f1(A,C)=cAC+f*3(C)=4+7=11 x1=D: f1(A,D)=cAD+f*3(D)=3+8=11

6、由此可知A到终点最小成本是f*1(A)=11,直接目的应为x*1=C或D,N=1,A,F,C,D,G,I,J,H,E,B,2,4,3,7,4,6,3,2,4,4,1,5,1,4,6,3,3,3,3,4,结论,动态规划问题的特征,问题可以分为几个阶段，每一个阶段都有一个策略决策（xn）。 每个阶段都有一些与那个阶段的开始有关的状态（sn）。 每个阶段策略决策的结果都是从当前状态变到下一阶段开始的状态。 设计求解过程是为整个问题找到一个最优策略 最优性原理：已知目前状态，对于剩余阶段的最优解策略与先前阶段采用的策略无关。即最优决策要依据当前状态，而不是如何到那里。 求解过程通过为最后阶段找到最优解

7、开始。 如果知道n+1阶段的最优策略，就可以确定第n阶段的最优策略，因此可以得到一种递推关系。（当第n阶段从s状态开始时找出的最优最优决策策略，就需要找到xn的最小值，于是通过使用xn的值求得相关的最小成本，然后遵循你在n+1阶段时开始于xn状态的最优策略。,1、阶段k：表示决策顺序的离散的量，阶段可以按时间或空间划分。 2、状态sk：能确定地表示决策过程当前特征的量。状态可以是数量，也可以是字符，数量状态可以是连续的，也可以是离散的。 3、决策xk：从某一状态向下一状态过渡时所做的选择。决策是所在状态的函数，记为xk(sk)。 决策允许集合Dk(sk)：在状态sk下，允许采取决策的全体。 4

8、、策略Pk,n(sk)：从第k阶段开始到最后第n阶段的决策序列，称k子策略。P1,n(s1)即为全过程策略。 5、状态转移方程 sk+1=Tk(sk, xk)：某一状态以及该状态下的决策，与下一状态之间的函数关系。,基本概念,6、阶段指标函数vk(sk, xk)：从状态sk出发，选择决策xk所产生的第k阶段指标。 过程指标函数Vk,n(sk, xk, xk+1, xn)：从状态sk出发，选择决策xk, xk+1, , xn所产生的过程指标。动态规划要求过程指标具有可分离 性，即 Vk,n(sk, xk, xk+1, , xn) = vk(sk, xk)+Vk+1(sk+1, xk+1, , x

9、n) 称指标具有可加性，或 Vk,n(sk, xk, xk+1, , xn) = vk(sk, xk)Vk+1(sk+1, xk+1, , xn)称指标具有可乘性。 二、基本方程： 最优指标函数fk(sk)：从状态sk出发，对所有的策略Pk,n，过程指 标Vk,n的最优值，即,基本概念、基本方程,对于可加性指标函数，上式可以写为 上式中“opt”表示“max”或“min”。对于可乘性指标函数，上式可以 写为 以上式子称为动态规划最优指标的递推方程，是动态规划的基本 方程。 终端条件：为了使以上的递推方程有递推的起点，必须要设定最 优指标的终端条件，一般最后一个状态n+1下最优指标fn+1(sn

10、+1) = 0。,基本方程,作为整个过程的最优策略具有如下性质： 不管在此最优策略上的某个状态以前的状 态和决策如何，对该状态来说，以后的所有决 策必定构成最优子策略。就是说，最优策略的 任意子策略都是最优的。,最优化原理,练习,下图表示从起点A到终点E之间各点的距离。求A到E的最 短路径。,B,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,N=4,第四阶段：两个始点D1和D2，终点只有一个； 分析得知：从D1和D2到E的最短路径唯一。,第三阶段：有三个始点C1，C2，C3，终点

11、有D1，D2，对始点和终点进行分析和讨论分别求C1，C2，C3到D1，D2 的最短路径问题： 分析得知：如果经过C1，则最短路为C1-D2-E； 如果经过C2，则最短路为C2-D2-E； 如果经过C3，则最短路为C3-D1-E。,N=3,第二阶段：有4个始点B1,B2,B3,B4，终点有C1,C2,C3。对始点和终点进行分 析和讨论分别求B1,B2,B3,B4到C1,C2,C3 的最短路径问题： 分析得知：如果经过B1，则走B1-C2-D2-E； 如果经过B2，则走B2-C3-D1-E； 如果经过B3，则走B3-C3-D1-E； 如果经过B4，则走B4-C3-D1-E。,N=2,第一阶段：只有

12、1个始点A，终点有B1,B2,B3,B4 。对始点和终点进行分析和讨论分别求A到B1,B2,B3,B4的最短路径问题： 最后，可以得到：从A到E的最短路径为A B4 C3 D1 E,N=1,动态规划的求解方法,一、逆推法,1.基本公式,实例,解：令,二、顺推法,1.基本公式,由于终止状态sn1已知， 故xn=xn(Sn+1)和fn(Sn+1)是可以确定的,这样按照上述递推过程相反的顺序推算下去， 就可逐步确定出每阶段的决策与收益。,2.实例,资源分配问题 某公司拟将某种设备5台，分配给所属的甲、乙、丙三个工 厂。各工厂获得此设备后，预测可创造的利润如表所示，问这 5台设备应如何分配给这3个工厂

13、，使得所创造的总利润为最大？,动态规划的应用,解：将问题按工厂分为三个阶段，甲、乙、丙三个厂分别编号为1、2、3厂。设 sk= 分配给第k个厂至第3个厂的设备台数（k=1、2、 3）。 xk=分配给第k个设备台数。 已知s1=5, 并有 从与的定义，可知 以下我们从第三阶段开始计算。,动态规划的应用,第三阶段: 显然将台设备都分配给第3工厂时， 也就是时，第3阶段的指标值（即第3厂的盈利） 为最大，即 由于第3阶段是最后的阶段，故有 其中可取值为0,1,2,3,4,5。其数值计算见下表。,动态规划的应用,动态规划的应用,其中表示取3子过程上最优指标值时的 决策，例如在表中可知当=4时，有有 此

14、时，即当时，此时取 （把4台设备分配给第3厂）是最优决策，此时阶段指标值 （盈利）为12，最优3子过程最优指标值也为12。 第二阶段： 当把台设备分配给第2工厂和第3工 厂时，则对每个值，有一种最优分配方案，使最大盈利 即最优2子过程最优指标函数值为,动态规划的应用,因为上式也可写成 其数值计算如表所示。,动态规划的应用,其中在的这一行里，当时， 这里从表中可知，把1台设备交给乙厂所得盈 利数即可，知，这里从表106查 即可知=11。同样可知当时，可知 ; 当时，；当时， ；当时， ；由于，不可能分2厂5 台设备，故时，栏空着不填。从 这些数值中取得最大即得，即有=16。在此行中 我们在取最大值的 上面加一横以示 区别，也可知这时的最优决策为1或2。,动态规划的应用,第一阶段： 把台设备分配给第1，第2，第3厂时，最大 盈利为其中可取值0,1,2,3,4,5. 数值计算