動(dòng)態(tài)規(guī)劃應(yīng)用舉例

1、南京航空航天大學(xué) 運(yùn)籌學(xué) 課程論文題目：動(dòng)態(tài)規(guī)劃應(yīng)用舉例學(xué)號(hào)： 姓名： 完成日期：2013。5。16摘 要?jiǎng)討B(tài)規(guī)劃是解決最優(yōu)控制的一種重要方法之一，算法的優(yōu)點(diǎn)有：（1）易于確定全局最優(yōu)解；（2）能得到一族解，有利于分析結(jié)果；（3）能利用經(jīng)驗(yàn)，提高求解的效率。動(dòng)態(tài)規(guī)劃方法雖然存在許多不足之處，但隨著計(jì)算機(jī)的日益普及，動(dòng)態(tài)規(guī)劃的應(yīng)用越來(lái)越廣泛，它能夠巧妙地解決科學(xué)技術(shù)和實(shí)際生活中的許多實(shí)例。本文列舉了一些典型例題，介紹了如何用動(dòng)態(tài)規(guī)劃去求解，不足之處是這些問(wèn)題大多數(shù)都是確定型的，而對(duì)于連續(xù)型、隨機(jī)型問(wèn)題接觸較少。關(guān)鍵詞：動(dòng)態(tài)規(guī)劃；應(yīng)用；正 文一、 資源分配問(wèn)題所謂分配問(wèn)題，就是將數(shù)量一定的一種或若

2、干種資源(例如原材料、資金、機(jī)器設(shè)備、勞力、食品等等)，恰當(dāng)?shù)胤峙浣o若干個(gè)使用者，而使目標(biāo)函數(shù)為最優(yōu)。設(shè)有某種原料，總數(shù)量為a，用于生產(chǎn)n種產(chǎn)品。若分配數(shù)量用于生產(chǎn)第i種產(chǎn)品，其收益為，問(wèn)應(yīng)如何分配，才能使生產(chǎn)n產(chǎn)品的總收入最大?此問(wèn)題可寫成靜態(tài)規(guī)劃問(wèn)題：當(dāng)都是線性函數(shù)時(shí)，它是一個(gè)線性規(guī)劃問(wèn)題；當(dāng)是非線性函數(shù)時(shí)，它是一個(gè)非線性規(guī)劃問(wèn)題。但當(dāng)n比較大時(shí)，具體求解是比較麻煩的。由于這類問(wèn)題的特殊結(jié)構(gòu)，可以將它看成一個(gè)多階段決策問(wèn)題，并利用動(dòng)態(tài)規(guī)劃的遞推關(guān)系來(lái)求解。在應(yīng)用動(dòng)態(tài)規(guī)劃方法處理這類“靜態(tài)規(guī)劃”問(wèn)題時(shí)，通常以把資源分配給一個(gè)或幾個(gè)使用者的過(guò)程作為一個(gè)階段，把問(wèn)題中的變量為決策變量，將累計(jì)的量

3、或隨遞推過(guò)程變化的量選為狀態(tài)變量。設(shè)狀態(tài)變量表示分配用于生產(chǎn)第k種產(chǎn)品至第n種產(chǎn)品的原料數(shù)量。決策變量表示分配給生產(chǎn)第k種產(chǎn)品的原料數(shù)，即=狀態(tài)轉(zhuǎn)移方程：允許決策集合：令最優(yōu)值函數(shù)表示以數(shù)量為的原料分配給第k種產(chǎn)品至第n種產(chǎn)品所得到的最大總收入。因而可寫出動(dòng)態(tài)規(guī)劃的逆推關(guān)系式為：利用這個(gè)遞推關(guān)系式進(jìn)行逐段計(jì)算，最后求得即為所求問(wèn)題的最大總收入。 例1 某工業(yè)部門根據(jù)國(guó)家計(jì)劃的安排，擬將某種高效率的設(shè)備五臺(tái)，分配給所屬的甲、乙、丙三個(gè)工廠，各工廠若獲得這種設(shè)備之后，可以為國(guó)家提供的盈利如表9-1所示。表9-1 問(wèn)：這五臺(tái)設(shè)備如何分配給各工廠，才能使國(guó)家得到的盈利最大。 解 將問(wèn)題按工廠分為三個(gè)階

4、段，甲、乙、丙三個(gè)工廠分別編號(hào)為1、2、3。設(shè)表示為分配給第k個(gè)工廠至第n個(gè)工廠的設(shè)備臺(tái)數(shù)。表示為分配給第k個(gè)工廠的設(shè)備臺(tái)數(shù)，則為分配給第k+1個(gè)工廠至第n個(gè)工廠的設(shè)備臺(tái)數(shù)。表示為臺(tái)設(shè)備分配到第k個(gè)工廠所得的盈利值。表示為臺(tái)設(shè)備分配給第k個(gè)工廠至第n個(gè)工廠時(shí)所得到的最大盈利值。因而可寫出逆推關(guān)系式為下面從最后一個(gè)階段開(kāi)始向前逆推計(jì)算。第三階段：設(shè)將臺(tái)設(shè)備(=0，1，2，3，4，5)全部分配給工廠丙時(shí)，則最大盈利值為，其中=0，1，2，3，4，5。因?yàn)榇藭r(shí)只有一個(gè)工廠，有多少臺(tái)設(shè)備就全部分配給工廠丙，故它的盈利值就是該段的最大盈利值，如下表。表9-201234500001441266231111

5、3412124512125表中表示使為最大值時(shí)的最優(yōu)決策。第二階段：設(shè)把臺(tái)設(shè)備(=0，1，2，3，4，5)分配給工廠乙和工廠丙時(shí)，則對(duì)每個(gè)值，有一種最優(yōu)分配方案，使最大盈利值為其中。因?yàn)榻o乙工廠臺(tái)，其盈利為，余下的臺(tái)就給丙工廠，則它的盈利最大值為?，F(xiàn)要選擇的值，使取最大值。其數(shù)值計(jì)算如表9-3所示。表9-3 012345000010+45+05120+65+410+010230+115+610+411+014240+125+1110+611+411+0161，250+125+1210+1111+611+411+0212第一階段：設(shè)把臺(tái)(這里只有=5的情況)設(shè)備分配給甲、乙、丙三個(gè)工廠時(shí)，則最大

6、盈利值為其中 。因?yàn)榻o甲工廠臺(tái)，其盈利為，剩下的5臺(tái)就分給乙和丙兩個(gè)工廠，則它的盈利最大值為?，F(xiàn)要選擇值，使取最大值，它就是所求的總盈利最大值，其數(shù)值計(jì)算如表9-4所示。表9-4 01234550+213+167+149+1012+513+0210，2然后按計(jì)算表格的順序反推算，可知最優(yōu)分配方案有兩個(gè)：(1) 由于=0 ，根據(jù)，查表9-3知=2，由，故，即得甲工廠分配0臺(tái)，乙工廠分配2臺(tái)，丙工廠分配3臺(tái)。(2) 由于=2，根據(jù)，查表9-3知=2，由，故，即得甲工廠分配2臺(tái)，乙工廠分配2臺(tái)，丙工廠分配1臺(tái)。以上兩個(gè)分配方案所得到的總盈利均為21萬(wàn)元。 資源連續(xù)分配問(wèn)題設(shè)有數(shù)量為的某種資源，可投入

7、A和B兩種生產(chǎn)。第一年若以數(shù)量投入生產(chǎn)A，剩下的量就投入生產(chǎn)B，則可得收入為，其中g(shù)()和h()為已知函數(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ù)為令表示由狀態(tài)出發(fā)，從第k年至第n年末時(shí)所生產(chǎn)的產(chǎn)品的總產(chǎn)量最大值?？蓪懗瞿嫱脐P(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)量也不高。 從前面的數(shù)字計(jì)算可以看出，前幾年一般是

8、全部用于低負(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)值愈大，表示在高負(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ā)來(lái)求出t與(b a)、(c d)的關(guān)系。令。則在低負(fù)荷生產(chǎn)時(shí)有，高負(fù)荷生產(chǎn)時(shí)有。對(duì)第n段，有由于cd，所以應(yīng)選1才能使最大。也就是說(shuō)，最后一年應(yīng)全部投入高負(fù)荷生產(chǎn)。

9、故對(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)。由前面知道，只要在第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)橛钟捎?，將它代入上式得?duì)n-2段，由(9-2)式有由此可知，只要滿足極值條件式就應(yīng)選，否則為0，即應(yīng)繼續(xù)在高負(fù)荷下生產(chǎn)。 依次類推，如果轉(zhuǎn)入高負(fù)荷下

10、生產(chǎn)的是第t年，則由可以推出，應(yīng)滿足極值關(guān)系的條件必然是：相應(yīng)的有最優(yōu)策略它就是例2在始端固定終端自由情況下最優(yōu)策略的一般結(jié)果。 從這個(gè)例子看到，應(yīng)用動(dòng)態(tài)規(guī)劃，可以在不求出數(shù)值解的情況下，確定最優(yōu)策略的結(jié)構(gòu)?？梢?jià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)量最高。上面的討論表明：當(dāng)x在0，上離散地變化時(shí)，利用遞推關(guān)系式逐步計(jì)算或表格法而求出數(shù)值解。當(dāng)x在0，上連續(xù)地變化時(shí)，若和是線性函數(shù)或凸函數(shù)時(shí)，根據(jù)遞推關(guān)系式運(yùn)用解析法不難求出和最優(yōu)解；若和不是線性函數(shù)或凸

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

12、問(wèn)題可寫成靜態(tài)規(guī)劃問(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ù)量。決策變量：分配給第k種產(chǎn)品用的第一種原料的單位數(shù)量。分配給第k種產(chǎn)品用的第二種原料的單位數(shù)量。狀態(tài)轉(zhuǎn)換關(guān)系：，式中和分別表示用來(lái)生產(chǎn)第k+1種產(chǎn)品至第n種產(chǎn)品的第一種和第二種原料的單位數(shù)量。允許決策集合： 表示以第一種原料數(shù)量為x單位，第二種原料數(shù)量為y單位，分配用于生產(chǎn)第k種產(chǎn)品至第n種產(chǎn)品時(shí)所得到的最大收入。故可寫出逆推關(guān)系為最后求得即為所求問(wèn)題的最大收入。 1。 拉格朗日乘數(shù)

13、法引入拉格朗日乘數(shù)，將二維分配問(wèn)題化為滿足條件；，其中作為一個(gè)固定的參數(shù)。令 于是問(wèn)題變?yōu)?，滿足且為整數(shù)這是一個(gè)一維分配問(wèn)題，可用對(duì)一維的方法去求解。這里，由于是參數(shù)，因此，最優(yōu)解是參數(shù)的函數(shù)，相應(yīng)的也是的函數(shù)。即，為其解。如果，則可證明為原問(wèn)題的最優(yōu)解。如果，將調(diào)整的值(利用插值法逐漸確定 )，直到滿足為止。這樣的降維方法在理論上有保證，在計(jì)算上是可行的，故對(duì)高維問(wèn)題，可用上述拉格朗日乘數(shù)法的思想來(lái)降低維數(shù)。2。 逐次逼近法這是另一種降維方法，先保持一個(gè)變量不變，對(duì)另一個(gè)變量實(shí)現(xiàn)最優(yōu)化。然后交替地固定，以迭代的形式反復(fù)進(jìn)行，直到獲得某種要求為止。先設(shè)為滿足的一個(gè)可行解，固定x在，先對(duì)y求解，

14、則二維分配問(wèn)題變?yōu)橐痪S問(wèn)題：可用對(duì)一維的方法來(lái)求解。設(shè)這解為，然后再固定y為，對(duì)x求解，即設(shè)其解為，再固定x為，對(duì)y求解，這樣依次輪換下去得到一系列的解。因?yàn)?，故函?shù)值序列是單調(diào)上升的，但不一定收斂到絕對(duì)的最優(yōu)解，一般只收斂到某一局部最優(yōu)解。因此，在實(shí)際計(jì)算時(shí)，可選擇幾個(gè)初始點(diǎn)進(jìn)行計(jì)算，然后從所得到的幾個(gè)局部最優(yōu)解中選出一個(gè)最好的。3粗格子點(diǎn)法(疏密法)在采用離散化的方法計(jì)算時(shí)，先將矩形定義域：0xa，0yb分成網(wǎng)格，然后在這些格子點(diǎn)上進(jìn)行計(jì)算。如將a、b各分為和等份，則總共有(+1)(+1)個(gè)格點(diǎn)，故對(duì)每個(gè)k值需要計(jì)算的共有(+1)(+1)個(gè)。因此，這里的計(jì)算量是相當(dāng)大的。隨著分點(diǎn)加多，格子

15、點(diǎn)數(shù)也增多，那時(shí)的計(jì)算量將大得驚人。為了使計(jì)算可行，往往根據(jù)問(wèn)題要求的精確度，采用粗格子點(diǎn)法逐步縮小區(qū)域來(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)行分析。1。3 固定資金分配問(wèn)題設(shè)有n個(gè)生產(chǎn)行業(yè)，都需要某兩種資源。對(duì)于第k個(gè)生產(chǎn)行業(yè)，如果用第1種資源和第2種資源進(jìn)行生產(chǎn)，可獲得利潤(rùn)為。若第1種資源的單位價(jià)格為a ，第2種資源的單位價(jià)格為b，現(xiàn)有資金Z。問(wèn)應(yīng)購(gòu)買第1種資源多少單位(設(shè)

16、為X)，第2種資源多少單位(設(shè)為Y)，分配到n個(gè)生產(chǎn)行業(yè)，使總利潤(rùn)最大?此問(wèn)題的數(shù)學(xué)模型可寫為(1) 把資源分配利潤(rùn)表?yè)Q算成資金分配利潤(rùn)表，即將換算成。但必須注意，分配的資金應(yīng)先使較貴的資源單位最大。設(shè)有資金分配到第k個(gè)生產(chǎn)行業(yè)，則由知，在給定z的情況下，若購(gòu)買第2種資源單位，則留下的資金只能購(gòu)買第1種資源單位，。于是得到資金利潤(rùn)函數(shù)為式中(z/b)指以資金z購(gòu)買第2種資源的最大單位數(shù)，指以資金z購(gòu)買了第2種資源單位以后能購(gòu)買第1種資源的最大單位數(shù)。(2) 計(jì)算最優(yōu)資金分配所獲得最大利潤(rùn)。規(guī)定最優(yōu)值函數(shù)表示以總的資金z分配到k至n個(gè)生產(chǎn)行業(yè)可能獲得的最大利潤(rùn)。則有逆推關(guān)系式：(3) 求出，即為

17、問(wèn)題的解。這樣，就把一個(gè)原含有兩個(gè)狀態(tài)變量的問(wèn)題轉(zhuǎn)化為只含有一個(gè)狀態(tài)變量的問(wèn)題。二、生產(chǎn)與存儲(chǔ)問(wèn)題在生產(chǎn)和經(jīng)營(yíng)管理中，經(jīng)常遇到要合理地安排生產(chǎn)(或購(gòu)買)與庫(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)。2。1 生產(chǎn)計(jì)劃問(wèn)題 設(shè)某公司對(duì)某種產(chǎn)品要制定一項(xiàng)n個(gè)階段的生產(chǎn)(或購(gòu)買)計(jì)劃。已知它的初始庫(kù)存量為零，每階段生產(chǎn)(或購(gòu)買)該產(chǎn)品的數(shù)量有上限的限制；每階段社會(huì)對(duì)該產(chǎn)品的需求量是已知的，公司保證供應(yīng)；在n階段末的終結(jié)庫(kù)存量為零。問(wèn)該公司如

18、何制定每個(gè)階段的生產(chǎn)(或采購(gòu))計(jì)劃，從而使總成本最小。設(shè)為第k階段對(duì)產(chǎn)品的需求量，為第k階段該產(chǎn)品的生產(chǎn)量(或采購(gòu)量)，為第k階段結(jié)束時(shí)的產(chǎn)品庫(kù)存量。則有表示第k階段生產(chǎn)產(chǎn)品時(shí)的成本費(fèi)用，它包括生產(chǎn)準(zhǔn)備成本K和產(chǎn)品成本a (其中a是單位產(chǎn)品成本)兩項(xiàng)費(fèi)用。即表示在第k階段結(jié)束時(shí)有庫(kù)存量所需的存儲(chǔ)費(fèi)用。故k階段的成本費(fèi)用為m表示每階段最多能生產(chǎn)該產(chǎn)品的上限數(shù)。 上述問(wèn)題的數(shù)學(xué)模型為用動(dòng)態(tài)規(guī)劃方法來(lái)求解，可看作一個(gè)n階段決策問(wèn)題。令為狀態(tài)變量，它表示第k階段開(kāi)始時(shí)的庫(kù)存量。為決策變量，它表示第k階段的生產(chǎn)量。狀態(tài)轉(zhuǎn)移方程為 最優(yōu)值函數(shù)表示從第1階段初始庫(kù)存量為0到第k階段末庫(kù)存量為時(shí)的最小總費(fèi)用。

19、順序遞推關(guān)系式為：其中。這是因?yàn)橐环矫婷侩A段生產(chǎn)的上限為m；另一方面由于保證供應(yīng)，故第k-1階段末的庫(kù)存量必須非負(fù)，即，所以。邊界條件為或從邊界條件出發(fā)，利用上面的遞推關(guān)系式，對(duì)每個(gè)k ，計(jì)算出中的在0至之間的值，最后求得的即為所求的最小總費(fèi)用。例3 某工廠要對(duì)一種產(chǎn)品制訂今后四個(gè)時(shí)期的生產(chǎn)計(jì)劃，據(jù)估計(jì)在今后四個(gè)時(shí)期內(nèi)，市場(chǎng)對(duì)于該產(chǎn)品的需求量如表9-5所示。表9-5時(shí)期(k)1234需求量()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千元。還假定在第

20、一個(gè)時(shí)期的初始庫(kù)存量為0，第四個(gè)時(shí)期之末的庫(kù)存量也為0。試問(wèn)該廠應(yīng)如何安排各個(gè)時(shí)期的生產(chǎn)與庫(kù)存，才能在滿足市場(chǎng)需要的條件下，使總成本最小。解 用動(dòng)態(tài)規(guī)劃方法來(lái)求解，其符號(hào)含義與上面相同。按四個(gè)時(shí)期將問(wèn)題分為四個(gè)階段。由題意知，在第k時(shí)期內(nèi)的生產(chǎn)成本為第k時(shí)期末庫(kù)存量為時(shí)的存儲(chǔ)費(fèi)用為故第k時(shí)期內(nèi)的總成本為而動(dòng)態(tài)規(guī)劃的順序遞推關(guān)系式為其中和邊界條件當(dāng)k=1時(shí)，由 對(duì)在0至之間的值分別進(jìn)行計(jì)算。同理得當(dāng)k=2時(shí)，由 其中。對(duì)在0至之間的值分別進(jìn)行計(jì)算。從而有當(dāng)k=3時(shí)，由 其中。對(duì)在0至之間的值分別進(jìn)行計(jì)算，從而有當(dāng)k=4時(shí)，因要求第4時(shí)期之末的庫(kù)存量為0，即=0，故有再按計(jì)算的順序反推算，可找出每

21、個(gè)時(shí)期的最優(yōu)生產(chǎn)決策為：其相應(yīng)的最小總成本為20。5千元。把上面例題中的有關(guān)數(shù)據(jù)列成表9-6，可找出一些規(guī)律性的東西。表9-6階段i01234需求量2324生產(chǎn)量5060庫(kù)存量03040由表中的數(shù)字可以看到，這類庫(kù)存問(wèn)題有如下特征：(1) 對(duì)每個(gè)i，有，（i1，2，3，4）其中=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)題的最小總成本。如果對(duì)每個(gè)i，都有，則稱該點(diǎn)的生產(chǎn)決策(或稱一個(gè)策略)具有再生產(chǎn)點(diǎn)性質(zhì)(又稱重生性質(zhì))。如果=0，則稱階段i為再生產(chǎn)點(diǎn)(又稱重生

22、點(diǎn))。由假設(shè)=0和=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è)(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)系式。設(shè)最優(yōu)值函數(shù)表示在階段i末庫(kù)存量=0時(shí)，從階段1到階段i的最小成本。則對(duì)應(yīng)的遞推關(guān)系式為 ，邊界條件為為了確定最優(yōu)生產(chǎn)決策，逐個(gè)計(jì)算。則(0)為n個(gè)階段的最小總成本。設(shè)為計(jì)算時(shí)，使(9-7)式右邊最小的j

23、值，即則從階段到階段n的最優(yōu)生產(chǎn)決策為：故階段為再生產(chǎn)點(diǎn)。為了進(jìn)一步確定階段1到階段1的最優(yōu)生產(chǎn)決策，記m= 1，而是在計(jì)算時(shí)，使(9-7)式右邊最小的j值，則從階段到階段的最優(yōu)生產(chǎn)決策為：故階段為再生產(chǎn)點(diǎn)，其余依此類推。 例4 利用再生產(chǎn)點(diǎn)性質(zhì)解例3。解 因都是凹函數(shù)，故可利用再生產(chǎn)點(diǎn)性質(zhì)來(lái)計(jì)算。(1) 按(9-6)式計(jì)算(2) 按(9-7)式和(9-8)式計(jì)算(3) 找出最優(yōu)生產(chǎn)決策由，故。因 所以故，所以最優(yōu)生產(chǎn)決策為：，相應(yīng)的最小總成本為20。5千元。 例5 某車間需要按月在月底供應(yīng)一定數(shù)量的某種部件給總裝車間，由于生產(chǎn)條件的變化，該車間在各月份中生產(chǎn)每單位這種部件所需耗費(fèi)的工時(shí)不同，

24、各月份的生產(chǎn)量于當(dāng)月的月底前，全部要存入倉(cāng)庫(kù)以備后用。已知總裝車間的各個(gè)月份的需求量以及在加工車間生產(chǎn)該部件每單位數(shù)量所需工時(shí)數(shù)如表9-7所示。表9-7月份k0123456需求量0853274單位工時(shí)111813172010設(shè)倉(cāng)庫(kù)容量限制為H=9，開(kāi)始庫(kù)存量為2，期終庫(kù)存量為0，需要制定一個(gè)半年的逐月生產(chǎn)計(jì)劃，既使得滿足需要和庫(kù)容量的限制，又使得生產(chǎn)這種部件的總耗費(fèi)工時(shí)數(shù)為最少。解 按月份劃分階段，用k表示月份序號(hào)。設(shè)狀態(tài)變量為第k段開(kāi)始時(shí)(本段需求量送出之前，上段產(chǎn)品送入之后)部件庫(kù)存量。決策變量為第k段內(nèi)的部件生產(chǎn)量。狀態(tài)轉(zhuǎn)移方程：且，故允許決策集合為最優(yōu)值函數(shù)表示在第k段開(kāi)始的庫(kù)存量為時(shí)

25、，從第k段至第6段所生產(chǎn)部件的最小累計(jì)工時(shí)數(shù)。因而可寫出逆推關(guān)系式為當(dāng)k=6時(shí)，因要求期終庫(kù)存量為0，即=0 。因每月的生產(chǎn)是供應(yīng)下月的需要，故第6個(gè)月不用生產(chǎn)，即=0。因此=0，而由(9-9)式有當(dāng)k=5時(shí)，由(9-9)式有，故及最優(yōu)解當(dāng)k=4時(shí)，有其中的允許決策集合由(9-11)式確定。由，故有。又，因而。而由(9-10)式知：，所以為，故得及最優(yōu)解當(dāng)k=3時(shí)，由(9-11)式得為，故得及最優(yōu)解。當(dāng)k=2時(shí)，其中為，故得及最優(yōu)解。當(dāng)k=1時(shí)，其中為，故得及最優(yōu)解當(dāng)k=0時(shí)，其中為，故得及最優(yōu)解，因=2，所以=357和=7再按計(jì)算順序反推，即得各階段最優(yōu)決策為：所以，0至5月最優(yōu)生產(chǎn)計(jì)劃為：

26、7，4，9，3，0，4，最小總工時(shí)為357。 2。2 不確定性的采購(gòu)問(wèn)題 在實(shí)際問(wèn)題中，還會(huì)遇到某些多階段決策過(guò)程，其狀態(tài)轉(zhuǎn)移不是完全確定的，出現(xiàn)了隨機(jī)性因素，狀態(tài)轉(zhuǎn)移是按照某種已知概率分布取值的。具有這種性質(zhì)的多階段決策過(guò)程稱為隨機(jī)性決策過(guò)程。 用動(dòng)態(tài)規(guī)劃方法也可處理這類隨機(jī)性問(wèn)題，又稱為隨機(jī)性動(dòng)態(tài)規(guī)劃。例6 采購(gòu)問(wèn)題。某廠生產(chǎn)上需要在近五周內(nèi)必須采購(gòu)一批原料，而估計(jì)在未來(lái)五周內(nèi)價(jià)格有波動(dòng)，其浮動(dòng)價(jià)格和概率已測(cè)得如表9-8所示。試求在哪一周以什么價(jià)格購(gòu)入，使其采購(gòu)價(jià)格的數(shù)學(xué)期望值最小，并求出期望值。表9-8單價(jià)概率5000。36000。37000。4解 價(jià)格是一個(gè)隨機(jī)變量，按某種已知的概率分

27、布取值。用動(dòng)態(tài)規(guī)劃方法處理，按采購(gòu)期限5周分為5個(gè)階段，將每周的價(jià)格看作該階段的狀態(tài)。設(shè)狀態(tài)變量，表示第k周的實(shí)際價(jià)格。決策變量， =1時(shí)表示第k周決定采購(gòu)；=0時(shí)表示第k周決定等待。第k周決定等待，而在以后采取最優(yōu)決策時(shí)采購(gòu)價(jià)格的期望值。第k周實(shí)際價(jià)格為時(shí)，從第k周至第5周采取最優(yōu)決策所得的最小期望值。因而可寫出逆序遞推關(guān)系式為其中 由和的定義可知：并且得出最優(yōu)決策為：從最后一周開(kāi)始，逐步向前遞推計(jì)算，具體計(jì)算過(guò)程如下。k=5時(shí)，因，故有即在第五周時(shí)，若所需的原料尚未買入，則無(wú)論市場(chǎng)價(jià)格如何，都必須采購(gòu)，不能再等。k=4時(shí)，由(9-16)式可知于是，由(9-13)式得由(9-17)式，第4周

28、最優(yōu)決策為同理求得所以 所以 所以 由上可知，最優(yōu)采購(gòu)策略為：在第一、二、三周時(shí)，若價(jià)格為500就采購(gòu)，否則應(yīng)該等待；在第四周時(shí)，價(jià)格為500或600應(yīng)采購(gòu)，否則就等待；在第五周時(shí)，無(wú)論什么價(jià)格都要采購(gòu)。依照上述最優(yōu)策略進(jìn)行采購(gòu)時(shí)，價(jià)格(單價(jià))的數(shù)學(xué)期望值為且 三、 背 包 問(wèn) 題有一個(gè)人帶一個(gè)背包上山，其可攜帶物品重量的限度為a公斤。設(shè)有n種物品可供他選擇裝入背包中，這n種物品編號(hào)為1，2，n。已知第i種物品每件重量為公斤，在上山過(guò)程中的作用(價(jià)值)是攜帶數(shù)量的函數(shù)。問(wèn)此人應(yīng)如何選擇攜帶物品(各幾件)，使所起作用(總價(jià)值)最大。這就是著名的背包問(wèn)題。類似的問(wèn)題有工廠里的下料問(wèn)題，運(yùn)輸中的貨物

29、裝載問(wèn)題，人造衛(wèi)星內(nèi)的物品裝載問(wèn)題等等。設(shè)為第i種物品的裝入件數(shù)，則問(wèn)題的數(shù)學(xué)模型為它是一個(gè)整數(shù)規(guī)劃問(wèn)題。如果只取0或1，又稱為01背包問(wèn)題。下面用動(dòng)態(tài)規(guī)劃方法來(lái)求解。 設(shè)按可裝入物品的n種類劃分為n個(gè)階段。狀態(tài)變量w表示用于裝第1種物品至第k種物品的總重量。決策變量表示裝入第k種物品的件數(shù)。則狀態(tài)轉(zhuǎn)移方程為允許決策集合為最優(yōu)值函數(shù)是當(dāng)總重量不超過(guò)w公斤，背包中可以裝入第1種到第k種物品的最大使用價(jià)值。即因而可寫出動(dòng)態(tài)規(guī)劃的順序遞推關(guān)系為：然后，逐步計(jì)算出，及相應(yīng)的決策函數(shù)，最后得出的就是所求的最大價(jià)值，其相應(yīng)的最優(yōu)策略由反推運(yùn)算即可得出。例7 解 用動(dòng)態(tài)規(guī)劃方法來(lái)解，此問(wèn)題變?yōu)榍?。由此看到?/p>

30、要計(jì)算，必須先計(jì)算出為了要計(jì)算出，必須先計(jì)算出，一般地有相應(yīng)的最優(yōu)決策為=w/3，于是得到從而故最后得到所以，最優(yōu)裝入方案為，最大使用價(jià)值為13。 如果再增加對(duì)背包體積的限制為b，并假設(shè)第i種物品每件的體積為立方米，問(wèn)應(yīng)如何裝使得總價(jià)值最大。這就是“二維背包問(wèn)題”，它的數(shù)學(xué)模型為用動(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à)值。故因而可寫出順序遞推關(guān)系式為最后算出即為所求的最大價(jià)值。四、復(fù)合系統(tǒng)工作可靠性問(wèn)題若某種機(jī)器的工作系統(tǒng)由n個(gè)部件串聯(lián)組

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

32、規(guī)劃問(wèn)題，因要求為整數(shù)，且目標(biāo)函數(shù)是非線性的。此問(wèn)題用動(dòng)態(tài)規(guī)劃方法來(lái)解，比較容易。 為構(gòu)造動(dòng)態(tài)規(guī)劃模型，根據(jù)兩個(gè)約束條件，取二維狀態(tài)變量，采用兩個(gè)狀態(tài)變量：由第k個(gè)到第n個(gè)部件所容許使用的總費(fèi)用。由第k個(gè)到第n個(gè)部件所容許具有的總重量。決策變量為部件k上裝的備用元件數(shù)，這里決策變量是一維的。這樣，狀態(tài)轉(zhuǎn)移方程為：允許決策集合為 最優(yōu)值函數(shù)為由狀態(tài)和出發(fā)，從部件k到部件n的系統(tǒng)的最大可靠性。因此，整機(jī)可靠性的動(dòng)態(tài)規(guī)劃基本方程為：邊界條件為1，這是因?yàn)?、均為零，裝置根本不工作，故可靠性當(dāng)然為1。最后計(jì)算得，即為所求問(wèn)題的最大可靠性。例8 某廠設(shè)計(jì)一種電子設(shè)備，由三種元件組成。已知這三種元件的價(jià)格和

33、可靠性如表9-9所示，要求在設(shè)計(jì)中所使用元件的費(fèi)用不超過(guò)105元。試問(wèn)應(yīng)如何設(shè)計(jì)使設(shè)備的可靠性達(dá)到最大(不考慮重量的限制)。表9-9元件單位/元可靠性D1300。9D2150。8D3200。5解 按元件種類劃分為三個(gè)階段，設(shè)狀態(tài)變量表示能容許用在元件至元件的總費(fèi)用；決策變量表示在元件上的并聯(lián)個(gè)數(shù)；表示一個(gè)元件正常工作的概率，則為個(gè)元件不正常工作的概率。令最優(yōu)值函數(shù)表示由狀態(tài)開(kāi)始從元件至元件組成的系統(tǒng)的最大可靠性。因而有由于=105，故此問(wèn)題為求出即可。而 但可是 所以同理 故 。從而求得為最優(yōu)方案，即元件用1個(gè)， 元件用2個(gè)，元件用2個(gè)。其總費(fèi)用為100元，可靠性為0。648。圖9-1五、排序

34、問(wèn)題設(shè)有n個(gè)工件需要在機(jī)床A、B上加工，每個(gè)工件都必須經(jīng)過(guò)先A而后B的兩道加工工序(見(jiàn)圖9-1)。以、分別表示工件在A、B上的加工時(shí)間。問(wèn)應(yīng)如何在兩機(jī)床上圖9-1安排各工件加工的順序，使在機(jī)床A上加工第一個(gè)工件開(kāi)始到在機(jī)床B上將最后一個(gè)工件加工完為止，所用的加工總時(shí)間最少?下面用動(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)加工完畢的

35、時(shí)間差， 我們以它來(lái)描述加工狀態(tài)?，F(xiàn)在，我們以在機(jī)床A上更換工件的時(shí)刻作為時(shí)段。以X表示在機(jī)床A上等待加工的按取定順序排列的工件集合。以x表示不屬于X的在A上最后加工完的工件。以t表示在A上加工完x的時(shí)刻算起到B上加工完x所需的時(shí)間。這樣，在A上加工完一個(gè)工件之后，就有(X，t)與之對(duì)應(yīng)。選取(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ù)。令為由狀態(tài)(X，t)出發(fā)，對(duì)未加工的工件采取最優(yōu)加工順序后，將X中所有工件加工完所需時(shí)間。為由狀態(tài)(X，t)出發(fā)，

36、在A上加工工件i后，對(duì)以后未加工的工件采取最優(yōu)加工順序后，將X中所有工件加工完所需時(shí)間。為由狀態(tài)(X，t)出發(fā)，在A上相繼加工工件i與j后，對(duì)以后加工的工件采取最優(yōu)順序后，將X中的工件全部加工完所需要的時(shí)間。不難得到 記，上式就可合并寫成其中X/i表示在集合X中去掉工件i后剩下的工件集合。由定義，可得 其中是在機(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)。仿照的定義，以代替，代替t，代替，代替，則可得故將i、j對(duì)調(diào)，可得由于為t的單調(diào)上升函

37、數(shù)，故當(dāng)時(shí)，有因此，不管t為何值，當(dāng)時(shí)，工件i放在工件j之前加工可以使總的加工時(shí)間短些。而由和的表示式可知，這只需要下面不等式成立就行。即將上不等式兩邊同減去與，得即有 這個(gè)條件就是工件i應(yīng)該排在工件j之前的條件。即對(duì)于從頭到尾的最優(yōu)排序而言，所有前后相鄰接的兩個(gè)工件所組成的對(duì)，都必須滿足上述不等式。根據(jù)這個(gè)條件，得到最優(yōu)排序規(guī)則如下：(1) 先給出工件加工時(shí)間的工時(shí)矩陣(2) 在工時(shí)矩陣M中找出最小元素；若它在上行，則將相應(yīng)的工件排在最前位置；若它在下行，則將相應(yīng)的工件排在最后位置。(3) 將排定位置的工件所對(duì)應(yīng)的列從M中劃掉，然后對(duì)余下的工件重復(fù)按(2)進(jìn)行。但那時(shí)的最前位置(或最后位置)

38、是在已排定位置的工件之后(或之前)。如此繼續(xù)下去，直至把所有工件都排完為止。例9 設(shè)有5個(gè)工件需在機(jī)床A、B上加工，加工的順序是先A后B，每個(gè)工件所需加工時(shí)間(單位：小時(shí))如表9-10所示。問(wèn)如何安排加工順序，使機(jī)床連續(xù)加工完所有工件的加工總時(shí)間最少?并求出總加工時(shí)間。表9-10 加工時(shí)間 機(jī)床工件號(hào)碼AB136272347453574解 工件的加工工時(shí)矩陣為根據(jù)最優(yōu)排序規(guī)則，故最優(yōu)加工順序?yàn)椋嚎偧庸r(shí)間為28小時(shí)。六、 設(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í)

39、間內(nèi)的總收入達(dá)到最大(或總費(fèi)用達(dá)到最小)?，F(xiàn)以一臺(tái)機(jī)器為例，隨著使用年限的增加，機(jī)器的使用效率降低，收入減少，維修費(fèi)用增加。而且機(jī)器使用年限越長(zhǎng)，它本身的價(jià)值就越小，因而更新時(shí)所需的凈支出費(fèi)用就愈多。設(shè)： 在第j年機(jī)器役齡為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ù)。 在第j年開(kāi)始使用一個(gè)役齡為t年的機(jī)器時(shí)，從第j年至第n年內(nèi)的最佳收入。 給出時(shí)，在第j年開(kāi)始時(shí)的決策(保留或更新)。 為了寫出遞推關(guān)系式，先從兩方面分析問(wèn)題。若在第j年開(kāi)始時(shí)購(gòu)買了新機(jī)器，則從第j年至第n年得到的總收入應(yīng)等于在第j年中由新機(jī)器獲得的收入，減去在第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)得出是更新還是保留的決策。將上面的分