動(dòng)態(tài)規(guī)劃例 求解下列整數(shù)規(guī)劃的最優(yōu)解

1、例1 求解下列整數(shù)規(guī)劃的最優(yōu)解：解 （1）建立動(dòng)態(tài)規(guī)劃模型：階段變量：將給每一個(gè)變量賦值看成一個(gè)階段，劃分為3個(gè)階段，且階段變量k=1,2,3.設(shè)狀態(tài)變量表示從第階段到第3階段約束右端最大值，則設(shè)決策變量表示第階段賦給變量的值.狀態(tài)轉(zhuǎn)移方程：階段指標(biāo)：基本方程；其中（1） 用逆序法求解：當(dāng)時(shí)，而表示不超過(guò)的最大整數(shù)。因此，當(dāng)時(shí)，；當(dāng)時(shí)，可取0或1；當(dāng)時(shí)，可取0，1，2，由此確定現(xiàn)將有關(guān)數(shù)據(jù)列入表4.1中表4.1中.012012345678910000000000006666661200000666661200000111112當(dāng)時(shí)，有而。所以當(dāng)時(shí)，；當(dāng)時(shí)，；當(dāng)時(shí)。由此確定?，F(xiàn)將有關(guān)數(shù)據(jù)列入表4

2、.2中.表4.2 0120123456789100+00+00+00+00+00+60+60+60+60+60+125+05+05+05+05+05+65+610+010+010+00000566610111200001000210012305670510當(dāng)時(shí),有而故只能取0,1,2,3,由此確定?，F(xiàn)將有關(guān)數(shù)據(jù)列入表4.3中。表 4.30123100+124+68+512+01324按計(jì)算順序反推，由表4.3可知,當(dāng)及例5 用動(dòng)態(tài)規(guī)劃方法解下列非線性規(guī)劃問(wèn)題解： 解決這一類(lèi)靜態(tài)規(guī)劃問(wèn)題，需要人為地賦予時(shí)間概念，從而將該問(wèn)題轉(zhuǎn)化為多階段決策過(guò)程。按問(wèn)題的變量個(gè)數(shù)劃分階段，把它看作一個(gè)三階段決策問(wèn)

3、題，k=1，2，3設(shè)狀態(tài)變量為s1，s2，s3，s4并記s1c取問(wèn)題中的變量x1，x2，x3為決策變量狀態(tài)轉(zhuǎn)移方程為：s3=x3s3+x2=s2s2+x1=s1c允許決策集合為：x3=s30x2s20x1s1各階段指標(biāo)函數(shù)為：v1（x1）=x1v2（x2）=x22v3（x3）=x3，各指標(biāo)函數(shù)以乘積方式結(jié)合，最優(yōu)指標(biāo)函數(shù)fk（sk）表示從第k階段初始狀態(tài)sk出發(fā)到第3階段所得到的最大值，則動(dòng)態(tài)規(guī)劃基本方程為：用逆序解法由后向前依次求解：k=3時(shí)，x3*=s3k=2時(shí)，令h2（s2，x2）=x22（s2x2）用經(jīng)典解析法求極值點(diǎn)：解得：x2=0（舍）所以是極大值點(diǎn)。k=1時(shí)，令解得：x1=s1（

4、舍）所以是極大值點(diǎn)。由于s1未知，所以對(duì)s1再求極值，顯然s1=c時(shí)，f1（s1）取得最大值反向追蹤得各階段最優(yōu)決策及最優(yōu)值：s1=c所以最優(yōu)解為：例6 用動(dòng)態(tài)規(guī)劃方法解下列非線性規(guī)劃問(wèn)題解： 按變量個(gè)數(shù)將原問(wèn)題分為三個(gè)階段，階段變量k=1，2，3；選擇xk為決策變量；狀態(tài)變量sk表示第k階段至第3階段決策變量之和；取小區(qū)間長(zhǎng)度=1，小區(qū)間數(shù)目m=6/1=6，狀態(tài)變量sk的取值點(diǎn)為：狀態(tài)轉(zhuǎn)移方程：sk+1=skxk；允許決策集合：Dk（sk）=xk|0xkskk=1，2，3xk，sk均在分割點(diǎn)上取值；階段指標(biāo)函數(shù)分別為：g1（x1）=x12g2（x2）=x2g3（x3）=x33，最優(yōu)指標(biāo)函數(shù)f

5、k（sk）表示從第k階段狀態(tài)sk出發(fā)到第3階段所得到的最大值，動(dòng)態(tài)規(guī)劃的基本方程為：k=3時(shí)，s3及x3取值點(diǎn)較多，計(jì)算結(jié)果以表格形式給出，見(jiàn)表6.1-6.3所示。表6.1 計(jì)算結(jié)果fx3s3x3f3(s3)x3*01234560123456018276412521601827641252160123456表6.2 計(jì)算結(jié)果fx2s2x2 f3(s2x2)f2(s2)x2*0123456012345600000001×01×11×81×271×641×1252×02×12×82×272×

6、;643×03×13×83×274×04×14×85×05×16×00018276412800,111112表6.3 計(jì)算結(jié)果fx1s1x12 f2(s1x1)f1(s1)x1*0123456601×644×279×816×125×036×01082由表6.3知，x1*=2，s1=6，則s2= s1x1*=62=4，查表6.2得：x2*=1，則s3= s2x2*=41=3，查表6.1得：x3*=3，所以最優(yōu)解為：x1*=2，x2*=1，

7、x3*=3，f1(s1)=108。上面討論的問(wèn)題僅有一個(gè)約束條件。對(duì)具有多個(gè)約束條件的問(wèn)題，同樣可以用動(dòng)態(tài)規(guī)劃方法求解，但這時(shí)是一個(gè)多維動(dòng)態(tài)規(guī)劃問(wèn)題，解法上比較繁瑣一些。例7 某公司打算在3個(gè)不同的地區(qū)設(shè)置4個(gè)銷(xiāo)售點(diǎn)，根據(jù)市場(chǎng)部門(mén)估計(jì)，在不同地區(qū)設(shè)置不同數(shù)量的銷(xiāo)售點(diǎn)每月可得到的利潤(rùn)如表6.4所示。試問(wèn)在各地區(qū)如何設(shè)置銷(xiāo)售點(diǎn)可使每月總利潤(rùn)最大。表6.4 利潤(rùn)值地區(qū)銷(xiāo)售點(diǎn)01234123000161210251714302116322217解： 如前所述，建立動(dòng)態(tài)規(guī)劃數(shù)學(xué)模型：將問(wèn)題分為3個(gè)階段，k=1，2，3；決策變量xk表示分配給第k個(gè)地區(qū)的銷(xiāo)售點(diǎn)數(shù)；狀態(tài)變量為sk表示分配給第k個(gè)至第3個(gè)地區(qū)

8、的銷(xiāo)售點(diǎn)總數(shù)；狀態(tài)轉(zhuǎn)移方程：sk+1=skxk，其中s1=4；允許決策集合：Dk（sk）=xk|0xksk階段指標(biāo)函數(shù)：gk（xk）表示xk個(gè)銷(xiāo)售點(diǎn)分配給第k個(gè)地區(qū)所獲得的利潤(rùn)；最優(yōu)指標(biāo)函數(shù)fk（sk）表示將數(shù)量為sk的銷(xiāo)售點(diǎn)分配給第k個(gè)至第3個(gè)地區(qū)所得到的最大利潤(rùn)，動(dòng)態(tài)規(guī)劃基本方程為：數(shù)值計(jì)算如表所示。表6.5 k=3時(shí)計(jì)算結(jié)果fx3s3g3（x3）f3(s3)x3*012340123401014161701014161701234表6.6 k=2時(shí)計(jì)算結(jié)果fx2s2g2(x2)+f3(s2x2)f2(s2)x2*012340123400+100+140+160+1712+012+1012+

9、1412+1617+017+1017+1421+021+1022+001222273101122,3表6.7 k=1時(shí)計(jì)算結(jié)果fx1s1g1(x1)+f2(s1x1)f1(s1)x1*0123440+3116+2725+2230+1232+0472所以最優(yōu)解為：x1*=2，x2*=1，x3*=1，f1(4)=47，即在第1個(gè)地區(qū)設(shè)置2個(gè)銷(xiāo)售點(diǎn)，第2個(gè)地區(qū)設(shè)置1個(gè)銷(xiāo)售點(diǎn)，第3個(gè)地區(qū)設(shè)置1個(gè)銷(xiāo)售點(diǎn)，每月可獲利潤(rùn)47。例9 （生產(chǎn)庫(kù)存問(wèn)題）某工廠要對(duì)一種產(chǎn)品制定今后四個(gè)時(shí)期的生產(chǎn)計(jì)劃，據(jù)估計(jì)在今后四個(gè)時(shí)期內(nèi)，市場(chǎng)對(duì)該產(chǎn)品的需求量分別為2，3，2，4單位，假設(shè)每批產(chǎn)品固定成本為3千元，若不生產(chǎn)為0，每

10、單位產(chǎn)品成本為1千元，每個(gè)時(shí)期最大生產(chǎn)能力不超過(guò)6個(gè)單位，每期期末未出售產(chǎn)品，每單位需付存貯費(fèi)0.5千元，假定第1期初和第4期末庫(kù)存量均為0，問(wèn)該廠如何安排生產(chǎn)與庫(kù)存，可在滿足市場(chǎng)需求的前提下總成本最小。解: 以每個(gè)時(shí)期作為一個(gè)階段，該問(wèn)題分為4個(gè)階段，k=1，2，3，4；決策變量xk表示第k階段生產(chǎn)的產(chǎn)品數(shù)；狀態(tài)變量sk表示第k階段初的庫(kù)存量；以dk表示第k階段的需求，則狀態(tài)轉(zhuǎn)移方程：sk+1=sk+xkdk；k=4，3，2，1由于期初及期末庫(kù)存為0，所以s1=0，s5=0；允許決策集合Dk（sk）的確定：當(dāng)skdk時(shí)，xk可以為0，當(dāng)sk<dk時(shí)，至少應(yīng)生產(chǎn)dksk，故xk的下限為m

11、ax（0，dksk）每期最大生產(chǎn)能力為6，xk最大不超過(guò)6，由于期末庫(kù)存為0，xk還應(yīng)小于本期至4期需求之和減去本期的庫(kù)存量，所以xk的上限為min（，6），故有：Dk（sk）=xk| max（0，dksk）xkmin（，6）階段指標(biāo)函數(shù)rk（sk，xk）表示第k期的生產(chǎn)費(fèi)用與存貯費(fèi)用之和：最優(yōu)指標(biāo)函數(shù)fk（sk）表示第k期庫(kù)存為sk到第4期末的生產(chǎn)與存貯最低費(fèi)用，動(dòng)態(tài)規(guī)劃基本方程為：先求出各狀態(tài)允許狀態(tài)集合及允許決策集合，如表6.8所示。表6.8 狀態(tài)允許狀態(tài)集合及允許決策集合s10D1(s1)2,3,4,5,6s201234D2(s2)3,4,5,62,3,4,5,61,2,3,4,5,6

12、0,1,2,3,4,5,60,1,2,3,4,5s30123456D3(s3)2,3,4,5,61,2,3,4,50,1,2,3,40,1,2,30,1,20,10s401234D4(s4)43210由基本方程計(jì)算各階段策略，結(jié)果如下表所示。表6.9 k=4時(shí)計(jì)算結(jié)果s4x4s5f5(s5)f4(s4)012344*3*2*1*0*76.565.5200000000007*6.5*6*5.5*2* 表6.10 k=3時(shí)計(jì)算結(jié)果s3x3s4= s3+ x32f4(s4)f3(s3)023456*567890123476.565.521212.51313.511*112345*4.55.56.57

13、.58.50123476.565.5211.51212.51310.5*20*1234156780123476.565.528*11.51212.51030*1231.55.56.57.512346.565.528*11.5129.540*1226723465.528*11.5950*12.56.5345.528*8.560*3425*表6.11 k=2時(shí)計(jì)算結(jié)果s2x2s3= s2+ x23f3(s3)f2(s2)0345*6678901231110.5881717.516*171234*565.56.57.58.59.5012341110.588816.51715.5*16.517.521

14、23*45656789100123451110.588881616.515*16171830*1234561.55.56.57.58.59.510.501234561110.58888512.5*1614.515.516.517.515.540*12345267891012345610.58888512.5*1415161715表6.12 k=1時(shí)計(jì)算結(jié)果s1x1s2= x12f2(s2)f1(s1)02345*656789012341615.51512.512.52121.52220.5*21.5逆向追蹤可得：x1*=5，s2=3，x2*=0，s3=0，x3*=6，s4=4，x4*=0，即第

15、1時(shí)期生產(chǎn)5個(gè)單位，第3時(shí)期生產(chǎn)6個(gè)單位，第2，4時(shí)期不生產(chǎn)，可使總費(fèi)用最小，最小費(fèi)用為20.5千元。例10 （庫(kù)存銷(xiāo)售問(wèn)題）設(shè)某公司計(jì)劃在1至4月份從事某種商品經(jīng)營(yíng)。已知倉(cāng)庫(kù)最多可存儲(chǔ)600件這種商品，已知1月初存貨200件，根據(jù)預(yù)測(cè)知1至4月份各月的單位購(gòu)貨成本及銷(xiāo)售價(jià)格如表6.13所示，每月只能銷(xiāo)售本月初的庫(kù)存，當(dāng)月進(jìn)貨供以后各月銷(xiāo)售，問(wèn)如何安排進(jìn)貨量和銷(xiāo)售量，使該公司四個(gè)月獲得利潤(rùn)最大（假設(shè)四月底庫(kù)存為零）。表6.13 單位購(gòu)貨成本及銷(xiāo)售價(jià)格月份購(gòu)貨成本C銷(xiāo)售價(jià)格P12344038404245423944解: 按月份劃分階段，k=1，2，3，4；狀態(tài)變量sk表示第k月初的庫(kù)存量，s1=

16、200，s5=0；決策變量： xk表示第k月售出的貨物數(shù)量，yk表示第k月購(gòu)進(jìn)的貨物數(shù)量；狀態(tài)轉(zhuǎn)移方程：sk+1=sk+ykxk；允許決策集合：0xksk，0yk600（skxk）；階段指標(biāo)函數(shù)為：pkxkckyk表示k月份的利潤(rùn)，其中pk為第k月份的單位銷(xiāo)售價(jià)格，ck為第k月份的單位購(gòu)貨成本；最優(yōu)指標(biāo)函數(shù)fk（sk）表示第k月初庫(kù)存為sk時(shí)從第k月至第4月末的最大利潤(rùn)，則動(dòng)態(tài)規(guī)劃基本方程為：k=4時(shí)，x4*=s4y4*=0k=3時(shí)，為求出使44s35x3+4y3最大的x3，y3，須求解線性規(guī)劃問(wèn)題：只有兩個(gè)變量x3，y3，可用圖解法也可用單純形法求解，取得最優(yōu)解，x3*=0，y3*=600s

17、3，f3（s3）=40s3+2400k=2時(shí)，類(lèi)似地求得：x2*=s2，y2*=600，f2（s2）=42s2+3600k=1時(shí)，類(lèi)似地求得：x1*=s1，y1*=600，f1（s1）=45s1+4800=13800逆向追蹤得各月最優(yōu)購(gòu)貨量及銷(xiāo)售量：x1*=s1=200y1*=600；x2*=s2=s1+ y1*x1*=600y2*=600；x3*=0y3*=600s3=600（s2+ y2*x2*）=0x4*=s4=（s3+ y3*x3*）=600y4*=0即1月份銷(xiāo)售200件，進(jìn)貨600件，2月份銷(xiāo)售600件，進(jìn)貨600件，3月份銷(xiāo)售量及進(jìn)貨量均為0，4月份銷(xiāo)售600件，不進(jìn)貨，可獲得最大

18、總利潤(rùn)13800。例11某鞋店銷(xiāo)售一種雪地防潮鞋，以往的銷(xiāo)售經(jīng)歷表明，此種鞋的銷(xiāo)售季節(jié)是從10月1日至3月31日。下個(gè)銷(xiāo)售季節(jié)各月的需求預(yù)測(cè)值如表6.14所示。 表6.14 需求預(yù)測(cè)值 (單位：雙)月份101112123需求402030403020該鞋店的此種鞋完全從外部生產(chǎn)商進(jìn)貨，進(jìn)貨價(jià)每雙4美元。進(jìn)貨批量的基本單位是箱，每箱10雙。由于存貯空間的限制，每次進(jìn)貨不超過(guò)5箱。對(duì)應(yīng)不同的訂貨批量，進(jìn)價(jià)享受一定的數(shù)量折扣，具體數(shù)值如表6.15所示。表6.15 數(shù)量折扣數(shù)值表進(jìn)貨批量1箱2箱3箱4箱5箱數(shù)量折扣4%5%10%20%25%假設(shè)需求是按一定速度均勻發(fā)生的，訂貨不需時(shí)間，但訂貨只能在月初辦

19、理一次，每次訂貨的采購(gòu)費(fèi)（與采購(gòu)數(shù)量無(wú)關(guān)）為10美元。月存貯費(fèi)按每月月底鞋的存量計(jì)，每雙0.2美元。由于訂貨不需時(shí)間，所以銷(xiāo)售季節(jié)外的其他月份的存貯量為“0”。試確定最佳的進(jìn)貨方案，以使總的銷(xiāo)售費(fèi)用最小。解：階段：將銷(xiāo)售季節(jié)6個(gè)月中的每一個(gè)月作為一個(gè)階段，即；狀態(tài)變量：第階段的狀態(tài)變量代表第個(gè)月初鞋的存量；決策變量：決策變量代表第個(gè)月的采購(gòu)批量；狀態(tài)轉(zhuǎn)移律：（是第個(gè)月的需求量）；邊界條件：，；階段指標(biāo)函數(shù)：代表第個(gè)月所發(fā)生的全部費(fèi)用，即與采購(gòu)數(shù)量無(wú)關(guān)的采購(gòu)費(fèi)、與采購(gòu)數(shù)量成正比的購(gòu)置費(fèi)和存貯費(fèi).其中：；最優(yōu)指標(biāo)函數(shù)：最優(yōu)指標(biāo)函數(shù)具有如下遞推形式當(dāng)時(shí)（3月）：表6.16 時(shí)計(jì)算結(jié)果S601020x

20、620100f6（S6）86480當(dāng)時(shí)（2月）：表6.17 時(shí)計(jì)算結(jié)果x5S501020304050020418816450164101721681424014220134136122301223086989008640505205050404當(dāng)時(shí)（1月）：表6.18 時(shí)計(jì)算結(jié)果x4S4010203040500302304403021028228228630、4028220250262264252202503021223024423021810212401641922122101961700164501441741781761520144601261401441320126當(dāng)時(shí)（12月）：表6.19 時(shí)計(jì)算結(jié)果x3S30102030405004204224145041410388402392384503842035037037236233250332303023323403423103140302402843023102902922980284當(dāng)時(shí)（11月）：表6.20 時(shí)計(jì)算結(jié)果x2S201020304050050050447446850468104624724544464