下面運(yùn)用再生產(chǎn)點(diǎn)性質(zhì)來(lái)求庫(kù)存問(wèn)題為凹函數(shù)的解課件

1、第10章 動(dòng)態(tài)規(guī)劃應(yīng)用舉例第1節(jié) 資源分配問(wèn)題第2節(jié) 生產(chǎn)與存儲(chǔ)問(wèn)題第3節(jié)* 背包問(wèn)題第4節(jié)* 復(fù)合系統(tǒng)工作可靠性問(wèn)題第5節(jié) 排序問(wèn)題第6節(jié) 設(shè)備更新問(wèn)題第7節(jié)* 貨郎擔(dān)問(wèn)題清華大學(xué)出版社1第1節(jié) 資源分配問(wèn)題所謂分配問(wèn)題，就是將數(shù)量一定的一種或若干種資源(例如原材料、資金、機(jī)器設(shè)備、勞力、食品等等)，恰當(dāng)?shù)胤峙浣o若干個(gè)使用者，而使目標(biāo)函數(shù)為最優(yōu)。清華大學(xué)出版社21.1資源分配問(wèn)題設(shè)有某種原料，總數(shù)量為a，用于生產(chǎn)n種產(chǎn)品。若分配數(shù)量xi用于生產(chǎn)第i種產(chǎn)品，其收益為問(wèn)應(yīng)如何分配，才能使生產(chǎn)n產(chǎn)品的總收入最大?此問(wèn)題可寫(xiě)成靜態(tài)規(guī)劃問(wèn)題：當(dāng)都是線性函數(shù)時(shí)，它是一個(gè)線性規(guī)劃問(wèn)題；當(dāng)是非線性函數(shù)時(shí)，它

2、是一個(gè)非線性規(guī)劃問(wèn)題。但當(dāng)n比較大時(shí)，具體求解是比較麻煩的。由于這類(lèi)問(wèn)題的特殊結(jié)構(gòu)，可以將它看成一個(gè)多階段決策問(wèn)題，并利用動(dòng)態(tài)規(guī)劃的遞推關(guān)系來(lái)求解。清華大學(xué)出版社31.1資源分配問(wèn)題 在應(yīng)用動(dòng)態(tài)規(guī)劃方法處理這類(lèi)“靜態(tài)規(guī)劃”問(wèn)題時(shí)，通常以把資源分配給一個(gè)或幾個(gè)使用者的過(guò)程作為一個(gè)階段，把問(wèn)題中的變量xi為決策變量，將累計(jì)的量或隨遞推過(guò)程變化的量選為狀態(tài)變量。清華大學(xué)出版社41.1資源分配問(wèn)題設(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種

3、產(chǎn)品所得到的最大總收入。因而可寫(xiě)出動(dòng)態(tài)規(guī)劃的逆推關(guān)系式為：利用這個(gè)遞推關(guān)系式進(jìn)行逐段計(jì)算，最后求得 即為所求問(wèn)題的最大總收入。 清華大學(xué)出版社51.1資源分配問(wèn)題例1 某工業(yè)部門(mén)根據(jù)國(guó)家計(jì)劃的安排，擬將某種高效率的設(shè)備五臺(tái)，分配給所屬的甲、乙、丙三個(gè)工廠，各工廠若獲得這種設(shè)備之后，可以為國(guó)家提供的盈利如表9-1所示。問(wèn)：這五臺(tái)設(shè)備如何分配給各工廠，才能使國(guó)家得到的盈利最大。 清華大學(xué)出版社61.1資源分配問(wèn)題解: 將問(wèn)題按工廠分為三個(gè)階段，甲、乙、丙三個(gè)工廠分別編號(hào)為1、2、3設(shè)sk表示為分配給第k個(gè)工廠至第n個(gè)工廠的設(shè)備臺(tái)數(shù)。xk表示為分配給第k個(gè)工廠的設(shè)備臺(tái)數(shù)。則為分配給第k+1個(gè)工廠至第

4、n個(gè)工廠的設(shè)備臺(tái)數(shù)。表示為sk臺(tái)設(shè)備分配到第k個(gè)工廠所得的盈利值。表示為sk臺(tái)設(shè)備分配給第k個(gè)工廠至第n個(gè)工廠時(shí)所得到的最大盈利值。因而可寫(xiě)出逆推關(guān)系式為清華大學(xué)出版社71.1資源分配問(wèn)題下面從最后一個(gè)階段開(kāi)始向前逆推計(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*012345000014412662311113412124512125表中x3*表示使f3(s3)為最大值時(shí)的最

5、優(yōu)決策。清華大學(xué)出版社81.1資源分配問(wèn)題第二階段：設(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é)出版社91.1資源分配問(wèn)題表9-3012345000010+45+05120+65+410+010230+115+610+411+014240+125+1110+611+411+0161,250+125+1210+1111+611+411+0212

6、清華大學(xué)出版社101.1資源分配問(wèn)題第一階段：設(shè)把s1臺(tái)(這里只有s1=5的情況)設(shè)備分配給甲、乙、丙三個(gè)工廠時(shí)，則最大盈利值為其中因?yàn)榻o甲工廠x1臺(tái)，其盈利為p1(x1) ，剩下的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é)出版社111.1資源分配問(wèn)題然后按計(jì)算表格的順序反推算，可知最優(yōu)分配方案有兩個(gè)：(1) 由于x1*=0 ，根據(jù)查表9-3知x2*=2，由故即得甲工廠分配0臺(tái)，乙工廠分配2臺(tái)，丙工廠分配

7、3臺(tái)。(2) 由于x1*=2，根據(jù)查表9-3知x2*=2，由故即得甲工廠分配2臺(tái)，乙工廠分配2臺(tái)，丙工廠分配1臺(tái)。以上兩個(gè)分配方案所得到的總盈利均為21萬(wàn)元。 清華大學(xué)出版社121.1資源分配問(wèn)題資源連續(xù)分配問(wèn)題設(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)系式。顯然，這時(shí)狀態(tài)轉(zhuǎn)移方程為k段的指標(biāo)函數(shù)為令fk(sk)

8、表示由狀態(tài)sk出發(fā)，從第k年至第n年末時(shí)所生產(chǎn)的產(chǎn)品的總產(chǎn)量最大值。清華大學(xué)出版社231.1資源分配問(wèn)題可寫(xiě)出逆推關(guān)系式為：我們知道，在低負(fù)荷下生產(chǎn)的時(shí)間愈長(zhǎng)，機(jī)器完好率愈高，但生產(chǎn)產(chǎn)量少。而在高負(fù)荷下生產(chǎn)產(chǎn)量會(huì)增加，但機(jī)器損壞大。這樣，即使每臺(tái)產(chǎn)量高，總起來(lái)看產(chǎn)量也不高。 清華大學(xué)出版社241.1資源分配問(wèn)題從前面的數(shù)字計(jì)算可以看出，前幾年一般是全部用于低負(fù)荷生產(chǎn)，后幾年則全部用于高負(fù)荷生產(chǎn)，這樣才產(chǎn)量最高。如果總共為n年，從低負(fù)荷轉(zhuǎn)為高負(fù)荷生產(chǎn)的是第t年，1tn。即是說(shuō)，從1至t1年在低負(fù)荷下生產(chǎn)，t至n年在高負(fù)荷下生產(chǎn)?，F(xiàn)在要分析t與系數(shù)a、b、c、d是什么關(guān)系。從回收率看，(b a)值

9、愈大，表示在高負(fù)荷下生產(chǎn)時(shí)，機(jī)車(chē)損壞情況比在低負(fù)荷時(shí)嚴(yán)重得多，因此t值應(yīng)選大些。從產(chǎn)量看，(c d)值愈大，表示在高負(fù)荷下生產(chǎn)較有利，故t應(yīng)選小些。下面我們從(9-2)式這一基本方程出發(fā)來(lái)求出t與(b a)、(c d)的關(guān)系。清華大學(xué)出版社251.1資源分配問(wèn)題令。則在低負(fù)荷生產(chǎn)時(shí)有，高負(fù)荷生產(chǎn)時(shí)有對(duì)第n段，有由于cd，所以應(yīng)選1才能使最大。也就是說(shuō)，最后一年應(yīng)全部投入高負(fù)荷生產(chǎn)。故清華大學(xué)出版社261.1資源分配問(wèn)題對(duì)n-1段，根據(jù)(9-2)式有因此，欲要滿足上式極值關(guān)系的條件是當(dāng)時(shí)，應(yīng)取即n 1年仍應(yīng)全部在高負(fù)荷下生產(chǎn)。否則，當(dāng)(9-4)式不滿足時(shí)，應(yīng)取即n 1年應(yīng)全部投入低負(fù)荷生產(chǎn)。清華

10、大學(xué)出版社271.1資源分配問(wèn)題由前面知道，只要在第k年投入低負(fù)荷生產(chǎn)，那么遞推計(jì)算結(jié)果必然是從第1年到第k年均為低負(fù)荷生產(chǎn)，即有 可見(jiàn)，算出后 ，前幾年就沒(méi)有必要再計(jì)算了。故只需研究哪一年由低負(fù)荷轉(zhuǎn)入高負(fù)荷生產(chǎn)，即從 那一年開(kāi)始變?yōu)?就行。 根據(jù)這點(diǎn)，現(xiàn)只分析滿足(9-4)式的情況。由于故(9-3)式變?yōu)橛钟捎趯⑺肷鲜降?清華大學(xué)出版社281.1資源分配問(wèn)題對(duì)n-2段，由(9-2)式有由此可知，只要滿足極值條件式就應(yīng)選否則為0，即應(yīng)繼續(xù)在高負(fù)荷下生產(chǎn)。 清華大學(xué)出版社291.1資源分配問(wèn)題依次類(lèi)推，如果轉(zhuǎn)入高負(fù)荷下生產(chǎn)的是第t年，則由可以推出，應(yīng)滿足極值關(guān)系的條件必然是：相應(yīng)的有最優(yōu)策略

11、它就是例2在始端固定終端自由情況下最優(yōu)策略的一般結(jié)果。 從本例可看出，應(yīng)用動(dòng)態(tài)規(guī)劃，可以在不求出數(shù)值解的情況下，確定最優(yōu)策略的結(jié)構(gòu)。清華大學(xué)出版社301.1資源分配問(wèn)題例如，只要知道了a,b,c,d四個(gè)值，就總可找到一個(gè)t值，滿足(9-5)式，且例如題中給定的代入(9-5)式，應(yīng)有可見(jiàn)所以t=3，即從第三年開(kāi)始將全部機(jī)器投入高負(fù)荷生產(chǎn)，五年內(nèi)總產(chǎn)量最高。清華大學(xué)出版社311.1資源分配問(wèn)題上面的討論表明：當(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)和最

12、優(yōu)解；若g(x)和h(x)不是線性函數(shù)或凸函數(shù)時(shí)，一般來(lái)說(shuō)，解析法不能奏效，那只好利用遞推關(guān)系式(91)求其數(shù)值解。首先要把問(wèn)題離散化，即把區(qū)間0，s1進(jìn)行分割，令x=0，2，m=s1。其的大小，應(yīng)根據(jù)計(jì)算精度和計(jì)算機(jī)容量等來(lái)確定。然后規(guī)定所有的fk(x)和決策變量只在這些分割點(diǎn)上取值。這樣，遞推關(guān)系式(9-1)便可寫(xiě)為清華大學(xué)出版社321.1資源分配問(wèn)題對(duì)依次計(jì)算，可逐步求出及相應(yīng)的最優(yōu)決策，最后求得就是所求的最大總收入。這種離散化算法可以編成程序在計(jì)算機(jī)中計(jì)算。 清華大學(xué)出版社331.2 二維資源分配問(wèn)題 設(shè)有兩種原料，數(shù)量各為a和b單位，需要分配用于生產(chǎn)n種產(chǎn)品。如果第一種原料以數(shù)量xi

13、為單位，第二種原料以數(shù)量yi為單位，用于生產(chǎn)第i種產(chǎn)品，其收入為問(wèn)應(yīng)如何分配這兩種原料于n種產(chǎn)品的生產(chǎn)使總收入最大?此問(wèn)題可寫(xiě)成靜態(tài)規(guī)劃問(wèn)題：清華大學(xué)出版社341.2 二維資源分配問(wèn)題 用動(dòng)態(tài)規(guī)劃方法來(lái)解，狀態(tài)變量和決策變量要取二維的。設(shè)狀態(tài)變量(x,y):x分配用于生產(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)系：式中和分別表示用來(lái)生產(chǎn)第k+1種產(chǎn)品至第n種產(chǎn)品的第一種和第二種原料的單位數(shù)量。清華大學(xué)出版社351.2 二

14、維資源分配問(wèn)題 允許決策集合： 表示以第一種原料數(shù)量為x單位，第二種原料數(shù)量為y單位，分配用于生產(chǎn)第k種產(chǎn)品至第n種產(chǎn)品時(shí)所得到的最大收入。故可寫(xiě)出逆推關(guān)系為最后求得即為所求問(wèn)題的最大收入。 清華大學(xué)出版社361.2 二維資源分配問(wèn)題 1. 拉格朗日乘數(shù)法引入拉格朗日乘數(shù)，將二維分配問(wèn)題化為滿足條件其中作為一個(gè)固定的參數(shù)。令于是問(wèn)題變?yōu)闈M足且為整數(shù)清華大學(xué)出版社371.2 二維資源分配問(wèn)題 這是一個(gè)一維分配問(wèn)題，可用對(duì)一維的方法去求解。這里，由于是參數(shù)，因此，最優(yōu)解xi 參數(shù)的函數(shù)，相應(yīng)的yi也是的函數(shù)。即為其解。如果則可證明為原問(wèn)題的最優(yōu)解。如果將調(diào)整的值(利用插值法逐漸確定 )，直到滿足為

15、止。這樣的降維方法在理論上有保證，在計(jì)算上是可行的，故對(duì)高維問(wèn)題，可用上述拉格朗日乘數(shù)法的思想來(lái)降低維數(shù)。清華大學(xué)出版社381.2 二維資源分配問(wèn)題 2. 逐次逼近法這是另一種降維方法，先保持一個(gè)變量不變，對(duì)另一個(gè)變量實(shí)現(xiàn)最優(yōu)化。然后交替地固定，以迭代的形式反復(fù)進(jìn)行，直到獲得某種要求為止。先設(shè)為滿足的一個(gè)可行解，固定x在x(0) ，先對(duì)y求解，則二維分配問(wèn)題變?yōu)橐痪S問(wèn)題：可用對(duì)一維的方法來(lái)求解。設(shè)這解為然后再固定y為y(0) ，對(duì)x求解，即清華大學(xué)出版社391.2 二維資源分配問(wèn)題 設(shè)其解為再固定x為x(1)，對(duì)y求解，這樣依次輪換下去得到一系列的解因?yàn)楣屎瘮?shù)值序列是單調(diào)上升的，但不一定收斂到

16、絕對(duì)的最優(yōu)解，一般只收斂到某一局部最優(yōu)解。因此，在實(shí)際計(jì)算時(shí)，可選擇幾個(gè)初始點(diǎn)x(0)進(jìn)行計(jì)算，然后從所得到的幾個(gè)局部最優(yōu)解中選出一個(gè)最好的。清華大學(xué)出版社401.2 二維資源分配問(wèn)題 3 粗格子點(diǎn)法(疏密法) 在采用離散化的方法計(jì)算時(shí)，先將矩形定義域：0 xa,0yb分成網(wǎng)格，然后在這些格子點(diǎn)上進(jìn)行計(jì)算。如將a、b各分為m1和m2等份，則總共有(m1+1)(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ù)問(wèn)題要求的精確度，采用粗格子點(diǎn)法逐步縮小區(qū)域

17、來(lái)減少計(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é)出版社411.3 固定資金分配問(wèn)題設(shè)有n個(gè)生產(chǎn)行業(yè)，都需要某兩種資源。對(duì)于第k個(gè)生產(chǎn)行業(yè)，如果用第1種資源xk和第2種資源yk進(jìn)行生產(chǎn)，可獲得利潤(rùn)為若第1種資源的單位價(jià)格為a ，第2種資源的單位價(jià)格為b，現(xiàn)有資金Z 。問(wèn)應(yīng)購(gòu)買(mǎi)第1種資源多少單位(設(shè)為X)，第2種資源多少單位(設(shè)為Y)，分配到n個(gè)生產(chǎn)行業(yè)，使總利潤(rùn)最大?此問(wèn)

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

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

20、制；每階段社會(huì)對(duì)該產(chǎn)品的需求量是已知的，公司保證供應(yīng)；在n階段末的終結(jié)庫(kù)存量為零。問(wèn)該公司如何制定每個(gè)階段的生產(chǎn)(或采購(gòu))計(jì)劃，從而使總成本最小。清華大學(xué)出版社462.1 生產(chǎn)計(jì)劃問(wèn)題 設(shè)dk為第k階段對(duì)產(chǎn)品的需求量，xk為第k階段該產(chǎn)品的生產(chǎn)量(或采購(gòu)量)，vk為第k階段結(jié)束時(shí)的產(chǎn)品庫(kù)存量。則有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í)有庫(kù)存量vk所需的存儲(chǔ)費(fèi)用。k階段的成本費(fèi)用為m表示每階段最多能生產(chǎn)該產(chǎn)品的上限數(shù)。 清華大學(xué)出版社472.1 生產(chǎn)計(jì)劃問(wèn)題 上述問(wèn)題的數(shù)學(xué)模型為

21、用動(dòng)態(tài)規(guī)劃方法來(lái)求解，可看作一個(gè)n階段決策問(wèn)題。令vk-1為狀態(tài)變量，它表示第k階段開(kāi)始時(shí)的庫(kù)存量。xk為決策變量，它表示第k階段的生產(chǎn)量。狀態(tài)轉(zhuǎn)移方程為最優(yōu)值函數(shù)fk(xk)表示從第1階段初始庫(kù)存量為0到第k階段末庫(kù)存量為vk時(shí)的最小總費(fèi)用。清華大學(xué)出版社482.1 生產(chǎn)計(jì)劃問(wèn)題 順序遞推關(guān)系式為：其中。這是因?yàn)橐环矫婷侩A段生產(chǎn)的上限為m；另一方面由于保證供應(yīng)，故第k-1階段末的庫(kù)存量vk-1必須非負(fù)，即所以邊界條件為 或從邊界條件出發(fā)，利用上面的遞推關(guān)系式，對(duì)每個(gè)k ，計(jì)算出fk(vk)中的vk在0至之間的值，最后求得的fn(0)即為所求的最小總費(fèi)用。清華大學(xué)出版社492.1 生產(chǎn)計(jì)劃問(wèn)題

22、 例3 某工廠要對(duì)一種產(chǎn)品制訂今后四個(gè)時(shí)期的生產(chǎn)計(jì)劃，據(jù)估計(jì)在今后四個(gè)時(shí)期內(nèi)，市場(chǎng)對(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)批量為不超過(guò)6個(gè)單位；每個(gè)時(shí)期末未售出的產(chǎn)品，每單位需付存儲(chǔ)費(fèi)0.5千元。還假定在第一個(gè)時(shí)期的初始庫(kù)存量為0，第四個(gè)時(shí)期之末的庫(kù)存量也為0。試問(wèn)該廠應(yīng)如何安排各個(gè)時(shí)期的生產(chǎn)與庫(kù)存，才能在滿足市場(chǎng)需要的條件下，使總成本最小。表9-5清華大學(xué)出版社502.1 生產(chǎn)計(jì)劃問(wèn)題 解: 用動(dòng)態(tài)規(guī)劃方法來(lái)求解，其符號(hào)含義與上面相同。按四個(gè)時(shí)期將

23、問(wèn)題分為四個(gè)階段。由題意知，在第k時(shí)期內(nèi)的生產(chǎn)成本為第k時(shí)期末庫(kù)存量為vk時(shí)的存儲(chǔ)費(fèi)用為故第k時(shí)期內(nèi)的總成本為而動(dòng)態(tài)規(guī)劃的順序遞推關(guān)系式為其中和邊界條件清華大學(xué)出版社512.1 生產(chǎn)計(jì)劃問(wèn)題 當(dāng)k=1時(shí)，由對(duì)v1在0至之間的值分別進(jìn)行計(jì)算。同理得清華大學(xué)出版社522.1 生產(chǎn)計(jì)劃問(wèn)題 當(dāng)k=2時(shí)，由其中。對(duì)v2在0至之間的值分別進(jìn)行計(jì)算。從而有 清華大學(xué)出版社532.1 生產(chǎn)計(jì)劃問(wèn)題 當(dāng)k=3時(shí)，由其中。對(duì)v3在0至之間的值分別進(jìn)行計(jì)算，從而有清華大學(xué)出版社542.1 生產(chǎn)計(jì)劃問(wèn)題 當(dāng)k=4時(shí)，因要求第4時(shí)期之末的庫(kù)存量為0，即v4=0，故有再按計(jì)算的順序反推算，可找出每個(gè)時(shí)期的最優(yōu)生產(chǎn)決策為

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

25、稱(chēng)該點(diǎn)的生產(chǎn)決策(或稱(chēng)一個(gè)策略 )具有再生產(chǎn)點(diǎn)性質(zhì)(又稱(chēng)重生性質(zhì))。如果vi=0，則稱(chēng)階段i為再生產(chǎn)點(diǎn)(又稱(chēng)重生點(diǎn))。由假設(shè)v0=0和vn=0 ，故階段0和n是再生產(chǎn)點(diǎn)?？梢宰C明：若庫(kù)存問(wèn)題的目標(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)性質(zhì)來(lái)求庫(kù)存問(wèn)題為凹函數(shù)的解。設(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è)更有效的動(dòng)態(tài)規(guī)劃遞推關(guān)系式。清華大學(xué)出版社572.1 生產(chǎn)計(jì)劃問(wèn)題 設(shè)最優(yōu)值函數(shù)fi表示在階段i末

26、庫(kù)存量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é)出版社582.1 生產(chǎn)計(jì)劃問(wèn)題 則從階段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)，其余依此類(lèi)推。 清華大學(xué)出版社592.1 生產(chǎn)計(jì)劃問(wèn)題 例4 利用再生產(chǎn)點(diǎn)性質(zhì)解例3。解： 因

27、都是凹函數(shù)，故可利用再生產(chǎn)點(diǎn)性質(zhì)來(lái)計(jì)算。(1) 按(9-6)式計(jì)算 清華大學(xué)出版社602.1 生產(chǎn)計(jì)劃問(wèn)題 (2) 按(9-7)式和(9-8)式計(jì)算fi(3) 找出最優(yōu)生產(chǎn)決策由 ，故因 所以故 所以最優(yōu)生產(chǎn)決策為：相應(yīng)的最小總成本為20.5千元。 清華大學(xué)出版社612.1 生產(chǎn)計(jì)劃問(wèn)題 例5 某車(chē)間需要按月在月底供應(yīng)一定數(shù)量的某種部件給總裝車(chē)間，由于生產(chǎn)條件的變化，該車(chē)間在各月份中生產(chǎn)每單位這種部件所需耗費(fèi)的工時(shí)不同，各月份的生產(chǎn)量于當(dāng)月的月底前，全部要存入倉(cāng)庫(kù)以備后用。已知總裝車(chē)間的各個(gè)月份的需求量以及在加工車(chē)間生產(chǎn)該部件每單位數(shù)量所需工時(shí)數(shù)如表9-7所示。月份k0123456需求量dk0

28、853274單位工時(shí)ak111813172010設(shè)倉(cāng)庫(kù)容量限制為H=0，開(kāi)始庫(kù)存量為2，期終庫(kù)存量為0，需要制定一個(gè)半年的逐月生產(chǎn)計(jì)劃，既使得滿足需要和庫(kù)容量的限制，又使得生產(chǎn)這種部件的總耗費(fèi)工時(shí)數(shù)為最少。表9-7清華大學(xué)出版社622.1 生產(chǎn)計(jì)劃問(wèn)題 解: 按月份劃分階段，用可表示月份序號(hào)。設(shè)狀態(tài)變量sk為第k段開(kāi)始時(shí)(本段需求量送出之前，上段產(chǎn)品送入之后)部件庫(kù)存量。決策變量uk為第k段內(nèi)的部件生產(chǎn)量。狀態(tài)轉(zhuǎn)移方程：且故允許決策集合為清華大學(xué)出版社632.1 生產(chǎn)計(jì)劃問(wèn)題 最優(yōu)值函數(shù) 表示在第k段開(kāi)始的庫(kù)存量為sk時(shí)，從第k段至第6段所生產(chǎn)部件的最小累計(jì)工時(shí)數(shù)。因而可寫(xiě)出逆推關(guān)系式為當(dāng)k=

29、6時(shí)，因要求期終庫(kù)存量為0，即s7=0 。因每月的生產(chǎn)是供應(yīng)下月的需要，故第6個(gè)月不用生產(chǎn)，即u6=0。因此f6(s6)=0，而由(9-9)式有當(dāng)k=5時(shí)，由(9-9)式有故及最優(yōu)解清華大學(xué)出版社642.1 生產(chǎn)計(jì)劃問(wèn)題 當(dāng)k=4時(shí)，有其中u4的允許決策集合D4(s4)由(9-11)式確定為由，故有又，因而而由(9-10)式知：，所以為故得及最優(yōu)解清華大學(xué)出版社652.1 生產(chǎn)計(jì)劃問(wèn)題 當(dāng)k=3時(shí)，由(9-11)式得D3(s3)為故得及最優(yōu)解當(dāng)k=2時(shí)，其中D2(s2)為故得 及最優(yōu)解 清華大學(xué)出版社662.1 生產(chǎn)計(jì)劃問(wèn)題 當(dāng)k=1時(shí)，其中D1(s1)為故得及最優(yōu)解當(dāng)k=0時(shí)，其中D0(s0

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

31、概率已測(cè)得如表9-8所示。試求在哪一周以什么價(jià)格購(gòu)入，使其采購(gòu)價(jià)格的數(shù)學(xué)期望值最小，并求出期望值。單價(jià)概率5000.36000.37000.4表9-8清華大學(xué)出版社692.2 不確定性的采購(gòu)問(wèn)題 解： 價(jià)格是一個(gè)隨機(jī)變量，按某種已知的概率分布取值。用動(dòng)態(tài)規(guī)劃方法處理，按采購(gòu)期限5周分為5個(gè)階段，將每周的價(jià)格看作該階段的狀態(tài)。設(shè)yk狀態(tài)變量，表示第k周的實(shí)際價(jià)格。xk決策變量，xk=1時(shí)表示第k周決定采購(gòu)；xk=0時(shí)表示第k周決定等待。ykE第k周決定等待，而在以后采取最優(yōu)決策時(shí)采購(gòu)價(jià)格的期望值。fk(yk)第k周實(shí)際價(jià)格為yk時(shí)，從第k周至第5周采取最優(yōu)決策所得的最小期望值因而可寫(xiě)出逆序遞推關(guān)

32、系式為其中由ykE和fk(yk)的定義可知：并且得出最優(yōu)決策為：清華大學(xué)出版社702.2 不確定性的采購(gòu)問(wèn)題 從最后一周開(kāi)始，逐步向前遞推計(jì)算，具體計(jì)算過(guò)程如下。k=5時(shí)，因，故有即在第五周時(shí)，若所需的原料尚未買(mǎi)入，則無(wú)論市場(chǎng)價(jià)格如何，都必須采購(gòu)，不能再等。k=4時(shí)，由(9-16)式可知于是，由(9-13)式得由(9-17)式，第4周最優(yōu)決策為清華大學(xué)出版社712.2 不確定性的采購(gòu)問(wèn)題 同理求得所以清華大學(xué)出版社722.2 不確定性的采購(gòu)問(wèn)題 所以清華大學(xué)出版社732.2 不確定性的采購(gòu)問(wèn)題 所以由上可知，最優(yōu)采購(gòu)策略為：在第一、二、三周時(shí)，若價(jià)格為500就采購(gòu)，否則應(yīng)該等待；在第四周時(shí)，價(jià)

33、格為500或600應(yīng)采購(gòu)，否則就等待；在第五周時(shí)，無(wú)論什么價(jià)格都要采購(gòu)。清華大學(xué)出版社742.2 不確定性的采購(gòu)問(wèn)題 依照上述最優(yōu)策略進(jìn)行采購(gòu)時(shí)，價(jià)格(單價(jià))的數(shù)學(xué)期望值為且清華大學(xué)出版社75第3節(jié) 背 包 問(wèn) 題 有一個(gè)人帶一個(gè)背包上山，其可攜帶物品重量的限度為a公斤。設(shè)有n種物品可供他選擇裝入背包中，這n種物品編號(hào)為1，2，n。已知第i種物品每件重量為wi公斤，在上山過(guò)程中的作用(價(jià)值)是攜帶數(shù)量xi的函數(shù)ci(xi)。問(wèn)此人應(yīng)如何選擇攜帶物品(各幾件)，使所起作用(總價(jià)值)最大。這就是著名的背包問(wèn)題。 類(lèi)似的問(wèn)題有工廠里的下料問(wèn)題，運(yùn)輸中的貨物裝載問(wèn)題，人造衛(wèi)星內(nèi)的物品裝載問(wèn)題等等。清華

34、大學(xué)出版社76第3節(jié) 背 包 問(wèn) 題設(shè)xi為第i種物品的裝入件數(shù)，則問(wèn)題的數(shù)學(xué)模型為它是一個(gè)整數(shù)規(guī)劃問(wèn)題。如果xi只取0或1，又稱(chēng)為01背包問(wèn)題。下面用動(dòng)態(tài)規(guī)劃方法來(lái)求解。 清華大學(xué)出版社77第3節(jié) 背 包 問(wèn) 題設(shè)按可裝入物品的n種類(lèi)劃分為n個(gè)階段。狀態(tài)變量w表示用于裝第1種物品至第k種物品的總重量。決策變量xk表示裝入第k種物品的件數(shù)。則狀態(tài)轉(zhuǎn)移方程為允許決策集合為最優(yōu)值函數(shù)fk(w)是當(dāng)總重量不超過(guò)w公斤，背包中可以裝入第1種到第k種物品的最大使用價(jià)值。即 清華大學(xué)出版社78第3節(jié) 背 包 問(wèn) 題因而可寫(xiě)出動(dòng)態(tài)規(guī)劃的順序遞推關(guān)系為： 然后，逐步計(jì)算出及相應(yīng)的決策函數(shù)最后得出的就是所求的最

35、大價(jià)值，其相應(yīng)的最優(yōu)策略由反推運(yùn)算即可得出。清華大學(xué)出版社79第3節(jié) 背 包 問(wèn) 題 例7解:用動(dòng)態(tài)規(guī)劃方法來(lái)解，此問(wèn)題變?yōu)榍骹3(10)。清華大學(xué)出版社80第3節(jié) 背 包 問(wèn) 題 由此看到，要計(jì)算f3(10) ，必須先計(jì)算出清華大學(xué)出版社81第3節(jié) 背 包 問(wèn) 題 為了要計(jì)算出f2(10),f2(5),f2(0) ，必須先計(jì)算出f1(10),f1(6),f1(5),f1(2),f1(1),f1(0) ，一般地有相應(yīng)的最優(yōu)決策為x1=w/3，于是得到清華大學(xué)出版社82第3節(jié) 背 包 問(wèn) 題 從而故最后得到所以，最優(yōu)裝入方案為最大使用價(jià)值為13。 清華大學(xué)出版社83第3節(jié) 背 包 問(wèn) 題 如果再

36、增加對(duì)背包體積的限制為b，并假設(shè)第i種物品每件的體積為vi立方米，問(wèn)應(yīng)如何裝使得總價(jià)值最大。這就是“二維背包問(wèn)題”，它的數(shù)學(xué)模型為清華大學(xué)出版社84第3節(jié) 背 包 問(wèn) 題 用動(dòng)態(tài)規(guī)劃方法來(lái)解。這時(shí)，狀態(tài)變量是兩個(gè)(重量和體積的限制)，決策變量仍是一個(gè)(物品的件數(shù))。設(shè)最優(yōu)值函數(shù)為 表示當(dāng)總重量不超過(guò)w公斤，總體積不超過(guò)v立方米時(shí)，背包中裝入第1種到第k種物品的最大使用價(jià)值。故因而可寫(xiě)出順序遞推關(guān)系式為最后算出即為所求的最大價(jià)值。清華大學(xué)出版社85第4節(jié)復(fù)合系統(tǒng)工作可靠性問(wèn)題 若某種機(jī)器的工作系統(tǒng)由n個(gè)部件串聯(lián)組成，只要有一個(gè)部件失靈，整個(gè)系統(tǒng)就不能工作。為提高系統(tǒng)工作的可靠性，在每一個(gè)部件上均

37、裝有主要元件的備用件，并且設(shè)計(jì)了備用元件自動(dòng)投入裝置。顯然，備用元件越多，整個(gè)系統(tǒng)正常工作的可靠性越大。但備用元件多了，整個(gè)系統(tǒng)的成本、重量、體積均相應(yīng)加大，工作精度也降低。因此，最優(yōu)化問(wèn)題是在考慮上述限制條件下，應(yīng)如何選擇各部件的備用元件數(shù)，使整個(gè)系統(tǒng)的工作可靠性最大。清華大學(xué)出版社86第4節(jié)復(fù)合系統(tǒng)工作可靠性問(wèn)題設(shè)部件 上裝有ui個(gè)備用件時(shí)，它正常工作的概率為pi(ui) 。因此，整個(gè)系統(tǒng)正常工作的可靠性，可用它正常工作的概率衡量。即設(shè)裝一個(gè)部件i備用元件費(fèi)用為ci，重量為wi ，要求總費(fèi)用不超過(guò)c，總重量不超過(guò)w，則這個(gè)問(wèn)題有兩個(gè)約束條件，它的靜態(tài)規(guī)劃模型為：這是一個(gè)非線性整數(shù)規(guī)劃問(wèn)題，

38、因ui要求為整數(shù)，且目標(biāo)函數(shù)是非線性的。此問(wèn)題用動(dòng)態(tài)規(guī)劃方法來(lái)解，比較容易。 清華大學(xué)出版社87第4節(jié)復(fù)合系統(tǒng)工作可靠性問(wèn)題為構(gòu)造動(dòng)態(tài)規(guī)劃模型，根據(jù)兩個(gè)約束條件，取二維狀態(tài)變量，采用兩個(gè)狀態(tài)變量：xk由第k個(gè)到第n個(gè)部件所容許使用的總費(fèi)用。yk由第k個(gè)到第n個(gè)部件所容許具有的總重量。決策變量uk為部件k上裝的備用元件數(shù)，這里決策變量是一維的。這樣，狀態(tài)轉(zhuǎn)移方程為：允許決策集合為最優(yōu)值函數(shù)為由狀態(tài)xk和yk出發(fā)，從部件k到部件n的系統(tǒng)的最大可靠性。清華大學(xué)出版社88第4節(jié)復(fù)合系統(tǒng)工作可靠性問(wèn)題因此，整機(jī)可靠性的動(dòng)態(tài)規(guī)劃基本方程為：邊界條件為1，這是因?yàn)閤n+1、yn+1均為零，裝置根本不工作，故

39、可靠性當(dāng)然為1。最后計(jì)算得即為所求問(wèn)題的最大可靠性。清華大學(xué)出版社89第4節(jié)復(fù)合系統(tǒng)工作可靠性問(wèn)題例8 某廠設(shè)計(jì)一種電子設(shè)備，由三種元件D1,D2,D3組成。已知這三種元件的價(jià)格和可靠性如表9-9所示，要求在設(shè)計(jì)中所使用元件的費(fèi)用不超過(guò)105元。試問(wèn)應(yīng)如何設(shè)計(jì)使設(shè)備的可靠性達(dá)到最大(不考慮重量的限制)。表9-9元件單位/元可靠性D1300.9D2150.8D3200.5清華大學(xué)出版社90第4節(jié)復(fù)合系統(tǒng)工作可靠性問(wèn)題解： 按元件種類(lèi)劃分為三個(gè)階段，設(shè)狀態(tài)變量sk表示能容許用在Dk元件至D3元件的總費(fèi)用；決策變量xk表示在Dk元件上的并聯(lián)個(gè)數(shù)；pk表示一個(gè)Dk元件正常工作的概率，則(1pk)xk為

40、xk個(gè)Dk元件不正常工作的概率。令最優(yōu)值函數(shù)fk(sk)表示由狀態(tài)sk開(kāi)始從Dk元件至D3元件組成的系統(tǒng)的最大可靠性。因而有由于s1=105，故此問(wèn)題為求出f1(105)即可。清華大學(xué)出版社91第4節(jié)復(fù)合系統(tǒng)工作可靠性問(wèn)題而但可是清華大學(xué)出版社92第4節(jié)復(fù)合系統(tǒng)工作可靠性問(wèn)題所以同理故從而求得為最優(yōu)方案，即D1元件用1個(gè)D2元件用2個(gè)，D3元件用2個(gè)。其總費(fèi)用為100元，可靠性為0.648。清華大學(xué)出版社93第5節(jié) 排 序 問(wèn) 題 設(shè)有n個(gè)工件需要在機(jī)床A、B上加工，每個(gè)工件都必須經(jīng)過(guò)先A而后B的兩道加工工序(見(jiàn)圖9-1)。以ai、bi分別表示工件 在A、B上的加工時(shí)間。問(wèn)應(yīng)如何在兩機(jī)床上圖9

41、-1安排各工件加工的順序，使在機(jī)床A上加工第一個(gè)工件開(kāi)始到在機(jī)床B上將最后一個(gè)工件加工完為止，所用的加工總時(shí)間最少?圖9-1清華大學(xué)出版社94第5節(jié) 排 序 問(wèn) 題下面用動(dòng)態(tài)規(guī)劃方法來(lái)研究同順序兩臺(tái)機(jī)床加工n個(gè)工件的排序問(wèn)題。當(dāng)加工順序取定之后，工件在A上加工時(shí)沒(méi)有等待時(shí)間，而在B上則常常等待。因此，尋求最優(yōu)排序方案只有盡量減少在B上等待加工的時(shí)間，才能使總加工時(shí)間最短。設(shè)第i個(gè)工件在機(jī)床A上加工完畢以后，在B上要經(jīng)過(guò)若干時(shí)間才能加工完，故對(duì)同一個(gè)工件來(lái)說(shuō)，在A、B上總是出現(xiàn)加工完畢的時(shí)間差，我們以它來(lái)描述加工狀態(tài)?，F(xiàn)在，我們以在機(jī)床A上更換工件的時(shí)刻作為時(shí)段。以X表示在機(jī)床A上等待加工的按取

42、定順序排列的工件集合。以x表示不屬于X的在A上最后加工完的工件。以t表示在A上加工完x的時(shí)刻算起到B上加工完x所需的時(shí)間。這樣，在A上加工完一個(gè)工件之后，就有(X,t)與之對(duì)應(yīng)。清華大學(xué)出版社95第5節(jié) 排 序 問(wèn) 題選取(X,t)作為描述機(jī)床A、B在加工過(guò)程中的狀態(tài)變量。這樣選取狀態(tài)變量，則當(dāng)X包含有s個(gè)工件時(shí)，過(guò)程尚有s段，其時(shí)段數(shù)已隱含在狀態(tài)變量之中，因而，指標(biāo)最優(yōu)值函數(shù)只依賴于狀態(tài)而不明顯依賴于時(shí)段數(shù)。令f(X,t)為由狀態(tài)(X,t)出發(fā)，對(duì)未加工的工件采取最優(yōu)加工順序后，將X中所有工件加工完所需時(shí)間。f(X,t,i)為由狀態(tài)(X,t)出發(fā)，對(duì)未加工的工件采取最優(yōu)加工順序后，將X中所有

43、工件加工完所需時(shí)間。f(X,t,i,j)為由狀態(tài)(X,t)出發(fā)，在A上相繼加工工件i與j后，對(duì)以后加工的工件采取最優(yōu)順序后，將X中的工件全部加工完所需要的時(shí)間。清華大學(xué)出版社96第5節(jié) 排 序 問(wèn) 題不難得到記上式就可合并寫(xiě)成其中X/i表示在集合X中去掉工件i后剩下的工件集合。清華大學(xué)出版社97第5節(jié) 排 序 問(wèn) 題由定義，可得其中zij(t)是在機(jī)床A上從X出發(fā)相繼加工工件i、j，并從它將j加工完的時(shí)刻算起，至在B上相繼加工工件i、j并將工件加工完所需時(shí)間。故 是在A加工i、j后所形成的新?tīng)顟B(tài)。即在機(jī)床A上加工i、j后由狀態(tài)(X,t)轉(zhuǎn)移到狀態(tài)仿照zi(t)的定義，以X/i,j 代替X/i

44、，zi(t)代替t,aj代替ai，bj代替bi，則可得故清華大學(xué)出版社98第5節(jié) 排 序 問(wèn) 題將i、j對(duì)調(diào)，可得由于f(X,t)為t的單調(diào)上升函數(shù)，故當(dāng)時(shí)，有因此，不管t為何值，當(dāng)時(shí)，工件i放在工件j之前加工可以使總的加工時(shí)間短些。而由zij(t)和zji(t)的表示式可知，這只需要下面不等式成立就行。即將上不等式兩邊同減去bi與bj ，得即有清華大學(xué)出版社99第5節(jié) 排 序 問(wèn) 題這個(gè)條件就是工件i應(yīng)該排在工件j之前的條件。即對(duì)于從頭到尾的最優(yōu)排序而言，所有前后相鄰接的兩個(gè)工件所組成的對(duì)，都必須滿足上述不等式。根據(jù)這個(gè)條件，得到最優(yōu)排序規(guī)則如下：(1) 先給出工件加工時(shí)間的工時(shí)矩陣(2)

45、在工時(shí)矩陣M中找出最小元素；若它在上行，則將相應(yīng)的工件排在最前位置；若它在下行，則將相應(yīng)的工件排在最后位置。(3) 將排定位置的工件所對(duì)應(yīng)的列從M中劃掉，然后對(duì)余下的工件重復(fù)按(2)進(jìn)行。但那時(shí)的最前位置(或最后位置)是在已排定位置的工件之后(或之前)。如此繼續(xù)下去，直至把所有工件都排完為止。清華大學(xué)出版社100第5節(jié) 排 序 問(wèn) 題加工時(shí)間（小時(shí)）例9 設(shè)有5個(gè)工件需在機(jī)床A、B上加工，加工的順序是先A后B，每個(gè)工件所需加工時(shí)間(單位：小時(shí))如表9-10所示。問(wèn)如何安排加工順序，使機(jī)床連續(xù)加工完所有工件的加工總時(shí)間最少?并求出總加工時(shí)間。 機(jī)床工件號(hào)碼AB136272347453574表9-

46、10清華大學(xué)出版社101第5節(jié) 排 序 問(wèn) 題解：工件的加工工時(shí)矩陣為根據(jù)最優(yōu)排序規(guī)則，故最優(yōu)加工順序?yàn)椋嚎偧庸r(shí)間為28小時(shí)。清華大學(xué)出版社102第6節(jié) 設(shè)備更新問(wèn)題 在工業(yè)和交通運(yùn)輸企業(yè)中，經(jīng)常碰到設(shè)備陳舊或部分損壞需要更新的問(wèn)題。從經(jīng)濟(jì)上來(lái)分析，一種設(shè)備應(yīng)該用多少年后進(jìn)行更新為最恰當(dāng)，即更新的最佳策略應(yīng)該如何，從而使在某一時(shí)間內(nèi)的總收入達(dá)到最大(或總費(fèi)用達(dá)到最小)。清華大學(xué)出版社103第6節(jié) 設(shè)備更新問(wèn)題現(xiàn)以一臺(tái)機(jī)器為例，隨著使用年限的增加，機(jī)器的使用效率降低，收入減少，維修費(fèi)用增加。而且機(jī)器使用年限越長(zhǎng)，它本身的價(jià)值就越小，因而更新時(shí)所需的凈支出費(fèi)用就愈多。設(shè)：Ij(t) 在第j年機(jī)器

47、役齡為t年的一臺(tái)機(jī)器運(yùn)行所得的收入。 在第j年機(jī)器役齡為t年的一臺(tái)機(jī)器運(yùn)行時(shí)所需的運(yùn)行費(fèi)用。 在第j年機(jī)器役齡為t年的一臺(tái)機(jī)器更新時(shí)所需更新凈費(fèi)用。 折扣因子()，表示一年以后的單位收入的價(jià)值視為現(xiàn)年的單位。T 在第一年開(kāi)始時(shí)，正在使用的機(jī)器的役齡。n 計(jì)劃的年限總數(shù)。gj(t) 在第j年開(kāi)始使用一個(gè)役齡為t年的機(jī)器時(shí)，從第j年至第n年內(nèi)的最佳收入。xj(t) 給出gj(t)時(shí)，在第j年開(kāi)始時(shí)的決策(保留或更新)。 清華大學(xué)出版社104第6節(jié) 設(shè)備更新問(wèn)題 為了寫(xiě)出遞推關(guān)系式，先從兩方面分析問(wèn)題。若在第j年開(kāi)始時(shí)購(gòu)買(mǎi)了新機(jī)器，則從第j年至第n年得到的總收入應(yīng)等于在第j年中由新機(jī)器獲得的收入，減

48、去在第j年中的運(yùn)行費(fèi)用，減去在第j年開(kāi)始時(shí)役齡為t年的機(jī)器的更新凈費(fèi)用，加上在第j+1年開(kāi)始使用役齡為1年的機(jī)器從第j+1年至第n年的最佳收入；若在第j年開(kāi)始時(shí)繼續(xù)使用役齡為t年的機(jī)器，則從第j年至第n年的總收入應(yīng)等于在第j年由役齡為t年的機(jī)器得到的收入，減去在第j年中役齡為t年的機(jī)器的運(yùn)行費(fèi)用，加上在第j+1年開(kāi)始使用役齡為t+1年的機(jī)器從第j+1年至第n年的最佳收入。然后，比較它們的大小，選取大的，并相應(yīng)得出是更新還是保留的決策。清華大學(xué)出版社105第6節(jié) 設(shè)備更新問(wèn)題將上面的分析寫(xiě)成數(shù)學(xué)形式，即得遞推關(guān)系式為：其中“K”是Keep的縮寫(xiě)，表示保留使用；“R”是Replacement的縮寫(xiě)，表示更新機(jī)器。由于研究的是今后n年的計(jì)劃，故還要求清華大學(xué)出版社106第6節(jié) 設(shè)備更新問(wèn)題例10 假設(shè)有關(guān)數(shù)據(jù)如表9-11所示。試制定5年中的設(shè)備更新策略，使在5年內(nèi)的總收入達(dá)到最大。機(jī)齡項(xiàng)目第一年第二年第三年第四年第五年期前01234012301201012345收入2221201816272524222926243028321816161414運(yùn)行費(fèi)用