【正文】 不是最短的 . 本問題路線的段數(shù)事先不固定，而是隨著最優(yōu)策略確定的，然而狀態(tài)、決策、狀態(tài)轉(zhuǎn)移、指標函數(shù)與以前的最短路線問題的相同 . 狀態(tài)記作 x=i， i=1,2,…,n ，決策記作 u(i).策略是對任意狀態(tài) x的決策函數(shù)，記作 u(x)。 管理科學與系統(tǒng)工程 {( ( )}kfx{( ( )}kux( ) , ( ) , ( , ) , nU x T x v x u X策略迭代法的基本思想是：先選定一初始策略 然后按某種方式求得新策略 直至最終求出最優(yōu)策略。 ( 存在明顯的級變量，但級 數(shù)是無限的 ) 管理科學與系統(tǒng)工程 1j j jx??? ??2200m in l imj j kkjz x V???????? ? ????求解這類問題如果仍使用以前的逐級遞推方法，將遇到極大的計算量，為此必需尋找新方法。 5 1 4 3 2 3 2 2 5 7 5 5 6 0.5 1 管理科學與系統(tǒng)工程 例 1：段數(shù)不定的最短路線問題（不定期決策過程） n個點相互連接組成 一 個連通圖 (右圖中 n=5),各點 標號為 1,2,…,n 。 管理科學與系統(tǒng)工程 定義：多階段的決策過程的階段數(shù) N確定，稱為定期決策過程，當 N不確定時，稱此類決策過程為 不定期決策過程 ，當 N趨向無窮時稱為 無期決策過程 。 管理科學與系統(tǒng)工程 例 1：段數(shù)不定的最短路線問題（不定期決策過程） n個點相互連接組成 一 個連通圖 (右圖中 n=5),各點 標號為 1,2,…,n 。任意兩點 i， j之間的距離 (費用 )記作 dij 。 函數(shù)方程可以用迭代法求解，通常有函數(shù)迭代法和策略迭代法兩種迭代方法。若對某一 k，對所有 i有： ，則稱 收斂，此時，策略 就是最優(yōu)策略。階段指標是任意兩狀態(tài) i,j間的距離 dij，指標函數(shù)V(i,u(x))是由狀態(tài) i出發(fā)，在策略 u(x)下到達狀態(tài) n的路線的 管理科學與系統(tǒng)工程 距離，它是階段指標之和， 并滿足可分離性要求，有 最優(yōu)值函數(shù) ?(i)為由 i出發(fā)到達 n的最短距離，即 式中 u*(x)是最優(yōu)策略，滿足基本方程 管理科學與系統(tǒng)工程 ( , ( ) ) ( , ( ) )ijV i u x d V j u x??*()( ) m i n ( , ( ) ) ( , ( ) )uxf i V i u x V i u x??1( ) m in ( ) , 1 , 2 , , 1 .ijjnf i d f j i n????? ? ? ???該式記為 (﹡) 式，它不是一個遞推方程，而是一個 關(guān)于 ?(i)的函數(shù)方程 ,對固定的 i使 (﹡) 右端 [dij+?(j)] 達到極小的 j即為最優(yōu)決策 u*(i)，對所有的 i求解 (﹡) 式得到最優(yōu)策略 u*(x)。 管理科學與系統(tǒng)工程 用函數(shù)迭代法求解例 1 只求 1,2,3,4各點到點 5的最優(yōu)路線，其余類似。 ③從任一點出發(fā)到靶點，走 m(m=1,2,…) 步與走m+1步的最優(yōu)距離一樣，決策函數(shù)也一樣，如果繼續(xù)計算走 m+2步、 m+3步、 …… ，其結(jié)果仍一樣 , 即 也就說明 一致收斂于 ， 一致收斂于 。 第二步，由 求 ，由策略迭代法的方程組可得： 因策略 直達靶點，應先計算： 管理科學與系統(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 ? 第三步，由 求 ,由 求出它的解 ： 時， 管理科學與系統(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 ? 所以， （不在含 的項取 ） 時， 管理科學與系統(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ù)反復使用第二、三步進行迭代。 管理科學與系統(tǒng)工程 例 2：無限期決策過程 模型 ，狀態(tài)變換函數(shù) 為 。 現(xiàn)在來確定第三次迭代的決策 ，有 管理科學與系統(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??? ? ? ??? ? ????????????? ? ? ????? ? ? ?則 由于 ，還必須進行下次迭代。 管理科學與系統(tǒng)工程 1 ( , )k k k kx T x u? ?()kkDx 00()Dx0 0 1 1{ ( ) , ( ) , }u x u x1, ( )kkk D x?0kV0k?0k?0lim kk V??注：對于定義一個無期決策過程的最優(yōu)化問題，須滿足三個條件，即對所有的 有： ①狀態(tài)轉(zhuǎn)移方程 有意義； ②允許決策集合 有意義，而且 非空，則存在允許策略 使得對所有 非空； ③目標函數(shù) 對所有 有意義，且對所有允許策略，極限