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

1、函数迭代法与策略迭代法管理科学与系统工程举例简单说明不定期与无期决策过程的形式和概念；以不定期和无期决策过程为例，介绍函数迭代法和策略迭代法。管理科学与系统工程定义：多阶段的决策过程的阶段数N确定，称为定期决策过程，当N不确定时，称此类决策过程为不定期决策过程，当N趋向无穷时称为无期决策过程。管理科学与系统工程例1：段数不定的最短路线问题（不定期决策过程）n个点相互连接组成 一个连通图(右图中n=5),各点标号为1,2,n。任意两点i，j之间的距离(费用)记作dij 。求任意一点i到点n(靶点)的最短路线(距离)。5143232257 5560.51管理科学与系统工程例1：段数不定的最短路线问

2、题（不定期决策过程）n个点相互连接组成 一个连通图(右图中n=5),各点标号为1,2,n。任意两点i，j之间的距离(费用)记作dij 。求任意一点i到点n(靶点)的最短路线(距离)。5143232257 5560.51管理科学与系统工程例2：无限期决策过程模型 ，状态变换函数为。( 存在明显的级变量，但级数是无限的 )管理科学与系统工程1jjjx2200minlimjjkkjzxV求解这类问题如果仍使用以前的逐级递推方法，将遇到极大的计算量，为此必需寻找新方法。函数方程可以用迭代法求解，通常有函数迭代法和策略迭代法两种迭代方法。管理科学与系统工程1.函数迭代法的步骤是：(1)选初始函数 (一般

3、取 )；(2)用迭代公式及 计算其中为当前阶段的状态和决策， 为已知终止函数， 为迭代步数, v为指标函数(3)当或管理科学与系统工程0( )fx0( )0fx 1( )( )( , )( ( , ) ,kku U xfxopt v x ufT x uxX( )( ),knfxx xX( ),1,2,kfx k , x u( ) xk1( )( ),kkfxfx xX1( )( )( )kkkfxfxfx(4)当或时迭代停止，最优值函数，最优策略 ；否则以k+1代替k重复(2),(3).管理科学与系统工程1( )( ),kkuxux xX1( )( ),( )kkkfxfxxXfx( )( )

4、kf xfx( )( )kuxux说明：函数迭代法和策略迭代法中，序列 和 的收敛性在相当广泛的条件下是可以保证的，一般来说它与 等的具体形式有关。函数迭代法的基本思想是以步数(段数)作为参数，先求在各个不同步数下的最优策略，然后从这些最优解中再选出最优者，从而同时确定了最优步数。管理科学与系统工程( )kfx( )kux( ), ( ), ( , ),nU x T x v x uX策略迭代法的基本思想是：先选定一初始策略 然后按某种方式求得新策略 直至最终求出最优策略。若对某一k，对所有i有： ，则称 收敛，此时，策略就是最优策略。一般来说，选定初始策略要比选定初始目标最优值函数容易得多，且

5、策略迭代的收敛速度稍快，但其计算量要大些。管理科学与系统工程( )1,2,1ku i in12( ),( ),u i u i 1( )( )kkuiu i12( ),( ),u i u i ( )1,2,1ku i in ( 是事先给定的数)时迭代停止，最优值函数,最优策略 。2.策略迭代法的步骤是：(1)选初始策略 ，令k=1；(2)用 求解 ，(3)用 求改进策略 ，管理科学与系统工程xX( )( )kf xfx( )( )kuxux1( )u x( )kux( )kfx( )( ,( )( ( ,( ),.kkkkfxv x uxf T x uxxX( )( ),.knfxx xX( )

6、kfx1( )kux1( )( )( , )( ( , ) ).kku U xuxu opt v x uf T x u例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出

7、发到达n的最短距离，即式中u*(x)是最优策略，满足基本方程 管理科学与系统工程( ,()(,()ijVi u xdVj u x*( )( )min( , ( )( ,( )u xf iV i u xV i ux1( )min( ) ,1,2,1.ijj nf idf jin 该式记为()式，它不是一个递推方程，而是一个关于(i)的函数方程,对固定的i使()右端 dij+(j) 达到极小的j即为最优决策u*(i)，对所有的i求解()式得到最优策略u*(x)。管理科学与系统工程例1：段数不定的最短路线问题（不定期决策过程）n个点相互连接组成 一个连通图(右图中n=5),各点标号为1,2,n。任意

8、两点i，j之间的距离(费用)记作dij 。求任意一点i到点n(靶点)的最短路线(距离)。管理科学与系统工程用函数迭代法求解例1只求1,2,3,4各点到点5的最优路线，其余类似。解：(1)假设从i点走一步到靶点5的最优距离为 , 则显然有： 最优决策为:管理科学与系统工程1( )f i115(1)2fd(1)5u125(2)7fd135(3)5fd145(4)3fd155(5)0fd(2)5u(3)5u(4)5u(5)5u5122257 5560.5 (2)假设从i点走两步到靶点5的最优距离为 , 根据最优化原理得：具体计算如下：管理科学与系统工程2( )f i21152( )min( ) ,1

9、,2,3,4(5)0ijif idfjif 21115(1)min( )jifdfj 111min(1),df121131141151(2),(3),(4),(5)dfdfdfdf 注：不取含 的地方作为最优决策管理科学与系统工程2(1)5umin02,67,55,23,2020ijd ( )u i22115(2)min( )jifdfj 211min(1),df221231241251(2),(3),(4),(5)dfdfdfdfmin62,07,0.55,53,705.52(2)3u (3)假设从i点走三步到靶点5的最优距离为 , 则得：计算结果如下：管理科学与系统工程3( )f i321

10、53( )min( ) ,1,2,3,4(5)0ijif idfjif 33(1)2,(1)5fu33(2)4.5,(2)3fu33(3)4,(3)4fu33(4)3,(4)5fu (4)假设从i点走四步到靶点5的最优距离为 , 则得：计算结果如下：管理科学与系统工程4( )f i43154( )min( ) ,1,2,3,4(5)0ijif idfjif 44(1)2,(1)5fu44(2)4.5,(2)3fu44(3)4,(3)4fu44(4)3,(4)5fu 管理科学与系统工程23115(3)min( )jifdfj 311min(1),df321331341351(2),(3),(4)

11、,(5)dfdfdfdfmin52,0.57,05,13,5042(3)4u24115(4)min( )jifdfj 411min(1),df421431441451(2),(3),(4),(5)dfdfdfdfmin22,57,15,03,3032(4)5u 由于只有5个点,因而从任一点出发到达靶点,其间最多有4步(否则，有回路)，这样就不需继续下去了。将计算结果列成表：管理科学与系统工程i1252525252755.534.534.533554444444353535351( )f i1( )u i2( )f i3( )f i4( )f i2( )u i3( )u i4( )u i 分析上

12、面的结果可得：从点1到点5走一步为最优，最优距离为2，最优路线 ；从点2到点5走三步为最优，最优距离为4.5,最优路线 ；从点3到点5走两步为最优，最优距离为4,最优路线 ；从点4到点5走一步为最优，最优距离为3，最优路线 。管理科学与系统工程11(1)5u3212(2)3(3)4(4)5uuu213(3)4(4)5uu14(4)5u 最优决策最多走4步，多于此步数，会出现走回头路或回路，显然这些不是最优路线。 从任一点出发到靶点，走m(m=1,2,)步与走m+1步的最优距离一样，决策函数也一样，如果继续计算走m+2步、m+3步、，其结果仍一样, 即 也就说明 一致收敛于 ， 一致收敛于 。故

13、当这种一出现，计算便可停止。管理科学与系统工程1( )( ),mmfifi1( )( ),mmuiui( )mfi( )f i( )mui( )u i例1的求解：(策略迭代法） 解：第一步，先选取初始策略 。如取：即 ,但必需没有回路，每点可达靶点。第二步，由 求 ，由策略迭代法的方程组可得：因策略 直达靶点，应先计算：管理科学与系统工程1( )u i1111(1)5,(2)4,(3)5,(4)3.uuuu1( )u i1( )f i11,( )111( )( )(5)0i uif idf u if11(1),(3)uu1 ( )5,4,5,3u i第三步，由 求 ,由求出它的解 ：时，管理科

14、学与系统工程1151135114311241(1)(5)202(3)(5)505(4)(3)156(2)(4)5611fdffdffdffdf 1( )f i2( )u i, ( )1( )min( ( )i u iu idf u i2( )u i( )1u i 所以， （不在含 的项取 ） 时，管理科学与系统工程2(1)5uiid1, ( )1( )111121131141151min( ( )min(1),(2),(3),(4),(5)min02,611,55,26,202u iu idf u idfdfdfdfdf2(1)u( )2u i 2, ( )1( )min( ( )min62,

15、011,0.55,56,705.5u iu idf u i所以，同理，可求得 ,于是得到第一次策略迭代的结果为以 为初始策略继续反复使用第二、三步进行迭代。第二步：由 求管理科学与系统工程2(2)3u2( )u i2( )u i22(3)5(4)5uu，2( )5,3,5,5u i2( )f i215235(1)2(3)5fdfd第三步：由 求,即由求解 。 时，所以同理，求出故第二次策略迭代的结果为管理科学与系统工程3( )u i2452232(4)3(2)(3)0.555.5fdfdf2( )f i, ( )2( )min( ( )i u iu idf u i3( )u i( )1u i

16、1, ( )2( )min( ( )u iu idf u imin02,65.5,55,23,2023(1)5u333(2)3,(3)4,(4)5uuu3( )5,3,4,5u i第二步：由 求第三步：由 求，类似前面的方法求得第三次策略迭代的结果为管理科学与系统工程3( )u i4( )5,3,4,5u i3( )f i31534533433233(1)2(4)3(3)(4)134(2)(3)0.544.5fdfdfdffdf 3( )f i4( )u ii1234545321156535525.553534524.5435345将以上结果记录下来：管理科学与系统工程1( )u i2( )f

17、 i1( )f i4( )u i2( )u i3( )u i3( )f i由以上结果得到 ，对所有的i都成立，说明迭代步骤可以停止。故找到最优策略为列表表示为从而可以得到各点到靶点(点5)的最优路线和最优距离：管理科学与系统工程34( )( )u iu i( )5,3,4,5u ii12345345( )u i最优路线 最短距离值 2 4.5 4 3可以看到策略迭代法得到的结果与函数迭代法的结果一致。管理科学与系统工程例2：无限期决策过程模型 ，状态变换函数为。( 存在明显的级变量，但级数是无限的 )管理科学与系统工程1jjjx2200minlimjjkkjzxV例2的求解（函数迭代法）解：(

18、1)任取初值，如状态变换函数为迭代公式为(2)i=1时，进行第一次迭代管理科学与系统工程20( )2g( , )Txx221( )min( )iixgxg2210( )min( )xgxg2221min2() min( , )xxxxGx 对 求导，并令其等于零，有 可得管理科学与系统工程222122( )()2() 33g 2251.66731G124()0Gxxx12( )0.6663x ，取i=2时，进行第二次迭代对 求导，并令其等于零，得管理科学与系统工程10( )( )gg2221( )min( )xgxg22225min() 3min( , )xxxxGx2G2102()03Gxx

19、x故由于 ，应继续进行迭代。当i=3时，进行第三次迭代，类似以上才方法，可得管理科学与系统工程25( )0.6258x 2222555( )()() 838g 22131.625821( )( )gg由于 ,取i=4继续进行第四次迭代。其结果如下:管理科学与系统工程313( )0.61921x 2223131313( )()() 21821g 22341.6192132( )( )gg由于 ,可以确定该问题的最优收益函数为最优决策为管理科学与系统工程434( )0.61855x 2224343434( )()() 552155g 22891.6185543( )( )gg2()1.618jg(

20、)0.618jjx 例2的求解（策略迭代法）解：(1)任取初始策略值，如及(2)进行第一次迭代，取i=1,2,得管理科学与系统工程0( )x ,0( )0 (1,2,3,)jgj( )( )min ( , ( )( ( , ( )xgfxg Tx0,100,00( )( ,( )( ( ,( )gfxgTx222()02 由于取 再来确定第二次迭代的决策 ： 管理科学与系统工程20( )2g0,20,1( )( )gg0,200,10( )( ,( )( ( ,( )gfxgTx2222()2()2 1( )x02222211111( ( , )( )2( )( )2 ( )4( )0 xg

21、Txxxxxxx上式的解为 由于，需要进行第二次迭代： 管理科学与系统工程10( )( )xx12( )0.6663x 1,111,01( )( ,( )( ( ,( )gfxgTx2222213()01.44439 1,211,11( )( ,( )( ( ,( )gfxgTx222222132130()()1.60539381 由于 ，需要继续进行迭代，直到 时为止，节省时间，直接给出结果 ，但由于 ，因此需要继续进行迭代。现在来确定第三次迭代的决策，有管理科学与系统工程1,21,1( )( )gg1,11,( )( )iigg211,( )( )1.625igg210( )( )2gg2

22、( )x12222222222( ( , )( )1.625( )( )2( )3.25( )0 xg Txxxxxxx则由于，还必须进行下次迭代。第三次迭代：管理科学与系统工程213( )0.61921x 21( )( )xx2,122,02( )( ,( )( ( ,( )gfxgTx222213610()01.38321441 2,222,12( )( ,( )( ( ,( )gfxgTx22221361013()()1.5832144121 由于 ，需要继续进行迭代，直到 时为止，最后得到 由于 ，因此需要继续进行迭代。现在来确定第四次迭代的决策，有管理科学与系统工程2,22,1( )

23、( )gg2,12,( )( )iigg222,( )( )1.618igg21( )( )gg3( )x22222233333( ( , )( )1.618( )( )2( )3.236( )0 xg Txxxxxxx则第四次迭代：管理科学与系统工程3( )0.618x 3,133,03( )( ,( )( ( ,( )gfxgTx222( 0.618 )01.382 3,233,13( )( ,( )( ( ,( )gfxgTx2222( 0.618 )1.382(0.618 )1.583 继续进行迭代，直到 时为止，最后得到 由于 ，因此可停止迭代。最优收益函数为 相应的最优策略为管理科

24、学与系统工程3,13,( )( )iigg23( )1.618g32( )( )gg2()1.618jjg()0.618jjjx 注：对于定义一个无期决策过程的最优化问题，须满足三个条件，即对所有的有：状态转移方程有意义；允许决策集合 有意义，而且非空，则存在允许策略使得对所有 非空；目标函数 对所有 有意义，且对所有允许策略，极限 存在。管理科学与系统工程1(,)kkkkxT x u()kkDx00()D x0011(),(),uxu x1,()kkkDx0kV0k 0k 0limkkV注：对于定义一个无期决策过程的最优化问题，须满足三个条件，即对所有的有：状态转移方程有意义；允许决策集合

25、有意义，而且非空，则存在允许策略使得对所有 非空；目标函数 对所有 有意义，且对所有允许策略，极限 存在。管理科学与系统工程1(,)kkkkxT x u()kkDx00()D x0011(),(),uxu x1,()kkkDx0kV0k 0k 0limkkV当上述三个条件成立时，就可以说，无期决策过程的最优化的意义在于求最优策略 使得其中P是定义在无期过程上的非空允许策略集。 是 P的元素， 是定义在P上的目标函数。管理科学与系统工程pP()( )p PV poptV p( )V pp00001(,)(,)(,)NNNkkkkkkkkVvx uv x uvx u( )( )( ,( ) ( , )( , ( )