1、例1 求解下列整數規劃的最優解：解 （1）建立動態規劃模型：階段變量：將給每一個變量賦值看成一個階段，劃分為3個階段，且階段變量k=1,2,3.設狀態變量表示從第階段到第3階段約束右端最大值，則設決策變量表示第階段賦給變量的值.狀態轉移方程：階段指標：基本方程；其中（1） 用逆序法求解：當時，而表示不超過的最大整數。因此，當時，；當時，可取0或1；當時，可取0，1，2，由此確定現將有關數據列入表4.1中表4.1中.012012345678910000000000006666661200000666661200000111112當時，有而。所以當時，；當時，；當時。由此確定。現將有關數據列入表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當時,有而故只能取0,1,2,3,由此確定。現將有關數據列入表4.3中。表 4.30123100+124+68+512+01324按計算順序反推，由表4.3可知,當及例5 用動態規劃方法解下列非線性規劃問題解： 解決這一類靜態規劃問題，需要人為地賦予時間概念，從而將該問題轉化為多階段決策過程。按問題的變量個數劃分階段，把它看作一個三階段決策問

3、題，k=1，2，3設狀態變量為s1，s2，s3，s4并記s1c取問題中的變量x1，x2，x3為決策變量狀態轉移方程為：s3=x3s3+x2=s2s2+x1=s1c允許決策集合為：x3=s30x2s20x1s1各階段指標函數為：v1（x1）=x1v2（x2）=x22v3（x3）=x3，各指標函數以乘積方式結合，最優指標函數fk（sk）表示從第k階段初始狀態sk出發到第3階段所得到的最大值，則動態規劃基本方程為：用逆序解法由后向前依次求解：k=3時，x3*=s3k=2時，令h2（s2，x2）=x22（s2x2）用經典解析法求極值點：解得：x2=0（舍）所以是極大值點。k=1時，令解得：x1=s1（

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

5、k（sk）表示從第k階段狀態sk出發到第3階段所得到的最大值，動態規劃的基本方程為：k=3時，s3及x3取值點較多，計算結果以表格形式給出，見表6.1-6.3所示。表6.1 計算結果fx3s3x3f3(s3)x3*01234560123456018276412521601827641252160123456表6.2 計算結果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 計算結果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，所以最優解為：x1*=2，x2*=1，

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

8、的銷售點總數；狀態轉移方程：sk+1=skxk，其中s1=4；允許決策集合：Dk（sk）=xk|0xksk階段指標函數：gk（xk）表示xk個銷售點分配給第k個地區所獲得的利潤；最優指標函數fk（sk）表示將數量為sk的銷售點分配給第k個至第3個地區所得到的最大利潤，動態規劃基本方程為：數值計算如表所示。表6.5 k=3時計算結果fx3s3g3（x3）f3(s3)x3*012340123401014161701014161701234表6.6 k=2時計算結果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時計算結果fx1s1g1(x1)+f2(s1x1)f1(s1)x1*0123440+3116+2725+2230+1232+0472所以最優解為：x1*=2，x2*=1，x3*=1，f1(4)=47，即在第1個地區設置2個銷售點，第2個地區設置1個銷售點，第3個地區設置1個銷售點，每月可獲利潤47。例9 （生產庫存問題）某工廠要對一種產品制定今后四個時期的生產計劃，據估計在今后四個時期內，市場對該產品的需求量分別為2，3，2，4單位，假設每批產品固定成本為3千元，若不生產為0，每

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

11、ax（0，dksk）每期最大生產能力為6，xk最大不超過6，由于期末庫存為0，xk還應小于本期至4期需求之和減去本期的庫存量，所以xk的上限為min（，6），故有：Dk（sk）=xk| max（0，dksk）xkmin（，6）階段指標函數rk（sk，xk）表示第k期的生產費用與存貯費用之和：最優指標函數fk（sk）表示第k期庫存為sk到第4期末的生產與存貯最低費用，動態規劃基本方程為：先求出各狀態允許狀態集合及允許決策集合，如表6.8所示。表6.8 狀態允許狀態集合及允許決策集合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由基本方程計算各階段策略，結果如下表所示。表6.9 k=4時計算結果s4x4s5f5(s5)f4(s4)012344*3*2*1*0*76.565.5200000000007*6.5*6*5.5*2* 表6.10 k=3時計算結果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時計算結果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時計算結果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時期生產5個單位，第3時期生產6個單位，第2，4時期不生產，可使總費用最小，最小費用為20.5千元。例10 （庫存銷售問題）設某公司計劃在1至4月份從事某種商品經營。已知倉庫最多可存儲600件這種商品，已知1月初存貨200件，根據預測知1至4月份各月的單位購貨成本及銷售價格如表6.13所示，每月只能銷售本月初的庫存，當月進貨供以后各月銷售，問如何安排進貨量和銷售量，使該公司四個月獲得利潤最大（假設四月底庫存為零）。表6.13 單位購貨成本及銷售價格月份購貨成本C銷售價格P12344038404245423944解: 按月份劃分階段，k=1，2，3，4；狀態變量sk表示第k月初的庫存量，s1=

16、200，s5=0；決策變量： xk表示第k月售出的貨物數量，yk表示第k月購進的貨物數量；狀態轉移方程：sk+1=sk+ykxk；允許決策集合：0xksk，0yk600（skxk）；階段指標函數為：pkxkckyk表示k月份的利潤，其中pk為第k月份的單位銷售價格，ck為第k月份的單位購貨成本；最優指標函數fk（sk）表示第k月初庫存為sk時從第k月至第4月末的最大利潤，則動態規劃基本方程為：k=4時，x4*=s4y4*=0k=3時，為求出使44s35x3+4y3最大的x3，y3，須求解線性規劃問題：只有兩個變量x3，y3，可用圖解法也可用單純形法求解，取得最優解，x3*=0，y3*=600s

17、3，f3（s3）=40s3+2400k=2時，類似地求得：x2*=s2，y2*=600，f2（s2）=42s2+3600k=1時，類似地求得：x1*=s1，y1*=600，f1（s1）=45s1+4800=13800逆向追蹤得各月最優購貨量及銷售量：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月份銷售200件，進貨600件，2月份銷售600件，進貨600件，3月份銷售量及進貨量均為0，4月份銷售600件，不進貨，可獲得最大

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

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

20、620100f6（S6）86480當時（2月）：表6.17 時計算結果x5S501020304050020418816450164101721681424014220134136122301223086989008640505205050404當時（1月）：表6.18 時計算結果x4S4010203040500302304403021028228228630、4028220250262264252202503021223024423021810212401641922122101961700164501441741781761520144601261401441320126當時（12月）：表6.19 時計算結果x3S30102030405004204224145041410388402392384503842035037037236233250332303023323403423103140302402843023102902922980284當時（11月）：表6.20 時計算結果x2S201020304050050050447446850468104624724544464