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

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

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

3、或隨遞推過程變化的量選為狀態(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)品所得到的最大總收入。因而可寫出動態(tài)規(guī)劃的逆推關(guān)系式為：利用這個遞推關(guān)系式進(jìn)行逐段計算，最后求得即為所求問題的最大總收入。 例1 某工業(yè)部門根據(jù)國家計劃的安排，擬將某種高效率的設(shè)備五臺，分配給所屬的甲、乙、丙三個工廠，各工廠若獲得這種設(shè)備之后，可以為國家提供的盈利如表9-1所示。表9-1 問：這五臺設(shè)備如何分配給各工廠，才能使國家得到的盈利最大。 解 將問題按工廠分為三個階

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

5、3412124512125表中表示使為最大值時的最優(yōu)決策。第二階段：設(shè)把臺設(shè)備(=0，1，2，3，4，5)分配給工廠乙和工廠丙時，則對每個值，有一種最優(yōu)分配方案，使最大盈利值為其中。因為給乙工廠臺，其盈利為，余下的臺就給丙工廠，則它的盈利最大值為。現(xiàn)要選擇的值，使取最大值。其數(shù)值計算如表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è)把臺(這里只有=5的情況)設(shè)備分配給甲、乙、丙三個工廠時，則最大

6、盈利值為其中 。因為給甲工廠臺，其盈利為，剩下的5臺就分給乙和丙兩個工廠，則它的盈利最大值為?，F(xiàn)要選擇值，使取最大值，它就是所求的總盈利最大值，其數(shù)值計算如表9-4所示。表9-4 01234550+213+167+149+1012+513+0210，2然后按計算表格的順序反推算，可知最優(yōu)分配方案有兩個：(1) 由于=0 ，根據(jù)，查表9-3知=2，由，故，即得甲工廠分配0臺，乙工廠分配2臺，丙工廠分配3臺。(2) 由于=2，根據(jù)，查表9-3知=2，由，故，即得甲工廠分配2臺，乙工廠分配2臺，丙工廠分配1臺。以上兩個分配方案所得到的總盈利均為21萬元。 資源連續(xù)分配問題設(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)系式。顯然，這時狀態(tài)轉(zhuǎn)移方程為k段的指標(biāo)函數(shù)為令表示由狀態(tài)出發(fā)，從第k年至第n年末時所生產(chǎn)的產(chǎn)品的總產(chǎn)量最大值。可寫出逆推關(guān)系式為：我們知道，在低負(fù)荷下生產(chǎn)的時間愈長，機(jī)器完好率愈高，但生產(chǎn)產(chǎn)量少。而在高負(fù)荷下生產(chǎn)產(chǎn)量會增加，但機(jī)器損壞大。這樣，即使每臺產(chǎn)量高，總起來看產(chǎn)量也不高。 從前面的數(shù)字計算可以看出，前幾年一般是

8、全部用于低負(fù)荷生產(chǎn)，后幾年則全部用于高負(fù)荷生產(chǎn)，這樣才產(chǎn)量最高。如果總共為n年，從低負(fù)荷轉(zhuǎn)為高負(fù)荷生產(chǎn)的是第t年，1tn。即是說，從1至t1年在低負(fù)荷下生產(chǎn)，t至n年在高負(fù)荷下生產(chǎn)。現(xiàn)在要分析t與系數(shù)a、b、c、d是什么關(guān)系。從回收率看，(b a)值愈大，表示在高負(fù)荷下生產(chǎn)時，機(jī)車損壞情況比在低負(fù)荷時嚴(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)系。令。則在低負(fù)荷生產(chǎn)時有，高負(fù)荷生產(chǎn)時有。對第n段，有由于cd，所以應(yīng)選1才能使最大。也就是說，最后一年應(yīng)全部投入高負(fù)荷生產(chǎn)。

9、故對n-1段，根據(jù)(9-2)式有因此，欲要滿足上式極值關(guān)系的條件是當(dāng)時，應(yīng)取，即n 1年仍應(yīng)全部在高負(fù)荷下生產(chǎn)。否則，當(dāng)(9-4)式不滿足時，應(yīng)取，即n 1年應(yīng)全部投入低負(fù)荷生產(chǎn)。由前面知道，只要在第k年投入低負(fù)荷生產(chǎn)，那么遞推計算結(jié)果必然是從第1年到第k年均為低負(fù)荷生產(chǎn)，即有?？梢姡愠龊?，前幾年就沒有必要再計算了。故只需研究哪一年由低負(fù)荷轉(zhuǎn)入高負(fù)荷生產(chǎn)，即從那一年開始變?yōu)?就行。根據(jù)這點，現(xiàn)只分析滿足(9-4)式的情況。由于，故(9-3)式變?yōu)橛钟捎?，將它代入上式得對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é)果。 從這個例子看到，應(yīng)用動態(tài)規(guī)劃，可以在不求出數(shù)值解的情況下，確定最優(yōu)策略的結(jié)構(gòu)?？梢?，只要知道了a，b，c，d四個值，就總可找到一個t值，滿足(9-5)式，且例如題中給定的，代入(9-5)式，應(yīng)有可見，所以t=3，即從第三年開始將全部機(jī)器投入高負(fù)荷生產(chǎn)，五年內(nèi)總產(chǎn)量最高。上面的討論表明：當(dāng)x在0，上離散地變化時，利用遞推關(guān)系式逐步計算或表格法而求出數(shù)值解。當(dāng)x在0，上連續(xù)地變化時，若和是線性函數(shù)或凸函數(shù)時，根據(jù)遞推關(guān)系式運(yùn)用解析法不難求出和最優(yōu)解；若和不是線性函數(shù)或凸

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

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

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

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

15、點數(shù)也增多，那時的計算量將大得驚人。為了使計算可行，往往根據(jù)問題要求的精確度，采用粗格子點法逐步縮小區(qū)域來減少計算量。粗格子點法是先用少數(shù)的格子點進(jìn)行粗糙的計算，在求出相應(yīng)的最優(yōu)解后，再在最優(yōu)解附近的小范圍內(nèi)進(jìn)一步細(xì)分，并求在細(xì)分格子點上的最優(yōu)解，如此繼續(xù)細(xì)分下去直到滿足要求為止。這種方法可能會出現(xiàn)最優(yōu)解“漏網(wǎng)”的情況，因此，應(yīng)用此法時要結(jié)合對指標(biāo)函數(shù)的特性進(jìn)行分析。1。3 固定資金分配問題設(shè)有n個生產(chǎn)行業(yè)，都需要某兩種資源。對于第k個生產(chǎn)行業(yè)，如果用第1種資源和第2種資源進(jìn)行生產(chǎn)，可獲得利潤為。若第1種資源的單位價格為a ，第2種資源的單位價格為b，現(xiàn)有資金Z。問應(yīng)購買第1種資源多少單位(設(shè)

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

17、問題的解。這樣，就把一個原含有兩個狀態(tài)變量的問題轉(zhuǎn)化為只含有一個狀態(tài)變量的問題。二、生產(chǎn)與存儲問題在生產(chǎn)和經(jīng)營管理中，經(jīng)常遇到要合理地安排生產(chǎn)(或購買)與庫存的問題，達(dá)到既要滿足社會的需要，又要盡量降低成本費(fèi)用。因此，正確制定生產(chǎn)(或采購)策略，確定不同時期的生產(chǎn)量(或采購量)和庫存量，以使總的生產(chǎn)成本費(fèi)用和庫存費(fèi)用之和最小，這就是生產(chǎn)與存儲問題的最優(yōu)化目標(biāo)。2。1 生產(chǎn)計劃問題 設(shè)某公司對某種產(chǎn)品要制定一項n個階段的生產(chǎn)(或購買)計劃。已知它的初始庫存量為零，每階段生產(chǎn)(或購買)該產(chǎn)品的數(shù)量有上限的限制；每階段社會對該產(chǎn)品的需求量是已知的，公司保證供應(yīng)；在n階段末的終結(jié)庫存量為零。問該公司如

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

19、順序遞推關(guān)系式為：其中。這是因為一方面每階段生產(chǎn)的上限為m；另一方面由于保證供應(yīng)，故第k-1階段末的庫存量必須非負(fù)，即，所以。邊界條件為或從邊界條件出發(fā)，利用上面的遞推關(guān)系式，對每個k ，計算出中的在0至之間的值，最后求得的即為所求的最小總費(fèi)用。例3 某工廠要對一種產(chǎn)品制訂今后四個時期的生產(chǎn)計劃，據(jù)估計在今后四個時期內(nèi)，市場對于該產(chǎn)品的需求量如表9-5所示。表9-5時期(k)1234需求量()2324假定該廠生產(chǎn)每批產(chǎn)品的固定成本為3千元，若不生產(chǎn)就為0；每單位產(chǎn)品成本為1千元；每個時期生產(chǎn)能力所允許的最大生產(chǎn)批量為不超過6個單位；每個時期末未售出的產(chǎn)品，每單位需付存儲費(fèi)0。5千元。還假定在第

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

21、個時期的最優(yōu)生產(chǎn)決策為：其相應(yīng)的最小總成本為20。5千元。把上面例題中的有關(guān)數(shù)據(jù)列成表9-6，可找出一些規(guī)律性的東西。表9-6階段i01234需求量2324生產(chǎn)量5060庫存量03040由表中的數(shù)字可以看到，這類庫存問題有如下特征：(1) 對每個i，有，（i1，2，3，4）其中=0。(2) 對于最優(yōu)生產(chǎn)決策來說，可分解為兩個子問題，一個是從第1階段到第2階段；另一個是從第3階段到第4階段。每個子問題的最優(yōu)生產(chǎn)決策特別簡單，它們的最小總成本之和就等于原問題的最小總成本。如果對每個i，都有，則稱該點的生產(chǎn)決策(或稱一個策略)具有再生產(chǎn)點性質(zhì)(又稱重生性質(zhì))。如果=0，則稱階段i為再生產(chǎn)點(又稱重生

22、點)。由假設(shè)=0和=0 ，故階段0和n是再生產(chǎn)點?？梢宰C明：若庫存問題的目標(biāo)函數(shù)g(x)在凸集合S上是凹函數(shù)(或凸函數(shù))，則g(x)在S的頂點上具有再生產(chǎn)點性質(zhì)的最優(yōu)策略。下面運(yùn)用再生產(chǎn)點性質(zhì)來求庫存問題為凹函數(shù)的解。設(shè)(ji)為階段j到階段i的總成本，給定j1和i是再生產(chǎn)點，并且階段j到階段i期間的產(chǎn)品全部由階段j供給。則根據(jù)兩個再生點之間的最優(yōu)策略，可以得到一個更有效的動態(tài)規(guī)劃遞推關(guān)系式。設(shè)最優(yōu)值函數(shù)表示在階段i末庫存量=0時，從階段1到階段i的最小成本。則對應(yīng)的遞推關(guān)系式為 ，邊界條件為為了確定最優(yōu)生產(chǎn)決策，逐個計算。則(0)為n個階段的最小總成本。設(shè)為計算時，使(9-7)式右邊最小的j

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

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

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

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

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

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

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

30、要計算，必須先計算出為了要計算出，必須先計算出，一般地有相應(yīng)的最優(yōu)決策為=w/3，于是得到從而故最后得到所以，最優(yōu)裝入方案為，最大使用價值為13。 如果再增加對背包體積的限制為b，并假設(shè)第i種物品每件的體積為立方米，問應(yīng)如何裝使得總價值最大。這就是“二維背包問題”，它的數(shù)學(xué)模型為用動態(tài)規(guī)劃方法來解。這時，狀態(tài)變量是兩個(重量和體積的限制)，決策變量仍是一個(物品的件數(shù))。設(shè)最優(yōu)值函數(shù)為表示當(dāng)總重量不超過w公斤，總體積不超過v立方米時，背包中裝入第1種到第k種物品的最大使用價值。故因而可寫出順序遞推關(guān)系式為最后算出即為所求的最大價值。四、復(fù)合系統(tǒng)工作可靠性問題若某種機(jī)器的工作系統(tǒng)由n個部件串聯(lián)組

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

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

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

34、問題設(shè)有n個工件需要在機(jī)床A、B上加工，每個工件都必須經(jīng)過先A而后B的兩道加工工序(見圖9-1)。以、分別表示工件在A、B上的加工時間。問應(yīng)如何在兩機(jī)床上圖9-1安排各工件加工的順序，使在機(jī)床A上加工第一個工件開始到在機(jī)床B上將最后一個工件加工完為止，所用的加工總時間最少?下面用動態(tài)規(guī)劃方法來研究同順序兩臺機(jī)床加工n個工件的排序問題。當(dāng)加工順序取定之后，工件在A上加工時沒有等待時間，而在B上則常常等待。因此，尋求最優(yōu)排序方案只有盡量減少在B上等待加工的時間，才能使總加工時間最短。設(shè)第i個工件在機(jī)床A上加工完畢以后，在B上要經(jīng)過若干時間才能加工完，故對同一個工件來說，在A、B上總是出現(xiàn)加工完畢的

35、時間差， 我們以它來描述加工狀態(tài)?，F(xiàn)在，我們以在機(jī)床A上更換工件的時刻作為時段。以X表示在機(jī)床A上等待加工的按取定順序排列的工件集合。以x表示不屬于X的在A上最后加工完的工件。以t表示在A上加工完x的時刻算起到B上加工完x所需的時間。這樣，在A上加工完一個工件之后，就有(X，t)與之對應(yīng)。選取(X，t)作為描述機(jī)床A、B在加工過程中的狀態(tài)變量。這樣選取狀態(tài)變量，則當(dāng)X包含有s個工件時，過程尚有s段，其時段數(shù)已隱含在狀態(tài)變量之中，因而，指標(biāo)最優(yōu)值函數(shù)只依賴于狀態(tài)而不明顯依賴于時段數(shù)。令為由狀態(tài)(X，t)出發(fā)，對未加工的工件采取最優(yōu)加工順序后，將X中所有工件加工完所需時間。為由狀態(tài)(X，t)出發(fā)，

36、在A上加工工件i后，對以后未加工的工件采取最優(yōu)加工順序后，將X中所有工件加工完所需時間。為由狀態(tài)(X，t)出發(fā)，在A上相繼加工工件i與j后，對以后加工的工件采取最優(yōu)順序后，將X中的工件全部加工完所需要的時間。不難得到 記，上式就可合并寫成其中X/i表示在集合X中去掉工件i后剩下的工件集合。由定義，可得 其中是在機(jī)床A上從X出發(fā)相繼加工工件i、j，并從它將j加工完的時刻算起，至在B上相繼加工工件i、j并將工件加工完所需時間。故是在A加工i、j后所形成的新狀態(tài)。即在機(jī)床A上加工i、j后由狀態(tài)(X，t)轉(zhuǎn)移到狀態(tài)。仿照的定義，以代替，代替t，代替，代替，則可得故將i、j對調(diào)，可得由于為t的單調(diào)上升函

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

38、是在已排定位置的工件之后(或之前)。如此繼續(xù)下去，直至把所有工件都排完為止。例9 設(shè)有5個工件需在機(jī)床A、B上加工，加工的順序是先A后B，每個工件所需加工時間(單位：小時)如表9-10所示。問如何安排加工順序，使機(jī)床連續(xù)加工完所有工件的加工總時間最少?并求出總加工時間。表9-10 加工時間 機(jī)床工件號碼AB136272347453574解 工件的加工工時矩陣為根據(jù)最優(yōu)排序規(guī)則，故最優(yōu)加工順序為：總加工時間為28小時。六、 設(shè)備更新問題在工業(yè)和交通運(yùn)輸企業(yè)中，經(jīng)常碰到設(shè)備陳舊或部分損壞需要更新的問題。從經(jīng)濟(jì)上來分析，一種設(shè)備應(yīng)該用多少年后進(jìn)行更新為最恰當(dāng)，即更新的最佳策略應(yīng)該如何，從而使在某一時

39、間內(nèi)的總收入達(dá)到最大(或總費(fèi)用達(dá)到最小)。現(xiàn)以一臺機(jī)器為例，隨著使用年限的增加，機(jī)器的使用效率降低，收入減少，維修費(fèi)用增加。而且機(jī)器使用年限越長，它本身的價值就越小，因而更新時所需的凈支出費(fèi)用就愈多。設(shè)： 在第j年機(jī)器役齡為t年的一臺機(jī)器運(yùn)行所得的收入。 在第j年機(jī)器役齡為t年的一臺機(jī)器運(yùn)行時所需的運(yùn)行費(fèi)用。 在第j年機(jī)器役齡為t年的一臺機(jī)器更新時所需更新凈費(fèi)用。 折扣因子()，表示一年以后的單位收入的價值視為現(xiàn)年的單位。T 在第一年開始時，正在使用的機(jī)器的役齡。n 計劃的年限總數(shù)。 在第j年開始使用一個役齡為t年的機(jī)器時，從第j年至第n年內(nèi)的最佳收入。 給出時，在第j年開始時的決策(保留或更新)。 為了寫出遞推關(guān)系式，先從兩方面分析問題。若在第j年開始時購買了新機(jī)器，則從第j年至第n年得到的總收入應(yīng)等于在第j年中由新機(jī)器獲得的收入，減去在第j年中的運(yùn)行費(fèi)用，減去在第j年開始時役齡為t年的機(jī)器的更新凈費(fèi)用，加上在第j+1年開始使用役齡為1年的機(jī)器從第j+1年至第n年的最佳收入；若在第j年開始時繼續(xù)使用役齡為t年的機(jī)器，則從第j年至第n年的總收入應(yīng)等于在第j年由役齡為t年的機(jī)器得到的收入，減去在第j年中役齡為t年的機(jī)器的運(yùn)行費(fèi)用，加上在第j+1年開始使用役齡為t+1年的機(jī)器從第j+1年至第n年的最佳收入。然后，比較它們的大小，選取大的，并相應(yīng)得出是更新還是保留的決策。將上面的分