运筹学之动态规划(new2009)

动态规划Dynamicprogramming驿站马车问题19世纪中叶，密苏里州的一个寻宝者决定去加州西部淘金。旅程需要乘坐驿站马车，途径那些有遭遇强盗袭击的危险的无人乡村。虽然他的出发点和目的地已定，但他有相当多的选择从哪个州中穿过。下图显示了可能路线，每个州都用字母表示，旅行方向在图中是从左到右的。因此从他的出发点A州（密苏里州）到目的地J州（加利福尼亚州），就需要4个阶段（驿站马车行驶）。于是，淘金者决定购买保险，每条路线的保单成本并不一样，淘金者决定选一条保单费用最便宜的路线。（每段保单的费用也如图所示）AFCDGIJHEB24374632441514633334驿站马车问题驿站马车问题考虑：寻找每个连续阶段费用最省的方案？ABFIJ(13)另一条ADFIJ(11)解决方案：找出所有路线（18条)动态规划：从原问题的很小的一个部分开始，给这个较小的问题寻找最优解，然后逐渐扩大问题，从前面的问题中找出目前最优解，然后取得全部问题的最优解。从小问题开始，假设淘金者几乎完成了他的旅行，只剩下最后一个阶段了。然后依次重复，通过每次增加一个阶段来不断来扩大问题。建模令决策变量xn（n=1，2，3，4）为阶段n（要进行的n段驿站马车运行）的直接目的地。这样选择路线是A→X1→

X2→

X3→

X4,其中X4=J。保单成本用cij表示。设fn（s，xn）为剩余阶段整体最优成本，已知淘金者在s州，准备开始第n阶段并选择xn作为直接目的地。最小化fn（s，xn），并设f*（s）为相应的fn（s，xn）的最小值。f*（s）=Minfn（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当淘金者只有一步要走时，他后来的路线完全由他目前所在的州（HorJ）和最终目的x4=J所决定。sf*4（s）x*4H3JI4JN=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=3x3sf3（s，x3）=csx3+f*4（x3）f*3（s）X*3HIE484HF977IH676HN=2此时，淘金者有三步要走，这里f2(s,x2)=csx2+f*3(x2)假设淘金者正在C州，他接着必须走到E州、F州或G州，直接成本是cCE=3,cCF=2或cCG=4，到达之后，第三阶段最小成本如n=3的表，分别为x2=E:f2(C,E)=cCE+f*3(E)=3+4=7x2=F:f2(C,F)=cCF+f*3(F)=2+7=9x2=G:f2(C,G)=cCG+f*3(G)=4+6=10显然，C到终点最小成本是f*2(C)=7,直接目的应为x*2=E同理从B或D开始计算，有类似计算N=2x2Sf2（s，x2）=csx2+f*3（x2）f*2（s）X*2EFGB11111211E或FC79107ED88118E或FN=1淘金者走第一步的问题包含了全部要走的4个阶段。但目前只有一个可能开始的周s=A.x1=B:f1(A,B)=cAB+f*3(B)=2+11=13x1=C:f1(A,C)=cAC+f*3(C)=4+7=11x1=D:f1(A,D)=cAD+f*3(D)=3+8=11由此可知A到终点最小成本是f*1(A)=11,直接目的应为x*1=C或DN=1X1Sf1（s，x1）=csx1+f*2（x1）f*1（s）X*1BCDA13111111C或DAFCDGIJHEB24374632441514633334结论动态规划问题的特征问题可以分为几个阶段，每一个阶段都有一个策略决策（xn）。每个阶段都有一些与那个阶段的开始有关的状态（sn）。每个阶段策略决策的结果都是从当前状态变到下一阶段开始的状态。设计求解过程是为整个问题找到一个最优策略最优性原理：已知目前状态，对于剩余阶段的最优解策略与先前阶段采用的策略无关。即最优决策要依据当前状态，而不是如何到那里。求解过程通过为最后阶段找到最优解开始。如果知道n+1阶段的最优策略，就可以确定第n阶段的最优策略，因此可以得到一种递推关系。（当第n阶段从s状态开始时找出的最优最优决策策略，就需要找到xn的最小值，于是通过使用xn的值求得相关的最小成本，然后遵循你在n+1阶段时开始于xn状态的最优策略。

1、阶段k：表示决策顺序的离散的量，阶段可以按时间或空间划分。

2、状态sk：能确定地表示决策过程当前特征的量。状态可以是数量，也可以是字符，数量状态可以是连续的，也可以是离散的。

3、决策xk：从某一状态向下一状态过渡时所做的选择。决策是所在状态的函数，记为xk(sk)。决策允许集合Dk(sk)：在状态sk下，允许采取决策的全体。

4、策略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,…,xn)称指标具有可加性，或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+1)=0。

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

阶段4本阶段始点（状态）本阶段各终点（决策）到E的最短距离本阶段最优终点（最优决策)ED1D210*6106EE

第三阶段：有三个始点C1，C2，C3，终点有D1，D2，对始点和终点进行分析和讨论分别求C1，C2，C3到D1，D2

的最短路径问题：

分析得知：如果经过C1，则最短路为C1-D2-E；如果经过C2，则最短路为C2-D2-E；如果经过C3，则最短路为C3-D1-E。

N=3

阶段3本阶段始点（状态）本阶段各终点（决策）到E的最短距离本阶段最优终点（最优决策)D1D2C1C2C38+10=187+10=171+10=116+6=125+6=116+6=12121111D2D2D1第二阶段：有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

阶段2本阶段始点（状态）

本阶段各终点（决策）到E的最短距离本阶段最优终点（最优决策)C1C2C3B1B2B3B42+12=144+12=164+12=167+12=191+11=127+11=188+11=195+11=166+11=172+11=133+11=141+11=1212131412C2C3C3C3第一阶段：只有1个始点A，终点有B1,B2,B3,B4

。对始点和终点进行分析和讨论分别求A到B1,B2,B3,B4的最短路径问题：

最后，可以得到：从A到E的最短路径为A

B4

C3

D1

EN=1

阶段1本阶段始点(状态)

本阶段各终点（决策）到E的最短距离本阶段最优终点(最优决策)B1B2B3B4A4+12=163+13=163+14=172+12=1414C2动态规划的求解方法一、逆推法1.基本公式已知初始状态为。并假定最优值函数表示第k阶段的初始状态为，从k阶段到n所得到的最大效益。从n阶段开始，则有得到最优解和最优值在n－1阶段有其中得到最优解和最优值在第k阶段有其中得到最优解和最优值如此类推，直到第1阶段有其中得到最优解和最优值由于初始状态s1已知，故是可以确定的,和从而和是可以确定的，于是和也就可以确定。这样按照上述递推过程相反的顺序推算下去，就可逐步确定出每阶段的决策与收益。实例解：令二、顺推法1.基本公式从第一阶段开始，则有得到最优解和最优值其中在第二阶段有其中得到最优解和最优值如此类推，直到第n阶段有其中得到最优解和最优值由于终止状态sn＋1已知，故xn=xn(Sn+1)和fn(Sn+1)是可以确定的这样按照上述递推过程相反的顺序推算下去，就可逐步确定出每阶段的决策与收益。2.实例解：范围资源分配问题

某公司拟将某种设备5台，分配给所属的甲、乙、丙三个工厂。各工厂获得此设备后，预测可创造的利润如表所示，问这5台设备应如何分配给这3个工厂，使得所创造的总利润为最大？

盈利工厂设备台数

甲厂

乙厂

丙厂000013542710639111141211125131112

动态规划的应用解：将问题按工厂分为三个阶段，甲、乙、丙三个厂分别编号为1、2、3厂。设

sk=分配给第k个厂至第3个厂的设备台数（k=1、2、3）。

xk=分配给第k个设备台数。已知s1=5,

并有

从与的定义，可知

以下我们从第三阶段开始计算。动态规划的应用

第三阶段:

显然将台设备都分配给第3工厂时，也就是时，第3阶段的指标值（即第3厂的盈利）为最大，即

由于第3阶段是最后的阶段，故有其中可取值为0,1,2,3,4,5。其数值计算见下表。

动态规划的应用

0

1

2

3

4

5

0

0－－－－－00

1－4－－－－41

2－－6－－－62

3－－－11－－113

4－－－－12－124

5－－－－－12125

动态规划的应用

其中表示取3子过程上最优指标值时的决策，例如在表中可知当=4时，有有此时，即当时，此时取（把4台设备分配给第3厂）是最优决策，此时阶段指标值（盈利）为12，最优3子过程最优指标值也为12。第二阶段：

当把台设备分配给第2工厂和第3工厂时，则对每个值，有一种最优分配方案，使最大盈利即最优2子过程最优指标函数值为

动态规划的应用因为上式也可写成其数值计算如表所示。

0

1

2

3

4

5

0－－－－－00

10＋4

－－－－51

20＋6

5＋4－－－102

30＋11

5＋6

11＋0－－142

40＋12

11＋4

11＋0－161,2

50＋12

5＋12

11＋6

11＋4

11＋0

212

动态规划的应用