1、第七章 動(dòng)態(tài)規(guī)劃,動(dòng)態(tài)規(guī)劃問題的基本概念和基本原理 動(dòng)態(tài)規(guī)劃模型的建立與求解 應(yīng)用舉例,動(dòng)態(tài)規(guī)劃問題的引出,例1：某運(yùn)輸公司有500輛運(yùn)輸卡車，重負(fù)荷運(yùn)輸（每天滿載行駛500km以上）時(shí)，年利潤(rùn)25萬元/輛，卡車的年損壞率為0.3；低負(fù)荷運(yùn)輸（每天行駛300km以下）時(shí)，年利潤(rùn)16萬元/輛，年損壞率為0.1?，F(xiàn)要求制定5年計(jì)劃，如何分配不同負(fù)荷下的卡車數(shù)量，使5年的總利潤(rùn)最大?,例1的線性規(guī)劃模型,s.t.,特點(diǎn)：遞歸性,動(dòng)態(tài)規(guī)劃,應(yīng)用對(duì)象： 1）不同時(shí)間段的規(guī)劃問題 動(dòng)態(tài)規(guī)劃的原意 2）可化為不同地段、步驟的靜態(tài)規(guī)劃問題,多階段決策過程最優(yōu)化問題的求解方法。,由美國(guó)數(shù)學(xué)家R. Bellman

2、 于50年代提出。,例2：最短路線問題,沿著線路網(wǎng)絡(luò)，在A、E之間鋪設(shè)一條管路，如何使總長(zhǎng)度最小?,3,2,1,4,3,1,3,3,5,2,5,3,1,4,2,3,1,5,動(dòng)態(tài)規(guī)劃的類型,根據(jù)變量的類型，動(dòng)態(tài)規(guī)劃可分為： 1）離散確定型： 2）連續(xù)確定型： 2）離散隨機(jī)型：Markov鏈 3）連續(xù)隨機(jī)型：Markov隨機(jī)過程,動(dòng)態(tài)規(guī)劃的基本概念,1。階段 2。狀態(tài) 3。決策和策略 4。狀態(tài)轉(zhuǎn)移方程 5。指標(biāo)函數(shù),階段,1。階段： 問題過程，按時(shí)間、空間的特征分解成若干相互聯(lián)系的階段。,狀態(tài),2。狀態(tài)： 各階段開始時(shí)的客觀條件，叫做狀態(tài)。 常用sk代表第k階段的狀態(tài)變量，其允許范圍為Sk。 S1

3、=A S2=B1，B2，B3 S3=C1，C2 S4=D1，D2，D3 S5=E,決策,3。決策： 對(duì)取定的狀態(tài)，可以作出不同的決定，以確定下一階段的狀態(tài)，稱為決策。 表示決策的變量，稱為決策變量，用uk(sk)表示。 決策變量的集合，稱為允許決策集合。用Dk(sk)表示。,決策舉例,例2中：D1(A)=B1，B2，B3 u1(A)=Bi,狀態(tài)轉(zhuǎn)移方程,給定第k階段的狀態(tài)sk及決策uk(sk)，則第k+1階段的狀態(tài)也完全確定，這一關(guān)系即狀態(tài)轉(zhuǎn)移方程： sk+1=Tk(sk, uk (sk) 狀態(tài)轉(zhuǎn)移方程給出了一種遞推關(guān)系。 在例2中： sk+1= uk(sk),狀態(tài)的無后效性,動(dòng)態(tài)規(guī)劃要求問題

4、具有無后效性： 給定k階段的狀態(tài)sk，則以后各階段的狀態(tài)sl（lk）都只受sk的影響，與之前的狀態(tài)無關(guān)。,策略,策略：各階段決策構(gòu)成的決策序列。 p1,n=u1(s1), u2(s2), un(sn) 例2中,策略的總數(shù)為：32 3 1=18 動(dòng)態(tài)規(guī)劃的目的是要選擇最優(yōu)的一種策略,指標(biāo)函數(shù),用Vk, n(sk, pk,n)表示從狀態(tài)sk出發(fā)，沿策略pk,n到達(dá)狀態(tài)sn+1時(shí)的指標(biāo)函數(shù)值 從k階段開始規(guī)劃的最優(yōu)指標(biāo)函數(shù)值：,系統(tǒng)優(yōu)化指標(biāo)為：,指標(biāo)函數(shù)舉例,V4, 4(D1, p4,4)= V4, 4(D1, u4,) =v4(D1, E)=3,指標(biāo)函數(shù)的可分離性,指標(biāo)函數(shù)具有可分離性,k是Vk+

5、1, n(sk+1, pk+1,n)的單調(diào)函數(shù)。 該要求是為了滿足動(dòng)態(tài)規(guī)劃的求解需要。,指標(biāo)函數(shù)的常見形式,k的常見的形式有：,階段指標(biāo)函數(shù),指標(biāo)函數(shù)的常見形式,最優(yōu)化原理,最優(yōu)策略具有如下性質(zhì)： 無論初始狀態(tài)及初始決策如何，對(duì)于先前形成的狀態(tài)，余下的決策序列應(yīng)構(gòu)成子問題的最優(yōu)策略。,最優(yōu)化原理只是策略最優(yōu)的一個(gè)必要條件,最優(yōu)化定理,策略p*1,n是最優(yōu)決策序列的充要條件是，對(duì)于所有的k，都有：,f1(s1),fk(sk),最優(yōu)化定理的推論,由最優(yōu)化定理可以得到一個(gè)遞推關(guān)系：,逆序解法,逆序解法：,T1,s1,s2,u1,v1(s1, u1),Tk,sk,sk+1,uk,vk(sk, uk),

6、Tn,sn,sn+1,un,vn(sn, un),分治思想,將原問題分解為子問題，只考慮最優(yōu)子問題所在的分支，類似于分支定界法 減少重復(fù)計(jì)算,例2：逆序法解,沿著線路網(wǎng)絡(luò)，在A、E之間鋪設(shè)一條管路，如何使總長(zhǎng)度最小。,3,2,1,4,3,1,3,3,5,2,5,3,1,4,2,3,1,5,第1步,3,2,1,4,3,1,3,3,5,2,5,3,1,4,2,3,1,5,S4=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)=5,3,1

7、,5,第2步,S3=C1，C2 f3 (s3)=min v3(s3, u3)+ f4 (s4) u3 D3 (s3) D3(C1)=D1，D2，D3 ; D3(C2)=D1，D2，D3 ,3,2,1,4,3,1,3,3,5,2,5,3,1,4,2,3,1,5,3,1,5,第2步（1）,3,2,1,4,3,1,3,3,5,2,5,3,1,4,2,3,1,5,3,1,5,5,第2步（2）,3,2,1,4,3,1,3,3,5,2,5,3,1,4,2,3,1,5,3,1,5,5,4,第3步,S2=B1，B2 ，B3 f2 (s2)=min v2(s2, u2)+ f3 (s3) u2 D2 (s2)

8、D2(B1)=C1,C2; D2(B2)=C1,C2; D2(B3)=C1,C2,3,2,1,4,3,1,3,3,5,2,5,3,1,4,2,3,1,5,3,1,5,5,4,第3步(1),3,2,1,4,3,1,3,3,5,2,5,3,1,4,2,3,1,5,3,1,5,5,4,7,第3步(2),3,2,1,4,3,1,3,3,5,2,5,3,1,4,2,3,1,5,3,1,5,5,4,7,6,第3步(3),3,2,1,4,3,1,3,3,5,2,5,3,1,4,2,3,1,5,3,1,5,5,4,7,6,8,第4步,S1=A f1 (s1)=min v1(s1, u1)+ f2 (s2) u

9、2 D1 (s1) D1(A)=B1,B2 ,B3,3,2,1,4,3,1,3,3,5,2,5,3,1,4,2,3,1,5,3,1,5,5,4,7,6,8,第4步(1),3,2,1,4,3,1,3,3,5,2,5,3,1,4,2,3,1,5,3,1,5,5,4,7,6,8,8,順序解法,狀態(tài)轉(zhuǎn)移方程： sk+1=Tk(sk, uk (sk) sk=Tk(sk +1, uk (sk +1) 階段指標(biāo)函數(shù)： vk(sk, uk) vk(sk+1, uk) 最優(yōu)指標(biāo)函數(shù)： fk (sk+1)表示起點(diǎn)s1到sk+1的最優(yōu)效益值,T1,s1,s2,u1,v1(s2, u1),Tk,sk,sk+1,uk,

10、vk(sk+1, uk),Tn,sn,sn+1,un,vn(sn+1, un),順序解法迭代方式,順序解法迭代方式：,第1步,3,2,1,4,3,1,3,3,5,2,5,3,1,4,2,3,1,5,S2=B1，B2，B3 ， u1(s2)= A , f1 (s2)=v1(s2, u1) f1 (B1)= v1(B1, A)=3, f1 (B2)=2, f1 (B3)=1,3,2,1,第2步,S3=C1，C2 f2 (s3)=min v2(s3, u2)+ f1 (s2) u2 D2 (s3) D2(C1)=B1，B2，B3 ; D2(C2)=B1，B2，B3 ,3,2,1,4,3,1,3,3,

11、5,2,5,3,1,4,2,3,1,5,3,2,1,第2步（1）,3,2,1,4,3,1,3,3,5,2,5,3,1,4,2,3,1,5,3,2,1,3,第2步（2）,3,2,1,4,3,1,3,3,5,2,5,3,1,4,2,3,1,5,3,2,1,3,5,第3步,S4=D1，D2 ，D3 f3 (s4)=min v3(s4, u3)+ f2 (s3) u3 D3 (s4) D3(D1)=C1,C2; D3(D2)=C1,C2; D3(D3)=C1,C2,3,2,1,4,3,1,3,3,5,2,5,3,1,4,2,3,1,5,3,2,1,3,5,第3步(1),3,2,1,4,3,1,3,3,

12、5,2,5,3,1,4,2,3,1,5,3,2,1,3,5,5,第3步(2),3,2,1,4,3,1,3,3,5,2,5,3,1,4,2,3,1,5,3,2,1,3,5,5,8,第3步(3),3,2,1,4,3,1,3,3,5,2,5,3,1,4,2,3,1,5,3,2,1,3,5,5,8,6,第4步,S4=E f4 (s5)=min v4(s5, u4)+ f3 (s4) u4 D4 (s5) D4(E)=D1,D2 ,D3,3,2,1,4,3,1,3,3,5,2,5,3,1,4,2,3,1,5,3,2,1,3,5,5,8,6,第4步(1),3,2,1,4,3,1,3,3,5,2,5,3,1

13、,4,2,3,1,5,3,2,1,3,5,5,8,6,8,順序解法和逆序解法,順序解法和逆序解法無本質(zhì)區(qū)別, 改變變量編號(hào)，可以互推，一般 初始、終止?fàn)顟B(tài)均給定：可任選一種解法。 初始狀態(tài)給定：用逆序解法比較簡(jiǎn)單。 終止?fàn)顟B(tài)給定：用順序解法比較簡(jiǎn)單。,例1：,例1：某運(yùn)輸公司有500輛運(yùn)輸卡車，超負(fù)荷運(yùn)輸（每天滿載行駛500km以上）時(shí)，年利潤(rùn)25萬元/輛，卡車的年損壞率為0.3；低負(fù)荷運(yùn)輸（每天行駛300km以下），年利潤(rùn)16萬元/輛，年損壞率為0.1?，F(xiàn)要求制定5年計(jì)劃，如何分配不同負(fù)荷下的卡車數(shù)量，使5年的總利潤(rùn)最大。,例1分析,階段k ：五年計(jì)劃， k =1,2,5 狀態(tài)變量sk ：第

14、k年度初完好的卡車數(shù)目 決策變量uk：第k年度重負(fù)荷運(yùn)行的卡車數(shù)目 0uk sk,已知初始狀態(tài)變量s1 = 500 終止?fàn)顟B(tài)s5未知 故選用逆序解法。,狀態(tài)轉(zhuǎn)移方程：sk+1=(1-0.3)uk + (1-0.1)(sk-uk) =0.9sk 0.2uk 注：由于損失率是一個(gè)估計(jì)，所以sk、 uk可看作連續(xù)狀態(tài)變量 階段指標(biāo)函數(shù)：第k年度的階段效益 vk(sk, uk)=25uk+16(sk-uk) =16sk+9uk 最優(yōu)指標(biāo)函數(shù)值的遞推方程： fk (sk)=max vk(sk, uk)+ fk+1 (sk+1) uk Dk (sk) f6 (s6)=0,第1步:k=5,f5 (s5)=m

15、ax v5(s5, u5)+ f6 (s6) 0 u5 S5 =max16s5+9u5 + 0 0 u5 S5 u5* =s5 f5 (s5)=25s5,f5,0,s5,u5,16s5,25s5,第2步:k=4,f4 (s4)=max v4(s4, u4)+ f5 (s5) 0 u4 S4 =max16s4+9u4 + 25s5 0 u4 S4 =max16s4+9u4 + 25(0.9s4 0.2u4) 0 u4 S4 =max38.5s4+4u4 0 u4 S4 u4* =s4 f4 (s4)=42.5s4,u5* =s5 f5 (s5)=25s5,sk+1=0.9sk 0.2uk,第3步

16、:k=3,f3 (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 S3 u3* =s3 f3 (s3)=54.75s3,u4* =s4 f4 (s4)=42.5s4,sk+1=0.9sk 0.2uk,第4步:k=2,f2 (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 S2 u2*

17、=0 f2 (s2)= 65.275s2,f2,s2,u2,u3* =s3 f3 (s3)=54.75s3,sk+1=0.9sk 0.2uk,第5步:k=1,f1 (s1)=max v1(s1, u1)+ f2 (s2) 0 u1 S1 =max16s1+9u1 + 65.275 (0.9s1 0.2u1) 0 u1 S1 =max74.7475s1-4.055u1 0 u1 S1 u1* =0 f1 (s1)= 74.7475s1= 74.7475500=37373.75萬元,u2* =0 f2 (s2)= 65.275s2,sk+1=0.9sk 0.2uk,最優(yōu)策略,u1*=u2*=0 全

18、部低負(fù)荷運(yùn)行 u3*= s3 , u4*= s4 , u5*= s5 全部重負(fù)荷運(yùn)行 f1 (s1)= 74.7475s1= 74.7475500=37373.75萬元,s1=500 s2=0.9s1 0.2u1*=450 s3=0.9s2 0.2u2*= 405 u3*=405 s4=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,動(dòng)態(tài)規(guī)劃法求解非線性規(guī)劃問題,求解非線性規(guī)劃問題： max z= 4x1+ 5x2 + 3x32,s.t. 3x1+ 4x2 + 5x3 10,xj0 j = 1, 2, 3,順序解法模型,階段： 分為3個(gè)階段 k = 1, 2, 3 狀態(tài)變量sk：前k階段的可用資源，則s3=1