動態(tài)規(guī)劃問題

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

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

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

4、的數(shù)目，階段變量用k表示。明確狀態(tài)變量和狀態(tài)可能集合。狀態(tài)變量必須包含在給定的階段上確定全部允許決策所需要的信息。狀態(tài)變量的確定決定了整個決策過程是不是具有無后效性，因而也決定著能不能用動態(tài)規(guī)劃方法來求解。狀態(tài)可能集是關(guān)于狀態(tài)的約束條件，因此為了求解必須正確地確定狀態(tài)可能集。動態(tài)規(guī)劃的建模動態(tài)規(guī)劃的建模確定決策變量和決策允許集合。與靜態(tài)問題相同，決策變量應(yīng)能夠反映對問題所作的決策，決策變量也應(yīng)有其相應(yīng)的約束條件，在建模時應(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)往后的決策過程，因此必須明確狀

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

6、最優(yōu)最優(yōu)目標值 R*最優(yōu)策略 使得目標達到最優(yōu)的決策序列。最優(yōu)路線 在采取最優(yōu)策略時，系統(tǒng)從x1開始所經(jīng)過的狀態(tài)序列求解動態(tài)規(guī)劃模型 找到最優(yōu)策略、最優(yōu)路線和最優(yōu)目標值。 ),(*2*1nuuu),(*1*2*1nxxx),(*1kkkkuxTx動態(tài)規(guī)劃最優(yōu)性原理動態(tài)規(guī)劃最優(yōu)性原理多段決策過程的特點 每個階段都要進行決策 相繼進行的階段決策構(gòu)成的決策序列 前一階段的終止狀態(tài)又是后一階段的初始狀態(tài)階段最優(yōu)決策不能只從本階段的效應(yīng)出發(fā)，必須通盤考慮，整體規(guī)劃。階段k的最優(yōu)決策不應(yīng)該只是本階段效應(yīng)的最優(yōu)，而必須是本階段及其所有后續(xù)階段的總體最優(yōu)，即關(guān)于整個k后部子過程的最優(yōu)決策。動態(tài)規(guī)劃最優(yōu)性原理動

7、態(tài)規(guī)劃最優(yōu)性原理最優(yōu)性原理 “最優(yōu)策略具有的基本性質(zhì)是：無論初始狀態(tài)和初始決策如何，對于前面決策所造成的某一狀態(tài)而言，下余的決策序列必構(gòu)成最優(yōu)策略”。AMB動態(tài)規(guī)劃最優(yōu)性原理動態(tài)規(guī)劃最優(yōu)性原理最優(yōu)性原理的含意 最優(yōu)策略的任何一部分子策略，也是相應(yīng)初始狀態(tài)的最優(yōu)策略。 每個最優(yōu)策略只能由最優(yōu)子策略構(gòu)成。顯然，對于具有無后效性的多段決策過程而言，如果按照k后部子過程最優(yōu)的原則來求各階段狀態(tài)的最優(yōu)決策，那么這樣構(gòu)成的最優(yōu)決策序列或策略一定具有最優(yōu)性原理所提示的性質(zhì)。 貝爾曼函數(shù)貝爾曼函數(shù)貝爾曼函數(shù)fk(xk)： 在階段k從初始狀態(tài)xk出發(fā)，執(zhí)行最優(yōu)決策序列或策略，到達過程終點時，整個k-子過程中的目

8、標函數(shù)取值，稱為條件最優(yōu)目標函數(shù)，亦稱貝爾曼函數(shù)。nkuxroptxfnkiiiiuukknk,.,2 , 1),()(條件最優(yōu)策略 多段決策過程的任一階段狀態(tài)xk的最優(yōu)策略 處于條件xk時的最優(yōu)策略。條件最優(yōu)決策 構(gòu)成條件最優(yōu)策略的決策)(kkxu,1nkkuuu貝爾曼函數(shù)貝爾曼函數(shù)條件最優(yōu)目標函數(shù)值fk(xk) 執(zhí)行條件最優(yōu)策略時的目標函數(shù)值nkiiiikkuxrxf),()(條件最優(yōu)路線 執(zhí)行條件最優(yōu)策略時的階段狀態(tài)序列),(1kkkkuxTx,11nnkkxxxx貝爾曼函數(shù)貝爾曼函數(shù)條件最優(yōu)k-子策略 系統(tǒng)從xk出發(fā)，在k-后部子過程中的最優(yōu)策略k-子過程條件最優(yōu)目標函數(shù) fk(xk)

9、是從xk出發(fā)系統(tǒng)在k-后部子過程中的最優(yōu)目標值，多段決策問題所求解的最優(yōu)目標函數(shù)值 R*=f1(x1*)動態(tài)規(guī)劃基本方程 fk(xk)與fk1(xk1)之間的遞推關(guān)系動態(tài)規(guī)劃方法的依據(jù)是最優(yōu)性原理動態(tài)規(guī)劃基本方程動態(tài)規(guī)劃基本方程設(shè)在階段k的狀態(tài)xk執(zhí)行了任意選定決策uk后的狀態(tài)是xk+1=Tk(xk,uk)。這時k-后部子過程就縮小為k+1后部子過程。根據(jù)最優(yōu)性原理，對k+1后部子過程應(yīng)采取最優(yōu)策略，由于無后效性，k后部子過程的目標函數(shù)值為 ),(),(1kkkkkkkuxTfuxr),(),()(1kkkkkkkukkuxTfuxroptxfk),(1kkkkuxTx動態(tài)規(guī)劃基本方程動態(tài)規(guī)劃

10、基本方程),(1kkkkuxTxnkiiiiuukkuxroptxfnk),()( ),(),(11nkiiiiuukkkuuxroptuxroptnkk)(),(11kkkkkuxfuxroptk動態(tài)規(guī)劃基本方程動態(tài)規(guī)劃基本方程),(1kkkkuxTxnkiiiikkuxrxf),()(nkiiiikkkuxruxr1),(),()(),(11kkkkkuxfuxroptk動態(tài)規(guī)劃方法基本原理動態(tài)規(guī)劃方法基本原理動態(tài)規(guī)劃方法基本原理 ),(),()(1kkkkkkkukkuxTfuxroptxfk),(1kkkkuxTxrk(xk, uk)和xk+1=Tk(xk, uk)都是已知的函數(shù)求fk

11、(xk)需要首先求關(guān)于xk的所有k+1段狀態(tài)xk+1的fk+1(xk+1)逆序地求出條件最優(yōu)目標函數(shù)值集合和條件最優(yōu)決策集合狀態(tài)xk+1是由前面階段的狀態(tài)決定的用問題給定的初始條件，即可順序地求出整個多段決策問題的最優(yōu)目標函數(shù)值、最優(yōu)策略和最優(yōu)路線。動態(tài)規(guī)劃問題求解的一般步驟動態(tài)規(guī)劃問題求解的一般步驟 逆序地求出條件最優(yōu)目標函數(shù)值集合和條件最優(yōu)決策集合k=n時，動態(tài)規(guī)劃基本方程是 )(),()(11nnnnnunnxfuxroptxfn0)(11nnxf邊界條件),()(nnnunnuxroptxfnk=n時的動態(tài)規(guī)劃基本方程成為 )(,()(nnnnnnxuxrxf動態(tài)規(guī)劃問題求解的一般步驟

12、動態(tài)規(guī)劃問題求解的一般步驟 逆序地求出條件最優(yōu)目標函數(shù)值集合和條件最優(yōu)決策集合k=n1時，動態(tài)規(guī)劃的基本方程是)(),()(111111nnnnnunnxfuxroptxfn所有的fn(xn)都已經(jīng)求出，因此可以根據(jù)xn=Tn-1(xn-1,un-1)就階段n-1每個可能狀態(tài)xn-1Xn-1求條件最優(yōu)決策及相應(yīng)的條件最優(yōu)目標函數(shù)值fn1(xn1) )();(111111nnnnnnXxxuxf動態(tài)規(guī)劃問題求解的一般步驟動態(tài)規(guī)劃問題求解的一般步驟 逆序地求出條件最優(yōu)目標函數(shù)值集合和條件最優(yōu)決策集合k=1時，動態(tài)規(guī)劃的基本方程是)(),()(22111111xfuxroptxfu所有的f2(x2)

13、都已經(jīng)求出，因此可以根據(jù)x2=T1(x1,u1)就階段1每個可能狀態(tài)x1X1求條件最優(yōu)決策及相應(yīng)的條件最優(yōu)目標函數(shù)值f1(x1) )();(111111Xxxuxf動態(tài)規(guī)劃問題求解的一般步驟動態(tài)規(guī)劃問題求解的一般步驟 逆序地求出條件最優(yōu)目標函數(shù)值集合和條件最優(yōu)決策集合)();(111111Xxxuxf),(111uxr)(22xf)();(111111nnnnnnXxxuxf),(111nnnuxr)(nnxf)();(nnnnnnXxxuxf),(nnnuxr動態(tài)規(guī)劃問題求解的一般步驟動態(tài)規(guī)劃問題求解的一般步驟 順序地求出最優(yōu)目標值、最優(yōu)策略和最優(yōu)路線若x1已知，則)(11*11xfoptR

14、Xx )(*11xf)(11*xfR )()(111*1xuxu階段1的條件最優(yōu)決策就是階段1的關(guān)于整個過程的最優(yōu)決策若x1未知 )()(*11*1*1xuxu動態(tài)規(guī)劃問題求解的一般步驟動態(tài)規(guī)劃問題求解的一般步驟順序地求出最優(yōu)目標值、最優(yōu)策略和最優(yōu)路線)(11*11xfoptRXx )(*11xf*1x)()(*1*1*11xuxu),(*1*11*2uxTx)()(*2*2*22xuxu)()(*1*1*11nnnnxuxu),(*1*11*nnnnuxTx)()(*nnnnxuxu),(*1nnnnuxTx),(*2*22*3uxTx 動態(tài)規(guī)劃四大要素、一個方程動態(tài)規(guī)劃四大要素、一個方程五

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

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

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

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