吉林大學(xué)遠(yuǎn)程教育運(yùn)籌學(xué)課件6

1、第六章第六章 動態(tài)規(guī)劃應(yīng)用舉例動態(tài)規(guī)劃應(yīng)用舉例第六章第六章 動態(tài)規(guī)劃應(yīng)用舉例動態(tài)規(guī)劃應(yīng)用舉例 2 生產(chǎn)與存貯問題生產(chǎn)與存貯問題 生產(chǎn)與存貯問題是實(shí)際生產(chǎn)中經(jīng)常遇到的問題，大量生產(chǎn)可以降低成本，但當(dāng)超過市場需求時，就造成積壓，增加庫存費(fèi)用，完全按市場需求安排生產(chǎn)雖然沒有庫存費(fèi)用，但由于開工不足或加班加點(diǎn)造成生產(chǎn)成本得的增加。因此，合理利用庫存調(diào)節(jié)產(chǎn)量，滿足需求是十分有意義的。所謂生產(chǎn)存貯問題，就是一個生產(chǎn)部門如何在已知生產(chǎn)成本、庫存費(fèi)用和各階段市場需求條件下，決定各階段產(chǎn)量，使計劃期內(nèi)的費(fèi)用總和為最小的問題。原材料采購部門也會遇到同樣問題，在那里需要確定各時期的采購量，使得計劃期內(nèi)總費(fèi)用最小。

2、這類問題通常是一個多階段決策問題，可以用動態(tài)規(guī)劃方法求解。在動態(tài)模型中，以時期為階段；取各時期初的庫存量為狀態(tài)變量；選各階段的產(chǎn)量（或采購量）為決策變量，在確定決策變量時一般要考慮需求量、生產(chǎn)能力、庫存限制等因素；指標(biāo)函數(shù)取生產(chǎn)（或采購）費(fèi)用。 下面舉例說明該問題的求解方法。例2 某工廠要制訂今后四個時期某產(chǎn)品的生產(chǎn)計劃，據(jù)估計今后四個時期內(nèi)，市場對于該產(chǎn)品的需求量如下表所示：時 期 k1 2 3 4需求量 dk2 3 2 4 假定該廠生產(chǎn)每批產(chǎn)品的固定費(fèi)用為2千元，若不生產(chǎn)則為0；每單位產(chǎn)品的成本為1千元；每件產(chǎn)品的每期保管費(fèi)為0.5千元；每個時期最大生產(chǎn)能力所允許的生產(chǎn)批量不超過5個單位；

3、最大庫存量為4個單位；假定開始時庫存量為1個單位，要求第四期末庫存為2個單位。試問該廠應(yīng)如何安排各個時期的產(chǎn)量，才能在滿足市場需求的條件下，使總費(fèi)用最小。 解：按四個時期將問題分成四個階段k=1，2，3，4；取k期初庫存量xk為狀態(tài)變量；k期內(nèi)產(chǎn)量uk為決策變量，則 xk+1=xk+uk- dk根據(jù)題意，第k期的費(fèi)用為 2+uk uk0 rk(xk, uk)=0.5xk+ 0 uk=0記fk（xk）為第k期至第4期末最小總費(fèi)用，則動態(tài)規(guī)劃基本方程為： fk（xk）= min rk(xk, uk) +fk+1（xk+1） uk f5（x5）=0 k=4,3,2,1k=4 注意：xk+1=xk+u

4、k-dk，x4=x5-u4+d4=2+4-u4，而u45，x4=1，2，3，4 于是由動態(tài)規(guī)劃基本方程fk（xk）= min rk(xk, uk) +fk+1（xk+1）有： f4（1）=0.51+2+5=7.5（注意：u4=6-x4） u4（1）=5 f4（2）=0.52+2+4=7 u4（2）=4 f4（3）=0.53+2+3=6.5 u4（3）=3 f4（4）=0.54+2+2=6 u4（2）=2 k=3 x3 =0,1,2,3,4 注意：x3+u3-d3=x41，而d3=2， u33-x3，又x44， u3min5,6-x3于是有： 0.50+2+3+f4（1） 5+7.5 f3（0）

5、=min 0.50+2+4+f4（2）=min 6+7 =12.5 0.50+2+5+f4（3） 7+6.5 u3（0）=3 0.51+2+2+f4（1） 4.5+7.5 f3（1）=min 0.51+2+3+f4（2）=min 5.5+7 =12 0.51+2+4+f4（3） 6.5+6.5 0.51+2+5+f4（4） 7.5+6 u3（1）=2 注意：u33-x3，u3min5,6-x3, x3+u3-2=x4 0.52+2+1+f4（1） 4+7.5 f3（2）=min 0.52+2+2+f4（2）=min 5+7 =11.5 0.52+2+3+f4（3） 6+6.5 0.52+2+4

6、+f4（4） 7+6 u3（2）=1 0.53+0+f4（1） 1.5+7.5 f3（3）=min 0.53+2+1+f4（2）=min 4.5+7 =9 0.53+2+2+f4（3） 5.5+6.5 0.53+2+3+f4（4） 6.5+6 u3（3）=0 0.54+0+f4（2） 2+7 f3（4）=min 0.54+2+1+f4（3）=min 5+6.5 =9 0.54+2+2+f4（4） 6+6 u3（4）=0 k=2 x2 =0,1,2,3,4 注意：0 x2+u2-d2=x34,而d2=3， 3-x2u2min5,7-x2 于是有： 0.50+2+3+f3（0） 5+12.5 f2

7、（0）=min 0.50+2+4+f3（1）=min 6+12 =17.5 0.50+2+5+f3（2） 7+11.5 u2（0）=3 0.51+2+2+f3（0） 4.5+12.5 f2（1）=min 0.51+2+3+f3（1）=min 5.5+12 =16.5 0.51+2+4+f3（2） 6.5+11.5 0.51+2+5+f3（3） 7.5+9 u2（1）=5 0.52+2+1+f3（0） 4+12.5 0.52+2+2+f3（1） 5+12 f2（2）=min 0.52+2+3+f3（2）=min 6+11.5 =16 0.52+2+4+f3（3） 7+9 0.52+2+5+f3（

8、4） 8+9 u2（2）=4注意：3-x2u2min5,7-x2 ,x2+u2-d2=x3 d2=3 0.53+0+f3（0） 1.5+12.5 0.53+2+1+f3（1） 4.5+12 f2（3）=min 0.53+2+2+f3（2）=min 5.5+11.5 =14 0.53+2+3+f3（3） 6.5+9 0.53+2+4+f3（4） 7.5+9 u2（3）=0 0.54+0+f3（1） 2+12 f2（4）=min 0.54+2+1+f3（2）=min 5+11.5 =14 0.54+2+2+f3（3） 6+9 0.54+2+3+f3（4） 7+9 u2（4）=0 k=1 x1 =1

9、 注意：0 x1+u1-d1=x24,而d1=2, 1u15 ， 于是有： 0.51+2+1+f2（0） 3.5+17.5 0.51+2+2+f2（1） 4.5+16.5 f1（1）=min 0.51+2+3+f2（2）=min 5.5+16 =20.5 0.51+2+4+f2（3） 6.5+14 0.51+2+5+f2（4） 7.5+14 u1（1）=4 至此，已算得本問題14期最小總費(fèi)用為20.5千元。再按計算的順序反推回去，可找出最優(yōu)生產(chǎn)計劃為：時 期 k1 2 3 4需求量dk2 3 2 4庫存量xk 1 3 0 1產(chǎn) 量uk 4 0 3 5 第六章第六章 動態(tài)規(guī)劃應(yīng)用舉例動態(tài)規(guī)劃應(yīng)用

10、舉例 2 生產(chǎn)與存貯問題（續(xù)）生產(chǎn)與存貯問題（續(xù)） 上講的例子中，決策變量和狀態(tài)變量允許取值都是離散的。對于決策變量允許取值連續(xù)的情況，有時計算更方便。 例3 某車間需按月生產(chǎn)一定數(shù)量的某種部件給總裝車間。由于生產(chǎn)條件的變化，該車間在各月份中生產(chǎn)這種部件的費(fèi)用不同，各月份的生產(chǎn)量于當(dāng)月月底前全部要存入倉庫以備后用。已知總裝車間在各月初的需求量以及加工車間生產(chǎn)該部件所需費(fèi)用如下表：月 份 k 0 1 2 3 4需 求 量 dk 0 8 5 3 2單位成本ck 11 18 13 17 20 設(shè)倉庫容量限制H=9，開始庫存量為2，要求4月末庫存量也為2，試制訂一個各月的生產(chǎn)計劃，使得既滿足需要和庫容

11、量限制，又使得生產(chǎn)該部件的總成本最低。 解：按月份劃分階段 k=0，1，2，3，4 ；取階段初庫存量為狀態(tài)變量xk；決策變量uk為k階段內(nèi)的生產(chǎn)量。則狀態(tài)轉(zhuǎn)移方程為： xk+1=xk+uk-dk， k=0，1，2，3，4由于 dk+1xk+1=xk+uk-dkH所以 max0，dk+1+dk-xkukH+dk-xk記fk（xk）為第k階段至第4階段末最小總費(fèi)用，則動態(tài)規(guī)劃基本方程為：kDuduxfucminxfkk1kkkkkKk f5（x5）=0 k=4,3,2,1,0 k=4 因?yàn)橐?月末庫存量為2，即x4+u4-d4=2，而d4=2，所以， u4=4-x4 ， f4（x4）=c4u4=

12、20（4-x4）=80-20 x4, k=3 注意：4-x4=u40，x44，又x4=x3+u3-d3d4，而d3=3， 5-x3u37-x3 3ux2080u17minxfucminxf33374433733333333xux5xux5333337x17119x20140 x73x20140u3min333xux5u3=7-x3 k=2 注意：u3=7-x30，x37，又x3=x2+u2-d2d3，而d2=5， 8-x2u212-x2 5ux17119u13minxfucminxf2221233221222222222xux8xux822222121315617204124172044min

13、2228xxxxuxux u2=12-x2k=1 注意： d2x2=x1+u1-d1H=9，而d1=8， 13-x1u117-x1 81315618minmin11117221117111111111313uxuxfucxfxuxxux11111171832513260135132605min11113xxxxuxux u1=13-x1 k=0 注意：d1x1=x0+u0-d0H=9，而d0=0,x0=26u07 0000711007001832511minmin0066duxuxfucxfuu240289u7min070u6 u0=7 至此，已算得本問題的最小總費(fèi)用為240，再按計算順序反推

14、回去，可得最優(yōu)生產(chǎn)計劃如下：月 份 k 0 1 2 3 4需 求 量 dk 0 8 5 3 2庫 存 量 xk 2 9 5 7 4 產(chǎn) 量 uk 7 4 7 0 0u3=7-x3 u4=4-x4 例4 （不確定性采購問題）某部門欲一次采購某種原料100 公斤，由于生產(chǎn)需要，必須在6周內(nèi)采購?fù)戤?。原料在未來?周內(nèi)可能有幾種價格，而每種價格的概率預(yù)先是已知的，設(shè)在前三周和后三周的價格及其相應(yīng)的概率如下表所示：第1周第3周第4周第6周單價（百元/公斤）概率單價（百元/公斤）概率4680.10.50.45670.30.30.4 試確定采購方案，使期望費(fèi)用最小。 解：以周為階段 k=1，2，3，4，5

15、，6；取第k周的價格為狀態(tài)變量xk；記決策變量：uk= 1，買 0，不買 記 fk（xk）為第k周至第6周在價格xk下的最小期望費(fèi)用。 k=6 x6=5，6，7 f6（5）=500，u6（5）=1； f6（6）=600， u6（6）=1； f6（7）=700，u6（7）=1。 K=5 x5=5，6，7 f5（5）=min500，0.3f6（5）+0.3f6（6）+0.4f6（7） =min500，0.3500+0.3600+0.4700 =min500，610=500， u5（5）=1；f5（6）=min600，0.3f6（5）+0.3f6（6）+0.4f6（7） =min600，610=60

16、0， u5（6）=1；f5（7）=min700，0.3f6（5）+0.3f6（6）+0.4f6（7） =min700，610=610， u5（7）=0；K=4 x4=5，6，7f4（5）=min500，0.3f5（5）+0.3f5（6）+0.4f5（7） =min500，0.3500+0.3600+0.4610 =min500，574=500， u4（5）=1；f4（6）=min600，0.3f5（5）+0.3f5（6）+0.4f5（7） =min600，574=574， u4（6）=0；f4（7）=min700，0.3f5（5）+0.3f5（6）+0.4f5（7） =min700，574=5

17、74， u4（7）=0；K=3 x3=4，6，8f3（4）=min400，0.3f4（5）+0.3f4（6）+0.4f4（7） =min400，0.3500+0.3574+0.4574 =min400，551.8=400， u3（4）=1；f3（6）=min600，0.3f4（5）+0.3f4（6）+0.4f4（7） =min600，551.8=551.8， u3（6）=0；f3（8）=min800，0.3f4（5）+0.3f4（6）+0.4f4（7） =min800，551.8=551.8， u3（8）=0；K=2 x2=4，6，8f2（4）=min400，0.1f3（4）+0.5f3（6）

18、+0.4f3（8） =min400，0.1400+0.5551.81+0.4551.8 =min400，536.62=400， u2（4）=1；f2（6）=min600， 0.1f3（4）+0.5f3（6）+0.4f3（8） =min600，536.62=536.62， u2（6）=0；f2（8）=min800，0.1f3（4）+0.5f3（6）+0.4f3（8） =min800，536.62=536.62， u2（8）=0； K=1 x1=4，6，8f1（4）=min400，0.1f2（4）+0.5f2（6）+0.4f2（8） =min400，0.1400+0.5536.62+0.4536.62 =min400，522.958=400， u1（4）=1；f1（6）=min600，0.1f2（4）+0.5f2（6）+0.4f2（8） =min600，522.958=522.958 u1（6）=0；f1（8）=min800，0.1f2（4）+0.5f2（6）+0.4f2（8） =min800，522.958=522.958， u1（8）=0； 綜上所述，我們得到最優(yōu)采購方案： 1由u1（4）=1；u1（6）=0；u1（8）=0