1、函數(shù)迭代法與策略迭代法:舉例簡單說明不定期與無期決策過程的形式和概念；以不定期和無期決策過程為例，介紹函數(shù)迭代法和策略迭代法。:定義：多階段的決策過程的階段數(shù)N確定，稱為定期決策過程，當N不確定時，稱此類決策過程為不定期決策過程，當N趨向無窮時稱為無期決策過程。:例1：段數(shù)不定的最短路線問題不定期決策過程）n個點相互連接組成 一個連通圖(右圖中n=5),各點標號為1,2,n。任意兩點i，j之間的距離(費用)記作dij 。求任意一點i到點n(靶點)的最短路線(間隔)。5143232257 5560.51:例1：段數(shù)不定的最短路線問題不定期決策過程）n個點相互連接組成 一個連通圖(右圖中n=5),

2、各點標號為1,2,n。任意兩點i，j之間的距離(費用)記作dij 。求任意一點i到點n(靶點)的最短路線(間隔)。5143232257 5560.51:例2：無限期決策過程模型 ，狀態(tài)變換函數(shù)為。( 存在明顯的級變量，但級數(shù)是無限的 ):1jjjx2200minlimjjkkjzxV求解這類問題如果仍使用以前的逐級遞推方法，將遇到極大的計算量，為此必需尋找新方法。函數(shù)方程可以用迭代法求解，通常有函數(shù)迭代法和策略迭代法兩種迭代方法。:1.函數(shù)迭代法的步驟是：(1)選初始函數(shù) (一般取 )；(2)用迭代公式及 計算其中為當前階段的狀態(tài)和決策， 為已知終止函數(shù)， 為迭代步數(shù), v為指標函數(shù)(3)當或

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)當或時迭代停止，最優(yōu)值函數(shù)，最優(yōu)策略 ；否則以k+1代替k重復(2),(3).:1( )( ),kkuxux xX1( )( ),( )kkkfxfxxXfx( )( )kf xfx( )( )kuxux闡明：函數(shù)迭代法和策略迭代法中，序列 和 的收斂性在相當廣泛的條件下是可以保證的，一般來說它與 等的具體形式有關。

4、函數(shù)迭代法的基本思想是以步數(shù)(段數(shù))作為參數(shù)，先求在各個不同步數(shù)下的最優(yōu)策略，然后從這些最優(yōu)解中再選出最優(yōu)者，從而同時確定了最優(yōu)步數(shù)。:( )kfx( )kux( ), ( ), ( , ),nU x T x v x uX策略迭代法的基本思想是：先選定一初始策略 然后按某種方式求得新策略 直至最終求出最優(yōu)策略。若對某一k，對所有i有： ，則稱 收斂，此時，戰(zhàn)略就是最優(yōu)策略。一般來說，選定初始策略要比選定初始目標最優(yōu)值函數(shù)容易得多，且策略迭代的收斂速度稍快，但其計算量要大些。:( )1,2,1ku i in12( ),( ),u i u i 1( )( )kkuiu i12( ),( ),u i

5、 u i ( )1,2,1ku i in ( 是事先給定的數(shù))時迭代停止，最優(yōu)值函數(shù),最優(yōu)策略 。2.策略迭代法的步驟是：(1)選初始策略 ，令k=1；(2)用 求解 ，(3)用 求改進策略 ，:xX( )( )kf xfx( )( )kuxux1( )u x( )kux( )kfx( )( ,( )( ( ,( ),.kkkkfxv x uxf T x uxxX( )( ),.knfxx xX( )kfx1( )kux1( )( )( , )( ( , ) ).kku U xuxu opt v x uf T x u例1的求解：分析：可以不考慮回路，因為含有回路的路線一定不是最短的.本問題路線

6、的段數(shù)事先不固定，而是隨著最優(yōu)策略確定的，然而狀態(tài)、決策、狀態(tài)轉移、指標函數(shù)與以前的最短路線問題的相同.狀態(tài)記作x=i，i=1,2,n，決策記作u(i).策略是對任意狀態(tài)x的決策函數(shù)，記作u(x)。階段指標是任意兩狀態(tài)i,j間的距離dij，指標函數(shù)V(i,u(x)是由狀態(tài)i出發(fā)，在策略u(x)下到達狀態(tài)n的路線的:間隔，它是階段指標之和， 并滿足可分離性要求，有最優(yōu)值函數(shù)(i)為由i出發(fā)到達n的最短距離，即式中u*(x)是最優(yōu)策略，滿足基本方程 :( ,()(,()ijVi u xdVj u x*( )( )min( , ( )( ,( )u xf iV i u xV i ux1( )min(

7、 ) ,1,2,1.ijj nf idf jin 該式記為()式，它不是一個遞推方程，而是一個關于(i)的函數(shù)方程,對固定的i使()右端 dij+(j) 達到極小的j即為最優(yōu)決策u*(i)，對所有的i求解()式得到最優(yōu)策略u*(x)。:例1：段數(shù)不定的最短路線問題不定期決策過程）n個點相互連接組成 一個連通圖(右圖中n=5),各點標號為1,2,n。任意兩點i，j之間的距離(費用)記作dij 。求任意一點i到點n(靶點)的最短路線(間隔)。:用函數(shù)迭代法求解例1只求1,2,3,4各點到點5的最優(yōu)路線，其余類似。解：(1)假設從i點走一步到靶點5的最優(yōu)距離為 , 則顯然有： 最優(yōu)決策為:1( )f

8、 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的最優(yōu)距離為 , 根據(jù)最優(yōu)化原理得：具體計算如下：:2( )f i21152( )min( ) ,1,2,3,4(5)0ijif idfjif 21115(1)min( )jifdfj 111min(1),df121131141151(2),(3),(4),(5)dfdfdfdf 注：不取含 的地方作為最優(yōu)決策:2(1)5umin02,67,55,23,2020ijd ( )u i22115(

9、2)min( )jifdfj 211min(1),df221231241251(2),(3),(4),(5)dfdfdfdfmin62,07,0.55,53,705.52(2)3u (3)假設從i點走三步到靶點5的最優(yōu)距離為 , 則得：計算結果如下：:3( )f i32153( )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的最優(yōu)距離為 , 則得：計算結果如下：:4( )f i43154( )min( ) ,1,2,3,4(5)0ijif

10、 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),(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個點,因而從任一點出發(fā)到達靶點,其間最多有4步(否則，有回路)，這樣就不需繼續(xù)下去了。將

11、計算結果列成表：:i1252525252755.534.534.533554444444353535351( )f i1( )u i2( )f i3( )f i4( )f i2( )u i3( )u i4( )u i 分析上面的結果可得：從點1到點5走一步為最優(yōu)，最優(yōu)距離為2，最優(yōu)路線 ；從點2到點5走三步為最優(yōu)，最優(yōu)距離為4.5,最優(yōu)路線 ；從點3到點5走兩步為最優(yōu)，最優(yōu)距離為4,最優(yōu)路線 ；從點4到點5走一步為最優(yōu)，最優(yōu)距離為3，最優(yōu)路線 。:11(1)5u3212(2)3(3)4(4)5uuu213(3)4(4)5uu14(4)5u 最優(yōu)決策最多走4步，多于此步數(shù)，會出現(xiàn)走回頭路或回路，

12、顯然這些不是最優(yōu)路線。 從任一點出發(fā)到靶點，走m(m=1,2,)步與走m+1步的最優(yōu)距離一樣，決策函數(shù)也一樣，如果繼續(xù)計算走m+2步、m+3步、，其結果仍一樣, 即 也就說明 一致收斂于 ， 一致收斂于 。故當這種一出現(xiàn)，計算便可停止。:1( )( ),mmfifi1( )( ),mmuiui( )mfi( )f i( )mui( )u i例1的求解：(策略迭代法） 解：第一步，先選取初始策略 。如取：即 ,但必需沒有回路，每點可達靶點。第二步，由 求 ，由策略迭代法的方程組可得：因策略 直達靶點，應先計算：:1( )u i1111(1)5,(2)4,(3)5,(4)3.uuuu1( )u i

13、1( )f i11,( )111( )( )(5)0i uif idf u if11(1),(3)uu1 ( )5,4,5,3u i第三步，由 求 ,由求出它的解 ：時，: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,

14、611,55,26,202u iu idf u idfdfdfdfdf2(1)u( )2u i 2, ( )1( )min( ( )min62,011,0.55,56,705.5u iu idf u i所以，同理，可求得 ,于是得到第一次策略迭代的結果為以 為初始策略繼續(xù)反復使用第二、三步進行迭代。第二步：由 求: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.5fd

15、fdf2( )f i, ( )2( )min( ( )i u iu idf u i3( )u i( )1u i 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.

16、553534524.5435345將以上結果記錄下來：:1( )u i2( )f i1( )f i4( )u i2( )u i3( )u i3( )f i由以上結果得到 ，對所有的i都成立，說明迭代步驟可以停止。故找到最優(yōu)策略為列表表示為從而可以得到各點到靶點(點5)的最優(yōu)路線和最優(yōu)距離：:34( )( )u iu i( )5,3,4,5u ii12345345( )u i最優(yōu)路線 最短距離值 2 4.5 4 3可以看到策略迭代法得到的結果與函數(shù)迭代法的結果一致。:例2：無限期決策過程模型 ，狀態(tài)變換函數(shù)為。( 存在明顯的級變量，但級數(shù)是無限的 ):1jjjx2200minlimjjkkjzx

17、V例2的求解函數(shù)迭代法）解：(1)任取初值，如狀態(tài)變換函數(shù)為迭代公式為(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()03Gxxx故由于 ，應繼續(xù)

18、進行迭代。當i=3時，進行第三次迭代，類似以上才方法，可得:25( )0.6258x 2222555( )()() 838g 22131.625821( )( )gg由于 ,取i=4繼續(xù)進行第四次迭代。其結果如下:313( )0.61921x 2223131313( )()() 21821g 22341.6192132( )( )gg由于 ,可以確定該問題的最優(yōu)收益函數(shù)為最優(yōu)決策為:434( )0.61855x 2224343434( )()() 552155g 22891.6185543( )( )gg2()1.618jg()0.618jjx 例2的求解策略迭代法）解：(1)任取初始策略值，

19、如及(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 Txxxxxxx上式的解為 由于，需要進行第二次迭代： :10( )( )xx12( )0.6663x

20、 1,111,01( )( ,( )( ( ,( )gfxgTx2222213()01.44439 1,211,11( )( ,( )( ( ,( )gfxgTx222222132130()()1.60539381 由于 ，需要繼續(xù)進行迭代，直到 時為止，節(jié)省時間，直接給出結果 ，但由于 ，因此需要繼續(xù)進行迭代。現(xiàn)在來確定第三次迭代的決策，有:1,21,1( )( )gg1,11,( )( )iigg211,( )( )1.625igg210( )( )2gg2( )x12222222222( ( , )( )1.625( )( )2( )3.25( )0 xg Txxxxxxx那么由于，還必

21、須進行下次迭代。第三次迭代：:213( )0.61921x 21( )( )xx2,122,02( )( ,( )( ( ,( )gfxgTx222213610()01.38321441 2,222,12( )( ,( )( ( ,( )gfxgTx22221361013()()1.5832144121 由于 ，需要繼續(xù)進行迭代，直到 時為止，最后得到 由于 ，因此需要繼續(xù)進行迭代?，F(xiàn)在來確定第四次迭代的決策，有:2,22,1( )( )gg2,12,( )( )iigg222,( )( )1.618igg21( )( )gg3( )x22222233333( ( , )( )1.618( )

22、( )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 繼續(xù)進行迭代，直到 時為止，最后得到 由于 ，因此可停止迭代。最優(yōu)收益函數(shù)為 相應的最優(yōu)策略為:3,13,( )( )iigg23( )1.618g32( )( )gg2()1.618jjg()0.618jjjx 注：對于定義一個無期決策過程的最優(yōu)化問題，須滿足三個條件，即對所

23、有的有：狀態(tài)轉移方程有意義；允許決策集合 有意義，而且非空，則存在允許策略使得對所有 非空；目標函數(shù) 對所有 有意義，且對所有允許策略，極限 存在。:1(,)kkkkxT x u()kkDx00()D x0011(),(),uxu x1,()kkkDx0kV0k 0k 0limkkV注：對于定義一個無期決策過程的最優(yōu)化問題，須滿足三個條件，即對所有的有：狀態(tài)轉移方程有意義；允許決策集合 有意義，而且非空，則存在允許策略使得對所有 非空；目標函數(shù) 對所有 有意義，且對所有允許策略，極限 存在。:1(,)kkkkxT x u()kkDx00()D x0011(),(),uxu x1,()kkkDx0kV0k 0k 0limkkV當上述三個條件成立時，就可以說，無期決策過程的最優(yōu)化的意義在于求最優(yōu)策略 使得其中P是定義在無期過程上的非空允許策略集。 是 P的元素， 是定義在P上的目標函數(shù)。:pP()( )p PV poptV p( )V pp00001(,)(,)(,)NNNkkkkkkkkVvx uv x uvx u( )( )( ,( ) ( , )( , ( )u D xp