23動(dòng)態(tài)規(guī)劃.ppt

1、7-2 動(dòng)態(tài)規(guī)劃應(yīng)用舉例 例7-6 一家著名的快餐店計(jì)劃在某城市建立5個(gè)分店，這個(gè)城市分成三個(gè)區(qū)，分別用1，2，3表示。由于每個(gè)區(qū)的地理位置、交通狀況及居民的構(gòu)成等諸多因素的差異，將對(duì)各分店的經(jīng)營(yíng)狀況產(chǎn)生直接的影響。經(jīng)營(yíng)者通過(guò)市場(chǎng)調(diào)查及咨詢后，建立了下表。,該表表明了各個(gè)區(qū)建立不同數(shù)目的分店時(shí)的利潤(rùn)估計(jì)，確定各區(qū)建店數(shù)目使總利潤(rùn)最大。,解： 階段：每個(gè)區(qū)，共三個(gè)階段。 狀態(tài)：Sk為第k階段開(kāi)始時(shí)，可供分配的店數(shù)。 決策：dk為分配給區(qū)k的店數(shù)。 狀態(tài)轉(zhuǎn)移方程：Sk+1=Sk-dk 效益：rk(dk)為分配給區(qū)k,dk個(gè)店時(shí)的利潤(rùn)。,fk(Sk)為當(dāng)?shù)趉階段初始狀態(tài)為Sk時(shí)，從第k階段到最后階段

2、所得最大利潤(rùn)。 fk(Sk)=Max rk(dk) + fk+1(Sk+1) dk (Sk) k=1，2，3 f4(S4)= 0,k=3 時(shí)， 計(jì)算如下：,k=2 時(shí)， 計(jì)算如下：,S3=S2-d2,k=1 時(shí)， 計(jì)算如下： 最優(yōu)解：d*1 =3， d*2 =2，d*3 =0 即：在區(qū)1建3個(gè)分店，在區(qū)2建2個(gè)分店，而不在區(qū)3建立分店。最大總利潤(rùn)=22。,d1*=3,s2=s1- d1*=5-3=2, d2*=2 s3=s2- d2*=2-2=0, d3*=0,建立動(dòng)態(tài)規(guī)劃模型的要點(diǎn)： 分析題意，識(shí)別問(wèn)題的多階段性，按時(shí)間或空間的先后順序適當(dāng)?shù)貏澐譂M足遞推關(guān)系的若干階段，對(duì)非時(shí)序的靜態(tài)問(wèn)題要人

3、為地賦予“時(shí)段”的概念。,建立動(dòng)態(tài)規(guī)劃模型的要點(diǎn)： 正確地選擇狀態(tài)變量，使其具備兩個(gè)必要特征： （1）可知性：即過(guò)去演變過(guò)程的各階段狀態(tài)變量的取值，能直接或間接地確定。 （2）能夠確切地描述過(guò)程的演變且滿足無(wú)后效性。,建立動(dòng)態(tài)規(guī)劃模型的要點(diǎn)： 根據(jù)狀態(tài)變量與決策變量的含義，正確寫(xiě)出狀態(tài)轉(zhuǎn)移方程或轉(zhuǎn)移規(guī)則。 根據(jù)題意明確指標(biāo)函數(shù)，最優(yōu)指標(biāo)函數(shù)以及一段效益即階段指標(biāo)的含義。并正確列出最優(yōu)指標(biāo)函數(shù)的遞推關(guān)系及邊界條件（即 DP基本方程）。,例7-7（投資問(wèn)題）現(xiàn)有資金5百萬(wàn)元，可對(duì)三個(gè)項(xiàng)目進(jìn)行投資，投資額均為整數(shù)（單位為百萬(wàn)元），其中2#項(xiàng)目的投資不得超過(guò)3百萬(wàn)元，1#和3#項(xiàng)目的投資均不得超過(guò)4百

4、萬(wàn)元， 3#項(xiàng)目至少要投資1百萬(wàn)元，每個(gè)項(xiàng)目投資5年后，預(yù)計(jì)可獲得收益由下表給出，問(wèn)如何投資可望獲得最大收益。,解：這個(gè)投資問(wèn)題可以分成三個(gè)階段，在第k階段確定k #的投資額 令 Sk對(duì)1#，2#.（ k -1）#項(xiàng)目投資后剩余的資金額。 Xk對(duì)k項(xiàng)目的投資額。 rk ( Xk)對(duì)k#項(xiàng)目投資Xk的收益. fk(Sk)應(yīng)用剩余的資金Sk 對(duì)k#,( k+1)#.N#投資可獲得的最大收益。,狀態(tài)轉(zhuǎn)移方程為：Sk+1= Sk- Xk 為了獲得最大收益，必須將5百萬(wàn)元全部用于投資，故假想有第4階段存在時(shí)，必有S4=0，于是得遞推方程： fk(Sk)= Max rk ( Xk)+ fk+1(Sk+1)

5、 dk(Sk) k=3,2,1 f4(S4)=0,當(dāng)k=3時(shí)，（3#至多投資4百萬(wàn)元，至少投資1百萬(wàn)元） f3(1）=4， f3(2）=8， f3(3）=11， f3(4）=15,當(dāng)k=2時(shí)，（2#投資不超過(guò)3百萬(wàn)元） f2(1）= r2(0)+ f3(1）=0 + 4 f2(2）= Max r2(1)+ f3(1) r2(0)+ f3(2） = Max 5+4，0+8 = 9,當(dāng)k=2時(shí)，（2#投資不超過(guò)3百萬(wàn)元） f2(3）= Max r2(2)+ f3(1) r2(1)+ f3(2） r2(0)+ f3(3） = Max 10+4，5+8，0+11 = 14,f2(4） = Max r2

6、(3)+ f3(1）r2(2)+ f3(2) r2(1)+ f3(3） r2(0)+ f3(4） = Max 12+4，10+8，5+11，0+15 = 18,當(dāng)k=2時(shí)，（2#投資不超過(guò)3百萬(wàn)元） f2(5）= Max r2(3)+ f3(2） r2(2)+ f3(3) r2(1)+ f3(4） = Max 12+8，10+11，5+15 = 21 注意：3#至多投資4百萬(wàn)元,當(dāng)k=1時(shí)，S1=5（最初有5百萬(wàn)元， 3#至少投資1百萬(wàn)元） f1(5）= Max r1(0)+ f2(5） r1(1)+ f2(4) r1(2)+ f2(3） r1(3)+ f2(2） r1(4)+ f2(1） =

7、 Max 0+21，3+18，6+14 10+9，12+4 = 21,解：應(yīng)用順序反推可知，最優(yōu)投資方案： 方案1：X*1=0，X*2=2，X*3=3 方案2：X*1=1，X*2=2，X*3=2 最大收益均為21百萬(wàn)元。,一維“背包”問(wèn)題 例7-8：有一輛最大貨運(yùn)量為10噸的卡車，用于裝載三種貨物，每種貨物的單位重量及相應(yīng)單位價(jià)值如下，應(yīng)如何裝載可使總價(jià)值最大？,解： 設(shè)第i種貨物裝載的件數(shù)為xi(i=1,2,3) 則問(wèn)題可表示為： max Z=4x1+5x2+6x3 3x1+4x2+5x3 10 xi0且為整數(shù)(i=1,2,3),方法一：由于決策變量取整數(shù)，所以可以用列表法求解。 當(dāng)k=1時(shí)

8、,f1(s)= max 4x1 03x1 s x1為整數(shù) 或 f1(s)= max 4x1 = 4 s/3 0 x1 s/3 x1為整數(shù),計(jì)算結(jié)果見(jiàn)下表：,當(dāng)k=2時(shí),f2(s)= max 5x2+ f1(s-4x2) 0 x2 s/4 x2為整數(shù) 計(jì)算結(jié)果見(jiàn)下表：,當(dāng)k=3時(shí) f3(10)= max 6x3+ f2(10-5x3) 0 x3 2 x3為整數(shù) = max 6x3+ f2(10-5x3) x3=0,1,2 = max f2(10),6+ f2(5),12+ f2(0) = max13,6+5,12+0 =13 此時(shí)x3*=0，可推得全部策略為： x1*=2，x2*=1， x3*=

9、0，最大價(jià)值為13。,方法二：?jiǎn)栴}最終要求f3(10)。 而f3(10)= max 4x1+5x2+6x3 3x1+4x2+5x3 10 xi為整數(shù)I=1,2,3 = max 4x1+5x2+6x3 3x1+4x2 10-5x3 xi為整數(shù)I=1,2,3,= max 6x3+ max 4x1+5x2 10-5x3 0 3x1+4x2 10-5x3 x3 0為整數(shù) xi 0為整數(shù)I=1,2 = max 6x3+ f2(10-5x3) x3=0,1,2 = max 0+f2(10),6+ f2(5),12+ f2(0),由此看到要計(jì)算f3(10)須先計(jì)算 f2(10)， f2(5) ，f2(0)

10、而 f2(10)= max 4x1+5x2 3x1+4x2 10 x1，x2 0整數(shù) = max 4x1+5x2 3x1 10-4x2 x1，x2 0整數(shù),= max 5x2+ max 4x1 10-4x2 0 3x1 10-4x2 x2 0整數(shù) x1 0整數(shù) = max 5x2+ f1(10-4x2 x2=0，1，2 = max f1(10),5+ f1(6),10+ f1(2),同理， f2(5)= max 4x1+5x2 3x1+4x2 5 x1，x2 0整數(shù) = max 5x2+ f1(5-4x2) x2=0，1 = max f1(5),5+ f1(1),f2(0) = max 4x1

11、+5x2 3x1+4x2 0 x1，x2 0整數(shù) = max 5x2+ f1(0-4x2) x2=0 = f1(0),為了計(jì)算f2(10） f2(5) f2(0)需要先計(jì)算f1(10) f1(6) f1(5) f1(2) f1(1) f1(0)。 由于 f1(s)= max 4x1=4s/3 0 x1 s/3 x1為整數(shù) f1(10)=12（x1=3），f1(6)=8（x1=2）， f1(5)=4（x1=1）， f1(2)=0 （x1=0）， f1(1)=0 （x1=0）， f1(0)=0 （x1=0）。,從而 f2(10)= max f1(10),5+ f1(6),10+ f1(2) = m

12、ax12，5+8，10+0 = 13 （x1=2， x2=1） f2(5) = max f1(5),5+ f1(1) = max4，5+0 = 5 （x1=0， x2=1） f2(0) = f1(0) = 0 （x1=0， x2=0）,最后有 f3(10)= max f2(10),6+ f2(5),12+ f2(0) = max13,6+5,12+0 = 13 （x1=2， x2=1， x3=0）,二維“背包”問(wèn)題 例7-9：有一輛最大貨運(yùn)量為12噸，最大容量10立方米的某種類型卡車，用于裝載兩種貨物A、B，每種貨物的單件重量分別3噸、4噸，體積為1立方米、5立方米，價(jià)值為2、3，求合理裝載的

13、最大效益？,解：設(shè)A、B貨物裝載的件數(shù)為 xi(i=1,2) 則問(wèn)題可表示為： max Z=2x1+3x2 3x1+4x2 12 x1+5x2 10 xi 0整數(shù) (i=1,2),并解出 f2(12，10)= max 2x1+3x2 3x1+4x2 12 x1+5x2 10 xi 0整數(shù)(i=1,2) = max 2x1+3x2 3x1 12-4x2 x1 10-5x2 xi 0整數(shù)(i=1,2),= max 3x2+ f1(12-4x2,10-5x2) 12-4x2 0 10-5x2 0 xi 0整數(shù)(i=2) = max 3x2+ f1(12-4x2,10-5x2) x2 12/4 x2

14、10/5 xi 0整數(shù)(i=2),= max 3x2+ f1(12-4 x2,10-5 x2) x2=0,1,2 = max f1(12,10),3+ f1(8,5),6+ f1(4,0),先 要計(jì)算 f1(12,10), f1(8,5),及 f1(4,0) f1(12,10)= max 2x1 = max 2x1 3x1 12 x1=0,1,2,3,4 x1 10 x1 0整數(shù) = 8 (x1*=4),同理， f1(8,5)=4 (x1*=2) f1(4,0)=0 (x1*=0) f2(12，10) = max f1(12,10),3+ f1(8,5),6+ f1(4,0) = max 8，

15、3+4，6+0 = 8 (x1*=4 x2*=0) 因此，最優(yōu)方案為：裝A種貨物4件，不裝B種貨物，最大價(jià)值為8。,連續(xù)變量的解法 例7-10：某公司有資金10萬(wàn)元，可投資于項(xiàng)目i(i=1,2,3)，若投資額為xi， 其收益分別為g1(x1)=4x1， g2(x2)=9x2, g3(x3)=2x32, 問(wèn)如何分配投資額，使總收益最大？,解：建立此問(wèn)題的數(shù)學(xué)模型求xi使 max Z=4x1+9x2+2x32 s.t. x1+x2+ x3 10 x1,x2, x3 0 按變量個(gè)數(shù)分階段，可看成三段決策問(wèn)題，設(shè)狀態(tài)變量sk表示：第k階段可以分配給第k到第3個(gè)項(xiàng)目的資金額。決策變量xk：決定投資給第k

16、個(gè)項(xiàng)目的資金額。,則有：s1=10, s2=s1-x1, s3=s2-x2 即狀態(tài)轉(zhuǎn)移方程為：sk+1=sk-xk 令最優(yōu)指標(biāo)函數(shù)fk(sk) 表示第k個(gè)階段，初始狀態(tài)為sk時(shí)，從第k個(gè)到第3個(gè)項(xiàng)目所獲最大收益,f1(s1)即為所求的總收益。 fk(sk)=maxgk(xk)+fk+1(sk+1) xk k=3,2,1 f4(s4)=0,k=3 時(shí)， f3(s3)= max 2x32 0 x3 s3 當(dāng)x3*=s3 時(shí),取得最大值 2s32 即：f3(s3)= max 2x32 = 2s32 0 x3 s3,k=2 時(shí)， f2(s2)= max 9x2+ f3(s3) 0 x2 s2 = ma

17、x 9x2+ 2s32 0 x2 s2 = max 9x2+ 2(s2-x2)2 0 x2 s2,令 h2(s2,x2)= 9x2+ 2(s2-x2)2 由 dh2/dx2=9+4(s2-x2)(-1)=0 解得 x2=s2-9/4 而 d2h2/dx22=40 所以 x2=s2-9/4 是極小點(diǎn)。,極大點(diǎn)只可能在0，s2端點(diǎn)取得： f2(0) = 2s22 f2(s2) = 9s2 當(dāng)s2 9/2時(shí), f2(0) f2(s2), 此時(shí)x2*=0 當(dāng)s2 9/2時(shí), f2(0) f2(s2) , 此時(shí)x2*= s2,k=1 時(shí)， f1(s1)= max 4x1+ f2(s2) 0 x1 s1 當(dāng)f2(s2)=9 s2時(shí), f1(10)= max 4x1+ 9 s1-9 x1 0 x1 10 = max 9 s1-5x1 0 x1 10 = 9 s1 (x1*=0) 但此時(shí)s2=s1-x1=10-0=109/2, 與s29/2矛盾。故舍去。,當(dāng)f2(0)= 2s22時(shí), f1(10)= max 4x1+ 2(s1-x1)2 0 x1