【正文】 5),各點(diǎn) 標(biāo)號為 1,2,…,n 。求任意一點(diǎn) i到點(diǎn) n(靶 點(diǎn) )的最短路線 (距離 )。 ( 存在明顯的級變量，但級 數(shù)是無限的 ) 管理科學(xué)與系統(tǒng)工程 1j j jx??? ??2200m in l imj j kkjz x V???????? ? ????求解這類問題如果仍使用以前的逐級遞推方法，將遇到極大的計(jì)算量，為此必需尋找新方法。 管理科學(xué)與系統(tǒng)工程 ： (1)選初始函數(shù) (一般取 )； (2)用迭代公式 及 計(jì)算 其中 為當(dāng)前階段的狀態(tài)和決策， 為 已知終止函數(shù)， 為迭代步數(shù) , v為指標(biāo)函數(shù) (3)當(dāng) 或 管理科學(xué)與系統(tǒng)工程 0()fx 0 ( ) 0fx ?? ?1()( ) ( , ) ( ( , ) ) ,kku U xf x o p t v x u f T x u x X??? ? ?( ) ( ) ,knf x x x X???( ) , 1 , 2 , ,kf x k ?,xu ()x?k1 ( ) ( ) , ,kkf x f x x X? ??1( ) ( )()kkkf x f xfx?? ? ?(4)當(dāng) 或 時(shí)迭代停止，最優(yōu)值函數(shù) ，最優(yōu)策略 ；否則以 k+1代替 k重復(fù)(2),(3). 管理科學(xué)與系統(tǒng)工程 1 ( ) ( ) , ,kku x u x x X? ??1 ( ) ( ) ,()kkkf x f x xXfx?? ? ??( ) ( )kf x f x?( ) ( )ku x u x? ?說明： 函數(shù)迭代法和策略迭代法中，序列 和 的收斂性在相當(dāng)廣泛的條件下是可以 保證的，一般來說它與 等 的具體形式有關(guān)。 管理科學(xué)與系統(tǒng)工程 {( ( )}kfx{( ( )}kux( ) , ( ) , ( , ) , nU x T x v x u X策略迭代法的基本思想是：先選定一初始策略 然后按某種方式求得新策略 直至最終求出最優(yōu)策略。 一般來說，選定初始策略要比選定初始目標(biāo)最優(yōu)值函數(shù)容易得多，且策略迭代的收斂速度稍快，但其計(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).策略是對任意狀態(tài) x的決策函數(shù)，記作 u(x)。 管理科學(xué)與系統(tǒng)工程 例 1：段數(shù)不定的最短路線問題（不定期決策過程） n個(gè)點(diǎn)相互連接組成 一 個(gè)連通圖 (右圖中 n=5),各點(diǎn) 標(biāo)號為 1,2,…,n 。求任意一點(diǎn) i到點(diǎn) n(靶 點(diǎn) )的最短路線 (距離 )。 解： (1)假設(shè)從 i點(diǎn)走一步到靶點(diǎn) 5的最優(yōu)距離為 , 則顯然有： 最優(yōu)決策為 : 管理科學(xué)與系統(tǒng)工程 1()fi1 1 5(1 ) 2fd?? (1) 5u? ?1 2 5( 2 ) 7fd??1 3 5(3 ) 5fd??1 4 5( 4 ) 3fd??1 5 5(5 ) 0fd??(2) 5u ? ?(3) 5u ? ?(4) 5u ? ?(5) 5u ? ?5 1 4 3 2 3 2 2 5 7 5 5 6 0.51 (2)假設(shè)從 i點(diǎn)走兩步到靶點(diǎn) 5的最優(yōu)距離為 , 根據(jù)最優(yōu)化原理得： 具體計(jì)算如下： 管理科學(xué)與系統(tǒng)工程 2()fi21152( ) m in ( ) , 1 , 2 , 3 , 4( 5 ) 0ijif i d f j if??? ??? ? ?? ??????2 1 115(1 ) m i n ( )jif d f j?? ??????1 1 1m in [ (1 ) ,df??1 2 1 1 3 1 1 4 1 1 5 1( 2 ) , ( 3 ) , ( 4 ) , ( 5 ) ]d f d f d f d f? ? ? ? 注：不取含 的地方作為最優(yōu)決策 管理科學(xué)與系統(tǒng)工程 2 (1) 5u? ?m i n [ 0 2 , 6 7 , 5 5 , 2 3 , 2 0 ] 2? ? ? ? ? ? ?0ijd ? ()ui?2 2 115( 2 ) m in ( )jif d f j?? ??????2 1 1m in [ (1 ) ,df2 2 1 2 3 1 2 4 1 2 5 1( 2 ) , ( 3 ) , ( 4 ) , ( 5 ) ]d f d f d f d f? ? ? ?m i n [ 6 2 , 0 7 , 0 . 5 5 , 5 3 , 7 0 ] 5 . 5? ? ? ? ? ? ?2 (2) 3u? ? (3)假設(shè)從 i點(diǎn)走三步到靶點(diǎn) 5的最優(yōu)距離為 , 則得： 計(jì)算結(jié)果如下： 管理科學(xué)與系統(tǒng)工程 3()fi32153( ) m in ( ) , 1 , 2 , 3 , 4( 5 ) 0ijif i d f j if??? ??? ? ?? ??????33(1 ) 2 , (1 ) 5fu ???33( 2 ) 4 .5 , ( 2 ) 3fu ???33( 3 ) 4 , ( 3 ) 4fu ???33( 4 ) 3 , ( 4 ) 5fu??? (4)假設(shè)從 i點(diǎn)走四步到靶點(diǎn) 5的最優(yōu)距離為 , 則得： 計(jì)算結(jié)果如下： 管理科學(xué)與系統(tǒng)工程 4()fi43154( ) m in ( ) , 1 , 2 , 3 , 4( 5 ) 0ijif i d f j if??? ??? ? ?? ??????44(1 ) 2 , (1 ) 5fu ???44( 2 ) 4 .5 , ( 2 ) 3fu ???44( 3 ) 4 , ( 3 ) 4fu ???44( 4 ) 3 , ( 4 ) 5fu??? 管理科學(xué)與系統(tǒng)工程 2 3 115( 3 ) m in ( )jif d f j?? ??????3 1 1in [ (1 ) ,df3 2 1 3 3 1 3 4 1 3 5 1( 2 )