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

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

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

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

5、k（sk）表示從第k階段狀態(tài)sk出發(fā)到第3階段所得到的最大值，動態(tài)規(guī)劃的基本方程為：k=3時，s3及x3取值點較多，計算結果以表格形式給出，見表6.1-6.3所示。表6.1 計算結果fx3s3x3f3(s3)x3*01234560123456018276412521601827641252160123456表6.2 計算結果fx2s2x2 f3(s2x2)f2(s2)x2*01234560123456000000010111812716411252021282272643031383274041485051600018276412800,111112表6.3 計算結果fx1s1x12 f2(s

6、1x1)f1(s1)x1*012345660164427981612503601082由表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，x3*=3，f1(s1)=108。上面討論的問題僅有一個約束條件。對具有多個約束條件的問題，同樣可以用動態(tài)規(guī)劃方法求解，但這時是一個多維動態(tài)規(guī)劃問題，解法上比較繁瑣一些。例7 某公司打算在3個不同的地區(qū)設置4個銷售點，根據(jù)市場部門估計，在不同地區(qū)設置不同數(shù)量的銷售點每月可得到的利潤如表6.4所示。試問在各地區(qū)如何設置銷售點

7、可使每月總利潤最大。表6.4 利潤值地區(qū)銷售點01234123000161210251714302116322217解： 如前所述，建立動態(tài)規(guī)劃數(shù)學模型：將問題分為3個階段，k=1，2，3；決策變量xk表示分配給第k個地區(qū)的銷售點數(shù)；狀態(tài)變量為sk表示分配給第k個至第3個地區(qū)的銷售點總數(shù)；狀態(tài)轉移方程：sk+1=skxk，其中s1=4；允許決策集合：dk（sk）=xk|0xksk階段指標函數(shù)：gk（xk）表示xk個銷售點分配給第k個地區(qū)所獲得的利潤；最優(yōu)指標函數(shù)fk（sk）表示將數(shù)量為sk的銷售點分配給第k個至第3個地區(qū)所得到的最大利潤，動態(tài)規(guī)劃基本方程為：數(shù)值計算如表所示。表6.5 k=3時

8、計算結果fx3s3g3（x3）f3(s3)x3*012340123401014161701014161701234表6.6 k=2時計算結果fx2s2g2(x2)+f3(s2x2)f2(s2)x2*012340123400+100+140+160+1712+012+1012+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所以最優(yōu)解為：x1*=2，x2*=1，x3*=1，f1(4)=47，即在第1

9、個地區(qū)設置2個銷售點，第2個地區(qū)設置1個銷售點，第3個地區(qū)設置1個銷售點，每月可獲利潤47。例9 （生產(chǎn)庫存問題）某工廠要對一種產(chǎn)品制定今后四個時期的生產(chǎn)計劃，據(jù)估計在今后四個時期內(nèi)，市場對該產(chǎn)品的需求量分別為2，3，2，4單位，假設每批產(chǎn)品固定成本為3千元，若不生產(chǎn)為0，每單位產(chǎn)品成本為1千元，每個時期最大生產(chǎn)能力不超過6個單位，每期期末未出售產(chǎn)品，每單位需付存貯費0.5千元，假定第1期初和第4期末庫存量均為0，問該廠如何安排生產(chǎn)與庫存，可在滿足市場需求的前提下總成本最小。解: 以每個時期作為一個階段，該問題分為4個階段，k=1，2，3，4；決策變量xk表示第k階段生產(chǎn)的產(chǎn)品數(shù)；狀態(tài)變量sk

10、表示第k階段初的庫存量；以dk表示第k階段的需求，則狀態(tài)轉移方程：sk+1=sk+xkdk；k=4，3，2，1由于期初及期末庫存為0，所以s1=0，s5=0；允許決策集合dk（sk）的確定：當skdk時，xk可以為0，當skdk時，至少應生產(chǎn)dksk，故xk的下限為max（0，dksk）每期最大生產(chǎn)能力為6，xk最大不超過6，由于期末庫存為0，xk還應小于本期至4期需求之和減去本期的庫存量，所以xk的上限為min（，6），故有：dk（sk）=xk| max（0，dksk）xkmin（，6）階段指標函數(shù)rk（sk，xk）表示第k期的生產(chǎn)費用與存貯費用之和：最優(yōu)指標函數(shù)fk（sk）表示第k期庫存為

11、sk到第4期末的生產(chǎn)與存貯最低費用，動態(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,60,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

12、*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.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*34

13、25*表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.52123*45656789100123451110.588881616.515*16171830*1234561.55.56.57.58.59.510.501234561110.58888512.5*1614.515.516.517.515.540*12345267891012345610.58888512.5*1415161715表

14、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，即第1時期生產(chǎn)5個單位，第3時期生產(chǎn)6個單位，第2，4時期不生產(chǎn)，可使總費用最小，最小費用為20.5千元。例10 （庫存銷售問題）設某公司計劃在1至4月份從事某種商品經(jīng)營。已知倉庫最多可存儲600件這種商品，已知1月初存貨200件，根據(jù)預測知1至4月份各月的單位購貨成本及銷售價格如表6.13所示，每月只能銷售本月初的庫存，當月進貨供以

15、后各月銷售，問如何安排進貨量和銷售量，使該公司四個月獲得利潤最大（假設四月底庫存為零）。表6.13 單位購貨成本及銷售價格月份購貨成本c銷售價格p12344038404245423944解: 按月份劃分階段，k=1，2，3，4；狀態(tài)變量sk表示第k月初的庫存量，s1=200，s5=0；決策變量： xk表示第k月售出的貨物數(shù)量，yk表示第k月購進的貨物數(shù)量；狀態(tài)轉移方程：sk+1=sk+ykxk；允許決策集合：0xksk，0yk600（skxk）；階段指標函數(shù)為：pkxkckyk表示k月份的利潤，其中pk為第k月份的單位銷售價格，ck為第k月份的單位購貨成本；最優(yōu)指標函數(shù)fk（sk）表示第k月初

16、庫存為sk時從第k月至第4月末的最大利潤，則動態(tài)規(guī)劃基本方程為：k=4時，x4*=s4y4*=0k=3時，為求出使44s35x3+4y3最大的x3，y3，須求解線性規(guī)劃問題：只有兩個變量x3，y3，可用圖解法也可用單純形法求解，取得最優(yōu)解，x3*=0，y3*=600s3，f3（s3）=40s3+2400k=2時，類似地求得：x2*=s2，y2*=600，f2（s2）=42s2+3600k=1時，類似地求得：x1*=s1，y1*=600，f1（s1）=45s1+4800=13800逆向追蹤得各月最優(yōu)購貨量及銷售量：x1*=s1=200y1*=600；x2*=s2=s1+ y1*x1*=600y2

17、*=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件，不進貨，可獲得最大總利潤13800。例11某鞋店銷售一種雪地防潮鞋，以往的銷售經(jīng)歷表明，此種鞋的銷售季節(jié)是從10月1日至3月31日。下個銷售季節(jié)各月的需求預測值如表6.14所示。 表6.14 需求預測值 (單位：雙)月份101112123需求402030403020該鞋店的此種鞋完全從外部生產(chǎn)商進貨，進貨價每雙4美元。進貨批量的基本單位是箱，每箱1

18、0雙。由于存貯空間的限制，每次進貨不超過5箱。對應不同的訂貨批量，進價享受一定的數(shù)量折扣，具體數(shù)值如表6.15所示。表6.15 數(shù)量折扣數(shù)值表進貨批量1箱2箱3箱4箱5箱數(shù)量折扣4%5%10%20%25%假設需求是按一定速度均勻發(fā)生的，訂貨不需時間，但訂貨只能在月初辦理一次，每次訂貨的采購費（與采購數(shù)量無關）為10美元。月存貯費按每月月底鞋的存量計，每雙0.2美元。由于訂貨不需時間，所以銷售季節(jié)外的其他月份的存貯量為“0”。試確定最佳的進貨方案，以使總的銷售費用最小。解：階段：將銷售季節(jié)6個月中的每一個月作為一個階段，即；狀態(tài)變量：第階段的狀態(tài)變量代表第個月初鞋的存量；決策變量：決策變量代表第

19、個月的采購批量；狀態(tài)轉移律：（是第個月的需求量）；邊界條件：，；階段指標函數(shù)：代表第個月所發(fā)生的全部費用，即與采購數(shù)量無關的采購費、與采購數(shù)量成正比的購置費和存貯費.其中：；最優(yōu)指標函數(shù)：最優(yōu)指標函數(shù)具有如下遞推形式當時（3月）：表6.16 時計算結果s601020x620100f6（s6）86480當時（2月）：表6.17 時計算結果x5s501020304050020418816450164101721681424014220134136122301223086989008640505205050404當時（1月）：表6.18 時計算結果x4s40102030405003023044030

20、21028228228630、4028220250262264252202503021223024423021810212401641922122101961700164501441741781761520144601261401441320126當時（12月）：表6.19 時計算結果x3s30102030405004204224145041410388402392384503842035037037236233250332303023323403423103140302402843023102902922980284當時（11月）：表6.20 時計算結果x2s2010203040500500504474468504681046247245444645240446當時（10月）：表6