運(yùn)籌學(xué) Ch4 動(dòng)態(tài)規(guī)劃

1、orxjtu第四章 動(dòng)態(tài)規(guī)劃ch 4 動(dòng)態(tài)規(guī)劃方法基本概念基本概念基本思想與最優(yōu)性定理基本思想與最優(yōu)性定理最短路徑問(wèn)題最短路徑問(wèn)題背包問(wèn)題背包問(wèn)題旅行商問(wèn)題旅行商問(wèn)題orxjtu第四章 動(dòng)態(tài)規(guī)劃學(xué)習(xí)目的學(xué)習(xí)目的orxjtu第四章 動(dòng)態(tài)規(guī)劃 刁在筠刁在筠 等等 編編 運(yùn)籌學(xué)（第二版）運(yùn)籌學(xué)（第二版） 高等教育出版社高等教育出版社 2001運(yùn)籌學(xué)運(yùn)籌學(xué) 教材編寫(xiě)組教材編寫(xiě)組 編編 運(yùn)籌學(xué)運(yùn)籌學(xué) （修訂版）（修訂版） 清華大學(xué)出版社清華大學(xué)出版社 1990 牛映武牛映武 主編主編 運(yùn)籌學(xué)運(yùn)籌學(xué) 西安交通大學(xué)出版社西安交通大學(xué)出版社 1990 參參考文考文獻(xiàn)獻(xiàn) 4.1 多階段決策問(wèn)題 與動(dòng)態(tài)規(guī)劃的基本

2、概念orxjtu第四章 動(dòng)態(tài)規(guī)劃問(wèn)題可劃分為一系列互相聯(lián)系的階段問(wèn)題可劃分為一系列互相聯(lián)系的階段 :決策決策 1決策決策 2決策決策 n初始狀態(tài)初始狀態(tài)狀態(tài)狀態(tài) 1狀態(tài)狀態(tài) 2最終狀態(tài)最終狀態(tài) 我們的目的是選取各個(gè)階段的決策我們的目的是選取各個(gè)階段的決策, 使整個(gè)過(guò)程達(dá)到最使整個(gè)過(guò)程達(dá)到最好的好的總體效果總體效果 .def. 當(dāng)各個(gè)階段決策確定后當(dāng)各個(gè)階段決策確定后, 所組成的決策序列稱為所組成的決策序列稱為策略策略. 具有上述特性的問(wèn)題稱作具有上述特性的問(wèn)題稱作多階段決策問(wèn)題多階段決策問(wèn)題. 相應(yīng)地相應(yīng)地, 稱把一個(gè)問(wèn)題看作是一個(gè)前后關(guān)聯(lián)、具有鏈稱把一個(gè)問(wèn)題看作是一個(gè)前后關(guān)聯(lián)、具有鏈 狀結(jié)構(gòu)

3、的多階段過(guò)程的方法為狀結(jié)構(gòu)的多階段過(guò)程的方法為多階段決策過(guò)程多階段決策過(guò)程, 也稱也稱 為為序貫決策過(guò)程序貫決策過(guò)程 .orxjtu第四章 動(dòng)態(tài)規(guī)劃美國(guó)數(shù)學(xué)家美國(guó)數(shù)學(xué)家 r. bellman 等等 , 1957 把原把原(多階段決策多階段決策)問(wèn)題變?yōu)橐幌盗邢嗷ヂ?lián)系、形式上很問(wèn)題變?yōu)橐幌盗邢嗷ヂ?lián)系、形式上很相似的相似的(單階段單階段)子問(wèn)題子問(wèn)題, 然后逐個(gè)加以解決然后逐個(gè)加以解決, 而每個(gè)子問(wèn)題的而每個(gè)子問(wèn)題的求解往往比較簡(jiǎn)單求解往往比較簡(jiǎn)單 .動(dòng)態(tài)規(guī)劃解決問(wèn)題的方法動(dòng)態(tài)規(guī)劃解決問(wèn)題的方法:def. :l 階段階段 階段的劃分一般是根據(jù)時(shí)間和空間的自然特征來(lái)階段的劃分一般是根據(jù)時(shí)間和空間的自

4、然特征來(lái)進(jìn)行進(jìn)行, 描述階段的變量稱為描述階段的變量稱為階段變量階段變量, 用用t表示表示; 總的階段數(shù)總的階段數(shù)用用t表示表示 .orxjtu第四章 動(dòng)態(tài)規(guī)劃l 狀態(tài)狀態(tài) 狀態(tài)狀態(tài)表示每個(gè)階段開(kāi)始時(shí)問(wèn)題或系統(tǒng)所處的自然表示每個(gè)階段開(kāi)始時(shí)問(wèn)題或系統(tǒng)所處的自然狀況或客觀條件狀況或客觀條件, 它描述了問(wèn)題過(guò)程的它描述了問(wèn)題過(guò)程的不可控因素不可控因素.這里的狀態(tài)應(yīng)具有無(wú)后效性這里的狀態(tài)應(yīng)具有無(wú)后效性馬爾科夫性馬爾科夫性l 決策決策 給定某階段的狀態(tài)后給定某階段的狀態(tài)后, 對(duì)從該狀態(tài)到達(dá)下一階段那對(duì)從該狀態(tài)到達(dá)下一階段那個(gè)狀態(tài)、如何到達(dá)的選擇就是個(gè)狀態(tài)、如何到達(dá)的選擇就是決策決策 .在最優(yōu)控制中稱為在

5、最優(yōu)控制中稱為控制控制 . 描述過(guò)程狀態(tài)的變量稱為描述過(guò)程狀態(tài)的變量稱為狀態(tài)變量狀態(tài)變量, 它可以是一個(gè)數(shù)它可以是一個(gè)數(shù), 也也可以是一個(gè)向量可以是一個(gè)向量. 用用 表示第表示第t階段的狀態(tài)變量階段的狀態(tài)變量, 第第t階段所有階段所有可能狀態(tài)的集合可能狀態(tài)的集合(稱為稱為可達(dá)狀態(tài)集合可達(dá)狀態(tài)集合)記為記為 .tsts 描述決策的變量稱為描述決策的變量稱為決策變量決策變量, 以下用以下用 表示第表示第t階階段狀態(tài)為段狀態(tài)為 時(shí)的決策時(shí)的決策, 它是狀態(tài)變量的函數(shù)它是狀態(tài)變量的函數(shù) .tt( )x sts 決策變量的取值往往限制在稱之為決策變量的取值往往限制在稱之為允許決策集合允許決策集合的某的某

6、一范圍之內(nèi)一范圍之內(nèi). 該集合記為該集合記為 .tt( )d sorxjtu第四章 動(dòng)態(tài)規(guī)劃l 策略策略 各個(gè)階段決策的一個(gè)有序集合稱為各個(gè)階段決策的一個(gè)有序集合稱為策略策略 .可供選擇的策略的范圍稱為可供選擇的策略的范圍稱為允許策略集合允許策略集合, 用用p表示表示 .稱稱p中達(dá)到中達(dá)到最優(yōu)效果的策略為最優(yōu)效果的策略為最優(yōu)策略最優(yōu)策略. 由過(guò)程的第由過(guò)程的第t階段開(kāi)始到終止?fàn)顟B(tài)為止的過(guò)程稱為問(wèn)題的階段開(kāi)始到終止?fàn)顟B(tài)為止的過(guò)程稱為問(wèn)題的后部子過(guò)程后部子過(guò)程或或t子過(guò)程子過(guò)程, 而稱由相應(yīng)每段的決策按順序排列組成而稱由相應(yīng)每段的決策按順序排列組成的決策函數(shù)序列的決策函數(shù)序列 為為t子過(guò)程策略子過(guò)

7、程策略,簡(jiǎn)稱子策略簡(jiǎn)稱子策略.記為記為 , 即即tttt ( ),()x sxst,tt( )pst,ttttt+1t+1tt( ) ( ),(),() .psx sxsxsl 狀態(tài)轉(zhuǎn)移方程狀態(tài)轉(zhuǎn)移方程 的值隨的值隨 和和 的變化而變化的變化而變化, 記為記為t+1sttsxt+1ttt( ,)ss xt稱為稱為狀態(tài)轉(zhuǎn)移方程狀態(tài)轉(zhuǎn)移方程, 稱為稱為狀態(tài)轉(zhuǎn)移函數(shù)狀態(tài)轉(zhuǎn)移函數(shù).orxjtu第四章 動(dòng)態(tài)規(guī)劃l 效益函數(shù)與最優(yōu)值函數(shù)效益函數(shù)與最優(yōu)值函數(shù) 用來(lái)衡量所選策略優(yōu)劣的某種用來(lái)衡量所選策略優(yōu)劣的某種數(shù)量指標(biāo)稱為數(shù)量指標(biāo)稱為效益函數(shù)效益函數(shù). . 對(duì)于要構(gòu)成動(dòng)態(tài)規(guī)劃模型的效益函數(shù)對(duì)于要構(gòu)成動(dòng)態(tài)規(guī)劃

8、模型的效益函數(shù), 應(yīng)具有可分離性應(yīng)具有可分離性, 并滿足遞推關(guān)系并滿足遞推關(guān)系, 即應(yīng)有即應(yīng)有常見(jiàn)的、滿足上述要求的效益函數(shù)有兩種常見(jiàn)的、滿足上述要求的效益函數(shù)有兩種: 一是一是用用 表示表示t子過(guò)程的效益函數(shù)子過(guò)程的效益函數(shù), 則有則有t,tgt,tt,tttt+1t+1,1,2,ggs x ssttt,tttt+1t+1tttt+1,tt+1t+1,(,)gs x sss x gsstt,tttt+1jjjj=t,( ,)gs xsg s x這里這里 為第為第j 階段的階段的階段效益階段效益 .jjj( ,)g s x( 1 )( 2 )可加可分可加可分orxjtu第四章 動(dòng)態(tài)規(guī)劃這時(shí)這時(shí)

9、( 1 )式可寫(xiě)為式可寫(xiě)為 t,tttt+1t+1tttt+1,tt+1t+1t+1,( ,)(,)gs x ssg s xgsxs另一種是另一種是tt,tttt+1jjjj=t,( ,)gs xsg s x此時(shí)相應(yīng)地有此時(shí)相應(yīng)地有t,tttt+1tttt+1,tt+1t+1t+1,( ,)(,)gs xsg s x gsxs效益函數(shù)的最優(yōu)值效益函數(shù)的最優(yōu)值, 稱為稱為最優(yōu)值函數(shù)最優(yōu)值函數(shù), 記為記為 .tt( )z sttttt,tttt+1,( )max,xxz sgs xs乘積可分乘積可分 4.2 動(dòng)態(tài)規(guī)劃方法的 基本思想與最優(yōu)性定理orxjtu第四章 動(dòng)態(tài)規(guī)劃依據(jù)依據(jù) : bellma

10、n最優(yōu)性原理最優(yōu)性原理動(dòng)態(tài)規(guī)劃的最優(yōu)性原理可描述為動(dòng)態(tài)規(guī)劃的最優(yōu)性原理可描述為 : 作為整個(gè)過(guò)程的最優(yōu)策略應(yīng)具有這樣的性質(zhì)作為整個(gè)過(guò)程的最優(yōu)策略應(yīng)具有這樣的性質(zhì), 無(wú)論過(guò)去的無(wú)論過(guò)去的狀態(tài)和決策如何狀態(tài)和決策如何, 對(duì)由前面的決策所確定的狀態(tài)而言對(duì)由前面的決策所確定的狀態(tài)而言, 余下的余下的諸決策必須構(gòu)成最優(yōu)策略諸決策必須構(gòu)成最優(yōu)策略.簡(jiǎn)言之簡(jiǎn)言之, 一個(gè)最優(yōu)策略的子策略總是最優(yōu)的一個(gè)最優(yōu)策略的子策略總是最優(yōu)的.abcorxjtu第四章 動(dòng)態(tài)規(guī)劃由由( 2)知有知有t,ttttt+1,tt+1t+1t+1( ,)(,)gg s xgsxs上面的遞推關(guān)系又可寫(xiě)成上面的遞推關(guān)系又可寫(xiě)成效益函數(shù)是初

11、始狀態(tài)和策略的函數(shù)效益函數(shù)是初始狀態(tài)和策略的函數(shù), 記為記為 t,ttt,tt,( )gs pst,ttt,ttttt+1,tt+1t+1,t,( ,),gs pg s xgsp而子策略而子策略 可看成是由決策可看成是由決策 和和 組合而成組合而成, 即即t,tt( )psttt+1,tt+1( )()x spst,tttt+1,tt+1( ),()px sps 如果用如果用 表示在初始狀態(tài)為表示在初始狀態(tài)為 的后部子過(guò)程的所有的后部子過(guò)程的所有子策略中子策略中, 可取得的最優(yōu)子策略可取得的最優(yōu)子策略, 則最優(yōu)值函數(shù)為則最優(yōu)值函數(shù)為t,tt( )pstst,tttt,ttt,ttt,ttt,t

12、t( ),( )max,( )pz sgs psgs psorxjtu第四章 動(dòng)態(tài)規(guī)劃而而t,ttt+1,tt,ttt,ttttt+1,tt+1t+1,t,max,max( ,),px pgs pg s xgsptt+1,ttttt+1,tmax( ,)maxxpg s xgt+1,tt+1t+1t+1,tt+1t+1,t()max,pzsgsp所以所以ttttttttt+1t+1()( )max( ,)()xd sz sg s xzs邊界條件邊界條件t+1t+1()0zs基本方程基本方程式中式中 .t+1ttt( ,)ss xorxjtu第四章 動(dòng)態(tài)規(guī)劃 求解過(guò)程求解過(guò)程 : 根據(jù)邊界條件根

13、據(jù)邊界條件, 從從t=t開(kāi)始開(kāi)始, 由后向前逆推由后向前逆推, 逐逐步求得各階段的最優(yōu)決策和相應(yīng)的最優(yōu)值步求得各階段的最優(yōu)決策和相應(yīng)的最優(yōu)值. 當(dāng)最后求出當(dāng)最后求出 時(shí)時(shí), 就可找到整個(gè)問(wèn)題的最優(yōu)解就可找到整個(gè)問(wèn)題的最優(yōu)解 .11( )z s逆序逆序由最優(yōu)性原理由最優(yōu)性原理, 動(dòng)態(tài)規(guī)劃方法在行進(jìn)方向規(guī)定后動(dòng)態(tài)規(guī)劃方法在行進(jìn)方向規(guī)定后, 均要逆著這個(gè)規(guī)定的行進(jìn)方向來(lái)求解問(wèn)題均要逆著這個(gè)規(guī)定的行進(jìn)方向來(lái)求解問(wèn)題 .最終階段和起始階段可以互換最終階段和起始階段可以互換順序解法順序解法 關(guān)鍵關(guān)鍵 : 正確地寫(xiě)出基本的遞推關(guān)系式和恰當(dāng)?shù)倪吔鐥l件正確地寫(xiě)出基本的遞推關(guān)系式和恰當(dāng)?shù)倪吔鐥l件, 即基本方程即基

14、本方程 .把一個(gè)大問(wèn)題化成一簇同類(lèi)型的子問(wèn)題把一個(gè)大問(wèn)題化成一簇同類(lèi)型的子問(wèn)題, 然后逐個(gè)求解然后逐個(gè)求解 .orxjtu第四章 動(dòng)態(tài)規(guī)劃 動(dòng)態(tài)規(guī)劃方法動(dòng)態(tài)規(guī)劃方法有時(shí)還需對(duì)相應(yīng)的最優(yōu)性原理給予必要的驗(yàn)證有時(shí)還需對(duì)相應(yīng)的最優(yōu)性原理給予必要的驗(yàn)證反映動(dòng)態(tài)規(guī)劃基本方程的反映動(dòng)態(tài)規(guī)劃基本方程的最優(yōu)性定理最優(yōu)性定理, 它給出了策略為最優(yōu)的充要條件它給出了策略為最優(yōu)的充要條件 .最優(yōu)性原理僅僅是策略最優(yōu)性的必要條件最優(yōu)性原理僅僅是策略最優(yōu)性的必要條件 .既把當(dāng)前一段和未來(lái)各段分開(kāi)既把當(dāng)前一段和未來(lái)各段分開(kāi), 又把又把當(dāng)前效益和未來(lái)效益結(jié)合起來(lái)考慮當(dāng)前效益和未來(lái)效益結(jié)合起來(lái)考慮orxjtu第四章 動(dòng)態(tài)規(guī)劃

15、th.1 ( (動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃的最的最優(yōu)優(yōu)性定理性定理) ): 考慮階段數(shù)為考慮階段數(shù)為t的多階段決策過(guò)程的多階段決策過(guò)程, 其階段編號(hào)為其階段編號(hào)為 . 允許策略允許策略 是最優(yōu)策略的充是最優(yōu)策略的充要條件是要條件是: 對(duì)任一對(duì)任一 和和 , 有有0,1,t ,1t 0,t 101t 1,pxxx00(01)tttss 0,t 10,t 10t,t-1t,t 1t0,t 100,t 10,t 100,t-1t,t-1tt,t-1pp(s )pp(s ),max,max,gspgspgsp式中式中 , , 它是由初始狀態(tài)它是由初始狀態(tài)和子策略和子策略 所確定的所確定的t階段狀態(tài)階段狀態(tài) .0

16、,t-10,t-1t,t-1tt-1t-1t-1,(,)pppssx0s0,t-1p( 3 )orxjtu第四章 動(dòng)態(tài)規(guī)劃proof: (必要性必要性)設(shè)設(shè) 為最優(yōu)策略為最優(yōu)策略, 并將整個(gè)決策過(guò)程分為并將整個(gè)決策過(guò)程分為0到到t-1和和 t 到到t-1 兩個(gè)部分兩個(gè)部分0,t 1p的定義及的定義及( 2 )i,j(01)gijt 0,t 10,t 10,t 100,t 10,t 100,t 1pp,max,gspgsp0,t 10,t 10,t 100,t 1t,t-1tt,t-1ppmax(,),gspgs pt到到t-1階段階段總指標(biāo)取決于總指標(biāo)取決于 和和tt-1t-1t-1(,)ss

17、xt,t-1p0,t 10,t 10t,t-1t,t 1t0,t 100,t 10,t 100,t-1t,t-1tt,t-1pp(s )pp(s ),maxmax,gspgspgs p0,t 10,t 1t,t-1t,t 1t0,t 100,t-1t,t-1tt,t-1pppp(s )max,max,gspgs porxjtu第四章 動(dòng)態(tài)規(guī)劃(充分性充分性)設(shè)設(shè) 為任一子策略為任一子策略, 為由為由 所確定的第所確定的第t階段的起始狀態(tài)階段的起始狀態(tài), 則則0,t-10,t-1t,t-1,pppt00,t 1(,)sspt,t-1t,t 1tt,t-1tt,t-1t,t-1tt,t-1pp(s

18、 ),max,gs pgs p由由( 2 )與與 的含義知的含義知i,j(01)gijt 0,t 100,t-10,t 100,t-1t,t 1tt,t-1,gspgspgs pt,t-1t,t 1t0,t 100,t-1t,t 1tt,t-1pp(s ),max,gspgs p0,t 10,t 10t,t-1t,t 1t0,t 100,t-1t,t 1tt,t-1pp(s )pp(s )max,max,gspgs p0,t 100,t 1,gsporxjtu第四章 動(dòng)態(tài)規(guī)劃只要只要 使使( 3 )式成立式成立, 則對(duì)任一策略則對(duì)任一策略 , 都有都有0,t 1p0,t-1p0,t 100,t

19、-10,t 100,t 1,gspgsp故故 必為最優(yōu)策略必為最優(yōu)策略 .0,t 1p利用該定理利用該定理, 則用反證法很容易證明下列結(jié)論成立則用反證法很容易證明下列結(jié)論成立 .推推論論 : 若允許策略若允許策略 是最優(yōu)策略是最優(yōu)策略, 則對(duì)任意的則對(duì)任意的 , , 它的子策略它的子策略 對(duì)以對(duì)以 為起點(diǎn)的為起點(diǎn)的t到到t-1 子過(guò)程來(lái)說(shuō)子過(guò)程來(lái)說(shuō), 必是最優(yōu)策略必是最優(yōu)策略 .0,t 1p(01)ttt t,t 1ptt-1t-1t-1(,)ssxorxjtu第四章 動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃方法的優(yōu)越性動(dòng)態(tài)規(guī)劃方法的優(yōu)越性 : 易于確定全局最優(yōu)解易于確定全局最優(yōu)解 .逐步改善法逐步改善法 能得到一族

20、解能得到一族解, 有利于分析結(jié)果有利于分析結(jié)果 . 能利用經(jīng)驗(yàn)及實(shí)際問(wèn)題的演變能利用經(jīng)驗(yàn)及實(shí)際問(wèn)題的演變, 提高求解的效率提高求解的效率 .不足之處不足之處 :l 沒(méi)有一個(gè)統(tǒng)一的標(biāo)準(zhǔn)模型沒(méi)有一個(gè)統(tǒng)一的標(biāo)準(zhǔn)模型 ;l 在數(shù)值求解時(shí)在數(shù)值求解時(shí), 內(nèi)存占有量與計(jì)算量隨問(wèn)題維數(shù)的增大而指內(nèi)存占有量與計(jì)算量隨問(wèn)題維數(shù)的增大而指 數(shù)增長(zhǎng)數(shù)增長(zhǎng), 此即所謂的此即所謂的維數(shù)災(zāi)難維數(shù)災(zāi)難 .orxjtu第四章 動(dòng)態(tài)規(guī)劃建立動(dòng)態(tài)規(guī)劃模型的一般步驟建立動(dòng)態(tài)規(guī)劃模型的一般步驟 : 將問(wèn)題的演變過(guò)程劃分成恰當(dāng)?shù)碾A段將問(wèn)題的演變過(guò)程劃分成恰當(dāng)?shù)碾A段 ; 正確選擇狀態(tài)變量正確選擇狀態(tài)變量 , 使它既能描述過(guò)程的演變使它既

21、能描述過(guò)程的演變, 又要滿足又要滿足 無(wú)后效性無(wú)后效性 ;ts 選定決策變量選定決策變量 及相應(yīng)的允許決策集合及相應(yīng)的允許決策集合 ;tx 正確寫(xiě)出效益函數(shù)正確寫(xiě)出效益函數(shù) 的關(guān)系的關(guān)系, 使之滿足下面三個(gè)性質(zhì)使之滿足下面三個(gè)性質(zhì) :t,tg 正確寫(xiě)出狀態(tài)轉(zhuǎn)移方程正確寫(xiě)出狀態(tài)轉(zhuǎn)移方程 ;a ) 是定義在全過(guò)程和所有后部子過(guò)程上的數(shù)量函數(shù)是定義在全過(guò)程和所有后部子過(guò)程上的數(shù)量函數(shù) ;b ) 要具有可分離性要具有可分離性, 并滿足遞推關(guān)系并滿足遞推關(guān)系, 即即 :t,tttt+1tttt+1,tt+1t+1t+1,(,)gs xss x gsxsc ) 函數(shù)函數(shù) 關(guān)于關(guān)于 嚴(yán)格單調(diào)嚴(yán)格單調(diào) .tt

22、tt+1,t,s x gt+1,tg 4.3 0-1背包問(wèn)題orxjtu第四章 動(dòng)態(tài)規(guī)劃一般的一般的01背包問(wèn)題可表述為下列優(yōu)化問(wèn)題背包問(wèn)題可表述為下列優(yōu)化問(wèn)題 :nnnjjjjj=1j=1( )max:,z bc xa xbxb( 4 )n維維01向量向量nb該問(wèn)題的任何一個(gè)例子可通過(guò)指定整數(shù)該問(wèn)題的任何一個(gè)例子可通過(guò)指定整數(shù)n和和b以及兩個(gè)正整值以及兩個(gè)正整值n維向量維向量 和和 的值來(lái)得到的值來(lái)得到 .tt1n1n( ,)(,)cccaaa將將01背包問(wèn)題看作具有背包問(wèn)題看作具有n個(gè)階段的序列決策過(guò)程個(gè)階段的序列決策過(guò)程. 該過(guò)程在第該過(guò)程在第 階段的狀態(tài)階段的狀態(tài) :(1)kknkkj

23、jk-1kkj=1sba xsaxorxjtu第四章 動(dòng)態(tài)規(guī)劃從而從而其中其中 . 對(duì)于對(duì)于 , 狀態(tài)變量與決策變量之允許取值狀態(tài)變量與決策變量之允許取值范圍分別為范圍分別為 .01,sbkn kk0,0,1sb x對(duì)于對(duì)于 ,定義定義 和和k1,1,knnkkkkkjjjjj nj n( )max:,0,1,zdc xa xdxbdb( 5 )從而從而 .n( )( )z bz b遞歸過(guò)程由下式來(lái)初始化遞歸過(guò)程由下式來(lái)初始化 :11,cad若若0否否則則. .1z ( )dkk-1kk-1kk(,),sxsa xkk-1kkk(,),1,gsxc xkn 狀態(tài)轉(zhuǎn)移方程狀態(tài)轉(zhuǎn)移方程階段效益階段

24、效益orxjtu第四章 動(dòng)態(tài)規(guī)劃u 若在若在( 5 )的一個(gè)最優(yōu)解中的一個(gè)最優(yōu)解中 ,則則 , 且且kk10 xdak-1k-1k-1kkjjjjkj nj n( )max:,zdcc xa xdaxbkk-1k()czdau 若若( 5 )的最優(yōu)解使的最優(yōu)解使 , 則則k0 x k-1k-1k-1kjjjjk-1j nj n( )max:,( )zdc xa xdxbzd對(duì)于對(duì)于 和和 , 有有2,0,kndbk-1k( )zdad若若k-1kk-1kkmax( ),()zdczdaad若若k( )zd( 6 )orxjtu第四章 動(dòng)態(tài)規(guī)劃關(guān)系關(guān)系( 6 )即為確定即為確定 的基本遞歸關(guān)系的

25、基本遞歸關(guān)系 .n( )z b若對(duì)若對(duì) 定義定義 , 則則( 6 )式對(duì)式對(duì)k=1也成立也成立 .00( )0dz d當(dāng)當(dāng) 時(shí)時(shí), 對(duì)所有的對(duì)所有的k, 令令 0d k( )zd 對(duì)對(duì) 和和 , 有有1,0,1,kndbkk-1kk-1k( )max( ),()zdzdczda( 7 )確定確定 所要求的運(yùn)算次數(shù)為所要求的運(yùn)算次數(shù)為 .()nbn( )z b 一旦確定了一旦確定了 , , 則沿相反方向的一個(gè)遞歸就則沿相反方向的一個(gè)遞歸就可確定最優(yōu)解可確定最優(yōu)解 .k1,zkn0001n,xxxorxjtu第四章 動(dòng)態(tài)規(guī)劃具體地具體地, 有有nn-10( )( ),z bzb若若1否否則則. .

26、0nx現(xiàn)令現(xiàn)令 , 則對(duì)則對(duì) , 有有n00kjjj=k+1dba x1,1kn 00kkk-1k0()(),zdzd若若1否否則則. .0kx上述算法總的運(yùn)行時(shí)間為上述算法總的運(yùn)行時(shí)間為 .()nborxjtu第四章 動(dòng)態(tài)規(guī)劃exp.: 求解下列求解下列01背包問(wèn)題背包問(wèn)題 :123412344max 16192328,s.t.23457 ,.xxxxxxxxxb應(yīng)用上述算法得應(yīng)用上述算法得001,d對(duì)對(duì)1627.d對(duì)對(duì)1( )z d001,d當(dāng)當(dāng)162,d 當(dāng)當(dāng)1934 max(16,190) ,d當(dāng)當(dāng)357 max(16,19 16) ,d當(dāng)當(dāng)5 52( )z dorxjtu第四章 動(dòng)態(tài)

27、規(guī)劃2( )03z dd當(dāng)當(dāng)時(shí)時(shí), ,max(19,230)234d當(dāng)當(dāng)時(shí)時(shí), ,max(35,230)355d當(dāng)當(dāng)時(shí)時(shí), ,max(35,23 16)396d當(dāng)當(dāng)時(shí)時(shí), ,max(35,23 19)427d當(dāng)當(dāng)時(shí)時(shí). .3( )z d43(7)max(42,28(2)44.zz000043211,0,1xxxx( , 而而 )3211(2)(2)(2)(2)0zzzzorxjtu第四章 動(dòng)態(tài)規(guī)劃以上算法可直接推廣到下列有界變量背包問(wèn)題以上算法可直接推廣到下列有界變量背包問(wèn)題 :njjjjjjj nj n( )max:,z bc xa xb xjn xz這里這里 , 表示表示n維非負(fù)整值向量維

28、非負(fù)整值向量 , 和和b均為正整數(shù)均為正整數(shù) .n1,2,nnzjjj,a c1jn( 8 )顯然顯然, 問(wèn)題問(wèn)題( 4 )是是( 8 )在對(duì)所有的在對(duì)所有的 有有 時(shí)的特例時(shí)的特例 .j1jn為求解問(wèn)題為求解問(wèn)題( 8 ), 只需將只需將( 7 )用下列遞歸方程來(lái)代替即可用下列遞歸方程來(lái)代替即可1kkkk-1kkkkkk( )max():min,dzdc xzda xxxza這里這里 , . 而對(duì)所有的而對(duì)所有的 , .1,0,1,kndb00( )0db z d( 9 )orxjtu第四章 動(dòng)態(tài)規(guī)劃對(duì)于固定的對(duì)于固定的k, 求解求解( 9 )所需運(yùn)算次數(shù)的界為所需運(yùn)算次數(shù)的界為k( (+1

29、) )b整個(gè)算法的運(yùn)行時(shí)間為整個(gè)算法的運(yùn)行時(shí)間為 .2()nb總可以對(duì)所有的總可以對(duì)所有的 取取 jnjkdxa對(duì)各個(gè)變量的顯式界是沒(méi)有必要的對(duì)各個(gè)變量的顯式界是沒(méi)有必要的 4.4 旅行商問(wèn)題orxjtu第四章 動(dòng)態(tài)規(guī)劃旅行商問(wèn)題可形象化地描述為旅行商問(wèn)題可形象化地描述為 : 設(shè)有設(shè)有n+1個(gè)城市個(gè)城市, 分別用分別用0,1, , n來(lái)表示來(lái)表示. 從城市從城市i到城市到城市j的距離為的距離為 . 一個(gè)推銷(xiāo)員要從城市一個(gè)推銷(xiāo)員要從城市0出發(fā)出發(fā), 到達(dá)其它任一城市到達(dá)其它任一城市一次且僅僅一次一次且僅僅一次, 然后再回到城市然后再回到城市0. 問(wèn)題是他應(yīng)如何選擇行走問(wèn)題是他應(yīng)如何選擇行走路線路

30、線, 使總的路程最短使總的路程最短 .ijdi1,2,3,1,1,niin 由城市由城市0到城市到城市i可以可以通過(guò)的中間城市的集合通過(guò)的中間城市的集合到達(dá)到達(dá)i之前中途所實(shí)際經(jīng)過(guò)的城市的集合之前中途所實(shí)際經(jīng)過(guò)的城市的集合sisnorxjtu第四章 動(dòng)態(tài)規(guī)劃, i s描述決策過(guò)程的描述決策過(guò)程的狀態(tài)變量狀態(tài)變量 將求解過(guò)程分為將求解過(guò)程分為n個(gè)階段個(gè)階段, 每個(gè)階段的每個(gè)階段的決策決策為由一個(gè)城市為由一個(gè)城市走到另外某個(gè)城市走到另外某個(gè)城市 第第 階段的階段的最優(yōu)值函數(shù)最優(yōu)值函數(shù)(從城市從城市0經(jīng)由經(jīng)由s中中k個(gè)城市到達(dá)城市個(gè)城市到達(dá)城市i的最短路線的長(zhǎng)度的最短路線的長(zhǎng)度)(1)kknk( ,

31、 )gi s動(dòng)態(tài)規(guī)劃的遞推關(guān)系動(dòng)態(tài)規(guī)劃的遞推關(guān)系 :kk-1jij si( , )min( , ),1,2, ,1,2, ,gi sgj sjdkninsn邊界條件為邊界條件為 .00i( ,)gid 第第k階段的最優(yōu)決策函數(shù)階段的最優(yōu)決策函數(shù)令令k( , )p i sorxjtu第四章 動(dòng)態(tài)規(guī)劃exp.: 求解距離矩陣由下表給出的四個(gè)城市旅行商求解距離矩陣由下表給出的四個(gè)城市旅行商問(wèn)題問(wèn)題 .四城市間的距離四城市間的距離距離距離ij 0 1 2 301236550580880970679orxjtu第四章 動(dòng)態(tài)規(guī)劃解解 :由邊界條件知由邊界條件知001002003(1,)8,(2,)5,(3,)6gdgdgd 當(dāng)當(dāng)k=1時(shí)時(shí)1021(1,2)(2,)5