动态规划的最优性原理.ppt

运筹学,第五章动态规划,2动态规划的最优性原理,多阶段决策过程的特点是每个阶段都要进行决策，具有n个阶段的决策过程的策略是由n个相继进行的阶段决策构成的决策序列。由于前阶段的终止状态又是后一阶段的初始状态，因此确定阶段最优决策不能只从本阶段的效应出发，必须通盘考虑，整体规划。就是说，阶段k的最优决策不应只是本阶段的最优，而必须是本阶段及其所有后续阶段的总体最优，即关于整个后部子过程的最优决策。对此，贝尔曼在深入研究的基础上，针对具有无后效性的多阶段决策过程的特点，提出了著名的多阶段决策的最优性原理：“整个过程的最优策略具有这样的性质：即无论过程过去的状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。”简而言之，最优性原理的含意就是：最优策略的任何一部分子策略也必须是最优的。,如例1，AB2C1D2E是由A到E的最短路线，我们在该路线上任取一点C1，按照最优性原理C1D2E应该是C1到E的最短路。很容易用反证法证明这一结论的正确性，从而说明最优性原理的正确性。按最优性原理，可以将例1分成ABCDE4个阶段，由后向前逐步求出各点到E的最短线路，直至求出A至E的最短线路。,K=4时，出发点有D1，D2，D3，记f4（Di）（i=1,2,3）为Di到E的最短距离；u4(Di)表示从状态Di出发采取的决策。显然：f4（D1）=7，u4(D1)=Ef4（D2）=8，u4(D2)=Ef4（D3）=6，u4(D3)=EK=3时，出发点有C1，C2，C3,f3（C1）=mind（C1D1）+f4（D1）,d（C1D2）+f4（D2）=min4+7,2+8=10,u3(C1)=D2f3（C2）=mind（C2D2）+f4（D2）,d（C2D3）+f4（D3）=min5+8,7+6=13,u3(C2)=D2或D3f3（C3）=mind（C3D2）+f4（D2）,d（C3D3）+f4（D3）=min10+8,9+6=15,u3(C3)=D3,K=2时，出发点有B1，B2，B3f2（B1）=mind（B1C1）+f3（C1）,d（B1C2）+f3（C2）=min6+10,4+13=16,u2(B1)=C1f2（B2）=mind（B2C1）+f3（C1）,d（B2C3）+f3（C3）=min3+10,1+15=13,u2(B2)=C1f2（B3）=mind（B3C2）+f3（C2）,d（B3C3）+f3（C3）=min8+13,4+15=19,u2(B3)=C3K=1时，出发点只有Ad（AB1）+f2（B1）4+16f1（A）=mind（AB2）+f2（B2）=5+13=18,d（AB3）+f2（B3）3+19u1(A)=B2由f1（A）=18，可知从起点A到终点E的最短距离为18。,为了找出最短线路，再按计算顺序反推回去，可求出最优决策序列，即由u1(A)=B2，u2(B2)=C1，u3(C1)=D2，u4(D2)=E组成最优策略，也就是最短线路为：AB2C1D2E,从上面的例子不难看出，对于最短线路问题，有如下的递推关系（函数方程）：fk（xk）=mind（xk,uk(xk)）+fk+1（T(xk,uk)）fn+1（xn+1）=0k=n,n-1,1,一般情况下，多阶段决策问题存在下面的递推关系：fk（xk）=optrk(xk,uk(xk)fk+1（T(xk,uk)）ukDk(uk)fn+1（xn+1）=Ck=n,n-1,1这里rk(xk,uk(xk)是第阶段采用uk(xk)决策产生的阶段效应；fn+1（xn+1）=C是边界条件；“”号大多数情况下是“+”号，也可能是“”号。称上述递推关系为动态规划的基本方程，这个方程是最优化原理的具体表达形式。,在基本方程中，rk(xk,uk)，xk+1=T(xk,uk)都是已知函数，最优子策略fk（xk）与fk+1（xk+1）之间是递推关系，要求出fk（xk）及uk(xk)，需要先求出fk+1（xk+1），这就决定了应用动态规划基本方程求最优策略总是逆着阶段的顺序进行的。,另一方面，由于k+1阶段的状态xk+1=T(xk,uk)是由前面的状态和决策所形成的，在计算fk+1（xk+1）时还不能具体确定xk+