動(dòng)態(tài)規(guī)劃基本理論推廣(函數(shù)迭代與策略迭代法)-文庫(kù)吧在線文庫(kù)
【正文】 財(cái)富。 如果決策序列 中 與 k無(wú)關(guān)，稱為平穩(wěn)的，可用一個(gè)函數(shù) u(x)表示。)( , ( ) ) { ( , ) ( 39。 現(xiàn)在來確定第三次迭代的決策 ，有 管理科學(xué)與系統(tǒng)工程 1 ,2 1 ,1( ) ( )gg???1 , 1 1 ,( ) ( )iigg??? ?21 1 ,( ) ( ) 25igg? ? ???210( ) ( ) 2gg? ? ???2()x ?1222 2 222222( ( , ) )( ) 25 ( ( ) )()2 ( ) 5 ( ( ) ) 0x g T xxxxxxx??? ? ? ??? ? ????????????? ? ? ????? ? ? ?則 由于 ，還必須進(jìn)行下次迭代。 第二步，由 求 ，由策略迭代法的方程組可得： 因策略 直達(dá)靶點(diǎn)，應(yīng)先計(jì)算： 管理科學(xué)與系統(tǒng)工程 1()ui1 1 1 1( 1 ) 5 , ( 2 ) 4 , ( 3 ) 5 , ( 4 ) 3 .u u u u? ? ? ?1()ui 1()fi11 , ( ) 1 11( ) ( ( ) )( 5 ) 0i u if i d f u if???? ??11(1), (3)uu1{ ( ) } { 5 , 4 , 5 , 3 }ui ? 第三步，由 求 ,由 求出它的解 ： 時(shí)， 管理科學(xué)與系統(tǒng)工程 1 1 5 11 3 5 11 4 3 11 2 4 1( 1 ) ( 5 ) 2 0 2( 3 ) ( 5 ) 5 0 5( 4) ( 3 ) 1 5 6( 2) ( 4) 5 6 1 1f d ff d ff d ff d f? ? ? ? ?? ? ? ? ?? ? ? ? ?? ? ? ? ?1()fi 2()ui , ( ) 1()m in [ ( ( ) ) ]i u iui d f u i?2()ui( ) 1ui ? 所以， （不在含 的項(xiàng)取 ） 時(shí)， 管理科學(xué)與系統(tǒng)工程 2 (1) 5u ? iid1 , ( ) 1()1 1 1 1 2 1 1 3 11 4 1 1 5 1m in [ ( ( ) ) ]m in[ ( 1 ) , ( 2) , ( 3 ) ,( 4) , ( 5 ) ]m in[ 0 2 , 6 1 1 , 5 5 , 2 6 , 2 0] 2uiuid f u id f d f d fd f d f?? ? ? ???? ? ? ? ? ? ?2(1)u( ) 2ui ?2 , ( ) 1()m in [ ( ( ) ) ]m in[ 6 2 , 0 11 , 0. 5 5 , 5 6 , 7 0] 5. 5uiui d f u i?? ? ? ? ? ? ?所以， 同理，可求得 ,于是得到第一次策略迭代的結(jié)果為 ②以 為初始策略繼續(xù)反復(fù)使用第二、三步進(jìn)行迭代。 管理科學(xué)與系統(tǒng)工程 用函數(shù)迭代法求解例 1 只求 1,2,3,4各點(diǎn)到點(diǎn) 5的最優(yōu)路線，其余類似。若對(duì)某一 k，對(duì)所有 i有： ，則稱 收斂，此時(shí)，策略 就是最優(yōu)策略。任意兩點(diǎn) i， j之間的距離 (費(fèi)用 )記作 dij 。 管理科學(xué)與系統(tǒng)工程 定義：多階段的決策過程的階段數(shù) N確定，稱為定期決策過程，當(dāng) N不確定時(shí)，稱此類決策過程為 不定期決策過程 ，當(dāng) N趨向無(wú)窮時(shí)稱為 無(wú)期決策過程 。 ( 存在明顯的級(jí)變量，但級(jí) 數(shù)是無(wú)限的 ) 管理科學(xué)與系統(tǒng)工程 1j j jx??? ??2200m in l imj j kkjz x V???????? ? ????求解這類問題如果仍使用以前的逐級(jí)遞推方法，將遇到極大的計(jì)算量，為此必需尋找新方法。 ： (1)選初始策略 ，令 k=1； (2)用 求解 ， (3)用 求改進(jìn)策略 ， 管理科學(xué)與系統(tǒng)工程 xX? ?( ) ( )kf x f x? ( ) ( )ku x u x? ?1()ux()kux ()kfx( ) ( , ( ) ) ( ( , ( ) ) ) , .k k k kf x v x u x f T x u x x X? ? ?( ) ( ) , .knf x x x X???()kfx 1()kux?? ?1()( ) ( ( , ) ( ( , ) ) ) .kku U xu x u o p t v x u f T x u????例 1的求解： 分析：可以不考慮回路，因?yàn)楹谢芈返穆肪€一定不是最短的 . 本問題路線的段數(shù)事先不固定，而是隨著最優(yōu)策略確定的，然而狀態(tài)、決策、狀態(tài)轉(zhuǎn)移、指標(biāo)函數(shù)與以前的最短路線問題的相同 . 狀態(tài)記作 x=i， i=1,2,…,n ，決策記作 u(i).策略是對(duì)任意狀態(tài) x的決策函數(shù)，記作 u(x)。 管理科學(xué)與系統(tǒng)工程 11 (1) 5u ???3 2 12 ( 2 ) 3 ( 3 ) 4 ( 4 ) 5uuu???? ? ? ? ? ?213 ( 3 ) 4 ( 4 ) 5uu??? ? ? ?14 ( 4 ) 5u ??? ②最優(yōu)決策最多走 4步，多于此步數(shù)，會(huì)出現(xiàn)走回頭路或回路，顯然這些不是最優(yōu)路線。故找到最優(yōu)策略為 列表表示為 從而可以得到各點(diǎn)到靶點(diǎn) (點(diǎn) 5)的最優(yōu)路線和最優(yōu)距離： 管理科學(xué)與系統(tǒng)工程 34( ) ( )u i u i?{ ( ) } { 5 , 3 , 4 , 5 }ui? ?i 1 2 3 4 5 3 4 5 ()ui?最優(yōu)路線 最短距離值 ① → ⑤ 2 ② → ③ → ④ → ⑤ ③ → ④ → ⑤ 4 ④ → ⑤ 3 可以看到策略迭代法得到的結(jié)果與函數(shù)迭代法的 結(jié)果 一致。 最優(yōu)收益函數(shù)為 相應(yīng)的最優(yōu)策略為 管理科學(xué)與系統(tǒng)工程 3 , 1 3 ,( ) ( )iigg??? ?23 ( ) 1 .6 1 8g ???32( ) ( )gg???2( ) 18jjg ???( ) 8j j jx ??? ??注：對(duì)于定義一個(gè)無(wú)期決策過程的最優(yōu)化問題，須滿足三個(gè)條件，即對(duì)所有的 有： ①狀態(tài)轉(zhuǎn)移方程 有意義； ②允許決策集合 有意義，而且 非空，則存在允許策略 使得對(duì)所有 非空； ③目標(biāo)函數(shù) 對(duì)所有 有意義，且對(duì)所有允許策略，極限 存在。 定義：滿足以下條件的多階段決策過程成為 平穩(wěn)過程 ，相應(yīng)的策略稱為 平穩(wěn)策略 : (1) 允許決策集合 Uk(x)與 k無(wú)關(guān)，可記為 U(x)， 為狀態(tài)變量 。 19:51:1119:51:1119:513/23/2023 7:51:11 PM 1以我獨(dú)沈久，愧君相見頻。 , March 23,
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1