1、7-2動(dòng)態(tài)規(guī)劃應(yīng)用示例7-6一家著名的快餐店計(jì)劃在一個(gè)城市設(shè)立五個(gè)分店，該城市分為三個(gè)區(qū)，分別用1、2和3表示。由于各地區(qū)的地理位置、交通狀況和居民構(gòu)成的差異，將對(duì)各分公司的經(jīng)營狀況產(chǎn)生直接影響。經(jīng)過市場調(diào)查和咨詢，經(jīng)營者制定了下表。該表顯示了在每個(gè)地區(qū)設(shè)立不同數(shù)量的分支機(jī)構(gòu)時(shí)的利潤估計(jì)，并且通過確定在每個(gè)地區(qū)設(shè)立的分支機(jī)構(gòu)的數(shù)量來使總利潤最大化。解決方案：每個(gè)領(lǐng)域都有三個(gè)階段。狀態(tài)：Sk是在K階段開始時(shí)可供分配的商店數(shù)量。決策：dk是分配給K區(qū)的商店數(shù)量。狀態(tài)轉(zhuǎn)移方程：Sk 1=Sk-dk效益：rk(dk)是分配給K和dk區(qū)商店的利潤。fk(Sk)是當(dāng)?shù)趉階段的初始狀態(tài)為Sk時(shí)，從第k階段到

2、最后階段的最大利潤。當(dāng)fk(sk)=max rk(dk)fk 1(sk 1)dk(sk)k=1，2，3f4 (S4)=0、k=3時(shí)，其計(jì)算如下：當(dāng)k=2時(shí)，其計(jì)算如下：d*3=0 S2-D2最大總利潤=22。D1 *=3，S2=S1-D1 *=5-3=2，D2 *=2s3=S2-D2 *=2-2=0，D3 *=0。建立動(dòng)態(tài)規(guī)劃模型的要點(diǎn)是：分析問題的意義，識(shí)別問題的多階段，并按時(shí)間或空間順序適當(dāng)劃分滿足遞歸關(guān)系的幾個(gè)階段。建立動(dòng)態(tài)規(guī)劃模型的要點(diǎn)：正確選擇狀態(tài)變量要具備兩個(gè)必要的特征：(1)可知性：可以直接或間接地確定過去演化過程中各階段狀態(tài)變量的值。(2)能準(zhǔn)確描述過程的演化，不滿足后效。建立

3、動(dòng)態(tài)規(guī)劃模型的要點(diǎn)：根據(jù)狀態(tài)變量和決策變量的含義，正確編寫狀態(tài)轉(zhuǎn)移方程或轉(zhuǎn)移規(guī)則。根據(jù)問題的含義，定義了指數(shù)函數(shù)、最優(yōu)指數(shù)函數(shù)和一段收益的含義，即階段指數(shù)。正確列出了最優(yōu)指標(biāo)函數(shù)的遞推關(guān)系和邊界條件(即微分方程基本方程)。例7-7(投資問題)現(xiàn)有資金500萬元，可用于投資三個(gè)項(xiàng)目。投資金額為整數(shù)(百萬元)，其中2#項(xiàng)目投資不超過300萬元，1#和3#項(xiàng)目投資不超過400萬元，3#項(xiàng)目投資不低于100萬元。每個(gè)項(xiàng)目投資5年后，預(yù)計(jì)收入如下表所示。詢問如何獲得最大的投資。解決方案：這個(gè)投資問題可以分為三個(gè)階段。在k階段，確定k #的投資金額，使Sk投資1#、2#.(k -1)#項(xiàng)目。Xk對(duì)k項(xiàng)目的

4、投資。Rk (Xk)投資k#項(xiàng)目Xk的收入。fk(Sk)在k #(k 1)#.N#通過使用剩余資金Sk。，狀態(tài)轉(zhuǎn)移方程為：Sk 1=Sk- Xk為了獲得最大效益，必須用500萬元進(jìn)行投資。因此，當(dāng)?shù)谒碾A段存在時(shí)，S4=0是必要的，所以遞推方程是fk(sk)=maxrk(xk)fk 1(sk 1)dk(sk)k=3，2，1f4 (S4投資至少100萬元)f3(1)=4，f3(2)=8，f3(3)=11，f3(4)=15，當(dāng)k=2，(2#投資少于300萬元)F2 (1)=R2 (0) F3 (1)=0 4f2 (2當(dāng)k (2#投資不超過300萬元)F2 (3)=最高R2(2)F3(1)R2(1)F

5、3(2)R2(0)F3(3)=最高104，58，011=14，F(xiàn)2 (4)=最高R2(3)F3(1)R2(2)F3(2)R2(1)F3(3)R2(0)F3(4)=最高124，108，511，015=18，當(dāng)k=2時(shí)，(2#投資不超過，當(dāng)k=1時(shí)，3#至少應(yīng)投資100萬元)F1(5)=Max R1(0)F2(5)R1(1)F2(4)R1(2)F2(3)R1(3)F2(2)R1(4)F2(1)=Max 0 21，3 18，6 14 10 9，最優(yōu)投資方案：方案1: x * 1=0，X*2=2，X * 3=3方案二：x * 1=1，X*2=2，X*3=2，最高收入為2100萬元。一維“背包”問題示例

6、7-8:有一輛卡車，最大貨運(yùn)量為10噸，用于裝載三種貨物。每種貨物的單位重量和相應(yīng)的單位價(jià)值如下?？們r(jià)值應(yīng)該如何最大化？解決方法：如果第一類貨物裝載的件數(shù)是xi(i=1，2，3)，則問題可以表示為：Max Z=4x15x26x3 1x14x25x3 10，這是一個(gè)整數(shù)(i=1，2，3)。方法1:因?yàn)闆Q策變量是一個(gè)整數(shù)，所以它可以通過列表方法來求解。當(dāng)k=1時(shí)，f1(s)=max 4x1 03x1 s x1為整數(shù)或f1(s)=max 4x1=4 s/3 0 x1 s/3 x1為整數(shù)，計(jì)算結(jié)果如下：當(dāng)k=2時(shí)，f2(s)=max 5x2 f1(s-4x2) 0 x2 s/4 x2為整數(shù)。當(dāng)k=3，

7、f3(10)=最大6x3 f2(10-5x3) 0 x3 2 x3是一個(gè)整數(shù)=最大6x3f2 (10-5x3) x3*=0 0，1，2=最大f2(10)，6f2 (5)，12f2 (0)=最大13，65，120方法2:問題的最終要求是f3(10)。F3 (10)=最大4x1 5x2 6x3 3x1 4x2 5x3 10 Xi是整數(shù)1=1，2，3=最大4x1 5x2 6x3 3x1 4x2 10-5x3 Xi是整數(shù)1=1，2，3=最大6x3最大4x1 5x2 10-5x3 0 3x1 4x2 10-5x3 x3 0是整數(shù)xi 0是整數(shù)1=1，2=最大6x3 F2 (10-5x3) x3=0，1，

8、2=最大0f2 (10 f2(5)和f2(0)必須在f3(10)=max 4x15x23x14x210x1，x2 0 integer=max 4x 1 5x 2 3x 1 10-4x 2 x1，x2 0 integer，max 5x 2 max 4x 110-4x 203 x110-4x 2 x20 integer x1 0 integer=max 5x 2 f1(10-4x 2 x2=0，1，2=maxf1 (10)，5f1 (6)，10f1 (2)之前計(jì)算，同樣如此。 F2(5)=最大4x1 5x2 3x1 4x2 5 x1，x2 0 integer=最大5x2 f1(5-4x2) x2=

9、0，1=maxf1 (5)，5f1 (1)，F(xiàn)2 (0)=max4x15x23x14x20x1，X2 0 integer=最大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)。因?yàn)閒1(s)=最大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因此F2 (10)=maxf1 (10)，5f1 (6)，10f1 (2)=max12，5 8，10 0=1

10、3 (x1=2，x2=1) F2 (5)=maxf1 (5)，5f1 (1)=max4，50 X2=1) f2(0)=f1(0)=0 (x1=0，x2=0)，最后F3 (10)=maxf2 (10)，6f2 (5)，12f2 (0)=max13，65， 120=13 (x1=2)用最大容量為10立方米的某型卡車裝載甲、乙兩種貨物，每件貨物重量分別為3噸和4噸，體積分別為1立方米和5立方米，取值分別為2和3，以獲得合理裝載的最大效益。解決方法：如果A和B裝載的貨物數(shù)量為xi(i=1，2)，則問題可以表示為：最大Z=2x13x23x14x212x15x210整數(shù)(i=1，2)，F(xiàn)2 (12，10)

11、=最大2x13x14x212x15x210整數(shù)(I=)2=最大2x 13 x2x3x 12-4x 2x 110-5x 2x 10整數(shù)(i=1，2)，最大3x2f1 (12-4x2， 6f1 (4，5) 0) f1 (12，10)=max2x1=max2x1 3x1 12x1=0，1，2，3，4x1 10x10 integer=8 (x1*=4)，同樣，f1 (8，5)=4 (x1 *=2) f1 (4，0)=0 3f1 (8，5)，6f1 (4，0)=max8，34，60=8 (x1 *=4x2 *=0)。 因此，最好的方案是包裝4件甲貨而不包裝乙貨，最大值為8件。例7-10:一家公司有10萬

12、元資金，可以投資項(xiàng)目一(i=1，2，3)。如果投資金額為xi，其收入為g1(x1)=4x1，g2(x2)=9x2，g3(x3)=2x32。如何分配投資金額使總收益最大化？解決方案：建立該問題的數(shù)學(xué)模型，并找到xi，這樣，根據(jù)變量的數(shù)量，最大Z=4x19X22x32 S.T. X1X2X310X1，X2，X30可視為一個(gè)三階段決策問題。讓狀態(tài)變量sk表示可以分配給第kth階段第三個(gè)項(xiàng)目的資金量。決策變量xk:決定kth項(xiàng)目的投資金額。有：s1=10，s2=s1-x1，s3=s2-x2，即狀態(tài)轉(zhuǎn)移方程為：sk 1=sk-xk，這樣最佳指標(biāo)函數(shù)fk(sk)代表kth階段，當(dāng)初始狀態(tài)為sk時(shí)，獲得從k

13、th到第3個(gè)項(xiàng)目的最大收益，f1(s1)是總收益。Fk (sk)=maxgk (xk) fk1 (sk1) xk k=3，2，1f4 (S4)=0，當(dāng)k=3時(shí)，f3(s3)=最大2x32 0 x3 s3當(dāng)x3*=s3時(shí)，最大值為2s32，即F3 (S3)=最大2x32 F2 (S2)=最大9X2F3 (S3)0x2S2=最大9X22S320x2S2=最大9X22 (S2-X2) 20x2S2，讓h2(s2，x2)=0 s2終點(diǎn)：F2 (0)=2s22f2 (S2)=9s2f2 (0) F2 (S2)當(dāng)s2 9/2時(shí)，x2*=0當(dāng)s2 9/2時(shí)，f2 (0) F2 (S2)當(dāng)x2 *=S2且k=1 F1(s1)=最大4x1 f2(s2) 0 x1 s1當(dāng)f2(s2)=9 s2時(shí)，f1 (10)=最大4x19s1-9x10x110=最大9s1-5x10x110=9s1