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

1、例1求解下列整數(shù)規(guī)劃的最優(yōu)解:max Z 4x1 5x2 6x33xi 4x2 5x3 < 10s.txj > 0 j 1,2,3 ,xj為整數(shù).解（1）建立動(dòng)態(tài)規(guī)劃模型：階段變量：將給每一個(gè)變量 xj賦值看成一個(gè)階段，劃分為3個(gè)階段，且階段變量 k=1,2,3.設(shè)狀態(tài)變量Sk表示從第k階段到第3階段約束右端最大值，則Sj 10.設(shè)決策變量xk表示第k階段賦給變量xk的值（k 1,2,3）.狀態(tài)轉(zhuǎn)移方程：s2 & 3x1, s3 s2 4x2.階段指標(biāo)：3（?1）4x1，U2(S2,x2) 5x2,U3(s3, x3)6x3.基本方程;fk(Sk)max UkSk, xk

2、fk 1s k0< x3< _k 3,2,1aksk 1f4(S4)0.其中 a13,a24,a3 5.(1)用逆序法求解：當(dāng)k 3時(shí)，f3 S3max 6x3 f4 s4max 6x3s 3S30< x3 0<x3< 55而S30,1,2,3,4,5,6,7,8,9,10 . x表示不超過x的最大整數(shù)。因此，當(dāng)S3 0,1,2,3,4時(shí),x30 ;當(dāng) S35,6,7,8,9 時(shí)，x3可取 0 或 1 ；當(dāng) S310時(shí)，x3可取0,1,2,由此確定f3 S3丁飛6x3 f4(S4)f3(s3)*x3012000010002000300040005066160661

3、現(xiàn)將有關(guān)數(shù)據(jù)列入表 4.1中表4.1中.706618066190661100612122當(dāng)k 2時(shí)，有f2s2max5x2f3, max5x2f3s24x2s 2s 20=x2 =0<x2< 一而S2又20,1,2,3,4,5,6,7,8,9,10 。所以當(dāng) s2 0,1,2,3 時(shí)，x2 0 ;當(dāng) s 4,5,6,7 時(shí),表4.2f1 S|max 4x1 f2 s2s10玄、1玄.max 4x1 f2 5 3x1 , s10玄、1玄50或1 ;當(dāng)S2 8,9,10時(shí)x20,1,2。由此確定f2 S2 ?，F(xiàn)將有關(guān)數(shù)據(jù)列入表4.2中.而'10,故x1只能取0,1,2,3，由此

4、確定f1 4。現(xiàn)將有關(guān)數(shù)據(jù)列入表4.3中。表 4.34x1 f2 § 3x1f Si*XS2、0123100+124+68+512+01324按 計(jì) 算 順 序 反 推， 由 表 4.3 可 知x12時(shí),f 1(s1)取得最大值13.又由s24查表4.2得*21,s3 0,再由表4.1查得x3 0.因此，最優(yōu)解為X 3 2,x3 1, x3 0,最優(yōu)解 maxZ 13.例5用動(dòng)態(tài)規(guī)劃方法解下列非線性規(guī)劃問題max z X1 x2 x323 s2XiXi解： 解決這一類靜態(tài)規(guī)劃問題, 轉(zhuǎn)化為多階段決策過程。X2X3c0 i 1,2,3需要人為地賦予時(shí)間概念，從而將該問題按問題的變量個(gè)數(shù)

5、劃分階段，把它看作一個(gè)三階段決策問題，k=1, 2, 3設(shè)狀態(tài)變量為s1 , s2,取問題中的變量Xi, 狀態(tài)轉(zhuǎn)移方程為： 允許決策集合為： 各階段指標(biāo)函數(shù)為：,s3, s4 并記 s10CX2, X3為決策變量S3=X3X3=S3S3+X2=S20<X2<S2V1（X1）=X1V2 （X2）=X2S2+X1=S1 <C0<X1< s12V3（X3）=X3 ,各指標(biāo)函數(shù)以乘積方式結(jié)合，最優(yōu)指標(biāo)函數(shù) fk （sk）表示從第k階段初始狀態(tài)sk出發(fā)到第 3階段所得到的最大值，則動(dòng)態(tài)規(guī)劃基本方程為：fk（sk）max、Vk（Xk） fk 1（sk 1）Xk Dk（sk）f

6、4（s4） 1用逆序解法由后向前依次求解：k=3 時(shí)，k 3,2,1f3（S3）max（x3） x3 s3S3*X3 =s3k=2 時(shí),f2（S2）max 2（X2） f3（s3）x2 D2（s2）/ 2max （x20 X2 s2S3）2,max x2 （s20 X2 s2X2 ）令 h2 （s2, X2）=X22 （s2X2）用經(jīng)典解析法求極值點(diǎn)：dh2dx22x2s23x2解得:X223S2X2=0 （舍）d2h2dx22s26X2d2h2dx2X223s22s2所以X223 s2是極大值點(diǎn)。f2（s2）/22 z（-s2）（s2 32 、4一 s2）一327*X2k=1 時(shí),fi(Si

7、)maX v1(x1) f2(S2)max (xi國(guó) Di (si )0 xi s.s2) maxx1270 xi 54 /、3 ,27 (siXi) 43,Xi) Xi 27 (Si Xi)dhi4 /、3- TZ (si xi ) dx12712,、2-、Xi；27(S1 Xi) ( 1)解得:Xixi=si (舍)d2hi(G27Xi)2(1) (Si27Xi)22427Xi(sXi)24(Si27Xi)(2xiSi)d2%dX2Xi92SI027一. 1所以Xi -Si是極大值點(diǎn)。4一、i 4 / 1 、3 fi(si ) si -； (si si )4274由于Si未知，所以對(duì)Si再

8、求極值,一、，14、max fi (Si) max( Si )0 Si c0 Si c 64i 4-Si64*Xi顯然Si=c時(shí)，fi (si)取得最大值fi(Si)i c 64反向追蹤得各階段最優(yōu)決策及最優(yōu)值:si=c*Xii4Sifi(Si)ic64s2si*XiS3S2*X23c4ic4*X2*X3所以最優(yōu)解為:*Xi-C,X2423S2f2(S2)4 3S2 27i 3一 cI61s3- c4f3(S3)S3-c, X3-c,z24i一 c64例6用動(dòng)態(tài)規(guī)劃方法解下列非線性規(guī)劃問題maX z x1 x2 x3xiX2X36Xj0j1,2,3解：按變量個(gè)數(shù)將原問題分為三個(gè)階段，階段變量k

9、=i, 2, 3;選才? Xk為決策變量；狀態(tài)變量sk表示第k階段至第3階段決策變量之和；取小區(qū)間長(zhǎng)度A =1,小區(qū)間數(shù)目m=6/1=6,狀態(tài)變量sk的取值點(diǎn)為：Sk0,1,2,3,4,5,6 k 2s16狀態(tài)轉(zhuǎn)移方程：Sk+1=Sk Xk；允許決策集合：Dk （ Sk） = Xk| 0< Xk< Skk=1 , 2, 3Xk, Sk均在分割點(diǎn)上取值；階段指標(biāo)函數(shù)分別為：g1（X1）=X12g2（X2）=X2g3（X3）=X33 ,最優(yōu)指標(biāo)函數(shù)fk （Sk）表示從第k階段狀態(tài)Sk出發(fā)到第3階段所得到的最大值， 動(dòng)態(tài)規(guī)劃的基本方程為：fk（Sk）maXgk（Xk） fk1（Sk1）k

10、 3,2,10 Xk Skf4（S4）1k=3 時(shí)，f3（S3） maX（X3） S3X3 8S3及X3取值點(diǎn)較多，計(jì)算結(jié)果以表格形式給出，見表 6.1-6.3所示。表6.1計(jì)算結(jié)果S3X3f3(S3)*X301234560000111128823272734646445125125562162166表6.2計(jì)算結(jié)果S2'、X2 f3(S2 X2)f2(S2)*X201234560000101 X 000,1201 X 12X011301 X 82X13X081401 X 272X83X14X0271501 X 642X273X84X 15X 0641601 X 1252X643X27

11、4X85X 16X 01282表6.3計(jì)算結(jié)果52，、x1 f2(S1 x1)f1(S1)*x10123456601 X 644X 279X816X 125 X 036 x 01082由表 6.3 知，xi =2, si=6,則 S2= si xi =6 2=4,查表 6.2 得：x2 =1,則 s3= s2 x2 =4 1=3,查表 6.1 得：x3 =3,所以最優(yōu)解為：xi =2,x2 =1, x3 =3, fi(si)=108。上面討論的問題僅有一個(gè)約束條件。對(duì)具有多個(gè)約束條件的問題，同樣可以 用動(dòng)態(tài)規(guī)劃方法求解，但這時(shí)是一個(gè)多維動(dòng)態(tài)規(guī)劃問題，解法上比較繁瑣一些。例7某公司打算在3個(gè)不同

12、的地區(qū)設(shè)置4個(gè)銷售點(diǎn)，根據(jù)市場(chǎng)部門估計(jì)，在不同地區(qū)設(shè)置不同數(shù)量的銷售點(diǎn)每月可得到的利潤(rùn)如表6.4所示。試問在各地區(qū)如何設(shè)置銷售點(diǎn)可使每月總利潤(rùn)最大。表6.4利潤(rùn)值地區(qū)銷售點(diǎn)01234101625303220121721223010141617解：如前所述，建立動(dòng)態(tài)規(guī)劃數(shù)學(xué)模型：將問題分為3個(gè)階段，k=1, 2, 3;決策變量xk表示分配給第k個(gè)地區(qū)的銷售點(diǎn)數(shù)；狀態(tài)變量為sk表示分配給第k個(gè)至第3個(gè)地區(qū)的銷售點(diǎn)總數(shù)；狀態(tài)轉(zhuǎn)移方程：Sk+1=Skxk,其中S1=4；允許決策集合：Dk (Sk) = xk| 0< xk<Sk階段指標(biāo)函數(shù)：gk (xk)表示xk個(gè)銷售點(diǎn)分配給第k個(gè)地區(qū)所獲

13、得的利潤(rùn)；最優(yōu)指標(biāo)函數(shù)fk (Sk)表示將數(shù)量為Sk的銷售點(diǎn)分配給第k個(gè)至第3個(gè)地區(qū) 所得到的最大利潤(rùn)，動(dòng)態(tài)規(guī)劃基本方程為：fk(Sk) maxgk(xk) fk 1 (Sk xjk 3,2,10 xk Skf4(S4)0數(shù)值計(jì)算如表所示表6.5 k=3時(shí)計(jì)算結(jié)果s3g3（X3）f3（S3）*X3012340000110101214142316163417174表6.6 k=2時(shí)計(jì)算結(jié)果g2(X2)+f3(s2-X2)f2（S2）*X201234000010+1012+012120+1412+1017+022130+1612+1417+1021+027240+1712+1617+1421+10

14、22+0312,3表6.7 k=1時(shí)計(jì)算結(jié)果s1 、g1(x1)+f2(s1-X1)f1(s1)*X10123440+3116+2725+2230+1232+0472所以最優(yōu)解為：xi =2, X2=1, X3 =1, fi（4）=47,即在第1個(gè)地區(qū)設(shè)置2個(gè)銷 售點(diǎn)，第2個(gè)地區(qū)設(shè)置1個(gè)銷售點(diǎn)，第3個(gè)地區(qū)設(shè)置1個(gè)銷售點(diǎn)，每月可獲利潤(rùn) 47。例9 （生產(chǎn)一庫(kù)存問題）某工廠要對(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,每單位產(chǎn)品成本為1千元，每個(gè)時(shí)期最大生產(chǎn)能力不超 過6個(gè)單位，

15、每期期末未出售產(chǎn)品，每單位需付存貯費(fèi) 0.5千元，假定第1期初 和第4期末庫(kù)存量均為0,問該廠如何安排生產(chǎn)與庫(kù)存，可在滿足市場(chǎng)需求的前 提下總成本最小。解：以每個(gè)時(shí)期作為一個(gè)階段，該問題分為 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+i=sk+xkdk； k=4, 3, 2, 1由于期初及期末庫(kù)存為0,所以S1=0, S5=0；允許決策集合Dk (sk)的確定：當(dāng)Sk>dk時(shí)，xk可以為0,當(dāng)Sk<dk時(shí)，至少 應(yīng)生產(chǎn)dk-sk,故xk的下限為max (0, dk-s

16、k)每期最大生產(chǎn)能力為 6, xk最大 不超過6,由于期末庫(kù)存為0, xk還應(yīng)小于本期至4期需求之和減去本期的庫(kù)存44量， d j sk,所以xk的上限為min ( d j sk, 6),故有：j kj k4Dk (sk) = xk| max (0, dksk) < x<< min ( d j s” 6) j k階段指標(biāo)函數(shù)rk (sk, xk)表示第k期的生產(chǎn)費(fèi)用與存貯費(fèi)用之和：k(sk,xk)0.5skxk0.5skxk 0xk123,4,5,6最優(yōu)指標(biāo)函數(shù)fk (sk)表示第k期庫(kù)存為sk到第4期末的生產(chǎn)與存貯最低費(fèi) 用，動(dòng)態(tài)規(guī)劃基本方程為：fk(sk)min、Tk(s

17、k,xk) fk 1(sk 1) k 4,3,2,1xk Dk(sk)fsM 0先求出各狀態(tài)允許狀態(tài)集合及允許決策集合，如表6.8所示。表6.8狀態(tài)允許狀態(tài)集合及允許決策集合si0Di(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,6123,4,50,123,40,1230,1,20,10s401234D4(s4)4310由基本方程計(jì)算各階段策略，結(jié)果如下表所示。表6.9 k=4時(shí)計(jì)算結(jié)果s4x4四外)0.5s43 x4x40.5s4 x

18、400s5f5(s5)f4(s4)0*4700*71*36.500_ *6.52_ *2600_ *63.*15.500 *5.540200_ *2表6.10 k =3時(shí)計(jì)算結(jié)果S3X30.5S3x3 0r3(s3,X3)0ncn3 x3 0.5s3 x3 0S4= S3+ X3 2f4（S4）f3（S3）02345_ *6567890123476.565.5212 12.5 13 13.5.*1111234*54.55.56.57.58.50123476.565.5211.5 1212.513*10.52_ *01234156780123476.565.52_ *811.51212.5103

19、*01231.55.56.57.512346.5 65.5 2*811.5129.54*01226723465.528*11.595*012.56.5345.52*88.56*0342*5表6.11k =2時(shí)計(jì)算結(jié)果S2X22（S2,X2）0.5s20.5s2X2X200S3= S2+ X2 3f3（S3）f2（S2）3X2360111747110.517.5058281669381725.501116.536.5110.5171*47.528*15.558.53816.569.54817.5150111626110.516.52_ *3728154838165948176105818_ *0

20、1.5011_ _ *12.515.5110.51626.52814.5337.53815.548.54816.559.55817.5610.56515.5*02110.5*12.516281427381543848164958175106515表6.12 k =1時(shí)計(jì)算結(jié)果S1X10.5sX10r1(s,X1)CCLC3 x1 0.5s1 x1 0S2= X1 -2f2（S2）f1（S1）0234_ *5656789012341615.51512.512.521 21.522 _ _ *20.521.5逆向追蹤可得：xi=5, S2=3, X2 =0, S3=0, X3 =6, S4=4,

21、X4=0,即第 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ù)存一銷售問題）設(shè)某公司計(jì)劃在1至4月份從事某種商品經(jīng)營(yíng)。已知倉(cāng)庫(kù)最多可存儲(chǔ) 600 件這種商品，已知1月初存貨200件，根據(jù)預(yù)測(cè)知1至4月份各月的單位購(gòu)貨成 本及銷售價(jià)格如表6.13所示，每月只能銷售本月初的庫(kù)存，當(dāng)月進(jìn)貨供以后各 月銷售，問如何安排進(jìn)貨量和銷售量，使該公司四個(gè)月獲得利潤(rùn)最大（假設(shè)四月 底庫(kù)存為零）。表6.13單位購(gòu)貨成本及銷售價(jià)格月份購(gòu)貨成本C銷售價(jià)格P14045238423403944244解：按月份劃分階段，k=1, 2, 3, 4;狀

22、態(tài)變量sk表示第k月初的庫(kù)存量，S1=200, s5=0;決策變量：xk表示第k月售出的貨物數(shù)量，yk表示第k月購(gòu)進(jìn)的貨物數(shù)量;狀態(tài)轉(zhuǎn)移方程：Sk+1=Sk+yk Xk；允許決策集合：0&xk&sk, 0<yk<600- (sk xk);階段指標(biāo)函數(shù)為：pkxk- ckyk表示k月份的利潤(rùn)，其中pk為第k月份的單位銷售價(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ī)劃基本方程為：fk(sk)max 0 xk sk pkxkckykfk 1(sk 1)k 4,3,2,10 yk 600

23、( sk xk )f5(s5) 0k=4 時(shí)，f4 (s4 )max(44x4 42y4) 44s40 x4 s40 y4 600 (s4 x4 )x4 =s4 y4 =0k=3 時(shí)，f3(s3)max0 x3 s30 y3 600 (s3max0 x3 s30 y3 600 (s3max0 x3 s30 y3 600 (s339x3x3 )39x3x3 )(44s3x3 )40y3 f4(s4 )40y3 44(s3 y3 x3 )5x3 4y3)為求出使44s3 5x3+4y3最大的x3, y3,須求解線性規(guī)劃問題: max z 44s3 5x3 4y3x3 s3x3 y3600 s3x3

24、 , y30只有兩個(gè)變量x3， y3， 可用圖解法也可用單純形法求解，取得最優(yōu)解，x3* =0，* _ _ y3 =600 s3， f3( s3) =40s3+2400k=2 時(shí)，f2(s2 )max42x2 38y2 f3(s3)0 x2 s20 y2 600 (s2 x2 )max 42x2 38y2 40(s2 y2 x2 ) 24000 x2 s2 0 y2 600 (s2 x2 )max (40s2 2x2 2y2 2400)0 x2 s20 y2 600 (s2 x2 )類似地求得：x2* =s2， y2*=600， f2( s2) =42s2+3600k=1 時(shí)，fi(Si)ma

25、x45xi 40y1 f2(S2)0 X1 S| 0 yi 600 (Si X1)max45x1 40y1 42(s1 y1 x1) 36000 x1 S1 0 y1 600 (Si x1)max(42 s 3x1 2y1 3600)0 x1 S1 0 y1 600 (R 為)x r r 小 r t . r r、. ztt*_ . .類似地求得：x1=S1, y1 =600, f1(S1)=45S1+4800=13800逆向追蹤得各月最優(yōu)購(gòu)貨量及銷售量：* *x1 =S1=200y1 =600;x2*=S2=S1+ y1* x1*=600y2*=600;* *、x3 =0y3 =600S3=6

26、00 ( S2+ y2 x2 ) =0x4 =S4=(S3+ y3 x3 ) =600y4 =0即1月份銷售200件，進(jìn)貨600件，2月份銷售600件，進(jìn)貨600件，3月份銷售量及進(jìn)貨量均為0,4月份銷售600件，不進(jìn)貨，可獲得最大總利潤(rùn)138000例11某鞋店銷售一種雪地防潮鞋，以往的銷售經(jīng)歷表明，此種鞋的銷售季節(jié)是從10月1日至3月31日。下個(gè)銷售季節(jié)各月的需求預(yù)測(cè)值如表 6.14所示表6.14需求預(yù)測(cè)值（單位：雙）月份101112123需求402030403020該鞋店的此種鞋完全從外部生產(chǎn)商進(jìn)貨， 進(jìn)貨價(jià)每雙4美元。進(jìn)貨批量的基本單位是箱，每箱10雙。由于存貯空間的限制，每次進(jìn)貨不超過

27、 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í)間，但訂貨只能在月初辦理 一次，每次訂貨的采購(gòu)費(fèi)（與采購(gòu)數(shù)量無關(guān)）為 10美元。月存貯費(fèi)按每月月底 鞋的存量計(jì)，每雙0.2美元。由于訂貨不需時(shí)間，所以銷售季節(jié)外的其他月份的 存貯量為“ 0”。試確定最佳的進(jìn)貨方案，以使總的銷售費(fèi)用最小。解：階段：將銷售季節(jié)6個(gè)月中的每一個(gè)月作為一個(gè)階段，即k 1,2, ,6； 狀態(tài)變量：第k階段的狀態(tài)變量Sk代表第k個(gè)月初鞋的存量； 決策變量：決策變量xk代

28、表第k個(gè)月的采購(gòu)批量；狀態(tài)轉(zhuǎn)移律：Sk 1 Sk xk dk （dk是第k個(gè)月的需求量）；邊界條件：S S7。，f7（S7）0;階段指標(biāo)函數(shù)：rk（Sk，Xk）代表第k個(gè)月所發(fā)生的全部費(fèi)用，即與采購(gòu)數(shù)量無關(guān)的采購(gòu)費(fèi)C與采購(gòu)數(shù)量成正比的購(gòu)置費(fèi) Gk和存貯費(fèi)Zk.其中：0,Xk 0Ck _ 八；Gk px xZk 0.2（Sk Xk dk） 10, xk 0最優(yōu)指標(biāo)函數(shù)：最優(yōu)指標(biāo)函數(shù)具有如下遞推形式fk（Sk） minCk Gk Zk fki（S） xkminCk Gk 0.2（& xk dk） f-（Sk xk dk） xk當(dāng)k 6時(shí)（3月）：表6.16 k 6時(shí)計(jì)算結(jié)果S601020x

29、620100f6 (S3)86480當(dāng)k 5時(shí)（2月）:表6.17 k 5時(shí)計(jì)算結(jié)果、x501020304050x5f5(S5)020418816450164101721681424014220134136122301223086989008640505205050404當(dāng)k 4時(shí)（1月）:表6.18 k 4時(shí)計(jì)算結(jié)果Xx4S401020304050x4fQ)0302304403021028228228630、4028220250262264252202503021223024423021810212401641922122101961700164501441741781761520144601261401441320126當(dāng)k 3時(shí)（12月）:表6.19 k 3時(shí)計(jì)算結(jié)果Xy3S301020304050X3f3(S3)04204224145041410388402392384503842035037037236233250332303023323403423103140302402843023102902922980284當(dāng)k 2時(shí)（11月）:表6.20 k 2時(shí)計(jì)算結(jié)果X