动态规划基本理论推广(函数迭代与策略迭代法)（PPT57页)

——函数迭代法与策略迭代法管理科学与系统工程举例简单说明不定期与无期决策过程的形式和概念；以不定期和无期决策过程为例，介绍函数迭代法和策略迭代法。管理科学与系统工程定义：多阶段的决策过程的阶段数N确定，称为定期决策过程，当N不确定时，称此类决策过程为不定期决策过程，当N趋向无穷时称为无期决策过程。管理科学与系统工程例1：段数不定的最短路线问题（不定期决策过程）n个点相互连接组成一个连通图(右图中n=5),各点标号为1,2,…,n。任意两点i，j之间的距离(费用)记作dij。求任意一点i到点n(靶点)的最短路线(距离)。51432322575560.51管理科学与系统工程例1：段数不定的最短路线问题（不定期决策过程）n个点相互连接组成一个连通图(右图中n=5),各点标号为1,2,…,n。任意两点i，j之间的距离(费用)记作dij。求任意一点i到点n(靶点)的最短路线(距离)。51432322575560.51管理科学与系统工程例2：无限期决策过程模型，状态变换函数为。(存在明显的级变量，但级数是无限的)管理科学与系统工程1jjjx2200minlimjjkkjzxV求解这类问题如果仍使用以前的逐级递推方法，将遇到极大的计算量，为此必需寻找新方法。函数方程可以用迭代法求解，通常有函数迭代法和策略迭代法两种迭代方法。管理科学与系统工程1.函数迭代法的步骤是：(1)选初始函数(一般取)；(2)用迭代公式及计算其中为当前阶段的状态和决策，为已知终止函数，为迭代步数,v为指标函数(3)当或管理科学与系统工程0()fx0()0fx1()()(,)((,)),kkuUxfxoptvxufTxuxX()(),knfxxxX(),1,2,,kfxk,xu()xk1()(),,kkfxfxxX1()()()kkkfxfxfx(4)当或时迭代停止，最优值函数，最优策略；否则以k+1代替k重复(2),(3).管理科学与系统工程1()(),,kkuxuxxX1()(),()kkkfxfxxXfx()()kfxfx()()kuxux说明：函数迭代法和策略迭代法中，序列和的收敛性在相当广泛的条件下是可以保证的，一般来说它与等的具体形式有关。函数迭代法的基本思想是以步数(段数)作为参数，先求在各个不同步数下的最优策略，然后从这些最优解中再选出最优者，从而同时确定了最优步数。管理科学与系统工程{(()}kfx{(()}kux(),(),(,),nUxTxvxuX策略迭代法的基本思想是：先选定一初始策略然后按某种方式求得新策略直至最终求出最优策略。若对某一k，对所有i有：，则称收敛，此时，策略就是最优策略。一般来说，选定初始策略要比选定初始目标最优值函数容易得多，且策略迭代的收敛速度稍快，但其计算量要大些。管理科学与系统工程{()1,2,,1}kuiin12(),(),,uiui1()()kkuiui12(),(),uiui{()1,2,,1}kuiin(是事先给定的数)时迭代停止，最优值函数,最优策略。2.策略迭代法的步骤是：(1)选初始策略，令k=1；(2)用求解，(3)用求改进策略，管理科学与系统工程xX()()kfxfx()()kuxux1()ux()kux()kfx()(,())((,())),.kkkkfxvxuxfTxuxxX()(),.knfxxxX()kfx1()kux1()()((,)((,))).kkuUxuxuoptvxufTxu例1的求解：分析：可以不考虑回路，因为含有回路的路线一定不是最短的.本问题路线的段数事先不固定，而是随着最优策略确定的，然而状态、决策、状态转移、指标函数与以前的最短路线问题的相同.状态记作x=i，i=1,2,…,n，决策记作u(i).策略是对任意状态x的决策函数，记作u(x)。阶段指标是任意两状态i,j间的距离dij，指标函数V(i,u(x))是由状态i出发，在策略u(x)下到达状态n的路线的管理科学与系统工程距离，它是阶段指标之和，并满足可分离性要求，有最优值函数ƒ(i)为由i出发到达n的最短距离，即式中u*(x)是最优策略，满足基本方程管理科学与系统工程(,())(,())ijViuxdVjux*()()min(,())(,())uxfiViuxViux1()min(),1,2,,1.ijjnfidfjin该式记为(﹡)式，它不是一个递推方程，而是一个关于ƒ(i)的函数方程,对固定的i使(﹡)右端[dij+ƒ(j)]达到极小的j即为最优决策u*(i)，对所有的i求解(﹡)式得到最优策略u*(x)。管理科学与系统工程例1：段数不定的最短路线问题（不定期决策过程）n个点相互连接组成一个连通图(右图中n=5),各点标号为1,2,…,n。任意两点i，j之间的距离(费用)记作dij。求任意一点i到点n(靶点)的最短路线(距离)。管理科学与系统工程用函数迭代法求解例1只求1,2,3,4各点到点5的最优路线，其余类似。解：(1)假设从i点走一步到靶点5的最优距离为,则显然有：最优决策为:管理科学与系统工程1()fi115(1)2fd(1)5u125(2)7fd135(3)5fd145(4)3fd155(5)0fd(2)5u(3)5u(4)5u(5)5u51432322575560.51(2)假设从i点走两步到靶点5的最优距离为,根据最优化原理得：具体计算如下：管理科学与系统工程2()fi21152()min(),1,2,3,4(5)0ijifidfjif21115(1)min()jifdfj111min[(1),df121131141151(2),(3),(4),(5)]dfdfdfdf注：不取含的地方作为最优决策管理科学与系统工程2(1)5umin[02,67,55,23,20]20ijd()ui22115(2)min()jifdfj211min[(1),df221231241251(2),(3),(4),(5)]dfdfdfdfmin[62,07,0.55,53,70]5.52(2)3u(3)假设从i点走三步到靶点5的最优距离为,则得：计算结果如下：管理科学与系统工程3()fi32153()min(),1,2,3,4(5)0ijifidfjif33(1)2,(1)5fu33(2)4.5,(2)3fu33(3)4,(3)4fu33(4)3,(4)5fu(4)假设从i点走四步到靶点5的最优距离为,则得：计算结果如下：管理科学与系统工程4()fi43154()min(),1,2,3,4(5)0ijifidfjif44(1)2,(1)5fu44(2)4.5,(2)3fu44(3)4,(3)4fu44(4)3,(4)5fu管理科学与系统工程23115(3)min()jifdfj311min[(1),df321331341351(2),(3),(4),(5)]dfdfdfdfmin[52,0.57,05,13,50]42(3)4u24115(4)min()jifdfj411min[(1),df421431441451(2),(3),(4),(5)]dfdfdfdfmin[22,57,15,03,30]32(4)5u由于只有5个点,因而从任一点出发到达靶点,其间最多有4步(否则，有回路)，这样就不需继续下去了。将计算结果列成表：管理科学与系统工程i1252525252755.534.534.533554444444353535351()fi1()ui2()fi3()fi4()fi2()ui3()ui4()ui分析上面的结果可得：①从点1到点5走一步为最优，最优距离为2，最优路线；从点2到点5走三步为最优，最优距离为4.5,最优路线；从点3到点5走两步为最优，最优距离为4,最优路线；从点4到点5走一步为最优，最优距离为3，最优路线。管理科学与系统工程11(1)5u3212(2)3(3)4(4)5uuu213(3)4(4)5uu14(4)5u②最优决策最多走4步，多于此步数，会出现走回头路或回路，显然这些不是最优路线。③从任一点出发到靶点，走m(m=1,2,…)步与走m+1步的最优距离一样，决策函数也一样，如果继续计算走m+2步、m+3步、……，其结果仍一样,即也就说明一致收敛于，一致收敛于。故当这种一出现，计算便可停止。管理科学与系统工程1()(),mmfifi1()(),mmuiui{()}mfi()fi{()}mui()ui例1的求解：(策略迭代法）解：①第一步，先选取初始策略。如取：即,但必需没有回路，每点可达靶点。第二步，由求，由策略迭代法的方程组可得：因策略直达靶点，应先计算：管理科学与系统工程1()ui1111(1)5,(2)4,(3)5,(4)3.uuuu1()ui1()fi11,()111()(())(5)0iuifidfuif11(1),(3)uu1{()}{5,4,5,3}ui第三步，由求,由求出它的解：时，管理科学与系统工程1151135114311241(1)(5)202(3)(5)505(4)(3)156(2)(4)5611fdffdffdffdf1()fi2()ui,()1()min[(())]iuiuidfui2()ui()1ui所以，（不在含的项取）时，管理科学与系统工程2(1)5uiid1,()1()111121131141151min[(())]min[(1),(2),(3),(4),(5)]min[02,611,55,26,20]2uiuidfuidfdfdfdfdf2(1)u()2ui2,()1()min[(())]min[62,011,0.55,56,70]5.5uiuidfui所以，同理，可求得,于是得到第一次策略迭代的结果为②以为初始策略继续反复使用第二、三步进行迭代。第二步：由求管理科学与系统工程2(2)3u2()ui2()ui22(3)5(4)5uu，2{()}{5,3,5,5}ui2()fi215235(1)2(3)5fdfd第三步：由求,即由求解。时，所以同理，求出故第二次策略迭代的结果为管理科学与系统工程3()ui2452232(4)3(2)(3)0.555.5fdfdf2()fi,()2()min[(())]iuiuidfui3()ui()1ui1,()2()min[(())]uiuidfuimin[02,65.5,55,23,20]23(1)5u333(2)3,(3)4,(4)5uuu3{()}{5,3,4,5}ui③第二步：由求第三步：由求，类似前面的方法求得第三次策略迭代的结果为管理科学与系统工程3()ui4{()}{5,3,4,5}ui3()fi31534533433233(1)2(4)3(3)(4)134(2)(3)0.544.5fdfdfdffdf3()fi4()uii1234545321156535525.553534524.5435345④将以上结果记录下来：管理科学与系统工程1()ui2()fi1()fi4()ui2()ui3()ui3()fi由以上结果得到，对所有的i都成立，说明迭代步骤可以停止。故找到最优策略为列表表示为从而可以得到各点到靶