運籌學chap7動態(tài)規(guī)劃

1、第七章 動態(tài)規(guī)劃動態(tài)規(guī)劃問題的基本概念和基本原理動態(tài)規(guī)劃模型的建立與求解應用舉例動態(tài)規(guī)劃問題的引出例例1：某運輸公司有：某運輸公司有500輛運輸卡車，重負輛運輸卡車，重負荷運輸（每天滿載行駛荷運輸（每天滿載行駛500km以上）時，以上）時，年利潤年利潤25萬元萬元/輛，卡車的年損壞率為輛，卡車的年損壞率為0.3；低負荷運輸（每天行駛低負荷運輸（每天行駛300km以下）時，以下）時，年利潤年利潤16萬元萬元/輛，年損壞率為輛，年損壞率為0.1。現(xiàn)要求?，F(xiàn)要求制定制定5年計劃，如何分配不同負荷下的卡車年計劃，如何分配不同負荷下的卡車數(shù)量，使數(shù)量，使5年的總利潤最大年的總利潤最大?例1的線性規(guī)劃模型

2、51)1625(maxiilihxxziailihxxx1,-1(1 0.3)(1 0.1)iaihilxxx,5001ax51i52i0,iailihxxxs.t.特點：遞歸性特點：遞歸性ihilxx和分別表示分別表示i年重、輕負荷運輸?shù)能囕v數(shù)年重、輕負荷運輸?shù)能囕v數(shù)iax表示表示i年的總車輛數(shù)年的總車輛數(shù)動態(tài)規(guī)劃應用對象：應用對象： 1）不同時間段的規(guī)劃問題）不同時間段的規(guī)劃問題 動態(tài)規(guī)劃的原意動態(tài)規(guī)劃的原意 2）可化為不同地段、步驟的靜態(tài)規(guī)劃問題）可化為不同地段、步驟的靜態(tài)規(guī)劃問題多階段決策過程最優(yōu)化問題的求解方法。多階段決策過程最優(yōu)化問題的求解方法。由美國數(shù)學家由美國數(shù)學家R. Bel

3、lman 于于50年代提出。年代提出。例2：最短路線問題沿著線路網絡，在沿著線路網絡，在A、E之間鋪設一條管路，之間鋪設一條管路，如何使總長度最小如何使總長度最小?AB1B3B2C1C2D1D3D2E321431335253142315動態(tài)規(guī)劃的類型根據(jù)變量的類型，動態(tài)規(guī)劃可分為：根據(jù)變量的類型，動態(tài)規(guī)劃可分為：1）離散確定型：）離散確定型：2）連續(xù)確定型：）連續(xù)確定型：2）離散隨機型：）離散隨機型：Markov鏈鏈3）連續(xù)隨機型：）連續(xù)隨機型：Markov隨機過程隨機過程動態(tài)規(guī)劃的基本概念1。階段。階段2。狀態(tài)。狀態(tài)3。決策和策略。決策和策略4。狀態(tài)轉移方程。狀態(tài)轉移方程5。指標函數(shù)。指標函

4、數(shù)階段1。階段：。階段：問題過程，按時間、空間的特征分解成若問題過程，按時間、空間的特征分解成若干相互聯(lián)系的階段。干相互聯(lián)系的階段。AB1B3B2C1C2D1D3D2E321431335253142315狀態(tài)2。狀態(tài)：。狀態(tài)：各階段各階段開始開始時的客觀條件，叫做狀態(tài)。時的客觀條件，叫做狀態(tài)。常用常用sk代表第代表第k階段的狀態(tài)變量，其允許范圍為階段的狀態(tài)變量，其允許范圍為Sk。S1=AS2=B1，B2，B3S3=C1，C2S4=D1，D2，D3S5=EAB1B3B2C1C2D1D3D2E321431335253142315決策3。決策：。決策：對取定的狀態(tài)，可以作出不同的決定，以確定下對取定

5、的狀態(tài)，可以作出不同的決定，以確定下一階段的狀態(tài)，稱為決策。一階段的狀態(tài)，稱為決策。表示決策的變量，稱為決策變量，用表示決策的變量，稱為決策變量，用uk(sk)表示。表示。決策變量的集合，稱為允許決策集合。用決策變量的集合，稱為允許決策集合。用Dk(sk)表示。表示。決策舉例例例2中：中：D1(A)=B1，B2，B3 u1(A)=Bi AB1B3B2C1C2D1D3D2E321431335253142315狀態(tài)轉移方程給定第給定第k階段的狀態(tài)階段的狀態(tài)sk及決策及決策uk(sk)，則第則第k+1階段的狀態(tài)也完全確定，這一關系即狀態(tài)轉階段的狀態(tài)也完全確定，這一關系即狀態(tài)轉移方程：移方程： sk+

6、1=Tk(sk, uk (sk)狀態(tài)轉移方程給出了一種遞推關系狀態(tài)轉移方程給出了一種遞推關系。在例在例2中：中： sk+1= uk(sk)狀態(tài)的無后效性動態(tài)規(guī)劃要求問題具有動態(tài)規(guī)劃要求問題具有無后效性無后效性：給定給定k階段的狀態(tài)階段的狀態(tài)sk，則以后各階段的狀則以后各階段的狀態(tài)態(tài)sl（lk）都只受都只受sk的影響，與之前的狀態(tài)的影響，與之前的狀態(tài)無關。無關。策略策略：各階段決策構成的決策序列。策略：各階段決策構成的決策序列。p1,n=u1(s1), u2(s2), un(sn)例例2中中,策略的總數(shù)為：策略的總數(shù)為：3 2 3 1=18動態(tài)規(guī)劃的目的是要選擇最優(yōu)的一種策略動態(tài)規(guī)劃的目的是要選

7、擇最優(yōu)的一種策略指標函數(shù)用用Vk, n(sk, pk,n)表示從狀態(tài)表示從狀態(tài)sk出發(fā)，沿策略出發(fā)，沿策略pk,n到達狀態(tài)到達狀態(tài)sn+1時的指標函數(shù)值時的指標函數(shù)值從從k階段開始規(guī)劃的最優(yōu)指標函數(shù)值：階段開始規(guī)劃的最優(yōu)指標函數(shù)值：,*,()(,)(,)k nk nkkk nkk nk nkk npPfsVspopt Vsp1,1,*111,11,1,11,( )( ,)( ,)nnnnnnpPf sVs popt Vs p系統(tǒng)優(yōu)化指標為：系統(tǒng)優(yōu)化指標為：指標函數(shù)舉例AB1B3B2C1C2D1D3D2E321431335253142315V4, 4(D1, p4,4)= V4, 4(D1, u

8、4,) =v4(D1, E)=3指標函數(shù)的可分離性指標函數(shù)具有可分離性指標函數(shù)具有可分離性),(,(),(, 11, 1,nkknkkkknkknkpsVuspsV k是是Vk+1, n(sk+1, pk+1,n)的單調函數(shù)。的單調函數(shù)。該要求是為了滿足動態(tài)規(guī)劃的求解需要。該要求是為了滿足動態(tài)規(guī)劃的求解需要。指標函數(shù)的常見形式 k的常見的形式有：的常見的形式有：,1,11,(,)(,)(,)k nkk nk kkkknkknVspVs uVspnkjjjjusv),(),(),(, 11, 1nkknkkkkpsVusv階段指標函數(shù)階段指標函數(shù)指標函數(shù)的常見形式,1,11,(,)(,)(,)k

9、 nkk nk kkkknkknVspVs u Vspnkjjjjusv),(最優(yōu)化原理 最優(yōu)策略具有如下性質：最優(yōu)策略具有如下性質： 無論初始狀態(tài)及初始決策如何，對于無論初始狀態(tài)及初始決策如何，對于先前形成的狀態(tài)，余下的決策序列應構成先前形成的狀態(tài)，余下的決策序列應構成子問題的最優(yōu)策略。子問題的最優(yōu)策略。最優(yōu)化原理只是策略最優(yōu)的一個最優(yōu)化原理只是策略最優(yōu)的一個必要條件必要條件最優(yōu)化定理策略策略p*1,n是最優(yōu)決策序列的充要條件是，是最優(yōu)決策序列的充要條件是，對于所有的對于所有的k，都有：，都有：),(*, 11, 1nnpsV),(),(,1, 111, 1,1, 11, 1nkknkPpk

10、kPppsVoptpsVoptnknkkkf1(s1)fk(sk)最優(yōu)化定理的推論由最優(yōu)化定理可以得到一個遞推關系：由最優(yōu)化定理可以得到一個遞推關系：)(),()(11kkkkkDukksfusvoptsfkk逆序解法逆序解法：逆序解法：)(),()(11)(kkkkksDukksfusvoptsfkkk0)(11nnsf T1s1s2u1v1(s1, u1) Tksksk+1ukvk(sk, uk) Tnsnsn+1unvn(sn, un)分治思想將原問題分解為子問題，只考慮最優(yōu)子問將原問題分解為子問題，只考慮最優(yōu)子問題所在的分支，類似于分支定界法題所在的分支，類似于分支定界法減少重復計算減

11、少重復計算例2：逆序法解沿著線路網絡，在沿著線路網絡，在A、E之間鋪設一條管路，之間鋪設一條管路，如何使總長度最小。如何使總長度最小。AB1B3B2C1C2D1D3D2E321431335253142315第1步AB1B3B2C1C2D1D3D2E321431335253142315S4=D1，D2，D3 ， u4(s4)= E , f4 (s4)=min v4(s4, u4)+ f5 (s5)u4 D4 (s4) f4 (D1)= v4(D1, E)=3, f4 (D2)=1, f4 (D3)=5315第2步S3=C1，C2f3 (s3)=min v3(s3, u3)+ f4 (s4)u3

12、D3 (s3)D3(C1)=D1，D2，D3 ; D3(C2)=D1，D2，D3 AB1B3B2C1C2D1D3D2E321431335253142315315第2步（1）AB1B3B2C1C2D1D3D2E3214313352531423155531532)(),()(),()(),(min)(34313242131411313DfDCvDfDCvDfDCvCf3155第2步（2）AB1B3B2C1C2D1D3D2E3214313352531423154521431)(),()(),()(),(min)(34323242231412323DfDCvDfDCvDfDCvCf31554第3步S2

13、=B1，B2 ，B3f2 (s2)=min v2(s2, u2)+ f3 (s3)u2 D2 (s2)D2(B1)=C1,C2; D2(B2)=C1,C2; D2(B3)=C1,C2AB1B3B2C1C2D1D3D2E32143133525314231531554第3步(1)AB1B3B2C1C2D1D3D2E32143133525314231574354)(),()(),(min)(232121311212CfCBvCfCBvBf315547第3步(2)AB1B3B2C1C2D1D3D2E32143133525314231564351)(),()(),(min)(232221312222Cf

14、CBvCfCBvBf3155476第3步(3)AB1B3B2C1C2D1D3D2E32143133525314231584553)(),()(),(min)(232321313232CfCBvCfCBvBf31554768第4步S1=Af1 (s1)=min v1(s1, u1)+ f2 (s2)u2 D1 (s1)D1(A)=B1,B2 ,B3AB1B3B2C1C2D1D3D2E32143133525314231531554768第4步(1)8816273)(),()(),()(),(min)(3231222112111BfBAvBfBAvBfBAvAfAB1B3B2C1C2D1D3D2E3

15、21431335253142315315547688順序解法狀態(tài)轉移方程：狀態(tài)轉移方程： sk+1=Tk(sk, uk (sk) sk=Tk(sk +1, uk (sk +1)階段指標函數(shù)：階段指標函數(shù)： vk(sk, uk) vk(sk+1, uk)最優(yōu)指標函數(shù)：最優(yōu)指標函數(shù)： fk (sk+1)表示起點表示起點s1到到sk+1的最的最優(yōu)效益值優(yōu)效益值 T1s1s2u1v1(s2, u1) Tksksk+1ukvk(sk+1, uk) Tnsnsn+1unvn(sn+1, un)順序解法迭代方式順序解法迭代方式：順序解法迭代方式：)(),()(11)(11kkkkksDukksfusvopt

16、sfkkk0)(10sf第1步AB1B3B2C1C2D1D3D2E321431335253142315S2=B1，B2，B3 ， u1(s2)= A , f1 (s2)=v1(s2, u1)f1 (B1)= v1(B1, A)=3, f1 (B2)=2, f1 (B3)=1321第2步S3=C1，C2f2 (s3)=min v2(s3, u2)+ f1 (s2)u2 D2 (s3)D2(C1)=B1，B2，B3 ; D2(C2)=B1，B2，B3 AB1B3B2C1C2D1D3D2E321431335253142315321第2步（1）3132134)(),()(),()(),(min)(31

17、312212121111212BfBCvBfBCvBfBCvCfAB1B3B2C1C2D1D3D2E3214313352531423153213第2步（2）5152333)(),()(),()(),(min)(31322212221112222BfBCvBfBCvBfBCvCfAB1B3B2C1C2D1D3D2E32143133525314231532135第3步S4=D1，D2 ，D3f3 (s4)=min v3(s4, u3)+ f2 (s3)u3 D3 (s4)D3(D1)=C1,C2; D3(D2)=C1,C2; D3(D3)=C1,C2AB1B3B2C1C2D1D3D2E321431

18、33525314231532135第3步(1)55132)(),()(),(min)(222131211313CfCDvCfCDvDfAB1B3B2C1C2D1D3D2E321431335253142315321355第3步(2)85435)(),()(),(min)(222231212323CfCDvCfCDvDfAB1B3B2C1C2D1D3D2E3214313352531423153213558第3步(3)65233)(),()(),(min)(222331213333CfCDvCfCDvDfAB1B3B2C1C2D1D3D2E32143133525314231532135586第4步S

19、4=Ef4 (s5)=min v4(s5, u4)+ f3 (s4)u4 D4 (s5)D4(E)=D1,D2 ,D3AB1B3B2C1C2D1D3D2E32143133525314231532135586第4步(1)8658153)(),()(),()(),(min)(3334232413144DfDEvDfDEvDfDEvEfAB1B3B2C1C2D1D3D2E321431335253142315321355868順序解法和逆序解法順序解法和逆序解法無本質區(qū)別順序解法和逆序解法無本質區(qū)別, 改變變量編改變變量編號，可以互推，號，可以互推，一般一般初始、終止狀態(tài)均給定：可任選一種解法。初始、

20、終止狀態(tài)均給定：可任選一種解法。初始狀態(tài)給定：用逆序解法比較簡單。初始狀態(tài)給定：用逆序解法比較簡單。終止狀態(tài)給定：用順序解法比較簡單。終止狀態(tài)給定：用順序解法比較簡單。例1：例例1：某運輸公司有：某運輸公司有500輛運輸卡車，超負輛運輸卡車，超負荷運輸（每天滿載行駛荷運輸（每天滿載行駛500km以上）時，以上）時，年利潤年利潤25萬元萬元/輛，卡車的年損壞率為輛，卡車的年損壞率為0.3；低負荷運輸（每天行駛低負荷運輸（每天行駛300km以下），年以下），年利潤利潤16萬元萬元/輛，年損壞率為輛，年損壞率為0.1。現(xiàn)要求制?，F(xiàn)要求制定定5年計劃，如何分配不同負荷下的卡車數(shù)年計劃，如何分配不同負荷

21、下的卡車數(shù)量，使量，使5年的總利潤最大。年的總利潤最大。例1分析階段階段k ：五年計劃，：五年計劃， k =1,2,5狀態(tài)變量狀態(tài)變量sk ：第第k年度初完好的卡車數(shù)目年度初完好的卡車數(shù)目決策變量決策變量uk：第第k年度重負荷運行的卡車數(shù)目年度重負荷運行的卡車數(shù)目 0 uk sk已知初始狀態(tài)變量已知初始狀態(tài)變量s1 = 500終止狀態(tài)終止狀態(tài)s5未知未知故選用故選用逆序解法逆序解法。狀態(tài)轉移方程：狀態(tài)轉移方程：sk+1=(1-0.3)uk + (1-0.1)(sk-uk) =0.9sk 0.2uk注：由于損失率是一個估計，所以注：由于損失率是一個估計，所以sk、 uk可可看作看作連續(xù)連續(xù)狀態(tài)變

22、量狀態(tài)變量階段指標函數(shù)：第階段指標函數(shù)：第k年度的階段效益年度的階段效益vk(sk, uk)=25uk+16(sk-uk) =16sk+9uk最優(yōu)指標函數(shù)值的遞推方程：最優(yōu)指標函數(shù)值的遞推方程：fk (sk)=max vk(sk, uk)+ fk+1 (sk+1)uk Dk (sk)f6 (s6)=0第1步:k=5f5 (s5)=max v5(s5, u5)+ f6 (s6) 0 u5 S5 =max16s5+9u5 + 0 0 u5 S5u5* =s5f5 (s5)=25s5f50s5u516s525s5第2步:k=4f4 (s4)=max v4(s4, u4)+ f5 (s5) 0 u4

23、S4 =max16s4+9u4 + 25s5 0 u4 S4 =max16s4+9u4 + 25(0.9s4 0.2u4) 0 u4 S4 =max38.5s4+4u4 0 u4 S4u4* =s4 f4 (s4)=42.5s4u5* =s5f5 (s5)=25s5sk+1=0.9sk 0.2uk第3步:k=3f3 (s3)=max v3(s3, u3)+ f4 (s4) 0 u3 S3 =max16s3+9u3 + 42.5 (0.9s3 0.2u3) 0 u3 S3 =max54.25s3+0.5u3 0 u3 S3u3* =s3 f3 (s3)=54.75s3u4* =s4 f4 (s4

24、)=42.5s4sk+1=0.9sk 0.2uk第4步:k=2f2 (s2)=max v2(s2, u2)+ f3 (s3) 0 u2 S2 =max16s2+9u2 + 54.75 (0.9s2 0.2u2) 0 u2 S2 =max65.275s2-1.95u2 0 u2 S2u2* =0 f2 (s2)= 65.275s2f2s2u2u3* =s3 f3 (s3)=54.75s3sk+1=0.9sk 0.2uk第5步:k=1f1 (s1)=max v1(s1, u1)+ f2 (s2) 0 u1 S1 =max16s1+9u1 + 65.275 (0.9s1 0.2u1) 0 u1 S1

25、 =max74.7475s1-4.055u1 0 u1 S1u1* =0 f1 (s1)= 74.7475s1= 74.7475 500=37373.75萬元萬元u2* =0f2 (s2)= 65.275s2sk+1=0.9sk 0.2uk最優(yōu)策略u1*=u2*=0 全部低負荷運行全部低負荷運行u3*= s3 , u4*= s4 , u5*= s5 全部重負荷運行全部重負荷運行 f1 (s1)= 74.7475s1= 74.7475 500=37373.75萬元萬元 s1=500s2=0.9s1 0.2u1*=450s3=0.9s2 0.2u2*= 405 u3*=405s4=0.9s3 0.2u3*=283.5 u4*= 283.5 s5=0.9s4 0.2u4*=198.45 u5*= 198.45 s6=0.9s5 0.2u5*=138.15動態(tài)規(guī)劃法求解非線性規(guī)劃問題動態(tài)規(guī)劃法求解非線性規(guī)劃問題求解非線性規(guī)劃問題：求解非線性規(guī)劃問題：max z= 4x1+ 5x2 + 3x32s.t. 3x1+ 4x2 + 5x3 10 xj 0 j = 1, 2, 3順序解法模型階段：階段： 分為分為3個階段個階段 k = 1, 2, 3 狀態(tài)變量狀態(tài)變量sk：前：前k階段的可用資源階段的可用資源，則則s3=10決策變量決策變量uk：uk= xk狀態(tài)轉移方程：狀態(tài)轉移方程：s0=s