运筹学第08讲 动态规划.pptx

动态规划Dynamic programming驿站马车问题19世纪中叶，密苏里州的一个寻宝者决定去加州西部淘金。旅程需要乘坐驿站马车，途径那些有遭遇强盗袭击的危险的无人乡村。虽然他的出发点和目的地已定，但他有相当多的选择从哪个州中穿过。下图显示了可能路线，每个州都用字母表示，旅行方向在图中是从左到右的。因此从他的出发点A州（密苏里州）到目的地J州（加利福尼亚州），就需要4个阶段（驿站马车行驶）。于是，淘金者决定购买保险，每条路线的保单成本并不一样，淘金者决定选一条保单费用最便宜的路线。（每段保单的费用也如图所示）驿站马车问题7BE144H62336ACF2J4344I3431DG35驿站马车问题考虑：寻找每个连续阶段费用最省的方案？A B F I J(13)另一条A D F I J(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）=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求解sf*4（s）x*4H3JI4JN=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 x3sf3（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=2 x2 Sf2（s，x2）=csx2+f*3（x2）f*2（s）X*2EFG或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=1 X1Sf1（s，x1）=csx1+f*2（x1）f*1（s）X*1BCD或D结论7BE144H62336ACF2J4344I3431DG35动态规划问题的特征问题可以分为几个阶段，每一个阶段都有一个策略决策（xn）。每个阶段都有一些与那个阶段的开始有关的状态（sn）。每个阶段策略决策的结果都是从当前状态变到下一阶段开始的状态。设计求解过程是为整个问题找到一个最优策略最优性原理：已知目前状态，对于剩余阶段的最优解策略与先前阶段采用的策略无关。即最优决策要依据当前状态，而不是如何到那里。求解过程通过为最后阶段找到最优解开始。如果知道n+1阶段的最优策略，就可以确定第n阶段的