運籌學動態(tài)規(guī)劃2

1、第十章第十章 動態(tài)規(guī)劃應用舉例動態(tài)規(guī)劃應用舉例運籌學運籌學第九章第九章 動態(tài)規(guī)劃應用舉例動態(tài)規(guī)劃應用舉例生產(chǎn)與存儲問題生產(chǎn)與存儲問題本章內(nèi)容本章內(nèi)容資源分配問題資源分配問題背包問題背包問題復合系統(tǒng)工作可靠性問題復合系統(tǒng)工作可靠性問題排序問題排序問題設(shè)備更新問題設(shè)備更新問題貨郎擔問題貨郎擔問題第一節(jié)第一節(jié) 資源分配問題資源分配問題 設(shè)總投資額為設(shè)總投資額為a萬元，擬投資于萬元，擬投資于n個項目上，已知個項目上，已知對第對第i個項目投資個項目投資xi萬元，收益函數(shù)為萬元，收益函數(shù)為gi(xi)，問應如，問應如何分配資金才可以使總收益最大？何分配資金才可以使總收益最大？這是一個與時間這是一個與時間無

2、明顯關(guān)系的靜態(tài)最優(yōu)化問題，可先列出其靜態(tài)模無明顯關(guān)系的靜態(tài)最優(yōu)化問題，可先列出其靜態(tài)模型為：型為： nixaxxgZiniiniii.2.1 0)(max11據(jù)此，有下式：據(jù)此，有下式： （一）投資分配問題（一）投資分配問題例例1 1 某公司有資金某公司有資金1010萬元，若投資于項目（萬元，若投資于項目（i=1,2,3i=1,2,3）的投資額為的投資額為x xi i時，其收益分別為時，其收益分別為g g1 1(x(x1 1)=4x)=4x1 1, , g g2 2(x(x2 2)=9x)=9x2 2, g, g3 3(x(x3 3)=2x)=2x3 3, ,問應如何分配投資額才能使問應如何分

3、配投資額才能使總收益最大？總收益最大？123100(1,2,3)ixxxxi123max492Zxxx建立模型：建立模型：例例2 有資金有資金4萬元，投資萬元，投資A、B、C三個項目，每三個項目，每個項目的投資效益與投入該項目的資金有關(guān)。三個項目的投資效益與投入該項目的資金有關(guān)。三個項目個項目A、B、C的投資效益（萬噸）和投入資金的投資效益（萬噸）和投入資金（萬元）關(guān)系見下表：（萬元）關(guān)系見下表： 求對三個項目的最優(yōu)投資分配，使總投資效求對三個項目的最優(yōu)投資分配，使總投資效益最大。益最大。1 1、階段、階段k k：每投資一個項目作為一個階段；：每投資一個項目作為一個階段；2 2、狀態(tài)變量、狀態(tài)

4、變量x xk k：投資第：投資第k k個項目前的資金數(shù)；個項目前的資金數(shù)；3 3、決策變量、決策變量d dk k：第：第k k個項目的投資；個項目的投資；4 4、決策允許集合：、決策允許集合：00d dk kx xk k5 5、狀態(tài)轉(zhuǎn)移方程：、狀態(tài)轉(zhuǎn)移方程：x xk k+1+1= =x xk k- -d dk k6 6、階段指標：、階段指標：v vk k( (x xk k , ,d dk k) )見表中所示；見表中所示；7 7、遞推方程：、遞推方程：f fk k( (x xk k)=max)=maxv vk k( (x xk k , ,d dk k)+)+f fk k+1+1( (x xk k

5、+1+1)8 8、終端條件：、終端條件：f f4 4( (x x4 4)=0)=0分析：分析：k=4k=4，f f4 4(x(x4 4)=0)=0 x3 D3(x3) x4 v3(x3,d3) v3(x3,d3)+f4(x4) f3(x3) d3* 0 0 0 0 0+0=0 0 0 0 1 0 0+0=0 1 1 0 11 11+0=11* 11 1 0 2 0 0+0=0 1 1 11 11+0=11 2 2 0 30 30+0=30* 30 2 0 3 0 0+0=0 1 2 11 11+0=11 2 1 30 30+0=30 3 3 0 45 45+0=45* 45 3 0 4 0 0

6、+0=0 1 3 11 11+0=11 2 2 30 30+0=30 3 1 45 45+0=45 4 4 0 58 58+0=58* 58 4 k=3k=3，0d0d3 3xx3 3，x x4 4=x=x3 3-d-d3 3k=2k=2，0d0d2 2xx2 2，x x3 3=x=x2 2-d-d2 2k=1k=1，0d0d1 1xx1 1，x x2 2=x=x1 1-d-d1 1最優(yōu)解為最優(yōu)解為x1=4, d1*=1, x2=x1-d1=3, d2*=0, x3=x2-d2*=3, d3=3, x4=x3-d3=0，即項目即項目A投資投資1萬元，項目萬元，項目B投資投資0萬元，項目萬元，項

7、目C投資投資3萬元，最大效益為萬元，最大效益為60萬噸。萬噸。 作業(yè)作業(yè) 某公司有資金某公司有資金8萬元，投資萬元，投資A、B、C三個項三個項目，單位投資為目，單位投資為2萬元。每個項目的投資效益率與萬元。每個項目的投資效益率與投入項目的資金有關(guān)。三個項目投入項目的資金有關(guān)。三個項目A、B、C的投資的投資效益（萬噸）和投入資金（萬元）關(guān)系見下表：效益（萬噸）和投入資金（萬元）關(guān)系見下表： 項目投入資金 A B C 2 萬元 8 萬噸 9 萬噸 10 萬噸 4 萬元 15 萬噸 20 萬噸 28 萬噸 6 萬元 30 萬噸 35 萬噸 35 萬噸 8 萬元 38 萬噸 40 萬噸 43 萬噸 求

8、對三個項目的最優(yōu)投資分配，使總投資效求對三個項目的最優(yōu)投資分配，使總投資效益最大。益最大。（二）機器負荷分配問題（二）機器負荷分配問題 例例3 3 某種機器可以在高、低兩種負荷下運行。在高某種機器可以在高、低兩種負荷下運行。在高負荷條件下運行時，機器完好率為負荷條件下運行時，機器完好率為0.70.7，即如果年初，即如果年初有有u u臺完好機器投入運行，則年末時完好機器的數(shù)量臺完好機器投入運行，則年末時完好機器的數(shù)量為為0.7u0.7u臺，產(chǎn)量臺，產(chǎn)量8 8噸噸/ /臺；在低負荷下運行時，機器臺；在低負荷下運行時，機器完好率為完好率為0.90.9，產(chǎn)量，產(chǎn)量5 5噸噸/ /臺。設(shè)開始時有臺。設(shè)開

9、始時有10001000臺完臺完好機器，要制訂五年計劃，每年年初將完好的機器好機器，要制訂五年計劃，每年年初將完好的機器一部分分配到高負荷運行，剩下的機器分配到低負一部分分配到高負荷運行，剩下的機器分配到低負荷運行，如何分配生產(chǎn)使五年的總產(chǎn)量為最高。荷運行，如何分配生產(chǎn)使五年的總產(chǎn)量為最高。 第第1年年s1s2s3x1x2x3第第2年年第第3年年第第4年年第第5年年s4s5s6x4x5指標值指標值(產(chǎn)量產(chǎn)量)V1(s1,x1)指標值指標值(產(chǎn)量產(chǎn)量)V2(s2,x2)指標值指標值(產(chǎn)量產(chǎn)量)V5(s5,x5)指標值指標值(產(chǎn)量產(chǎn)量)V4(s4,x4)指標值指標值(產(chǎn)量產(chǎn)量)V3(s3,x3)動態(tài)

10、規(guī)劃模型構(gòu)造動態(tài)規(guī)劃模型構(gòu)造階段階段k： 運行年份（運行年份（k=1,2,3,4,5）；）；狀 態(tài) 變 量狀 態(tài) 變 量 sk： 第第 k 年 初 完 好 的 機 器 數(shù)年 初 完 好 的 機 器 數(shù)（k=1,2,3,4,5）；）；決策變量決策變量xk： 第第k年投入高負荷運行的機器數(shù)；年投入高負荷運行的機器數(shù)；狀態(tài)轉(zhuǎn)移方程：狀態(tài)轉(zhuǎn)移方程：sk+1=0.7xk+0.9(sk-xk)決策允許集合：決策允許集合：Dk(sk)=xk|0 xk sk階段指標：階段指標： vk(sk,xk)=8xk+5(sk-xk)終端條件：終端條件： f6(s6)=0遞推方程：遞推方程： fk(sk)=maxvk(s

11、k,xk)+fk+1(sk+1) 0 xk sk=max8xk+5(sk-xk)+fk+10.7xk+0.9(sk-xk) 0 xk sk555sx066555sx055853xmax )(sf)x5(s8xmax)(sf5555ss5*5sx 第第5年年s5s6x5指標值指標值(產(chǎn)量產(chǎn)量)V5(s5,x5)+f6(s6)4444444444444550 xs44450 xs4444440 xs4440 xsf (s )max 8x5(sx )f (s ) max 8x5(sx )8s max 8x5(sx )80.7x0.9(sx ) max 1.4x12.2s13.6s4*4sx 第第4年

12、年s4s5x4指標值指標值(產(chǎn)量產(chǎn)量)V4(s4,x4)+f5(s5)f3(s3)=max8x3+5(s3-x3)+f4(s4)0 x3 3 s3 3 =max8x =max8x3 3+5(s+5(s3 3-x-x3 3)+13.6s)+13.6s4 4 0 x3 s3 =max8d =max8d3 3+5(s+5(s3 3-d-d3 3)+13.60.7d)+13.60.7d3 3+0.9(s+0.9(s3 3-d-d3 3) 0 x3 s3 =max0.28x =max0.28x3 3+17.24s+17.24s3 3=17.52s=17.52s3 3 0 x3 s3 x x3 3* *=

13、s=s3 3s3x3第第3年年s4指標值指標值(產(chǎn)量產(chǎn)量)V3(s3,x3)+f4(s4)f2(s2)=max8x2+5(s2-x2)+f3(s3) 0 x2 2 s2 2 =max8x =max8x2 2+5(s+5(s2 2-x-x2 2)+17.52s)+17.52s3 3 0 0 x2 2 s2 2 =max8x =max8x2 2+5(s+5(s2 2-x-x2 2)+17.520.7x)+17.520.7x2 2+0.9(s+0.9(s2 2-x-x2 2)0 0 x2 2 s2 2 =max-0.504x =max-0.504x2 2+20.77s+20.77s2 2=20.77

14、s=20.77s2 20 0 x2 2 s2 2x x2 2* *=0=0s2s3x2第第2年年指標值指標值(產(chǎn)量產(chǎn)量)V2(s2,x2)+f3(s3)f1(s1)=max8x1+5(s1-x1)+f2(s2)0 x1 1 s1 1 =max8x =max8x1 1+5(s+5(s1 1-x-x1 1)+20.77s)+20.77s2 2 0 0 x1 1 s1 1 =max8x =max8x1 1+5(s+5(s1 1-x-x1 1)+20.770.7x)+20.770.7x1 1+0.9(s+0.9(s1 1-x-x1 1)0 0 x1 1 s1 1 =max-0.05x =max-0.0

15、5x1 1+23.69s+23.69s1 1=23.69s=23.69s1 10 0 x1 1 s1 1x x1 1* *=0=0第第1年年s1s2x1指標值指標值(產(chǎn)量產(chǎn)量)V1(s1,x1)+f2(s2)由此可以得到：由此可以得到：f1(s1)=23.69s1,x1*=0f2(s2)=20.77s2,x2*=0f3(s3)=17.52s3,x3*=s3f4(s4)=13.60s4,x4*=s4f5(s5)=8s5x5*=s5用用s1=1000代入，得到五年最大產(chǎn)量為代入，得到五年最大產(chǎn)量為f1(s1)=f1(1000)=23690每年投入高負荷運行的機器數(shù)以及每年初完好的機每年投入高負荷運

16、行的機器數(shù)以及每年初完好的機器數(shù)為：器數(shù)為：s1=1000 x1*=0,s2=0.7x1+0.9(s1-x1)=900 x2*=0,s3=0.7x2+0.9(s2-x2)=810 x3*=s3=810,s4=0.7x3+0.9(s3-x3)=567x4*=s4=567,s5=0.7x4+0.9(s4-x4)=397x5*=s5=397,s6=0.7x5+0.9(s5-x5)=278 該例題對該例題對S6沒有限制，有時會對最后一年年末沒有限制，有時會對最后一年年末完好設(shè)備數(shù)施以約束，例如完好設(shè)備數(shù)施以約束，例如S6=300。5555555()| 0.70.9()300,0D SXXSXX即即 下

17、面數(shù)需重新算下面數(shù)需重新算5504.51500XS 從上題計算結(jié)果可以看出從上題計算結(jié)果可以看出：前兩年低負荷運行，：前兩年低負荷運行，后三年高負荷運行。是否有這樣的規(guī)律，后三年高負荷運行。是否有這樣的規(guī)律，n年的生年的生產(chǎn)計劃，總是前產(chǎn)計劃，總是前1t-1年底負荷運行，年底負荷運行，tn年高負荷年高負荷運行。運行。這時決策變量這時決策變量x5的決策允許集合為：的決策允許集合為：則最優(yōu)設(shè)備分配策略是則最優(yōu)設(shè)備分配策略是：從：從1至至t-1年，年初將全年，年初將全部完好設(shè)備投入低負荷運行，從部完好設(shè)備投入低負荷運行，從t至至n年，年初將年，年初將全部完好設(shè)備投入高負荷運行，總產(chǎn)量達到最大。全部完

18、好設(shè)備投入高負荷運行，總產(chǎn)量達到最大。條件：條件：g(x)、h(x)為線性函數(shù)，且為線性函數(shù)，且g(0)=h(0)=0。一般地，設(shè)一個周期為一般地，設(shè)一個周期為n年，年，高負荷生產(chǎn)時設(shè)備的完好率為高負荷生產(chǎn)時設(shè)備的完好率為a，單臺產(chǎn)量為，單臺產(chǎn)量為g；低負荷生產(chǎn)時設(shè)備的完好率為低負荷生產(chǎn)時設(shè)備的完好率為b，單臺產(chǎn)量為，單臺產(chǎn)量為h;100()n tn tiiiighaag ba 計算計算t： 某公司有某公司有1000輛運輸卡車，在超負荷運輸（即每輛運輸卡車，在超負荷運輸（即每天滿載行駛天滿載行駛500km以上）情況下，年利潤為以上）情況下，年利潤為25萬元萬元/輛，這時卡車的年損壞率為輛，這時

19、卡車的年損壞率為0.3；在低負荷下運輸；在低負荷下運輸（即每天行駛（即每天行駛300km以下）情況下，年利潤為以下）情況下，年利潤為16萬萬元元/輛。年損壞率為輛。年損壞率為0.1?，F(xiàn)要制定一個。現(xiàn)要制定一個5年計劃，問年計劃，問每年年初應如何分配完好車輛在兩種不同的負荷下每年年初應如何分配完好車輛在兩種不同的負荷下運輸?shù)目ㄜ嚁?shù)量，使在第運輸?shù)目ㄜ嚁?shù)量，使在第5年年末剩余的完好卡車年年末剩余的完好卡車數(shù)量為數(shù)量為500臺，并且使在臺，并且使在5年內(nèi)的總利潤最大？年內(nèi)的總利潤最大？習題習題1：第二節(jié)第二節(jié) 生產(chǎn)與存儲問題生產(chǎn)與存儲問題 在生產(chǎn)和經(jīng)營管理中，經(jīng)常會遇到要合理在生產(chǎn)和經(jīng)營管理中，經(jīng)常

20、會遇到要合理地安排生產(chǎn)地安排生產(chǎn)(或購買或購買)與庫存的問題，達到既要與庫存的問題，達到既要滿足社會的需要，又要盡量降低成本費用。因滿足社會的需要，又要盡量降低成本費用。因此，正確制定生產(chǎn)（采購）策略，確定不同時此，正確制定生產(chǎn)（采購）策略，確定不同時期的生產(chǎn)量（或采購量）和庫存量，以使總的期的生產(chǎn)量（或采購量）和庫存量，以使總的生產(chǎn)成本費用和庫存費用之和最小，這就是生生產(chǎn)成本費用和庫存費用之和最小，這就是生產(chǎn)和存儲問題的目標。產(chǎn)和存儲問題的目標。第三節(jié)第三節(jié) 背包問題背包問題 有一個徒步旅行者，其可攜帶物品重量的限度為有一個徒步旅行者，其可攜帶物品重量的限度為w 公公斤，有斤，有n 種物品可

21、供他選擇裝入包中。已知每種物品的種物品可供他選擇裝入包中。已知每種物品的重量及使用價值（作用），問此人應如何選擇攜帶的重量及使用價值（作用），問此人應如何選擇攜帶的物品（各幾件），使所起作用（使用價值）最大？物品（各幾件），使所起作用（使用價值）最大？物品物品 1 2 i n重量（公斤重量（公斤/ /件）件） w1 w2 wi wn使用價值使用價值 c1 c2 ci cn 這就是背包問題。類似的還有運輸中的貨物裝載問這就是背包問題。類似的還有運輸中的貨物裝載問題、人造衛(wèi)星內(nèi)的物品裝載問題等。題、人造衛(wèi)星內(nèi)的物品裝載問題等。設(shè)設(shè)x xi i 為第為第i i 種物品的裝件數(shù)（非負整數(shù)）則問題的數(shù)種

22、物品的裝件數(shù)（非負整數(shù)）則問題的數(shù)學模型如下：學模型如下：1max()10(1.2.)且 為 整 數(shù)niiiiZcxniiixinw xw例題：求下面背包問題的最優(yōu)解例題：求下面背包問題的最優(yōu)解123123123max60406032510,0Zxxxxxxx xx且為整數(shù)物品物品 1 2 3重量（公斤）重量（公斤） 3 2 5使用價值使用價值 60 40 60例例1 有一輛最大貨運量為有一輛最大貨運量為10 t 的卡車，用以裝載的卡車，用以裝載3種種貨物，每種貨物的單位重量及相應單位價值如表所示。貨物，每種貨物的單位重量及相應單位價值如表所示。應如何裝載可使總價值最大？應如何裝載可使總價值最

23、大？分析：分析：狀態(tài)轉(zhuǎn)移方程狀態(tài)轉(zhuǎn)移方程：s sk+1k+1=s=sk k-w-wk k* *x xk k物品物品1 13x1s2狀態(tài)s1v1(s1,u1)=60 x1物品物品2 22x2S3v2(s2,u2)=40 x2物品物品3 35x3S4v3(s3,u3)=60 x3階段階段k k： 物品（物品（k=3,2,1k=3,2,1）；）；狀態(tài)變量狀態(tài)變量s sk k：從第從第k k種物品到第種物品到第3 3種物品可載重量；種物品可載重量；決策變量決策變量x xk k：裝第裝第k k種物品數(shù)量種物品數(shù)量; ;決策允許集合：決策允許集合：D Dk k(s(sk k)=x)=xk k|0|0 x

24、xk k s sk k/w/wk k階段指標：階段指標：v vk k(s(sk k,x,xk k)=c)=ck k* *x xk k遞推方程遞推方程：f fk k(s(sk k)=maxc)=maxck k* *x xk k+f+fk+1k+1(s(sk+1k+1)邊界條件邊界條件：f f4 4(s(s4 4)=0)=0解：終端條件：解：終端條件：f4(s4)=0k=3時，遞推方程為時，遞推方程為3333333443005()max()max60ssxxwfsc xfsxs3D3(s3)s460 x3+f4(s4)f3(s3)X*3解：終端條件：解：終端條件：f4(s4)=0k=3時，遞推方程為時，遞推方程為3333333443005()max()max60ssxxwfsc xfsxs3D3(s3)s460 x3+f4(s4)f3(s3)X*30000+0=0001010+0=000501500+0=060+0=606011001210500+0=060+0=60120+0=1201202k=2時，遞推方程為時，遞推方程為22222223