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

运筹学
第五章动态规划

§2 动态规划的最优性原理
多阶段决策过程的特点是每个阶段都要进行决策,具有n个阶段的决策过程的策略是由n个相继进行的阶段决策构成的决策序列。由于前阶段的终止状态又是后一阶段的初始状态,因此确定阶段最优决策不能只从本阶段的效应出发,必须通盘考虑,整体规划。就是说,阶段k的最优决策不应只是本阶段的最优,而必须是本阶段及其所有后续阶段的总体最优,即关于整个后部子过程的最优决策。
对此,贝尔曼在深入研究的基础上,针对具有无后效性的多阶段决策过程的特点,提出了著名的多阶段决策的最优性原理:
“整个过程的最优策略具有这样的性质:即无论过程过去的状态和决策如何,对前面的决策所形成的状态而言,余下的诸决策必须构成最优策略。”
简而言之,最优性原理的含意就是:最优策略的任何一部分子策略也必须是最优的。

如例1,A—B2—C1—D2—E是由A到E的最短路线,我们在该路线上任取一点C1 ,按照最优性原理C1—D2—E应该是C1到E的最短路。很容易用反证法证明这一结论的正确性,从而说明最优性原理的正确性。
按最优性原理,可以将例1分成A—B—C—D—E 4个阶段,由后向前逐步求出各点到E的最短线路,直至求出A至E的最短线路。
K=4时,出发点有D1,D2,D3,记
f4(Di)(i=1,2,3)为Di到E的最短距离;u4(Di)表示从状态Di出发采取的决策。显然: f4(D1)=7,u4(D1)=E
f4(D2)=8,u4(D2)=E
f4(D3)=6,u4(D3)=E
K=3时,出发点有C1,C2,C3
f3(C1)=min{d(C1D1)+f4(D1),d(C1D2)+f4(D2)}
=min{4+7,2+8}=10, u3(C1)= D2
f3(C2)=min{d(C2D2)+f4(D2),d(C2D3)+f4(D3)}
=min{5+8,7+6}=13, u3(C2)= D2或D3
f3(C3)=min{d(C3D2)+f4(D2),d(C3D3)+f4(D3)}
=min{10+8,9+6}=15, u3(C3)= D3
堵须涕下拴***
K=2时,出发点有B1,B2,B3
f2(B1)=min{d(B1C1)+f3(C1),d(B1C2)+f3(C2)}
=min{6+10,4+13}=16, u2(B1)= C1
f2(B2)=min{d(B2C1)+f3(C1),d(B2C3)+f3(C3)}
=min{3+10,1+15}=13, u2(B2)= C1
f2(B3)=min{d(B3C2)+f3(C2),d(B3C3)+f3(C3)}
=min{8+13,4+15}=19, u2(B3)= C3
K=1时,出发点只有A
d(AB1)+f2(B1) 4+16
f1(A)=min d(AB2)+f2(B2)= 5+13 =18,
d(AB3)+f2(B3