運(yùn)籌學(xué) 第9章_動(dòng)態(tài)規(guī)劃應(yīng)用舉例

1、清華大學(xué)出版社清華大學(xué)出版社1五、動(dòng)態(tài)規(guī)劃n第8章 動(dòng)態(tài)規(guī)劃的基本方法n第9章 動(dòng)態(tài)規(guī)劃應(yīng)用舉例清華大學(xué)出版社清華大學(xué)出版社2第9章 動(dòng)態(tài)規(guī)劃應(yīng)用舉例n第1節(jié) 資源分配問題n第2節(jié) 生產(chǎn)與存儲(chǔ)問題n第3節(jié)* 背包問題n第4節(jié)* 復(fù)合系統(tǒng)工作可靠性問題n第5節(jié) 排序問題n第6節(jié) 設(shè)備更新問題n第7節(jié)* 貨郎擔(dān)問題清華大學(xué)出版社3第1節(jié) 資源分配問題v所謂分配問題，就是將數(shù)量一定的一種或若干種資源(例如原材料、資金、機(jī)器設(shè)備、勞力、食品等等)，恰當(dāng)?shù)胤峙浣o若干個(gè)使用者，而使目標(biāo)函數(shù)為最優(yōu)。清華大學(xué)出版社41.1資源分配問題( )iig x112212max ( )()()0, 1,2,nnnizg

2、 xgxgxxxxaxiniig (x )iig (x )設(shè)有某種原料，總數(shù)量為a，用于生產(chǎn)n種產(chǎn)品。若分配數(shù)量xi用于生產(chǎn)第i種產(chǎn)品，其收益為問應(yīng)如何分配，才能使生產(chǎn)n產(chǎn)品的總收入最大?此問題可寫成靜態(tài)規(guī)劃問題：當(dāng)都是線性函數(shù)時(shí)，它是一個(gè)線性規(guī)劃問題；當(dāng)是非線性函數(shù)時(shí)，它是一個(gè)非線性規(guī)劃問題。但當(dāng)n比較大時(shí)，具體求解是比較麻煩的。由于這類問題的特殊結(jié)構(gòu)，可以將它看成一個(gè)多階段決策問題，并利用動(dòng)態(tài)規(guī)劃的遞推關(guān)系來求解。清華大學(xué)出版社51.1資源分配問題 在應(yīng)用動(dòng)態(tài)規(guī)劃方法處理這類“靜態(tài)規(guī)劃”問題時(shí)，通常以把資源分配給一個(gè)或幾個(gè)使用者的過程作為一個(gè)階段，把問題中的變量xi為決策變量，將累計(jì)的量或

3、隨遞推過程變化的量選為狀態(tài)變量。清華大學(xué)出版社61.1資源分配問題1kkkkkssusx()0kkkkkkD suuxs()kkfs10 ()max()() , 1,1()max()kknnkkkkkkkxsnnnnxsfsgxfsxknfsgx1( )f a設(shè)狀態(tài)變量sk表示分配用于生產(chǎn)第k種產(chǎn)品至第n種產(chǎn)品的原料數(shù)量。決策變量uk表示分配給生產(chǎn)第k種產(chǎn)品的原料數(shù)，即uk=xk狀態(tài)轉(zhuǎn)移方程：允許決策集合：令最優(yōu)值函數(shù)表示以數(shù)量為sk的原料分配給第k種產(chǎn)品至第n種產(chǎn)品所得到的最大總收入。因而可寫出動(dòng)態(tài)規(guī)劃的逆推關(guān)系式為：利用這個(gè)遞推關(guān)系式進(jìn)行逐段計(jì)算，最后求得 即為所求問題的最大總收入。 清華

4、大學(xué)出版社71.1資源分配問題例例1 某工業(yè)部門根據(jù)國家計(jì)劃的安排，擬將某種高效率的設(shè)備五臺(tái)，分配給所屬的甲、乙、丙三個(gè)工廠，各工廠若獲得這種設(shè)備之后，可以為國家提供的盈利如表9-1所示。問：這五臺(tái)設(shè)備如何分配給各工廠，才能使國家得到的盈利最大。問：這五臺(tái)設(shè)備如何分配給各工廠，才能使國家得到的盈利最大。 清華大學(xué)出版社81.1資源分配問題1kkkssx()kkP x()kkfs1044()max()() , 3,2,1()0kkkkkkkkkxsfsP xfsxkfs解解: 將問題按工廠分為三個(gè)階段，甲、乙、丙三個(gè)工廠分別編號(hào)為1、2、3設(shè)sk表示為分配給第k個(gè)工廠至第n個(gè)工廠的設(shè)備臺(tái)數(shù)。xk

5、表示為分配給第k個(gè)工廠的設(shè)備臺(tái)數(shù)。則為分配給第k+1個(gè)工廠至第n個(gè)工廠的設(shè)備臺(tái)數(shù)。表示為sk臺(tái)設(shè)備分配到第k個(gè)工廠所得的盈利值。表示為sk臺(tái)設(shè)備分配給第k個(gè)工廠至第n個(gè)工廠時(shí)所得到的最大盈利值。因而可寫出逆推關(guān)系式為清華大學(xué)出版社91.1資源分配問題33333( )max()xf sP x下面從最后一個(gè)階段開始向前逆推計(jì)算。第三階段：設(shè)將s3臺(tái)設(shè)備(s3=0,1,2,3,4,5)全部分配給工廠丙時(shí)，則最大盈利值為其中x3=s3=0,1,2,3,4,5因?yàn)榇藭r(shí)只有一個(gè)工廠，有多少臺(tái)設(shè)備就全部分配給工廠丙，故它的盈利值就是該段的最大盈利值，如下表。x3s3P3(x3)f3(s3)x3*012345

6、000014412662311113412124512125表中x3*表示使f3(s3)為最大值時(shí)的最優(yōu)決策。清華大學(xué)出版社101.1資源分配問題22222322()max()()xfsP xf sx20,1,2,3,4,5x 22322()()pxf sx第二階段：設(shè)把s2臺(tái)設(shè)備(s2=0,1,2,3,4,5)分配給工廠乙和工廠丙時(shí)，則對(duì)每個(gè)s2值，有一種最優(yōu)分配方案，使最大盈利值為其中因?yàn)榻o乙工廠x2臺(tái)，其盈利為p2(x2) ，余下的s2x2臺(tái)就給丙工廠，則它的盈利最大值為f3(s2 x2) ?，F(xiàn)要選擇x2的值，使取最大值。其數(shù)值計(jì)算如表9-3所示。清華大學(xué)出版社111.1資源分配問題2x

7、2s22322()()pxf sx)x(f22*2x表9-3012345000010+45+05120+65+410+010230+115+610+411+014240+125+1110+611+411+0161,250+125+1210+1111+611+411+0212清華大學(xué)出版社121.1資源分配問題111121(5)max()(5)xfp xfx10,1,2,3,4,5x 1121()(5)p xfx1x1s1121( )(5)p xfx1(5)f*1x第一階段：設(shè)把s1臺(tái)(這里只有s1=5的情況)設(shè)備分配給甲、乙、丙三個(gè)工廠時(shí)，則最大盈利值為其中因?yàn)榻o甲工廠x1臺(tái)，其盈利為p1(x

8、1) ，剩下的5x1臺(tái)就分給乙和丙兩個(gè)工廠，則它的盈利最大值為f2(5x1) ?，F(xiàn)要選擇x1值，使取最大值，它就是所求的總盈利最大值，其數(shù)值計(jì)算如表9-4所示。01234550+213+167+149+1012+513+0210,2表9-4清華大學(xué)出版社131.1資源分配問題*211505ssx*322523ssx*333xs*211523ssx*322321ssx*331xs然后按計(jì)算表格的順序反推算，可知最優(yōu)分配方案有兩個(gè)：(1) 由于x1*=0 ，根據(jù)查表9-3知x2*=2，由故即得甲工廠分配0臺(tái)，乙工廠分配2臺(tái)，丙工廠分配3臺(tái)。(2) 由于x1*=2，根據(jù)查表9-3知x2*=2，由故即

9、得甲工廠分配2臺(tái)，乙工廠分配2臺(tái)，丙工廠分配1臺(tái)。以上兩個(gè)分配方案所得到的總盈利均為21萬元。 清華大學(xué)出版社141.1資源分配問題111( )()g uh su2111()saub su222()()g uh su12,nu uu資源連續(xù)分配問題資源連續(xù)分配問題設(shè)有數(shù)量為s1的某種資源，可投入A和B兩種生產(chǎn)。第一年若以數(shù)量u1投入生產(chǎn)A，剩下的量s1u1就投入生產(chǎn)B，則可得收入為其中g(shù)(u1)和h(u1)為已知函數(shù)，且g(0)=h(0)=0。這種資源在投入A、B生產(chǎn)后，年終還可回收再投入生產(chǎn)。設(shè)年回收率分別為0a1和0b0,cd。年回收率分別為a和b,0ab1。試求出最優(yōu)策略的一般關(guān)系式。顯

10、然，這時(shí)狀態(tài)轉(zhuǎn)移方程為k段的指標(biāo)函數(shù)為令fk(sk)表示由狀態(tài)sk出發(fā)，從第k年至第n年末時(shí)所生產(chǎn)的產(chǎn)品的總產(chǎn)量最大值。清華大學(xué)出版社251.1資源分配問題可寫出逆推關(guān)系式為：1110()0()max()()(92) 1,2,kknnkkkkkkkkkusfsfscud sufaub sukn我們知道，在低負(fù)荷下生產(chǎn)的時(shí)間愈長，機(jī)器完好率愈高，但生產(chǎn)產(chǎn)量少。而在高負(fù)荷下生產(chǎn)產(chǎn)量會(huì)增加，但機(jī)器損壞大。這樣，即使每臺(tái)產(chǎn)量高，總起來看產(chǎn)量也不高。 清華大學(xué)出版社261.1資源分配問題v從前面的數(shù)字計(jì)算可以看出，前幾年一般是全部用于低負(fù)荷生產(chǎn)，后幾年則全部用于高負(fù)荷生產(chǎn)，這樣才產(chǎn)量最高。如果總共為n年

11、，從低負(fù)荷轉(zhuǎn)為高負(fù)荷生產(chǎn)的是第t年，1tn。即是說，從1至t1年在低負(fù)荷下生產(chǎn)，t至n年在高負(fù)荷下生產(chǎn)?，F(xiàn)在要分析t與系數(shù)a、b、c、d是什么關(guān)系。v從回收率看，(b a)值愈大，表示在高負(fù)荷下生產(chǎn)時(shí)，機(jī)車損壞情況比在低負(fù)荷時(shí)嚴(yán)重得多，因此t值應(yīng)選大些。從產(chǎn)量看，(c d)值愈大，表示在高負(fù)荷下生產(chǎn)較有利，故t應(yīng)選小些。下面我們從(9-2)式這一基本方程出發(fā)來求出t與(b a)、(c d)的關(guān)系。清華大學(xué)出版社271.1資源分配問題kkkus0k1k0001()max()max ()max ()nnnnnnnnnusnnusnnnfscud sucd udscdd sn()nnfs()nnnf

12、scs令。則在低負(fù)荷生產(chǎn)時(shí)有，高負(fù)荷生產(chǎn)時(shí)有對(duì)第n段，有由于cd，所以應(yīng)選1才能使最大。也就是說，最后一年應(yīng)全部投入高負(fù)荷生產(chǎn)。故清華大學(xué)出版社281.1資源分配問題1111111111101111111111111()max()()max()max()()max()()()max()()()(93nnnnnnnnnnnnnusnnnnunnnnnnunnunnfscud sufscud sucscud suc aub sucdc ba udcb scdc badcbs )()(94)cdc ba*11n*10n對(duì)n-1段，根據(jù)(9-2)式有因此，欲要滿足上式極值關(guān)系的條件是當(dāng)時(shí)，應(yīng)取即n 1

13、年仍應(yīng)全部在高負(fù)荷下生產(chǎn)。否則，當(dāng)(9-4)式不滿足時(shí)，應(yīng)取即n 1年應(yīng)全部投入低負(fù)荷生產(chǎn)。清華大學(xué)出版社291.1資源分配問題*120k*0k*11n1111()()(1)nnnnfscca sca s1222()nnnnsaub su1122()(1) ()nnnnfscaab ubs由前面知道，只要在第k年投入低負(fù)荷生產(chǎn)，那么遞推計(jì)算結(jié)果必然是從第1年到第k年均為低負(fù)荷生產(chǎn)，即有 可見，算出后 ，前幾年就沒有必要再計(jì)算了。故只需研究哪一年由低負(fù)荷轉(zhuǎn)入高負(fù)荷生產(chǎn)，即從 那一年開始變?yōu)?就行。 根據(jù)這點(diǎn)，現(xiàn)只分析滿足(9-4)式的情況。由于故(9-3)式變?yōu)橛钟捎趯⑺肷鲜降?清華大學(xué)出版

14、社301.1資源分配問題2222222222110222222222()max(-)()max()(1) ()max()(1)()(1)max()(1)()(1)nnnnnnnnnnnnusnnnnnunnunnfscud sufscud sucaab ubscdca ba udca b scdca badcbas(1)()cdca ba*21n對(duì)n-2段，由(9-2)式有由此可知，只要滿足極值條件式就應(yīng)選否則為0，即應(yīng)繼續(xù)在高負(fù)荷下生產(chǎn)。 清華大學(xué)出版社311.1資源分配問題11( )max()()ttttttttuf scud sufs2(1)2(1)()(95)(1)()ntn tcdc

15、aaabacdcaaaba *1*12110nntt依次類推，如果轉(zhuǎn)入高負(fù)荷下生產(chǎn)的是第t年，則由可以推出，應(yīng)滿足極值關(guān)系的條件必然是：相應(yīng)的有最優(yōu)策略它就是例2在始端固定終端自由情況下最優(yōu)策略的一般結(jié)果。 從本例可看出，應(yīng)用動(dòng)態(tài)規(guī)劃，可以在不求出數(shù)值解的情況下，確定從本例可看出，應(yīng)用動(dòng)態(tài)規(guī)劃，可以在不求出數(shù)值解的情況下，確定最優(yōu)策略的結(jié)構(gòu)。最優(yōu)策略的結(jié)構(gòu)。清華大學(xué)出版社321.1資源分配問題11tn 0.7,0.8,8,5abcd1/1 5/831.875(1)1 0.7()0.90.71.6cdd cac baba 151 1ntt 例如，只要知道了a,b,c,d四個(gè)值，就總可找到一個(gè)t值

16、，滿足(9-5)式，且例如題中給定的代入(9-5)式，應(yīng)有可見所以t=3，即從第三年開始將全部機(jī)器投入高負(fù)荷生產(chǎn)，五年內(nèi)總產(chǎn)量最高。清華大學(xué)出版社331.1資源分配問題上面的討論表明：當(dāng)x在0，s1上離散地變化時(shí)，利用遞推關(guān)系式逐步計(jì)算或表格法而求出數(shù)值解。當(dāng)x在0，s1上連續(xù)地變化時(shí)，若g(x)和h(x)是線性函數(shù)或凸函數(shù)時(shí)，根據(jù)遞推關(guān)系式運(yùn)用解析法不難求出fk(x)和最優(yōu)解；若g(x)和h(x)不是線性函數(shù)或凸函數(shù)時(shí)，一般來說，解析法不能奏效，那只好利用遞推關(guān)系式(91)求其數(shù)值解。首先要把問題離散化，即把區(qū)間0，s1進(jìn)行分割，令x=0，2，m=s1。其的大小，應(yīng)根據(jù)計(jì)算精度和計(jì)算機(jī)容量等

17、來確定。然后規(guī)定所有的fk(x)和決策變量只在這些分割點(diǎn)上取值。這樣，遞推關(guān)系式(9-1)便可寫為010()max()()()max()()()() 1,2,1nj ikkj if ig jh ijf ig jh ijfa jb ijkn 清華大學(xué)出版社341.1資源分配問題010()max()()()max()()()() 1,2,1nj ikkj if ig jh ijf ig jh ijfa jb ijkn 0,1,im11(),(),()nnf ifif i111()( )f mf s 對(duì)依次計(jì)算，可逐步求出及相應(yīng)的最優(yōu)決策，最后求得就是所求的最大總收入。這種離散化算法可以編成程序在計(jì)

18、算機(jī)中計(jì)算。 清華大學(xué)出版社351.2 二維資源分配問題 ( ,)iiig x y1112221212max( ,)(,)(,)0,0, (1,2, )nnnnniig x ygx ygxyxxxayyybxyin且為整數(shù)設(shè)有兩種原料，數(shù)量各為a和b單位，需要分配用于生產(chǎn)n種產(chǎn)品。如果第一種原料以數(shù)量xi為單位，第二種原料以數(shù)量yi為單位，用于生產(chǎn)第i種產(chǎn)品，其收入為問應(yīng)如何分配這兩種原料于n種產(chǎn)品的生產(chǎn)使總收入最大?此問題可寫成靜態(tài)規(guī)劃問題：清華大學(xué)出版社361.2 二維資源分配問題 (,)kkxykkxxxyyyxy用動(dòng)態(tài)規(guī)劃方法來解，狀態(tài)變量和決策變量要取二維的。設(shè)狀態(tài)變量(x,y):x

19、分配用于生產(chǎn)第k種產(chǎn)品至第n種產(chǎn)品的第一種原料的單位數(shù)量。y分配用于生產(chǎn)第k種產(chǎn)品至第n種產(chǎn)品的第二種原料的單位數(shù)量。決策變量xk分配給第k種產(chǎn)品用的第一種原料的單位數(shù)量。yk分配給第k種產(chǎn)品用的第二種原料的單位數(shù)量。狀態(tài)轉(zhuǎn)換關(guān)系：式中和分別表示用來生產(chǎn)第k+1種產(chǎn)品至第n種產(chǎn)品的第一種和第二種原料的單位數(shù)量。清華大學(xué)出版社371.2 二維資源分配問題 0( , )0kkkkxxDx yuyy( , )kfx y100( , )( , )( , )max(,)(,) 1,1kknnkkkkkkkxxyyfx ygx yfx ygxyfxxyykn1( , )f a b允許決策集合： 表示以第一

20、種原料數(shù)量為x單位，第二種原料數(shù)量為y單位，分配用于生產(chǎn)第k種產(chǎn)品至第n種產(chǎn)品時(shí)所得到的最大收入。故可寫出逆推關(guān)系為最后求得即為所求問題的最大收入。 清華大學(xué)出版社381.2 二維資源分配問題 1112221max( ,)(,)(,)(2)nnnng x ygxygxyyyy120,0, 1,2, niixxxaxyin且為整數(shù)0( )( ,)max( ,)iiiiiiiiiyh xh xg x yy1122max( )()()nnh xh xh x12, 0nixxxax1. 拉格朗日乘數(shù)法引入拉格朗日乘數(shù)，將二維分配問題化為滿足條件其中作為一個(gè)固定的參數(shù)。令于是問題變?yōu)闈M足且為整數(shù)清華大學(xué)

21、出版社391.2 二維資源分配問題 ()iixx()iiyy1()niiyb,iix y1()niiyb1()niiyb這是一個(gè)一維分配問題，可用對(duì)一維的方法去求解。這里，由于是參數(shù)，因此，最優(yōu)解xi 參數(shù)的函數(shù)，相應(yīng)的yi也是的函數(shù)。即為其解。如果則可證明為原問題的最優(yōu)解。如果將調(diào)整的值(利用插值法逐漸確定 )，直到滿足為止。這樣的降維方法在理論上有保證，在計(jì)算上是可行的，故對(duì)高維問題，可用上述拉格朗日乘數(shù)法的思想來降低維數(shù)。清華大學(xué)出版社401.2 二維資源分配問題 (0)(0)(0)(0)12,nxxxx(0)1niixa(0)(0)(0)11122212max(,)(,)(,),0 n

22、nnnig xygxygxyyyyb y且為整數(shù)(0)(0)(0)(0)12,nyyyy(0)11max( ,),0 niiiiniiig x yxa x且為整數(shù)2. 逐次逼近法這是另一種降維方法，先保持一個(gè)變量不變，對(duì)另一個(gè)變量實(shí)現(xiàn)最優(yōu)化。然后交替地固定，以迭代的形式反復(fù)進(jìn)行，直到獲得某種要求為止。先設(shè)為滿足的一個(gè)可行解，固定x在x(0) ，先對(duì)y求解，則二維分配問題變?yōu)橐痪S問題：可用對(duì)一維的方法來求解。設(shè)這解為然后再固定y為y(0) ，對(duì)x求解，即清華大學(xué)出版社411.2 二維資源分配問題 (1)(1)(1)(1)12,nxxxx ( )( )(0,1,)kkxyk ，(1)(1)(0)(

23、1)(0)111(,)(,)(,)nnniiiiiiiiiiiig xyg xyg xy( )( )1(,)nkkiiiig xy設(shè)其解為再固定x為x(1)，對(duì)y求解，這樣依次輪換下去得到一系列的解因?yàn)楣屎瘮?shù)值序列是單調(diào)上升的，但不一定收斂到絕對(duì)的最優(yōu)解，一般只收斂到某一局部最優(yōu)解。因此，在實(shí)際計(jì)算時(shí)，可選擇幾個(gè)初始點(diǎn)x(0)進(jìn)行計(jì)算，然后從所得到的幾個(gè)局部最優(yōu)解中選出一個(gè)最好的。清華大學(xué)出版社421.2 二維資源分配問題 3 粗格子點(diǎn)法(疏密法) 在采用離散化的方法計(jì)算時(shí)，先將矩形定義域：0 xa,0yb分成網(wǎng)格，然后在這些格子點(diǎn)上進(jìn)行計(jì)算。如將a、b各分為m1和m2等份，則總共有(m1+1

24、)(m2+1)個(gè)格點(diǎn)，故對(duì)每個(gè)k值需要計(jì)算的fk(x,y)共有(m1+1)(m2+1)個(gè)。因此，這里的計(jì)算量是相當(dāng)大的。隨著分點(diǎn)加多，格子點(diǎn)數(shù)也增多，那時(shí)的計(jì)算量將大得驚人。為了使計(jì)算可行，往往根據(jù)問題要求的精確度，采用粗格子點(diǎn)法逐步縮小區(qū)域來減少計(jì)算量。 粗格子點(diǎn)法是先用少數(shù)的格子點(diǎn)進(jìn)行粗糙的計(jì)算，在求出相應(yīng)的最優(yōu)解后，再在最優(yōu)解附近的小范圍內(nèi)進(jìn)一步細(xì)分，并求在細(xì)分格子點(diǎn)上的最優(yōu)解，如此繼續(xù)細(xì)分下去直到滿足要求為止。這種方法可能會(huì)出現(xiàn)最優(yōu)解“漏網(wǎng)”的情況，因此，應(yīng)用此法時(shí)要結(jié)合對(duì)指標(biāo)函數(shù)的特性進(jìn)行分析。清華大學(xué)出版社431.3 固定資金分配問題(,)kkkr xy111max(,) nkkk

25、knkkkknkkkkr xyxXxxyYyxaXbYZ為非負(fù)整數(shù)為非負(fù)整數(shù)設(shè)有n個(gè)生產(chǎn)行業(yè)，都需要某兩種資源。對(duì)于第k個(gè)生產(chǎn)行業(yè)，如果用第1種資源xk和第2種資源yk進(jìn)行生產(chǎn)，可獲得利潤為若第1種資源的單位價(jià)格為a ，第2種資源的單位價(jià)格為b，現(xiàn)有資金Z 。問應(yīng)購買第1種資源多少單位(設(shè)為X)，第2種資源多少單位(設(shè)為Y)，分配到n個(gè)生產(chǎn)行業(yè)，使總利潤最大?此問題的數(shù)學(xué)模型可寫為清華大學(xué)出版社441.3 固定資金分配問題(,)kkkr xy( ), 0,1,kR zzZ(0)zzZZaXbYkkzbyxa0,1,( / )( )max,kkkkkyz bzbyR zryakzbya(1) 把

26、資源分配利潤表換算成資金分配利潤表，即將換算成但必須注意，分配的資金應(yīng)先使較貴的資源單位最大。設(shè)有資金分配到第k個(gè)生產(chǎn)行業(yè)，則由知，在給定z的情況下，若購買第2種資源yk單位，則留下的資金只能購買第1種資源xk單位，于是得到資金利潤函數(shù)Rk(z)為式中(z/b)指以資金z購買第2種資源的最大單位數(shù)，指以資金z購買了第2種資源yk單位以后能購買第1種資源的最大單位數(shù)。 清華大學(xué)出版社451.3 固定資金分配問題10,1,( )max()()( )( )kkkkkkzzfzR zfzzfn zRn z(2) 計(jì)算最優(yōu)資金分配所獲得最大利潤。規(guī)定最優(yōu)值函數(shù)fk(z)表示以總的資金z分配到k至n個(gè)生產(chǎn)

27、行業(yè)可能獲得的最大利潤。則有逆推關(guān)系式： (3) 求出f1(z) ，即為問題的解。這樣，就把一個(gè)原含有兩個(gè)狀態(tài)變量的問題轉(zhuǎn)化為只含有一個(gè)狀態(tài)變量的問題。清華大學(xué)出版社46第2節(jié) 生產(chǎn)與存儲(chǔ)問題 在生產(chǎn)和經(jīng)營管理中，經(jīng)常遇到要合理地安排生產(chǎn)(或購買)與庫存的問題，達(dá)到既要滿足社會(huì)的需要，又要盡量降低成本費(fèi)用。因此，正確制定生產(chǎn)(或采購)策略，確定不同時(shí)期的生產(chǎn)量(或采購量)和庫存量，以使總的生產(chǎn)成本費(fèi)用和庫存費(fèi)用之和最小，這就是生產(chǎn)與存儲(chǔ)問題的最優(yōu)化目標(biāo)。清華大學(xué)出版社472.1 生產(chǎn)計(jì)劃問題 設(shè)某公司對(duì)某種產(chǎn)品要制定一項(xiàng)個(gè)階段的生產(chǎn)(或購買)計(jì)劃。已知它的初始庫存量為零，每階段生產(chǎn)(或購買)該

28、產(chǎn)品的數(shù)量有上限的限制；每階段社會(huì)對(duì)該產(chǎn)品的需求量是已知的，公司保證供應(yīng)；在n階段末的終結(jié)庫存量為零。問該公司如何制定每個(gè)階段的生產(chǎn)(或采購)計(jì)劃，從而使總成本最小。清華大學(xué)出版社482.1 生產(chǎn)計(jì)劃問題 1kkkkvvxd0 0() 1,2, kkkkkkxcxKaxxmxm當(dāng)當(dāng)當(dāng)()()kkkkcxh x設(shè)dk為第k階段對(duì)產(chǎn)品的需求量，xk為第k階段該產(chǎn)品的生產(chǎn)量(或采購量)，vk為第k階段結(jié)束時(shí)的產(chǎn)品庫存量。則有ck(xk)表示第k階段生產(chǎn)產(chǎn)品xk時(shí)的成本費(fèi)用，它包括生產(chǎn)準(zhǔn)備成本K和產(chǎn)品成本axk (其中a是單位產(chǎn)品成本)兩項(xiàng)費(fèi)用。即hk(vk)表示在第k階段結(jié)束時(shí)有庫存量vk所需的存儲(chǔ)

29、費(fèi)用。k階段的成本費(fèi)用為m表示每階段最多能生產(chǎn)該產(chǎn)品的上限數(shù)。 清華大學(xué)出版社492.1 生產(chǎn)計(jì)劃問題 101min ()()0,0()0 2,1 0 1,2, 1,2,nkkkkknkkjjjkkgcxh vvvvxdknxmknxkn為整數(shù)1 1,2,kkkkvvxdkn上述問題的數(shù)學(xué)模型為用動(dòng)態(tài)規(guī)劃方法來求解，可看作一個(gè)n階段決策問題。令vk-1為狀態(tài)變量，它表示第k階段開始時(shí)的庫存量。xk為決策變量，它表示第k階段的生產(chǎn)量。狀態(tài)轉(zhuǎn)移方程為最優(yōu)值函數(shù)fk(xk)表示從第1階段初始庫存量為0到第k階段末庫存量為vk時(shí)的最小總費(fèi)用。清華大學(xué)出版社502.1 生產(chǎn)計(jì)劃問題 110()min()

30、()() 1,kkkkkkkkkkxfvcxh vfvkn,min()kkk mvd0kkkvdxkkkxvd00()0f v11111111( )min()( )xf vc xh v,1minnj mkj kdd 順序遞推關(guān)系式為：其中。這是因?yàn)橐环矫婷侩A段生產(chǎn)的上限為m；另一方面由于保證供應(yīng)，故第k-1階段末的庫存量vk-1必須非負(fù)，即所以邊界條件為 或從邊界條件出發(fā)，利用上面的遞推關(guān)系式，對(duì)每個(gè)k ，計(jì)算出fk(vk)中的vk在0至之間的值，最后求得的fn(0)即為所求的最小總費(fèi)用。清華大學(xué)出版社512.1 生產(chǎn)計(jì)劃問題 例例3 3 某工廠要對(duì)一種產(chǎn)品制訂今后四個(gè)時(shí)期的生產(chǎn)計(jì)劃，據(jù)估計(jì)在

31、今后四個(gè)時(shí)期內(nèi)，市場對(duì)于該產(chǎn)品的需求量如表9-5所示。時(shí)期(k)1234需求量(dk)2324假定該廠生產(chǎn)每批產(chǎn)品的固定成本為3千元，若不生產(chǎn)就為0；每單位產(chǎn)品成本為1千元；每個(gè)時(shí)期生產(chǎn)能力所允許的最大生產(chǎn)批量為不超過6個(gè)單位；每個(gè)時(shí)期末未售出的產(chǎn)品，每單位需付存儲(chǔ)費(fèi)0.5千元。還假定在第一個(gè)時(shí)期的初始庫存量為0，第四個(gè)時(shí)期之末的庫存量也為0。試問該廠應(yīng)如何安排各個(gè)時(shí)期的生產(chǎn)與庫存，才能在滿足市場需要的條件下，使總成本最小。表9-5清華大學(xué)出版社522.1 生產(chǎn)計(jì)劃問題 0 0()3 1 1,2,6 6kkkkkkxcxxxx當(dāng)當(dāng)當(dāng)()0.5kkkh vv()()kkkkcxh v10()mi

32、n()()() , 2,3,4kkkkkkkkkkkkxfvcxh vfvdxkmin(,6)kkkvd111111111min(,5)( )min( )( )xvdf vc xh v解解: 用動(dòng)態(tài)規(guī)劃方法來求解，其符號(hào)含義與上面相同。按四個(gè)時(shí)期將問題分為四個(gè)階段。由題意知，在第k時(shí)期內(nèi)的生產(chǎn)成本為第k時(shí)期末庫存量為vk時(shí)的存儲(chǔ)費(fèi)用為故第k時(shí)期內(nèi)的總成本為而動(dòng)態(tài)規(guī)劃的順序遞推關(guān)系式為其中和邊界條件清華大學(xué)出版社532.1 生產(chǎn)計(jì)劃問題 11111111min(2,5)( )min()( )xvf vc xh v412min,min 9,624jjdmd1111111211113111140 (

33、0)min 30.5 05 21 (1)min 30.5 16.5 32 (2)min 30.5 28 4xxxvfxxvfxxvfxx時(shí)，所以時(shí)，所以時(shí)，所以1111(3)9.5 5(4)11 6fxfx所以所以當(dāng)k=1時(shí)，由對(duì)v1在0至之間的值分別進(jìn)行計(jì)算。同理得清華大學(xué)出版社542.1 生產(chǎn)計(jì)劃問題 222222221220()min()()(3)xf vc xh vf vx 22min(3,6)v43min,63min 6,33jjd222222120322122122212212222104(0)min()(0)(3)(0)(0)(3)09.5(1)(0)(2)48minmin9.5

34、 0(2)(0)(1)56.565(3)(0)(0)(1)min()(1)(4xxfc xhfxchfchfxchfchffc xhf所以 2222222212205222212206)11.5 0(2)min()(2)(5)14 5(3)min()(3)(6)15.5 6xxxxfc xhfxxfc xhfxx所以 所以 所以 當(dāng)k=2時(shí)，由其中。對(duì)v2在0至之間的值分別進(jìn)行計(jì)算。從而有清華大學(xué)出版社552.1 生產(chǎn)計(jì)劃問題 333333332330()min()()(2)xf vc xh vf vx 33min(2,6)vmin 4,6243333333333(0)14 0(1)16 03

35、(2)17.5 4(3)19 5(4)20.5 6fxfxfxfxfx所以所以或所以所以所以當(dāng)k=3時(shí)，由其中。對(duì)v3在0至之間的值分別進(jìn)行計(jì)算，從而有清華大學(xué)出版社562.1 生產(chǎn)計(jì)劃問題 1444434044343434343(0)min()(0)(4)(0)(4)020.5(1)(3)4 19min(2)(2)min 5 17.520.5 406 16(3)(1)7 14(4)(0)xfc xhfxcfcfcfxcfcf所以12345,0,6,0 xxxx當(dāng)k=4時(shí)，因要求第4時(shí)期之末的庫存量為0，即v4=0，故有再按計(jì)算的順序反推算，可找出每個(gè)時(shí)期的最優(yōu)生產(chǎn)決策為： 其相應(yīng)的最小總成本

36、為20.5千元。清華大學(xué)出版社572.1 生產(chǎn)計(jì)劃問題 把上面例題中的有關(guān)數(shù)據(jù)列成表9-6，可找出一些規(guī)律性的東西。階段i01234需求量di2324生產(chǎn)量xi5060庫存量vi03040由表中的數(shù)字可以看到，這類庫存問題有如下特征：(1) 對(duì)每個(gè)i，有vi-1xi0，（i1，2，3，4）其中v0=0。(2) 對(duì)于最優(yōu)生產(chǎn)決策來說，可分解為兩個(gè)子問題：一個(gè)是從第1階段到第2階段；另一個(gè)是從第3階段到第4階段。每個(gè)子問題的最優(yōu)生產(chǎn)決策特別簡單，它們的最小總成本之和就等于原問題的最小總成本。表9-6清華大學(xué)出版社582.1 生產(chǎn)計(jì)劃問題 1,nxxx如果對(duì)每個(gè)i，都有vi-1xi=0，則稱該點(diǎn)的生

37、產(chǎn)決策(或稱一個(gè)策略 )具有再生產(chǎn)點(diǎn)性質(zhì)(又稱重生性質(zhì))。如果vi=0，則稱階段i為再生產(chǎn)點(diǎn)再生產(chǎn)點(diǎn)(又稱重生點(diǎn)重生點(diǎn))。由假設(shè)v0=0和vn=0 ，故階段0和n是再生產(chǎn)點(diǎn)?？梢宰C明：若庫存問題的目標(biāo)函數(shù)g(x)在凸集合S上是凹函數(shù)(或凸函數(shù))，則g(x)在S的頂點(diǎn)上具有再生產(chǎn)點(diǎn)性質(zhì)的最優(yōu)策略。下面運(yùn)用再生產(chǎn)點(diǎn)再生產(chǎn)點(diǎn)性質(zhì)來求庫存問題為凹函數(shù)的解。111( , )(0)iiiijssstsjsjsjt sc j icdchd 設(shè)c(j,i) (ji)為階段j到階段i的總成本，給定j1和i是再生產(chǎn)點(diǎn)，并且階段j到階段i期間的產(chǎn)品全部由階段j供給。則根據(jù)兩個(gè)再生點(diǎn)之間的最優(yōu)策略，可以得到一個(gè)更有效

38、的動(dòng)態(tài)規(guī)劃遞推關(guān)系式。清華大學(xué)出版社592.1 生產(chǎn)計(jì)劃問題 11min( , ) 1,2,tjj iffc j iin 00f 12, , , nfff1( ) 11min( , )( ( ), )njj nj nffc j nfc j n n 設(shè)最優(yōu)值函數(shù)fi表示在階段i末庫存量vi=0時(shí)，從階段1到階段i的最小成本。則對(duì)應(yīng)的遞推關(guān)系式為邊界條件為為了確定最優(yōu)生產(chǎn)決策，逐個(gè)計(jì)算 。則fn(0)為n個(gè)階段的最小總成本。設(shè)j(n)為計(jì)算fn時(shí)，使(9-7)式右邊最小的j值，即清華大學(xué)出版社602.1 生產(chǎn)計(jì)劃問題 ( )( )0 ( ) 1, ( )2, njssj nsx ndxsj nj

39、nn當(dāng)時(shí)()( )0 ( ) 1, ( )2, mjssj msx ndxsj mj mm當(dāng)時(shí)( ) 1j m 則從階段j(n)到階段n的最優(yōu)生產(chǎn)決策為：故階段j(n)-1為再生產(chǎn)點(diǎn)。為了進(jìn)一步確定階段j(n)1到階段1的最優(yōu)生產(chǎn)決策，記m=j(n)1，而j(m)是在計(jì)算fm時(shí)，使(9-7)式右邊最小的j值，則從階段j(m)到階段j(n)的最優(yōu)生產(chǎn)決策為：故階段為再生產(chǎn)點(diǎn)，其余依此類推。 清華大學(xué)出版社612.1 生產(chǎn)計(jì)劃問題 0 0( )3 1,2,6( )0.5 6iiiiiiiiixc xxxh vvx 。和( , ), 1, 1,2,3,4c j ijii(1,1)(2)(0)5(1,

40、2)(5)(3)350.5 39.5(1,3)(7)(5)(2)0.5 50.5 2(1,4)(11)(9)(6)(4)(2,2)(3)(0)6 (2,3)(5)(2 )9(2,4)(9)(6)(4) (3cchcchcchhcchhhcchcchcchhc ,3)(2)(0)5(3,4)(6)(4)11 (4,4)(4)7chcchcc例例4 利用再生產(chǎn)點(diǎn)性質(zhì)解例3。解：解： 因都是凹函數(shù)，故可利用再生產(chǎn)點(diǎn)性質(zhì)來計(jì)算。(1) 按(9-6)式計(jì)算 清華大學(xué)出版社622.1 生產(chǎn)計(jì)劃問題 01020130120(1,1)055 (1)1min(1,2),(2,2)min 09.5,569.5 (

41、2)1min(1,3),(2,3),(3,3)min 0,59fffcjffcfcjffcfcfc 所以 所以 40123,9.5514 (3)2min(1,4),(2,4),(3,4),(4,4)min 0,5,9.511,14720.5 (4)3jffcfcfcfcj 所以 所以(4)3j33446,0 xddx(4) 13 12mj ( )(2)1j mj11225,0 xddx12345,0,6,0 xxxx(2) 按(9-7)式和(9-8)式計(jì)算fi(3) 找出最優(yōu)生產(chǎn)決策由 ，故因 所以故 所以最優(yōu)生產(chǎn)決策為：相應(yīng)的最小總成本為20.5千元。 清華大學(xué)出版社632.1 生產(chǎn)計(jì)劃問題

42、 例例5 某車間需要按月在月底供應(yīng)一定數(shù)量的某種部件給總裝車間，由于生產(chǎn)條件的變化，該車間在各月份中生產(chǎn)每單位這種部件所需耗費(fèi)的工時(shí)不同，各月份的生產(chǎn)量于當(dāng)月的月底前，全部要存入倉庫以備后用。已知總裝車間的各個(gè)月份的需求量以及在加工車間生產(chǎn)該部件每單位數(shù)量所需工時(shí)數(shù)如表9-7所示。月份k0123456需求量dk0853274單位工時(shí)ak111813172010設(shè)倉庫容量限制為H=0，開始庫存量為2，期終庫存量為0，需要制定一個(gè)半年的逐月生產(chǎn)計(jì)劃，既使得滿足需要和庫容量的限制，又使得生產(chǎn)這種部件的總耗費(fèi)工時(shí)數(shù)為最少。表9-7清華大學(xué)出版社642.1 生產(chǎn)計(jì)劃問題 1 0,1,6kkkkssudk

43、kkdsH1():0,kkkkkkkkD su udsudH解解: 按月份劃分階段，用可表示月份序號(hào)。設(shè)狀態(tài)變量sk為第k段開始時(shí)(本段需求量送出之前，上段產(chǎn)品送入之后)部件庫存量。決策變量uk為第k段內(nèi)的部件生產(chǎn)量。狀態(tài)轉(zhuǎn)移方程：且故允許決策集合為清華大學(xué)出版社652.1 生產(chǎn)計(jì)劃問題 ()kkfs1()77()min() , 0,1,6()0kkkkkkkkkkkuDsfsa ufsudkfs664sd最優(yōu)值函數(shù) 表示在第k段開始的庫存量為sk時(shí)，從第k段至第6段所生產(chǎn)部件的最小累計(jì)工時(shí)數(shù)。因而可寫出逆推關(guān)系式為當(dāng)k=6時(shí)，因要求期終庫存量為0，即s7=0 。因每月的生產(chǎn)是供應(yīng)下月的需要，

44、故第6個(gè)月不用生產(chǎn)，即u6=0。因此f6(s6)=0，而由(9-9)式有6555ssud5511us5555555511( )min ()10(11)110 10usf sa uss*5511us當(dāng)k=5時(shí)，由(9-9)式有故及最優(yōu)解清華大學(xué)出版社662.1 生產(chǎn)計(jì)劃問題 4444444445444()44444()min()min 20110 10(2)min 10-10130uDsuufsa uf sudusuus5444dsudH444911sus40u 444max 0,911sus49s 44()D s444911sus44444()10(9) 1013022020fssss*449

45、us當(dāng)k=4時(shí)，有其中u4的允許決策集合D4(s4)由(9-11)式確定為由，故有又，因而而由(9-10)式知：，所以為故得及最優(yōu)解清華大學(xué)出版社672.1 生產(chǎn)計(jì)劃問題 3333333334333()33333( )min()min 1722020(3)min320280uDsuuf sa ufsudusuus333max 0,512sus333( )244 17f ss*3312us222222223222()22()min()min417329uDsufsa uf sudus222max 0,814sus222()273 13fss*2214us當(dāng)k=3時(shí)，由(9-11)式得D3(s3)

46、為故得及最優(yōu)解當(dāng)k=2時(shí)，其中D2(s2)為故得 及最優(yōu)解清華大學(xué)出版社682.1 生產(chǎn)計(jì)劃問題 1111111 12111()11( )min()min 5-13377uD suf saufsudus1111317sus111( )442 18f ss*1113us000000001000()00()min()min7442 18uDsufsa uf sudus00089sus000()379 11fss*009us*0123457,4,9,3,0,4uuuuuu當(dāng)k=1時(shí)，其中D1(s1)為故得及最優(yōu)解當(dāng)k=0時(shí)，其中D0(s0)為故得及最優(yōu)解因s0=2，所以f0=357和u0*=7再按計(jì)

47、算順序反推，即得各階段最優(yōu)決策為：所以，0至5月最優(yōu)生產(chǎn)計(jì)劃為：7，4，9，3，0，4，最小總工時(shí)為357。 清華大學(xué)出版社692.2 不確定性的采購問題 在實(shí)際問題中，還會(huì)遇到某些多階段決策過程，其狀態(tài)轉(zhuǎn)移不是完全確定的，出現(xiàn)了隨機(jī)性因素，狀態(tài)轉(zhuǎn)移是按照某種已知概率分布取值的。 具有這種性質(zhì)的多階段決策過程稱為隨機(jī)性決策過程。 用動(dòng)態(tài)規(guī)劃方法也可處理這類隨機(jī)性問題，又稱為隨機(jī)性動(dòng)態(tài)規(guī)劃。清華大學(xué)出版社702.2 不確定性的采購問題 例例6 采購問題。某廠生產(chǎn)上需要在近五周內(nèi)必須采購一批原料，而估計(jì)在未來五周內(nèi)價(jià)格有波動(dòng)，其浮動(dòng)價(jià)格和概率已測得如表9-8所示。試求在哪一周以什么價(jià)格購入，使其采

48、購價(jià)格的數(shù)學(xué)期望值最小，并求出期望值。單價(jià)概率5000.36000.37000.4表9-8清華大學(xué)出版社712.2 不確定性的采購問題 5555()min, (9 13)(), (9 14)kkkkEkkkfyyyysfyyys500,600,700 , 1,2,3,4,5(9 15)ksk11111()0.3(500)0.3(600)0.4(700)(9 16)kEkkkkkyEfyfff1() ()(9 17)0() ()kkkkkkkEfyyxfyy采購當(dāng)?shù)却?dāng)解：解： 價(jià)格是一個(gè)隨機(jī)變量，按某種已知的概率分布取值。用動(dòng)態(tài)規(guī)劃方法處理，按采購期限5周分為5個(gè)階段，將每周的價(jià)格看作該階段的

49、狀態(tài)。設(shè)yk狀態(tài)變量，表示第k周的實(shí)際價(jià)格。xk決策變量，xk=1時(shí)表示第k周決定采購；xk=0時(shí)表示第k周決定等待。ykE第k周決定等待，而在以后采取最優(yōu)決策時(shí)采購價(jià)格的期望值。fk(yk)第k周實(shí)際價(jià)格為yk時(shí)，從第k周至第5周采取最優(yōu)決策所得的最小期望值因而可寫出逆序遞推關(guān)系式為其中由ykE和fk(yk)的定義可知：并且得出最優(yōu)決策為：清華大學(xué)出版社722.2 不確定性的采購問題 55555(),fyyys555(500)500,(600)600,(700)700fff45550.3(500)0.3(600)0.4(700)0.3 5000.3 6000.4 700610Eyfff444

50、444444444()min,min,610500 500600 600610 700Eysysfyyyyyyy若 若 若 4441() 500 6000() 700yxy采購若 或等待若 從最后一周開始，逐步向前遞推計(jì)算，具體計(jì)算過程如下。k=5時(shí)，因，故有即在第五周時(shí)，若所需的原料尚未買入，則無論市場價(jià)格如何，都必須采購，不能再等。k=4時(shí)，由(9-16)式可知于是，由(9-13)式得由(9-17)式，第4周最優(yōu)決策為清華大學(xué)出版社732.2 不確定性的采購問題 33333333333()min,min,574500 500574 600 700Eysysfyyyyyy若 若 或3331

51、5000 600 700yxy若 若 或同理求得所以清華大學(xué)出版社742.2 不確定性的采購問題 22222222222()min,min,551.8500 500551.8 600 700Eysysfyyyyyy若 若 或2221 5000 600 700yxy若 若 或所以清華大學(xué)出版社752.2 不確定性的采購問題 11111111111()min,min,536.26500 500536.26 600 700Eysysf yy yyyy若 若 或1111 5000 600 700yxy若 若 或所以由上可知，最優(yōu)采購策略為：在第一、二、三周時(shí)，若價(jià)格為500就采購，否則應(yīng)該等待；在第四

52、周時(shí)，價(jià)格為500或600應(yīng)采購，否則就等待；在第五周時(shí)，無論什么價(jià)格都要采購。清華大學(xué)出版社762.2 不確定性的采購問題 23333500 0.3 1 0.70.70.70.70.4 600 0.3 0.70.4 0.7700 0.42 0.73 500 0.80106600 0.14406700 0.05488 525.3825250.801060.144060.054881依照上述最優(yōu)策略進(jìn)行采購時(shí)，價(jià)格(單價(jià))的數(shù)學(xué)期望值為且清華大學(xué)出版社77第3節(jié) 背 包 問 題 有一個(gè)人帶一個(gè)背包上山，其可攜帶物品重量的限度為a公斤。設(shè)有n種物品可供他選擇裝入背包中，這n種物品編號(hào)為1，2，n。

53、已知第i種物品每件重量為wi公斤，在上山過程中的作用(價(jià)值)是攜帶數(shù)量xi的函數(shù)ci(xi)。問此人應(yīng)如何選擇攜帶物品(各幾件)，使所起作用(總價(jià)值)最大。這就是著名的背包問題。 類似的問題有工廠里的下料問題，運(yùn)輸中的貨物裝載問題，人造衛(wèi)星內(nèi)的物品裝載問題等等。清華大學(xué)出版社78第3節(jié) 背 包 問 題11max ( )0 (1,2, )niiiniiiifc xw xaxin且為整數(shù)設(shè)xi為第i種物品的裝入件數(shù)，則問題的數(shù)學(xué)模型為它是一個(gè)整數(shù)規(guī)劃問題。如果xi只取0或1，又稱為01背包問題。下面用動(dòng)態(tài)規(guī)劃方法來求解。 清華大學(xué)出版社79第3節(jié) 背 包 問 題kkwwx w( )0kkkkwD

54、wxxw110(1,2, )( )max()kiiiikkiiiw xwxikfwc x且為整數(shù)設(shè)按可裝入物品的n種類劃分為n個(gè)階段。狀態(tài)變量w表示用于裝第1種物品至第k種物品的總重量。決策變量xk表示裝入第k種物品的件數(shù)。則狀態(tài)轉(zhuǎn)移方程為允許決策集合為最優(yōu)值函數(shù)fk(w)是當(dāng)總重量不超過w公斤，背包中可以裝入第1種到第k種物品的最大使用價(jià)值。即 清華大學(xué)出版社80第3節(jié) 背 包 問 題11111110,1,/10,1,/( )max( )( )max()() 2xw wkkkkkkxw wf wc xf wc xfww xkn-因而可寫出動(dòng)態(tài)規(guī)劃的順序遞推關(guān)系為： 12( ),( ),( )

55、nf wfwfw12( ),( ),( )nx w x wx w( )nfa然后，逐步計(jì)算出及相應(yīng)的決策函數(shù)最后得出的就是所求的最大價(jià)值，其相應(yīng)的最優(yōu)策略由反推運(yùn)算即可得出。清華大學(xué)出版社81第3節(jié) 背 包 問 題 123123max 4563451001,2,3ifxxxxxxxi且為整數(shù)，1231233123331233123345100,1,2,31233410 50,1,2,331210 5034510 50,0,0,3230,1,2(10)max456max45(6)max6max45max 6(105)max 0iixxxxixxxxixxxxxxxxxfxxxxxxxxxxfx整

56、數(shù)，整數(shù)，整數(shù)整數(shù)222(10),6(5),12(0)fff例例7解解:用動(dòng)態(tài)規(guī)劃方法來解，此問題變?yōu)榍骹3(10)。清華大學(xué)出版社82第3節(jié) 背 包 問 題 202(10),(5),(0)fff12121212212212121234100,0,12310 40,0,2110 40310 40,0,2120,1,2111234(10)max45max4(5)max5max (4 )max 5(104)max(10),5(6),10(2)(5)maxxxxxxxxxxxxxxxxxfxxxxxxxfxffff整數(shù)整數(shù)整數(shù)整數(shù)2212122121221250,10,0,1121221213400

57、0,0,45max 5(54)max(5),5(1)(0)max45max 5(04)(0)xxxxxxxxxxxfxfffxxxfxf整數(shù)整數(shù)由此看到，要計(jì)算f3(10) ，必須先計(jì)算出清華大學(xué)出版社83第3節(jié) 背 包 問 題 111130,( )max (4 )4 (/3)4/3xwxf wxww整數(shù)不超過的最大整數(shù)111111111111(10)4 312 (3)(6)4 28 (2)(5)4 14 (1)(2)4 00 (0)(1)4 00 (0)(0)4 00 (0)fxfxfxfxfxfx 為了要計(jì)算出f2(10),f2(5),f2(0) ，必須先計(jì)算出f1(10),f1(6),f

58、1(5),f1(2),f1(1),f1(0) ，一般地有相應(yīng)的最優(yōu)決策為x1=w/3，于是得到清華大學(xué)出版社84第3節(jié) 背 包 問 題 2112122111221(10)max(10),5(6),10(0)max 12,58,10013 (2,1)(5)max(5),5(1)max 4,505 (0,1)(0)(0)0 ffffxxfffxxff12 (0,0)xx3222123(10)max(10),6(5),12(0)max 13,65,12013 (2,1, 0)ffffxxx*1232,1,0 xxx從而故最后得到所以，最優(yōu)裝入方案為最大使用價(jià)值為13。 清華大學(xué)出版社85第3節(jié) 背

59、包 問 題 111max ( )0,1,2,niiiniiiniiiifc xw xav xbxin整數(shù)， 如果再增加對(duì)背包體積的限制為b，并假設(shè)第i種物品每件的體積為vi立方米，問應(yīng)如何裝使得總價(jià)值最大。這就是“二維背包問題”，它的數(shù)學(xué)模型為清華大學(xué)出版社86第3節(jié) 背 包 問 題 ( , )kfw v110,1,2,1( , )max( )ki iiki iixikikkiiiw xwv xvfw vc x整數(shù)10min,0( , )max()(,) 1( , )0kkkkkkkkkkkwvxwvfw vcxfww x vv xknfw v ( , )nfa b用動(dòng)態(tài)規(guī)劃方法來解。這時(shí)，狀

60、態(tài)變量是兩個(gè)(重量和體積的限制)，決策變量仍是一個(gè)(物品的件數(shù))。設(shè)最優(yōu)值函數(shù)為 表示當(dāng)總重量不超過w公斤，總體積不超過v立方米時(shí)，背包中裝入第1種到第k種物品的最大使用價(jià)值。故因而可寫出順序遞推關(guān)系式為最后算出即為所求的最大價(jià)值。清華大學(xué)出版社87第4節(jié)復(fù)合系統(tǒng)工作可靠性問題 若某種機(jī)器的工作系統(tǒng)由n個(gè)部件串聯(lián)組成，只要有一個(gè)部件失靈，整個(gè)系統(tǒng)就不能工作。為提高系統(tǒng)工作的可靠性，在每一個(gè)部件上均裝有主要元件的備用件，并且設(shè)計(jì)了備用元件自動(dòng)投入裝置。顯然，備用元件越多，整個(gè)系統(tǒng)正常工作的可靠性越大。但備用元件多了，整個(gè)系統(tǒng)的成本、重量、體積均相應(yīng)加大，工作精度也降低。因此，最優(yōu)化問題是在考慮上