1、第四章動(dòng)態(tài)規(guī)劃問(wèn)題動(dòng)態(tài)規(guī)劃的概念與模型 靜態(tài)決策 一次性決策l動(dòng)態(tài)決策 多階段決策決策x1x2Zu輸入決策輸出決策效應(yīng)第一月x1x2r1u1第二月x3r2u2第三月x4r3u3多段決策過(guò)程T1x1x2r1u1T2x3r2u2Tkxkxk+!rkukTnxnxn+1rnunn個(gè)決策子問(wèn)題K稱為階段變量xk描述k階段初的狀態(tài)，稱為狀態(tài)變量一般把輸入狀態(tài)稱為該階段的階段狀態(tài)。uk的取值代表k階段對(duì)第k子問(wèn)題所進(jìn)行的決策，稱為k階段的決策變量rk為k階段從狀況xk出發(fā),做決策uk之后的后果，稱為k階段的階段效應(yīng)。 具有無(wú)后效性的多段決策過(guò)程 Xk+1=Tk (xk, uk)系統(tǒng)從k階段往后的決策只與k

2、階段系統(tǒng)的狀態(tài)xk有關(guān),而與系統(tǒng)以前的決策無(wú)關(guān)，則稱為具有無(wú)后效性的多段決策過(guò)程。 T1x1x2r1 (x1, u1)u1(x1)T2x3r2 (x2 ,u2)u2 (x2)Tkxkxk+!rk (xk,uk)uk (xk)Tnxnxn+1rn (xn,un)un (xn)K后部子過(guò)程多段決策過(guò)程中從第k階段到最終階段的過(guò)程稱為k-后部子過(guò)程，簡(jiǎn)稱k-子過(guò)程。 Tkxkxk+!rk (xk,uk)uk (xk)Tnxnxn+1rn (xn,un)un (xn)動(dòng)態(tài)規(guī)劃模型Opt表示求優(yōu)Xk是一個(gè)集合，表示k階段狀態(tài)可能取值的范圍，稱為狀態(tài)可能集合。Uk是一個(gè)集合，表示k階段決策可能取值的范圍，

3、稱為決策允許集合，一般來(lái)說(shuō)對(duì)于不同狀態(tài)，可以作的決策的范圍是不同的。因此決策允許集合一般寫為Uk(xk)。 ),(11kkknkuuuxrRoptnnkUuXxuxTxtskkkkkkkk1),(. .1動(dòng)態(tài)規(guī)劃的建模 動(dòng)態(tài)規(guī)劃建模確定階段與階段變量明確狀態(tài)變量和狀態(tài)可能集合。確定決策變量和決策允許集合。確定狀態(tài)轉(zhuǎn)移方程。明確階段效應(yīng)和目標(biāo)。動(dòng)態(tài)規(guī)劃的建模確定階段與階段變量階段的劃分一般是按照決策進(jìn)行的時(shí)間或空間上的先后順序劃分的，階段數(shù)等于多段決策過(guò)程中從開(kāi)始到結(jié)束所需要作出決策的數(shù)目，階段變量用k表示。明確狀態(tài)變量和狀態(tài)可能集合。狀態(tài)變量必須包含在給定的階段上確定全部允許決策所需要的信息。

4、狀態(tài)變量的確定決定了整個(gè)決策過(guò)程是不是具有無(wú)后效性，因而也決定著能不能用動(dòng)態(tài)規(guī)劃方法來(lái)求解。狀態(tài)可能集是關(guān)于狀態(tài)的約束條件，因此為了求解必須正確地確定狀態(tài)可能集。動(dòng)態(tài)規(guī)劃的建模確定決策變量和決策允許集合。與靜態(tài)問(wèn)題相同，決策變量應(yīng)能夠反映對(duì)問(wèn)題所作的決策，決策變量也應(yīng)有其相應(yīng)的約束條件，在建模時(shí)應(yīng)明確決策允許集合Uk(xk)。確定狀態(tài)轉(zhuǎn)移方程。系統(tǒng)k階段從狀態(tài)xk出發(fā)作了決策uk(xk)之后的結(jié)果之一是系統(tǒng)狀態(tài)的轉(zhuǎn)移，這一結(jié)果直接影響系統(tǒng)往后的決策過(guò)程，因此必須明確狀態(tài)的轉(zhuǎn)移過(guò)程，即根據(jù)問(wèn)題的內(nèi)在關(guān)系，明確xk+1=Tk(xk,uk)中的函數(shù)Tk（ ）。動(dòng)態(tài)規(guī)劃的建模明確階段效應(yīng)和目標(biāo)。階段效

5、應(yīng)rk(xk,uk)是在階段k以xk出發(fā)作了決策uk之后所產(chǎn)生的后果，必須明確rk與xk，uk的關(guān)系，才能構(gòu)成目標(biāo)函數(shù)。目標(biāo)函數(shù)是由階段效應(yīng)經(jīng)過(guò)某種集結(jié)而得到的，如何集結(jié)視具體問(wèn)題而定，同時(shí)還應(yīng)根據(jù)問(wèn)題確定目標(biāo)是求最大還是最小。由于在經(jīng)濟(jì)系統(tǒng)中的大多數(shù)情況下，目標(biāo)的集結(jié)方法都是求和，因此，在不作說(shuō)明的情況下，往后的討論都針對(duì)目標(biāo)為和的形式進(jìn)行。 動(dòng)態(tài)規(guī)劃解的概念多段決策過(guò)程中所要求解的是，從起始狀態(tài)x1開(kāi)始，進(jìn)行一系列的決策，使目標(biāo)R達(dá)到最優(yōu)最優(yōu)目標(biāo)值 R*最優(yōu)策略 使得目標(biāo)達(dá)到最優(yōu)的決策序列。最優(yōu)路線 在采取最優(yōu)策略時(shí)，系統(tǒng)從x1開(kāi)始所經(jīng)過(guò)的狀態(tài)序列求解動(dòng)態(tài)規(guī)劃模型 找到最優(yōu)策略、最優(yōu)路線和

6、最優(yōu)目標(biāo)值。 ),(*2*1nuuu),(*1*2*1nxxx),(*1kkkkuxTx動(dòng)態(tài)規(guī)劃最優(yōu)性原理多段決策過(guò)程的特點(diǎn) 每個(gè)階段都要進(jìn)行決策 相繼進(jìn)行的階段決策構(gòu)成的決策序列 前一階段的終止?fàn)顟B(tài)又是后一階段的初始狀態(tài)階段最優(yōu)決策不能只從本階段的效應(yīng)出發(fā)，必須通盤考慮，整體規(guī)劃。階段k的最優(yōu)決策不應(yīng)該只是本階段效應(yīng)的最優(yōu)，而必須是本階段及其所有后續(xù)階段的總體最優(yōu)，即關(guān)于整個(gè)k后部子過(guò)程的最優(yōu)決策。動(dòng)態(tài)規(guī)劃最優(yōu)性原理最優(yōu)性原理 “最優(yōu)策略具有的基本性質(zhì)是：無(wú)論初始狀態(tài)和初始決策如何，對(duì)于前面決策所造成的某一狀態(tài)而言，下余的決策序列必構(gòu)成最優(yōu)策略”。AMB動(dòng)態(tài)規(guī)劃最優(yōu)性原理最優(yōu)性原理的含意 最

7、優(yōu)策略的任何一部分子策略，也是相應(yīng)初始狀態(tài)的最優(yōu)策略。 每個(gè)最優(yōu)策略只能由最優(yōu)子策略構(gòu)成。顯然，對(duì)于具有無(wú)后效性的多段決策過(guò)程而言，如果按照k后部子過(guò)程最優(yōu)的原則來(lái)求各階段狀態(tài)的最優(yōu)決策，那么這樣構(gòu)成的最優(yōu)決策序列或策略一定具有最優(yōu)性原理所提示的性質(zhì)。 貝爾曼函數(shù)貝爾曼函數(shù)fk(xk)： 在階段k從初始狀態(tài)xk出發(fā)，執(zhí)行最優(yōu)決策序列或策略，到達(dá)過(guò)程終點(diǎn)時(shí)，整個(gè)k-子過(guò)程中的目標(biāo)函數(shù)取值，稱為條件最優(yōu)目標(biāo)函數(shù)，亦稱貝爾曼函數(shù)。nkuxroptxfnkiiiiuukknk,.,2 , 1),()(條件最優(yōu)策略 多段決策過(guò)程的任一階段狀態(tài)xk的最優(yōu)策略 處于條件xk時(shí)的最優(yōu)策略。條件最優(yōu)決策 構(gòu)成條

8、件最優(yōu)策略的決策)(kkxu,1nkkuuu貝爾曼函數(shù)條件最優(yōu)目標(biāo)函數(shù)值fk(xk) 執(zhí)行條件最優(yōu)策略時(shí)的目標(biāo)函數(shù)值nkiiiikkuxrxf),()(條件最優(yōu)路線 執(zhí)行條件最優(yōu)策略時(shí)的階段狀態(tài)序列),(1kkkkuxTx,11nnkkxxxx貝爾曼函數(shù)條件最優(yōu)k-子策略 系統(tǒng)從xk出發(fā)，在k-后部子過(guò)程中的最優(yōu)策略k-子過(guò)程條件最優(yōu)目標(biāo)函數(shù) fk(xk)是從xk出發(fā)系統(tǒng)在k-后部子過(guò)程中的最優(yōu)目標(biāo)值，多段決策問(wèn)題所求解的最優(yōu)目標(biāo)函數(shù)值 R*=f1(x1*)動(dòng)態(tài)規(guī)劃基本方程 fk(xk)與fk1(xk1)之間的遞推關(guān)系動(dòng)態(tài)規(guī)劃方法的依據(jù)是最優(yōu)性原理動(dòng)態(tài)規(guī)劃基本方程設(shè)在階段k的狀態(tài)xk執(zhí)行了任意

9、選定決策uk后的狀態(tài)是xk+1=Tk(xk,uk)。這時(shí)k-后部子過(guò)程就縮小為k+1后部子過(guò)程。根據(jù)最優(yōu)性原理，對(duì)k+1后部子過(guò)程應(yīng)采取最優(yōu)策略，由于無(wú)后效性，k后部子過(guò)程的目標(biāo)函數(shù)值為 ),(),(1kkkkkkkuxTfuxr),(),()(1kkkkkkkukkuxTfuxroptxfk),(1kkkkuxTx動(dòng)態(tài)規(guī)劃基本方程),(1kkkkuxTxnkiiiiuukkuxroptxfnk),()( ),(),(11nkiiiiuukkkuuxroptuxroptnkk)(),(11kkkkkuxfuxroptk動(dòng)態(tài)規(guī)劃基本方程),(1kkkkuxTxnkiiiikkuxrxf),()(

10、nkiiiikkkuxruxr1),(),()(),(11kkkkkuxfuxroptk動(dòng)態(tài)規(guī)劃方法基本原理動(dòng)態(tài)規(guī)劃方法基本原理 ),(),()(1kkkkkkkukkuxTfuxroptxfk),(1kkkkuxTxrk(xk, uk)和xk+1=Tk(xk, uk)都是已知的函數(shù)求fk(xk)需要首先求關(guān)于xk的所有k+1段狀態(tài)xk+1的fk+1(xk+1)逆序地求出條件最優(yōu)目標(biāo)函數(shù)值集合和條件最優(yōu)決策集合狀態(tài)xk+1是由前面階段的狀態(tài)決定的用問(wèn)題給定的初始條件，即可順序地求出整個(gè)多段決策問(wèn)題的最優(yōu)目標(biāo)函數(shù)值、最優(yōu)策略和最優(yōu)路線。動(dòng)態(tài)規(guī)劃問(wèn)題求解的一般步驟 逆序地求出條件最優(yōu)目標(biāo)函數(shù)值集合

11、和條件最優(yōu)決策集合k=n時(shí)，動(dòng)態(tài)規(guī)劃基本方程是 )(),()(11nnnnnunnxfuxroptxfn0)(11nnxf邊界條件),()(nnnunnuxroptxfnk=n時(shí)的動(dòng)態(tài)規(guī)劃基本方程成為 )(,()(nnnnnnxuxrxf動(dòng)態(tài)規(guī)劃問(wèn)題求解的一般步驟 逆序地求出條件最優(yōu)目標(biāo)函數(shù)值集合和條件最優(yōu)決策集合k=n1時(shí)，動(dòng)態(tài)規(guī)劃的基本方程是)(),()(111111nnnnnunnxfuxroptxfn所有的fn(xn)都已經(jīng)求出，因此可以根據(jù)xn=Tn-1(xn-1,un-1)就階段n-1每個(gè)可能狀態(tài)xn-1Xn-1求條件最優(yōu)決策及相應(yīng)的條件最優(yōu)目標(biāo)函數(shù)值fn1(xn1) )();(1

12、11111nnnnnnXxxuxf動(dòng)態(tài)規(guī)劃問(wèn)題求解的一般步驟 逆序地求出條件最優(yōu)目標(biāo)函數(shù)值集合和條件最優(yōu)決策集合k=1時(shí)，動(dòng)態(tài)規(guī)劃的基本方程是)(),()(22111111xfuxroptxfu所有的f2(x2)都已經(jīng)求出，因此可以根據(jù)x2=T1(x1,u1)就階段1每個(gè)可能狀態(tài)x1X1求條件最優(yōu)決策及相應(yīng)的條件最優(yōu)目標(biāo)函數(shù)值f1(x1) )();(111111Xxxuxf動(dòng)態(tài)規(guī)劃問(wèn)題求解的一般步驟 逆序地求出條件最優(yōu)目標(biāo)函數(shù)值集合和條件最優(yōu)決策集合)();(111111Xxxuxf),(111uxr)(22xf)();(111111nnnnnnXxxuxf),(111nnnuxr)(nnxf

13、)();(nnnnnnXxxuxf),(nnnuxr動(dòng)態(tài)規(guī)劃問(wèn)題求解的一般步驟 順序地求出最優(yōu)目標(biāo)值、最優(yōu)策略和最優(yōu)路線若x1已知，則)(11*11xfoptRXx )(*11xf)(11*xfR )()(111*1xuxu階段1的條件最優(yōu)決策就是階段1的關(guān)于整個(gè)過(guò)程的最優(yōu)決策若x1未知 )()(*11*1*1xuxu動(dòng)態(tài)規(guī)劃問(wèn)題求解的一般步驟順序地求出最優(yōu)目標(biāo)值、最優(yōu)策略和最優(yōu)路線)(11*11xfoptRXx )(*11xf*1x)()(*1*1*11xuxu),(*1*11*2uxTx)()(*2*2*22xuxu)()(*1*1*11nnnnxuxu),(*1*11*nnnnuxTx)

14、()(*nnnnxuxu),(*1nnnnuxTx),(*2*22*3uxTx 動(dòng)態(tài)規(guī)劃四大要素、一個(gè)方程五個(gè)關(guān)鍵因素 四大要素、一個(gè)方程：狀態(tài)變量及其可能集合決策變量及其允許集合狀態(tài)轉(zhuǎn)移方程階段效應(yīng)動(dòng)態(tài)規(guī)劃基本方程：),(1kkkkuxTx),(kkkuxr),(),()(1kkkkkkkukkuxTfuxroptxfk動(dòng)態(tài)規(guī)劃應(yīng)用舉例-最短路問(wèn)題例 某旅行者希望從s地起到t地，其間的道路系統(tǒng)如圖41所示，圖上圓圈表示途徑的地方，稱為節(jié)點(diǎn)，連結(jié)兩地的箭線表示道路，其上的數(shù)字表示該段道路長(zhǎng)度，箭頭表示通行的方向。試求s到t的最短路。adbetcfs9757845646547圖4-1動(dòng)態(tài)規(guī)劃應(yīng)用

15、舉例-最短路問(wèn)題adbetcfs9757845646547第一階段第一階段 第二階段第二階段 第三階段第三階段劃分階段劃分階段 k=1,2,3 代表三個(gè)階段代表三個(gè)階段動(dòng)態(tài)規(guī)劃應(yīng)用舉例-最短路問(wèn)題adbetcfs9757845646547狀態(tài)變量狀態(tài)變量xk取為取為k階段所在地，則有：階段所在地，則有： ,2211cbaXxsXx,4433tXxfedXx動(dòng)態(tài)規(guī)劃應(yīng)用舉例-最短路問(wèn)題adbetcfs9757845646547k階段決策是決定下一步走到哪里，階段決策是決定下一步走到哪里，uk(xk)取為下一步的所在點(diǎn)。取為下一步的所在點(diǎn)。 ,)(11cbasUu,)()(22fdaUau,)()

16、(22edbUbu,)()(22fedcUcu33tUu動(dòng)態(tài)規(guī)劃應(yīng)用舉例-最短路問(wèn)題逆序求條件最優(yōu)目標(biāo)函數(shù)集和條件最優(yōu)決策集由于第3階段末已到達(dá)t，往后的距離自然是零，因此f4(t)=0對(duì)3階段所有可能的狀態(tài)X3=d, e, f計(jì)算f3( )如下)(),(min)(4433333xfudrdfUutdutftdr)(5)(),(min343)(),(min)(4433333xfudrefUuteuter)(70),(min33)(),(min)(4433333xfufrffUutfutfr)(40),(min33動(dòng)態(tài)規(guī)劃應(yīng)用舉例-最短路問(wèn)題逆序求條件最優(yōu)目標(biāo)函數(shù)集和條件最優(yōu)決策集也可以用表格方

17、法計(jì)算如下t/tF3()U3()def5+07+04+0574tttr3(x3,u3)+f4(x4) f3(x3) u3(x3) 動(dòng)態(tài)規(guī)劃應(yīng)用舉例-最短路問(wèn)題逆序求條件最優(yōu)目標(biāo)函數(shù)集和條件最優(yōu)決策集對(duì)2階段所有可能的狀態(tài)X2=a, b, c計(jì)算f2( )如下)(),(min)(3322)(222xfuarafaUu)(),(min3322,2xfuarfdu)(),()(),(min3232fffardfdarfau)(84457min2)(),(min)(3322)(222xfubrbfbUu)(),()(),(min3232efebrdfdbrdbu)(107655min2動(dòng)態(tài)規(guī)劃應(yīng)用舉例

18、-最短路問(wèn)題逆序求條件最優(yōu)目標(biāo)函數(shù)集和條件最優(yōu)決策集對(duì)2階段所有可能的狀態(tài)X2=a, b, c計(jì)算f2( )如下)(),(min)(3322)(222xfucrcfcUu)(),()(),()(),(min323232fffcrefecrdfdcrdcu)(9467554min2動(dòng)態(tài)規(guī)劃應(yīng)用舉例-最短路問(wèn)題逆序求條件最優(yōu)目標(biāo)函數(shù)集和條件最優(yōu)決策集也可以用表格方法計(jì)算如下d/de/ef/fF2()U2()abc7+55+54+56+75+74+46+48109fddf2(x2) u2(x2) r2(x2,u2)+f3(x3) 動(dòng)態(tài)規(guī)劃應(yīng)用舉例-最短短問(wèn)題逆序求條件最優(yōu)目標(biāo)函數(shù)集和條件最優(yōu)決策集對(duì)1階段所有可能的狀態(tài)X1=s計(jì)算f1(