動態(tài)規(guī)劃理論部分

1、動態(tài)規(guī)劃理論部分第一頁，共53頁。 動態(tài)規(guī)劃是解決多階段決策過程最優(yōu)化問題的一種方法。在二十世紀(jì)五十年代由美國數(shù)學(xué)家理查德.貝爾曼(RichardBa11man)首先提出的。它可以把一個 n 維最優(yōu)化問題轉(zhuǎn)化為 n 個一維最優(yōu)化問題來求解。 一個決策問題，往往可以分解成若干個相互聯(lián)系，又相對獨(dú)立的階段，對于每一個階段，存在著很多方案可供選擇，我們要對每個階段作出一個決策。 而各階段之間又有密切的聯(lián)系，某一個階段的不同決策，將會對其它階段的決策產(chǎn)生重大的影響，某個階段局部的較優(yōu)方案，未必是整個問題的最好方案，某個階段局部的不好方案，也未必是整個問題的不好方案。 我們要尋找的是整個問題，也就是所有

2、階段總體的一個最優(yōu)方案，這就是動態(tài)規(guī)劃所要討論的問題。第二頁，共53頁。一、多階段決策問題 所謂多階段決策問題是有這樣一類決策過程，它可以劃分為若干個相互聯(lián)系的階段，在任一階段都有若干種方案可供選擇，選擇哪一種方案需要作出決策，這樣就形成一個決策序列，通常稱為一種策略。不同的策略就產(chǎn)生不同的效果，在所有可能的策略當(dāng)中，選擇一個效果最好的最優(yōu)策略，就是解決多階段決策問題的主要目的。下面舉幾個例子來說明。第三頁，共53頁。 例1： （最短路程問題）設(shè)從A地到E地要鋪設(shè)一條管道，其中要經(jīng)過若干個中間點(diǎn)(如圖)。圖中兩點(diǎn)之間連線上的數(shù)字表示兩地間的距離?，F(xiàn)在要選擇一條鋪設(shè)管道的路線，使總長度最短。25

3、11214106104131112396581052C1C3D1 AB1B3B2D2EC2第四頁，共53頁。 在這個問題中，從A到B 1 ，B2 ， B3中的哪一個點(diǎn)要作出一項(xiàng)決策，從B 1 ，B2 ， B3某點(diǎn)到 C 1，C2，C3 中的哪一個點(diǎn)又要作出一項(xiàng)決策等等。所以總共要作出四個決策。因此，我們可以把整個路程分為A，B ( 包括B 1 ，B2 ， B3) ，C ( 包括C 1，C2 ， C3 ， ) ，D (包括D1和D2)，E 五個階段。這就是一個多階段的決策問題。二、動態(tài)規(guī)劃的基本思想 用動態(tài)規(guī)劃求解多階段決策問題，是把整個問題劃分為若干階段后，依次地為每一個階段作出最優(yōu)決策，而每

4、個階段的最優(yōu)決策應(yīng)該是包含本階段和所有以前各階段在內(nèi)的最優(yōu)決策，也就是到本階段為止，包含以前各階段在內(nèi)的最優(yōu)總決策。因此，在確定了最后一個階段的決策之后，整個問題的最優(yōu)決策序列也就隨之產(chǎn)生。這就是用動態(tài)規(guī)劃解多階段決策問題的基本思想。第五頁，共53頁。以上面的例1來說明動態(tài)規(guī)劃解決問題的思想。設(shè)：Sk-第k階段的起點(diǎn)（狀態(tài)變量）dk(x, y) -第k階段的頂點(diǎn) x 到頂點(diǎn) y 的“距離”；fk(Sk) -第k階段從頂點(diǎn)Sk到終點(diǎn)的最短“路”長。 最短路線的重要特性就是：如果最短路線在第K站通過點(diǎn)Pk。則由點(diǎn)Pk 出發(fā)到達(dá)終點(diǎn)的這條路線，對于從點(diǎn)Pk 出發(fā)到達(dá)終點(diǎn)的所有可能選擇的不同路經(jīng)來說，

5、必定也是最短路線。第六頁，共53頁。例如，在最短路線問題中，如果找到了A到E的最短路：121ABCDE 則 應(yīng)該是由C2 出發(fā)到E點(diǎn)的所有可能不同線路中的最短路線21CDE 最短路線這一特性，啟發(fā)我們找最短路線的方法：那就是從最后一段開始，用由后向前逐步遞推的方法，求出各點(diǎn)到E點(diǎn)的最短路線，最后求得由A點(diǎn)到E點(diǎn)的最短路線。所以，動態(tài)規(guī)劃的常用的方法是從終點(diǎn)逐段向始點(diǎn)方向?qū)ふ摇白疃搪肪€” 。如圖所示：行進(jìn)方向起點(diǎn)終點(diǎn)動態(tài)規(guī)劃尋優(yōu)途徑第七頁，共53頁。 下面按上述思想，將例1從最后一段開始計(jì)算，由后向前逐步推移至A點(diǎn)。2511214106104131112396581052C1C3D1AB1B3B

6、2D2EC2f5(E)=0設(shè)想有k 5 時(shí)， f5(E) 0 。第八頁，共53頁。2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D1)=5f5(E)=04115()(,)( )505fDd D EfEK=4時(shí)：第九頁，共53頁。2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f4(D1)=54225()(,)( )202fDd D EfE第十頁，共53頁。2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E

7、)=0f3(C1)=8f4(D1)=5311242114111()min(,)()minmin8最優(yōu) 決 策9(,)()358211f CC DfDfDC DCDK=3時(shí)：第十一頁，共53頁。2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C2)=7f4(D1)=5f3(C1)=8222422141223DC7711min2556min)D(f)D,C()D(f)D,C(min)C(f最優(yōu)決策第十二頁，共53頁。2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)

8、=2f5(E)=0f3(C3)=12f4(D1)=5f3(C1)=8f3(C2)=7232423141333DC121213min21058min)D(f)D,C()D(f)D,C(min)C(f最優(yōu)決策第十三頁，共53頁。2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B1)=20f3(C2)=7f3(C1)=81131211232133311(,)()12820()min (,)()min 147min 2120(,)()10 1222最優(yōu) 決 策:B Cf CfBB Cf C

9、B Cf CBCK=2時(shí)：第十四頁，共53頁。2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B2)=14f3(C2)=7f3(C1)=8f2(B1)=212222322333212131()min (,)()min 107min 1714(,)(,)()4 1216最優(yōu) 決 策:)6814B CffBB Cf CB Cf CCBC第十五頁，共53頁。2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3

10、)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f2(B1)=21f2(B2)=143131233232333332(,)()13 821()min (,)()min 127min 1919(,)()11 1223最優(yōu) 決 策:B Cf CfBB Cf CB Cf CBC第十六頁，共53頁。2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f1(A)=19f2(B2)=14f2(B1)=2112113232222(

11、 ,)()22123( )minminmin19( ,)()1 1920最優(yōu) 決( ,)()5 14策9:1A BfBf AA BfBA BfBABK=1時(shí)：第十七頁，共53頁。2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f1(A)=19f2(B2)=14f2(B1)=21狀態(tài) 最優(yōu)決策 狀態(tài) 最優(yōu)決策 狀態(tài) 最優(yōu)決策 狀態(tài) 最優(yōu)決策 狀態(tài)AB2C1D1E（ A，B2）（ B2 ，C1 ）（ C1 , D1 ）（ D1 ,E）第十八頁

12、，共53頁。2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f1(A)=19f2(B2)=14f2(B1)=21狀態(tài) 最優(yōu)決策 狀態(tài) 最優(yōu)決策 狀態(tài) 最優(yōu)決策 狀態(tài) 最優(yōu)決策 狀態(tài)A （ A，B2） B2 （B2，C1） C1 （C1，D1） D1 （D1，E） E從A到E的最短路徑為19，路線為AB 2C1 D1 E 第十九頁，共53頁。三、動態(tài)規(guī)劃的基本概念 (1) 階段（stage） 把所研究的決策問題，按先后順序劃分為若 （2）狀

13、態(tài)（state） 狀態(tài)表示每個階段開始時(shí)所處的自然狀況或 (3) 決策（decision）決策表示在某一階段處于某種狀態(tài)時(shí)，決策者在若干種方案中作出的選擇決定。描述決策的變量稱決策變量，第k階段的決策變量常用uk表示。決策變量的取值會受到狀態(tài)變量的制約，被限制在某一范圍之內(nèi)。干相互聯(lián)系的決策步驟，以便按一定的次序進(jìn)行求解。描述階段的變量稱階段變量，常用k表示?？陀^條件，它描述了影響決策的因素隨決策進(jìn)程的變化情況，它既是前面階段所作決策的結(jié)果又是本階段作出決策的出發(fā)點(diǎn)和依據(jù)。描述狀態(tài)的變量稱為狀態(tài)變量，第k階段的狀態(tài)變量常用sk表示。通常，在第一階段狀態(tài)變量s1是確定的，稱初始狀態(tài)。第二十頁，共

14、53頁。T1S1S2V1u1T2S3V2u2TkSkSk+1VkukTnSnSn+1Vnun多階段決策過程如下：n個決策子問題k稱為階段變量Sk描述k階段初的狀態(tài)，即狀態(tài)變量一般把輸入狀態(tài)稱為該階段的階段狀態(tài)。uk的取值代表k階段對第k子問題所進(jìn)行的決策，稱為k階段的決策變量Vk為k階段從狀況Sk出發(fā),做出決策uk之后的后果，第二十一頁，共53頁。(4)策略（policy） 把從第一階段開始到最后階段終止的整個決策過程，稱為問題的全過程；而把從第k階段開始到最后階段終止的決策過程，或稱為k子過程。在全過程上，各階段的決策按順序排列組成的決策序列 p1,n u1,u2,un 稱為全過程策略，簡稱

15、策略；而在k子過程上的決策序列 pk,n uk,uk+1,un 稱為k子過程策略，也簡稱子策略。第二十二頁，共53頁。(5)(5)狀態(tài)轉(zhuǎn)移方程狀態(tài)轉(zhuǎn)移方程(6)指標(biāo)函數(shù)（準(zhǔn)則函數(shù)）,目標(biāo)函數(shù)和最優(yōu)值函數(shù) 指標(biāo)函數(shù)分為階段指標(biāo)函數(shù)和過程指標(biāo)函數(shù)。 階段指標(biāo)函數(shù)是對某一階段的狀態(tài)和決策產(chǎn)生的效益值的度量用Vk(sk,uk)表示。 從第k階段到最終階段的過程稱為k-后部子過程，簡稱為：k-子過程。 若第k階段的狀態(tài)變量值為sk，當(dāng)決策變量uk 的取值決定后，下一階段狀態(tài)變量Sk+1的值也就完全確定。即Sk+1的值對應(yīng)于Sk和uk的值。這種對應(yīng)關(guān)系記為: sk+1Tk(sk,uk)，稱為狀態(tài)轉(zhuǎn)移方程。

16、狀態(tài)轉(zhuǎn)移方程描述了由一個階段的狀態(tài)到下一階段的狀態(tài)的演變規(guī)律。第二十三頁，共53頁。 過程指標(biāo)函數(shù)是指從第k階段至第n階段所包含的各階段的狀態(tài)和決策所產(chǎn)生的總的效益值，記為: Vk,nVk,n(Sk,uk,Sk+1,uk+1,Sn,un)TkSkSk+!Vk (Sk,uk)uk (Sk)TnSnSn+1Vn (Sn,un)un (Sn)K子過程 定義在全過程上的準(zhǔn)則函數(shù)相當(dāng)于目標(biāo)函數(shù)，一般記為: V1,nV1,n(S1,u1, Sk,uk ,Sn,un)，或簡記為V1,n 第二十四頁，共53頁。,11,()(,)knkkk nkkkknnuufSopt VSuSuSu()kkfS 把過程指標(biāo)函

17、數(shù)Vk,n對k子過程策略pk,n求最優(yōu)，得到一個關(guān)于狀態(tài)Sk的函數(shù)，稱為最優(yōu)值函數(shù)或貝爾曼函數(shù)，記為: 。即各階段指標(biāo)函數(shù)的和: ,(,)nk njjjj kVV S u,(,)nk njjjj kVV S u各階段指標(biāo)函數(shù)的積: 動態(tài)規(guī)劃所要求的過程指標(biāo)函數(shù)應(yīng)具有可分離性，即可表達(dá)為它所包含的各階段指標(biāo)函數(shù)的函數(shù)形式。常見的兩種過程指標(biāo)函數(shù)形式是： 也就是說在階段k從初始狀態(tài)Sk出發(fā)，執(zhí)行最優(yōu)決策序列或策略，到達(dá)過程終點(diǎn)時(shí)，整個k-子過程中的最優(yōu)目標(biāo)函數(shù)取值。第二十五頁，共53頁。 式中式中的的“optopt”（optimizationoptimization）可根據(jù)具體問題的可根據(jù)具體問題

18、的實(shí)際實(shí)際意而取意而取minmin或或maxmax。,()(,)knnkkjjjuuj kfSoptV S u,()(,)knnkkjjjuuj kfSoptVSu或第二十六頁，共53頁。,1,1,11,1,11,11()(;)(,)(;)(,)(;)(,)()k nk nkkknkkkkk nkk npkkkknkknpkkkknkknuUpkkkkkuUfSoptvSpopt vSuVSpopt vSuoptVSpopt vSufS由最優(yōu)性定理可知：四、動態(tài)規(guī)劃基本方程 逆序法由此逆序算法的遞歸方程如下：第二十七頁，共53頁。 其中：fk(sk)表示第k階段初始狀態(tài)為sk 時(shí)，k后部子過程

19、的最優(yōu)準(zhǔn)則函數(shù) 。1111()(,)()()0kkkkkkkkkuUnnfsopt vs ufsfs逆序遞歸方程：1(,)kkkksT s u狀態(tài)轉(zhuǎn)移方程：第二十八頁，共53頁。正序遞歸方程：1100()(,)()()0kkkkkkkkkuUfsopt vs ufsfs111(,)kkkksTs u狀態(tài)轉(zhuǎn)移方程： 其中：fk(sk)表示第k階段初始狀態(tài)為sk 時(shí)，k前部子過程的最優(yōu)準(zhǔn)則函數(shù) 。第二十九頁，共53頁。 動態(tài)規(guī)劃建模有以下過程：確定階段與階段變量明確狀態(tài)變量和狀態(tài)可能集合。確定決策變量和決策允許集合。確定狀態(tài)轉(zhuǎn)移方程。明確階段效應(yīng)和目標(biāo)。五、動態(tài)規(guī)劃的建模第三十頁，共53頁。k=n

20、時(shí)，動態(tài)規(guī)劃基本方程是 11() (,)()nnnnnnnnufSopt v S ufS11()0nnfx邊界條件：() (,)nnnnnnufSopt v S u即 ：逆序地求出條件最優(yōu)目標(biāo)函數(shù)值集合和條件最優(yōu)決策集合，僅就逆序法說明求解步驟：六、動態(tài)規(guī)劃問題求解的一般步驟式中的“opt” 可根據(jù)具體問題的實(shí)際意義，而取 min或 max。第三十一頁，共53頁。k = n1時(shí)，動態(tài)規(guī)劃的基本方程是111111()(,)()nnnnnnnnufsopt Vsufs 因所有的 都已經(jīng)求出，因此可以根據(jù) 就階段n-1每個可能狀態(tài) ，求出條件最優(yōu)決策及相應(yīng)的條件最優(yōu)目標(biāo)函數(shù)值。111(,)nnnns

21、Tsu()nnfs1ns 因所有 都已求出，因此可以根據(jù) 就階段n-2每個可能狀態(tài) ，求出條件最優(yōu)決策及相應(yīng)的條件最優(yōu)目標(biāo)函數(shù)值。1222(,)nnnnsTsu11()nnfs2ns k = n2時(shí)，動態(tài)規(guī)劃的基本方程是22222211()(,)()nnnnnnnnufsopt Vsufs第三十二頁，共53頁。k=1時(shí)，動態(tài)規(guī)劃的基本方程是11111122( ) ( ,)()uf sopt v s ufs 由于所有的 f2(s2) 都已經(jīng)求出，因此可以根據(jù) s2=T1(s1,u1)就階段1每個可能狀態(tài)s1 ,求條件最優(yōu)決策及相應(yīng)的條件最優(yōu)目標(biāo)函數(shù)值 f1(s1) . 依次下去 .最后，順序地求

22、出最優(yōu)目標(biāo)值、最優(yōu)策略和最優(yōu)路線第三十三頁，共53頁。 解 該問題可以作為三段決策過程。對A、B、C三個部門分配資金分別形成1，2，3三個階段。sk表示給部門k分配資金時(shí)擁有的資金數(shù)。uk表示給部門k分配的資金數(shù)（萬元為單位）。狀態(tài)轉(zhuǎn)移方程是 sk+1=sk- uk。目標(biāo)函數(shù)是階段效應(yīng)求和。 例2：某公司擬將5百萬元資金投放下屬A、B、C三個部門，其中A與C的投資額不超過4百萬元，B的投資額不超過3百萬元，C投資額至少是1百萬元。各部門在獲得資金后的收益如表所示，用動態(tài)規(guī)劃方法求總收益最大的投資分配方案（投資數(shù)以百萬元為單位）。151184C121050B1210630A收益 （萬元） 432

23、1投放資金(萬元)0第三十四頁，共53頁。44()0fs遞歸方程為： （1）K=3時(shí)（第3階段） 注意到C的投資額不超過4百萬元， 至少是1百萬元. 允許狀態(tài)集合 S3 1, 2, 3, 4 , 即用剩余額S31，2，3，4 投資部門C，得到的收益為：3333(1)4,(2)8,(3)11,(4)15ffff （2） K=2時(shí)（第2階段） 注意到C的投資額至少是1百萬元， 允許狀態(tài)集合 S2 1, 2, 3, 4, 5 , 下面是各種可能方案的列表11()max()(),3,2,1kkkkkkkufsgufsk第三十五頁，共53頁。s21s2 2s2 3s2 4s2 5 B C B C B C

24、 B C B C0 10 20 30 41 4 1 11 21 32 32 12 23 23 1故223(1)(0)(1)4fgf23232(1)(0)(2)0 8(2)m1)54axmax9gffgf2322233104(2)(1)(0)(3)0 1(3)max(1)(2)max 5 814gffffgg第三十六頁，共53頁。232322323(0)(4)0 15(1)(3)5 11(4)maxmax18124(3)(1)(2)(2)10 8ggfgffgff2223332(1)(4)5 15(5)maxmax2112 8(3)(2)(2)(3)10 11gffgfgf（3）K=1時(shí) （第1

25、階段） S1 = 5 允許決策集合 D1(S1) 0, 1, 2, 3, 4, 第三十七頁，共53頁。11121212212(5)max(2)(3)max 6 1421109(3)(2)124(4)(1)(0)(5)021(1)(4)3 18fgfgfgfgfgf應(yīng)用順序追蹤可知：最優(yōu)方案有兩個：方案 1：*1230,2,3uuu方案 2：*1231,2,2uuu最大收益都為21百萬元。第三十八頁，共53頁。例例3：逆推解法求解下面問題: 2123123123max,0zx x xxxxcx x x解: 按問題的變量個數(shù)劃分階段,把它看作一個三階段決策問題。設(shè)狀態(tài)變量為s1，s2，s3，s4。

26、并記s1c；令變量x1，x2，x3為決策變量；各階段指標(biāo)按乘積方式結(jié)合。即令: 2111122223333( ,),(,),(,)v s xx vsxxv sxx第三十九頁，共53頁。令最優(yōu)值函數(shù)令最優(yōu)值函數(shù)f k k(s(sk k) )表示為第表示為第k k階段的初始狀態(tài)為階段的初始狀態(tài)為s sk k時(shí)，從第時(shí)，從第k k階段到第階段到第3 3階段所得到的最大值。階段所得到的最大值。 設(shè): s3= x3, s3+ x2=s2, s2+ x1=s1=c則有：x3=s3, 0 x2s2, 0 x1s1=c即狀態(tài)轉(zhuǎn)移方程為： s3=s2x2, s2 =s1x1由逆推解法，即最優(yōu)解x3=s3, 33

27、3333( )max(),xsf sxs第四十頁，共53頁。23222222222223233,0222222200()maxmax( )max()max(,)xxxsxsxsfsxxxf sxsxh sx由,得和（舍去）222222230dhx sxdx2223xs20 x 第四十一頁，共53頁。又，而故為極大值點(diǎn)。 22222226d hsxdx222222223|20 xsd hsdx 2223xs所以 ，即最優(yōu)解。22224()27fss*2223xs第四十二頁，共53頁。123111111211123122,0311111100( )maxmax()4max() max( ,)27x

28、 xxxsxsxsf sxxxxfsxsxh s x求導(dǎo)并令導(dǎo)數(shù)等于0可得：，故 *1114xs41111( )64f ss由于s1=c，*114xc411( )64f cc由s2 =s1x1，, *222132xsc3221()16fsc由s3 =s2x2，*3314xsc331()4fsc第四十三頁，共53頁。因此最優(yōu)解為：， *114xc*212xc*314xc最大值為：411max( )64zf cc第四十四頁，共53頁。例例：正推解法求解下面問題: 2123123123max,0zx x xxxxcx x x解：設(shè)s4c，決策變量仍為x1，x2，x3；最優(yōu)值函數(shù)f k(sk+1)表示

29、為第k階段末的結(jié)束狀態(tài)為sk+1，從第1階段到第k階段所得到的最大值。設(shè): s2= x1, s2+ x2=s3, s3+ x3=s4=c則有：x1=s2, 0 x2s3, 0 x3s4=c即狀態(tài)轉(zhuǎn)移方程為： s2=s3x2, s3=s4x3第四十五頁，共53頁。由順推解法， 即最優(yōu)解x1=s2,121212()max( ),xsf sxs122323222312212,02323230( )maxmax()4max()27x xxsxsfsxxxf sxsxs最優(yōu)解。 *2323xs第四十六頁，共53頁。1233434234123323,03434340()maxmax( )41max() 2764x xxxsxsf sxxxxfsxsxs最優(yōu)解 *3414xs由于s4=c，*314xc4341()64fsc由s3=s4x3，,*23213