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

运筹学第五章动态规划 1 §2 动态规划的最优性原理多阶段决策过程的特点是每个阶段都要进行决策,具有 n 个阶段的决策过程的策略是由 n个相继进行的阶段决策构成的决策序列。由于前阶段的终止状态又是后一阶段的初始状态, 因此确定阶段最优决策不能只从本阶段的效应出发,必须通盘考虑,整体规划。就是说,阶段 k的最优决策不应只是本阶段的最优,而必须是本阶段及其所有后续阶段的总体最优,即关于整个后部子过程的最优决策。对此,贝尔曼在深入研究的基础上,针对具有无后效性的多阶段决策过程的特点,提出了著名的多阶段决策的最优性原理:“整个过程的最优策略具有这样的性质:即无论过程过去的状态和决策如何,对前面的决策所形成的状态而言,余下的诸决策必须构成最优策略。”简而言之,最优性原理的含意就是: 最优策略的任何一部分子策略也必须是最优的。 2 如例 1,A—B 2—C 1—D 2—E是由 A到E的最短路线,我们在该路线上任取一点 C 1,按照最优性原理 C 1—D 2—E应该是 C 1到 E的最短路。很容易用反证法证明这一结论的正确性,从而说明最优性原理的正确性。按最优性原理,可以将例 1分成 A—B—C—D— E 4 个阶段,由后向前逐步求出各点到 E的最短线路,直至求出 A至E的最短线路。例1 的线路网络图: A B1 B2 E B3 C2 C3 C1 D2 D3 D1 453 4 4 4 31 6 5 8 8 7 7 10 2 9 6 K=4 时,出发点有 D 1,D 2,D 3,记 f 4(D i)(i=1,2,3 )为D i到E的最短距离; u 4 (D i)表示从状态 D i出发采取的决策。显然: f 4(D 1)=7,u 4 (D 1 )=E f 4(D 2)=8,u 4 (D 2 )=E f 4(D 3)=6,u 4 (D 3 )=E K=3 时,出发点有 C 1,C 2,C 3 f 3(C 1)=min {d(C 1D 1)+f 4(D 1),d(C 1D 2)+f 4(D 2)} =min {4+7,2+8 }=10, u 3 (C 1 )= D 2 f 3(C 2)=min {d(C 2D 2)+f 4(D 2),d(C 2D 3)+f 4(D 3)} =min {5+8,7+6 }=13, u 3 (C 2 )= D 2或D 3 f 3(C 3)=min {d(C 3D 2)+f 4(D 2),d(C 3D 3)+f 4(D 3)} =min {10+8,9+6 }=15, u 3 (C 3 )= D 3 3 例1的线路网络图: A B1 B2 E B3 C2 C3 C1 D2 D3 D1 453 4 4 4 3 1 6 5 8 8 7 7 10 2 9 6 K=2 时,出发点有 B 1,B 2,B 3f 2(B 1)=min {d(B 1C 1)+f 3(C 1),d(B 1C 2)+f 3(C 2)} =min {6+10,4+13 }=16, u 2 (B 1 )= C 1 f 2(B 2)=min {d(B 2C 1)+f 3(C 1),d(B 2C 3)+f