運(yùn)籌學(xué)第06章動態(tài)規(guī)劃

1、第六章 動態(tài)規(guī)劃 (Dynamic programming)多階段決策問題及其舉例 動態(tài)規(guī)劃的基本概念及基本方程 資源分配問題 生產(chǎn)與存儲問題 背包問題 其他動態(tài)規(guī)劃問題WinQSB軟件應(yīng)用 動態(tài)規(guī)劃是解決多階段決策問題最優(yōu)化的一種數(shù)學(xué)方法，大約產(chǎn)生于50年代，1951年美國數(shù)學(xué)家數(shù)學(xué)家貝爾曼(R.Bellman)等人根據(jù)多階段決策問題的特點(diǎn)，把多階段決策問題變換為一系列相互聯(lián)系的單階段問題，然后逐個加以解決。與此同時他提出了解決這類問題的最優(yōu)性原理，研究了許多實(shí)際問題，從而創(chuàng)立了解決最優(yōu)化問題的一種新方法動態(tài)規(guī)劃（Dynmamic Programming），他的名著動態(tài)規(guī)劃于1957年出版。

2、 動態(tài)規(guī)劃問世之初，受計算技術(shù)水平的限制，對人們所關(guān)心的許多復(fù)雜問題難以進(jìn)行處理。以后,隨著計算技術(shù)的進(jìn)步,動態(tài)規(guī)劃的思想方法,在工程技術(shù)、企業(yè)管理、工農(nóng)業(yè)生產(chǎn)以及軍事等部門都有廣泛的應(yīng)用。例如在企業(yè)管理方面，動態(tài)規(guī)劃可以用來解決最優(yōu)路徑問題、資源分配問題、生產(chǎn)調(diào)度問題、庫存問題、裝載問題、排序問題、設(shè)備更新問題、生產(chǎn)過程最優(yōu)控制問題等等。 第一節(jié) 多階段決策問題及其舉例 動態(tài)規(guī)劃是用來解決多階段決策過程最優(yōu)化的一種數(shù)量方法。其特點(diǎn)在于，它可以把一個n 維決策問題變換為幾個一維最優(yōu)化問題，從而一個一個地去解決。 需指出：動態(tài)規(guī)劃是求解某類問題的一種方法，是考察問題的一種途徑，而不是一種算法。必

3、須對具體問題進(jìn)行具體分析，運(yùn)用動態(tài)規(guī)劃的原理和方法，建立相應(yīng)的模型，然后再用動態(tài)規(guī)劃方法去求解。 多階段決策過程最優(yōu)化的目標(biāo)，就是要在所有可采取的策略中選取一個最優(yōu)的策略，從而使整個過程在預(yù)定目標(biāo)下達(dá)到最好的活動效果。 所謂多階段決策問題是指這樣一類活動過程：由于它的特殊性，可將整個過程按照時間劃分為若干個互相聯(lián)系的階段，在它的每一個階段都需要作出決策，當(dāng)各個階段決策確定后，就組成了一個決策序列，因而也就確定了整個過程的一條活動路線。如下圖： 12n狀態(tài)決策狀態(tài)決策狀態(tài)狀態(tài)決策狀態(tài) 2、即在系統(tǒng)發(fā)展的不同時刻（或階段）根據(jù)系統(tǒng)所處的狀態(tài)，不斷地做出決策；一、動態(tài)決策問題的特點(diǎn) 1、系統(tǒng)所處的狀

4、態(tài)和時刻是進(jìn)行決策的重要因素；3、找到不同時刻的最優(yōu)決策以及整個過程的最優(yōu)策略。二、多階段決策問題舉例 如果由A點(diǎn)經(jīng)過P點(diǎn)和H點(diǎn)而到達(dá)G點(diǎn)是一條最短線路，則由P點(diǎn)出發(fā)經(jīng)過H點(diǎn)到達(dá)終點(diǎn)的這條子線路，相對于從P點(diǎn)出發(fā)到達(dá)終點(diǎn)的所有可選擇的不同線路來說，PG為最短線路。 【例6-1】生產(chǎn)與存貯問題。某工廠每月需供應(yīng)市場一定數(shù)量的產(chǎn)品，并將所余產(chǎn)品存入倉庫。一般某月適當(dāng)增加產(chǎn)量可降低生產(chǎn)成本，但超產(chǎn)部分存入倉庫會增加庫存費(fèi)用。要求確定一個逐月的生產(chǎn)計劃，在滿足需求的條件下，使一年的生產(chǎn)與存貯費(fèi)用之和最小。 本例中，我們可以把每個月作為一個階段，全年分為12個階段逐次決策。 【例6-2】設(shè)備更新問題。企

5、業(yè)在使用設(shè)備時都要考慮設(shè)備的更新問題，因為設(shè)備越陳舊所需的維修費(fèi)用越多，但購買新設(shè)備則要一次性支出較大的費(fèi)用?，F(xiàn)某企業(yè)要決定一臺設(shè)備未來8年的更新計劃，已預(yù)測了第j 年購買設(shè)備的價格為Ki，設(shè)Gj為設(shè)備經(jīng)過 j 年后的殘值，Cj為設(shè)備連續(xù)使用j-1年后在第j 年的維修費(fèi)(j =1，2，n)，問應(yīng)在哪些年更新設(shè)備可使總費(fèi)用最小。 【例6-3】投資決策問題。某公司現(xiàn)有資金Q萬元，在今后5年內(nèi)考慮給A、B、C、D四個項目投資，這些項目投資的回收期限、回報率均不相同，問該公司應(yīng)如何確定這些項目每年的投資額，使到第5年年末擁有資金的本利總額最大。這是一個5階段決策問題。 第二節(jié) 動態(tài)規(guī)劃的基本概念及基本

6、方程一、動態(tài)規(guī)劃的基本概念 【例6-4】最短路問題。今有如圖6-2所示交通網(wǎng)絡(luò)，頂點(diǎn)連接線段上的數(shù)字表示兩地距離，求s至t距離最短的線路。 1、階段 把一個問題的過程，恰當(dāng)?shù)胤譃槿舾蓚€相互聯(lián)系的階段，以便于按一定的次序去求解。 描述階段的變量稱為階段變量，通常用k表示。階段的劃分，一般是根據(jù)時間和空間的自然特征來進(jìn)行的，但要便于問題轉(zhuǎn)化為多階段決策。8A1A2A3sB1B2B3C1C2t6473643562652744445 例6-4中，從s到t可以分成四個階段：sA(A有三種選擇，A1或A2或A3)，AB(B1或B2或B3)，BC(C1或C2)，Ct，因此k1，2，3，4。 表示每個階段開始

7、所處的自然狀況或客觀條件。 狀態(tài)變量的取值有一定的允許集合或范圍，此集合稱為狀態(tài)允許集合，第k階段的可能狀態(tài)集用Sk 表示。2、狀態(tài) 描述各階段狀態(tài)的變量稱為狀態(tài)變量，常用sk表示第k階段的狀態(tài)變量。 在例6-4中，第一階段有一個狀態(tài)s，則S1=s；第二階段的狀態(tài)有A1、A2、A3三個，則S2=A1,A2,A3；第三階段的狀態(tài)也有B1、B2和B3三個，則S3=B1,B2,B3；第四階段的狀態(tài)有兩個，C1和C2，記為則S4=C1,C2。 3.決策和策略 當(dāng)各階段的狀態(tài)確定以后，就可以做出不同的選擇，從而確定下一階段的狀態(tài)，這種選擇稱為決策。 表示決策的變量稱為決策變量，用uk(sk)表示第k階段

8、狀態(tài)為sk 時的決策變量。在實(shí)際問題中，決策變量的取值往往限制在一定范圍內(nèi)，我們稱該范圍為允許決策集合，用Dk(sk)表示第k階段狀態(tài)為 sk 時的允許決策集合，顯然uk(sk)Dk(sk)。 在例6-4中，從第二階段的狀態(tài)A1出發(fā)，可選擇下一階段到達(dá)B1、B2或B3，即第二階段狀態(tài)為A1時的允許決策集合為D2(A1)=B1，B2，B3。如決定選B2，則可表示為u2(A1)=B2。4.狀態(tài)轉(zhuǎn)移方程 各階段的決策確定后，整個問題的決策序列就構(gòu)成一個策略。含n個階段的動態(tài)規(guī)劃問題的策略可表示為u1(s1)，u2(s2)，un(sn)。自第k 階段開始到最后第 n 階段的決策序列稱為k子策略，記為u

9、k(sk)，uk+1(sk+1)，un(sn)。 動態(tài)規(guī)劃中本階段的狀態(tài)往往是上一階段狀態(tài)和上一階段的決策結(jié)果。如果給定了第k 階段的狀態(tài)sk，本階段決策為uk(sk)，則第k+1階段的狀態(tài)sk+1也就完全確定，它們的關(guān)系可表示為： 由于它表示了由k 階段到k+1階段的狀態(tài)轉(zhuǎn)移規(guī)律，所以稱為狀態(tài)轉(zhuǎn)移方程。 5.指標(biāo)函數(shù) 階段指標(biāo)函數(shù) 階段指標(biāo)函數(shù)是指第k 階段，從狀態(tài)sk 出發(fā)，采取決策uk(sk)時的效益，用vk(sk，uk)表示。 過程指標(biāo)函數(shù) 過程指標(biāo)函數(shù)是指從第k階段的狀態(tài)sk(k1，2，n)出發(fā)，采取某種策略到第n階段的終止?fàn)顟B(tài)時的效益，它與所選取的策略有關(guān)，因此常記作： 常用的指標(biāo)

10、函數(shù)的形式有各階段指標(biāo)函數(shù)的和的形式和積的形式兩種。 和的形式 積的形式 指標(biāo)函數(shù)的最優(yōu)值稱為最優(yōu)值函數(shù)，是指對某一確定狀態(tài)選取最優(yōu)策略后得到的指標(biāo)函數(shù)值。對應(yīng)于從狀態(tài)sk 出發(fā)的最優(yōu)子策略的最優(yōu)值函數(shù)，記為fk(sk)，則有： 其中opt表示最優(yōu)化，可根據(jù)具體問題取max(求最大)或min(求最小)。 二、動態(tài)規(guī)劃的數(shù)學(xué)模型 動態(tài)規(guī)劃的數(shù)學(xué)模型可以描述如下： 建立實(shí)際問題的動態(tài)規(guī)劃模型一般可遵循以下步驟： 第一，按時間或空間順序?qū)⒍嚯A段決策問題劃分為適當(dāng)?shù)碾A段； 第二，恰當(dāng)選擇狀態(tài)變量sk，使它既能確切地描述過程的演變，又滿足過程的無后效性； 第三，確定決策變量uk 及每階段的容許決策集Dk

11、(sk)。狀態(tài)變量和決策變量可以是連續(xù)的，也可以是離散的； 第四，正確寫出狀態(tài)轉(zhuǎn)移方程sk+1Tk(sk，uk)； 第五，正確寫出指標(biāo)函數(shù)Vk,n，它應(yīng)具有可分離性，并滿足遞推關(guān)系。 三、動態(tài)規(guī)劃的基本方程 在n階段決策過程中，當(dāng)指標(biāo)函數(shù)滿足 時，根據(jù)最優(yōu)值函數(shù)的定義有：當(dāng)指標(biāo)函數(shù)滿足 時，有：動態(tài)規(guī)劃的求解有兩種基本方法：逆序解法和順序解法。 若尋優(yōu)方向與實(shí)際行進(jìn)方向相反，即從最后一階段開始計算，逐段前推，求得全過程的最優(yōu)解，則稱為逆序解法。 若尋優(yōu)方向與實(shí)際行進(jìn)方向相同，計算時從第一階段開始向后遞推，計算后一階段要用到前一階段的結(jié)果，最后一階段的結(jié)果就是全過程的最優(yōu)結(jié)果，則稱為順序解法。

12、下面我們用例6-4來說明順序解法。 將求s至t的最短路問題視為一個四階段決策問題，設(shè)： sk 第k 階段的初始狀態(tài)。 sk+1 第k 階段的終止?fàn)顟B(tài)。 uk 第k 階段選擇的路線。狀態(tài)轉(zhuǎn)移方程：skuk(sk+1) vk(sk+1，uk)第k 階段選擇路線uk 時增加的距離，即從初 始狀態(tài)sk 到sk+1 的距離。 fk(sk+1)從起點(diǎn)s到第k階段終止?fàn)顟B(tài)sk+1 的距離。 于是，可得下面的動態(tài)規(guī)劃基本方程： k=0時，f0(s1)= f0(s)=0，這是邊界條件。 k=1時，S2=A1，A2，A3 8A1A2A3s64k=2時，S3=B1，B2，B3 B1B2B38A1A2A3s64736

13、435626即從s到B1的最短路線為：sA2B1或sA3B1。 即從s到B2的最短路線為：sA3B2。 即從s到B3的最短路線為：sA3B3。 C1C2B1B2B38A1A2A3s64736435626527444k=3時，S4=C1，C2 即從s到C1的最短路線為：sA2B1C1 或sA3B1C1。 即從s到C2的最短路線為：sA3B2C2。 k=4時，S5=t 即從s到t的最短路線為：sA3B2C2t。 t4C1C2B1B2B38A1A2A3s647364356265274445即從s到t的最短距離為：4+2+4+5=15第三節(jié) 資源分配問題 資源分配問題就是將一定數(shù)量的一種或幾種資源恰當(dāng)

14、地分配給若干使用者，以獲取最大效益。這里的資源可以是資金、設(shè)備、原材料、勞動力等。資源分配問題是動態(tài)規(guī)劃的典型應(yīng)用之一。本節(jié)和后面幾節(jié)中我們都采用逆序解法來求解動態(tài)規(guī)劃問題。 一、一維資源分配問題 假設(shè)某部門掌握總數(shù)為a的某種資源，現(xiàn)有n 個項目提出對這種資源的需求。若把數(shù)量為xk 的資源分配給第k 個項目，則其相應(yīng)的收益為gk(xk)。問應(yīng)如何分配這種資源，才能獲得最大收益？ 這個問題可寫成如下的規(guī)劃模型： 把它看做一個多階段決策問題，從而應(yīng)用動態(tài)規(guī)劃方法求解。確定一個項目的資源分配數(shù)量視為一個階段，于是共有n個階段。令： sk 分配給第k 個項目到第n 個項目的資源數(shù)量之和。 xk 分配給

15、第k 個項目的資源數(shù)量。 vk(sk，xk)從sk 中取出xk 數(shù)量的資源分配給第k 個項目 可獲得的收益。即： fk(sk)將數(shù)量為sk 的資源分配給第k 個項目到第n 個項 目可獲得的最大收益。 于是，可得到下面的狀態(tài)轉(zhuǎn)移方程和動態(tài)規(guī)劃基本方程： 【例6-5】某公司有資金10萬元，若投資于項目xi(i=1,2,3)的投資額為xi時，其收益分別為g(x1)=4x1, g(x2)=9x2, g(x3)=2x32,問應(yīng)如何分配投資數(shù)額才能使總收益最大？ 解:該問題的靜態(tài)模型為： 將投資項目排序時，首先考慮對項目1的投資，然后再考慮對項目2的投資，最后考慮對項目3的投資，這樣可以把問題劃分為3個階

16、段，每個階段只決定對一個項目應(yīng)投資的金額。這樣就把問題轉(zhuǎn)化為一個3段決策過程。 通?？梢园褯Q策變量uk 定為原問題中的變量xk ，即設(shè)：uk=xk (k=1,2,3)把每個階段可供使用的資金定為狀態(tài)變量sk，初始狀態(tài)s1=10。當(dāng)?shù)谝浑A段(k =1)時，有：當(dāng)?shù)诙A段(k =2)時，有：第k 階段時，有：于是，有：階段k=1,2,3； 狀態(tài)變量sk ：第k段可以投資于第k 到第3個項目的資金；決策變量xk ：決定給第k 個項目投資的資金； 狀態(tài)轉(zhuǎn)移方程：sk+1 =sk - xk 最優(yōu)目標(biāo)函數(shù)fk(sk)：可投資金為sk 時，投資第k-3項所得的最大收益。 該問題的動態(tài)規(guī)劃基本方程為： 指標(biāo)函

17、數(shù)：下面用逆序解法求解例6-5：當(dāng)k=3時： 顯然，當(dāng)x3=s3時，f3(s3)取得極大值，即：當(dāng)k=2時：令： 由 所以 為極小值點(diǎn)。 而： 解得： 故極大值只可能在0,s2的端點(diǎn)處取得，則：f2(0)與f2(s2)的關(guān)系，有以下三種情況： f2(0)=f2(s2)，即：解得： f2(0)f2(s2)，即：解得： f2(0)f2(s2)，即：當(dāng)k=1時： 當(dāng)f2(s2)=9s2為最大時： 當(dāng)f2(s2)=2s22為最大時：，與s29/2矛盾，所以舍去。 令： 解得：由 解得： 所以 為極小值點(diǎn)。 而： 故極大值只可能在0,s1的端點(diǎn)處取得。比較兩個端點(diǎn)：再由狀態(tài)轉(zhuǎn)移方程順推得： 因為 所以：

18、 例 設(shè)有500萬元資金用于擴(kuò)建三個工廠A、B、C，各廠獲得資金后的利潤增長額與投資數(shù)有關(guān)，詳細(xì)數(shù)據(jù)如下表所示： 543210C742100B333220A利潤增長額543210投資數(shù)(百萬元)解：將問題視為三個階段決策問題。sk 表示k 階段初可用的投資數(shù)； uk 為分配給第k 個工廠的資金數(shù)； 狀態(tài)轉(zhuǎn)移方程為sk+1sk - uk fk(sk)表示sk資金被分配給工廠k - n 后，所得利潤增長額。 問應(yīng)如何確定這三個工廠的投資數(shù)，使總的利潤增長額為最大？ 則該問題的動態(tài)規(guī)劃基本方程為： 當(dāng)k=3時，s3的可能取值為0、1、2、3、4、5，這些投資全部分配給C工廠，即u3=s3。因此有以下

19、關(guān)系式：若s3=0，則：若s3=1，則：若s3=2，則：若s3=3，則：若s3=4，則：543210C742100B333220A利潤增長額543210投資數(shù)(百萬元)若s3=5，則：用表格表示為：543210543210 u3s3012345012345012345 當(dāng)k=2時，s2的可能取值為0、1、2、3、4、5，這些投資全部分配給B工廠和C工廠，即u2s2。因此有以下關(guān)系式：若x2=0，則u2=x2=0 若s2=1，則u2的取值可以為0、1，利用狀態(tài)轉(zhuǎn)移方程知s3的取值為1、0。 若s2=2，則u2的取值可以為0、1、2，利用狀態(tài)轉(zhuǎn)移方程知s3的取值為2、1、0。543210C7421

20、00B333220A利潤增長額543210投資數(shù)(百萬元) 若s2=3，則u2的取值可以為0、1、2、3，利用狀態(tài)轉(zhuǎn)移方程知s3的取值為3、2、1、0。 若s2=4，則u2的取值可以為0、1、2、3、4，利用狀態(tài)轉(zhuǎn)移方程知s3的取值為4、3、2、1、0。 若s2=5，則u2的取值可以為0、1、2、3、4、5，利用狀態(tài)轉(zhuǎn)移方程知s3的取值為5、4、3、2、1、0。用表格表示為：543210543210 u2s20+00+10+20+30+40+50+00+10+20+30+41+01+11+21+32+02+12+24+04+17+001234700000/45543210C742100B333

21、220A利潤增長額543210投資數(shù)(百萬元) 當(dāng)k=1時，s1的可能取值為5，這些投資全部分配給A工廠、B工廠和C工廠，即u1s1。因此有以下關(guān)系式：用表格表示為：5543210 u1s10+72+42+33+23+13+070543210C742100B333220A利潤增長額543210投資數(shù)(百萬元)543210543210 u2s20+00+10+20+30+40+50+00+10+20+30+41+01+11+21+32+02+12+24+04+17+00123470123455543210 u1s10+72+42+33+23+13+070543210543210 u2s20+00

22、+10+20+30+40+50+00+10+20+30+41+01+11+21+32+02+12+24+04+17+0012347012345543210543210 u3s3012345012345012345 【例】某企業(yè)根據(jù)計劃安排，擬將某種高效率的設(shè)備五臺，分配給所屬的甲、乙、丙三個工廠，各工廠若獲得這種設(shè)備之后，可以為企業(yè)提供的盈利如下表所示。 問：這五臺設(shè)備如何分配給各工廠，才能使企業(yè)得到的盈利最大。 121113512111241111936107245310000丙乙甲 工廠 盈利設(shè)備臺數(shù) 解：將問題按工廠分為三個階段，即k=1、2、3。 設(shè)sk 表示為分配給第k 個工廠至第n

23、 個工廠的設(shè)備臺數(shù)。 狀態(tài)轉(zhuǎn)移方程為： 表示 sk 臺設(shè)備分配給第k個工廠至第n個工廠時所得到的最大盈利值。 因而可寫出逆推關(guān)系式為：表示 uk 臺設(shè)備分配到第k個工廠所得的盈利值。 下面從最后一個階段開始向前逆推計算。uk 表示為分配給第k 個工廠的設(shè)備臺數(shù)。121113512111241111936107245310000丙乙甲 543210543210u3*f3(s3)g3(u3)u3s3406111212406111212102345 第三階段： 設(shè)將s3臺設(shè)備(s3=0,1,2,3,4,5)全部分配給工廠丙時，則最大盈利為：其中x3=s3=0,1,2,3,4,5 因為此時只有一個工廠

24、，有多少臺設(shè)備就全部分配給工廠丙，故它的盈利值就是該段的最大盈利值，如下表：543210543210 第二階段： 設(shè)把s2臺設(shè)備(s2=0,1,2,3,4,5)分配給工廠乙和工廠丙時，則對每個s2值，有一種最優(yōu)分配方案，使最大盈利值為：121113512111241111936107245310000丙乙甲 其數(shù)值計算如下表所示：00+40+60+110+120+1255+45+65+115+121010+410+610+111111+411+61111+411501014162110221,22其中121113512111241111936107245310000丙乙甲 第一階段： 設(shè)把s1

25、臺(這里只有s1=5的情況)設(shè)備分配給甲、乙、丙三個工廠時，則最大盈利值為：其中 因為給甲工廠u1臺，其盈利為g1(u1) ，剩下的5u1臺就分給乙和丙兩個工廠，則它的盈利最大值為f2(5u1) 。其數(shù)值計算如下表所示：55432100+2113+09+1012+5210,23+167+1455432100+2113+09+1012+5210,23+167+1454321054321000+40+60+110+120+1255+45+65+115+121010+410+610+111111+411+61111+411501014162110221,22 即得甲工廠分配0臺，乙工廠分配2臺，丙工

26、廠分配3臺。 或：甲工廠分配2臺，乙工廠分配2臺，丙工廠分配1臺。 以上兩個分配方案所得到的總盈利均為21萬元。 例 現(xiàn)有1000臺機(jī)床，要投入到A、B兩個生產(chǎn)部門，計劃連續(xù)使用5年。在A部門的收益函數(shù)為g(uA)=7uA，其中uA為投入生產(chǎn)的機(jī)床數(shù)，年末機(jī)床完好率為a=0.4；在B部門的收益函數(shù)為h(uB)=3uB，其中uB為投入生產(chǎn)的機(jī)床數(shù)，年末機(jī)床完好率為b=0.8求5年間總收益最大的年度機(jī)床分配計劃方案。 解：這是一個5階段決策過程，一個年度為一個階段。利用上述假設(shè)，狀態(tài)轉(zhuǎn)移方程為： sk+1auk+b(sk-uk)=0.8sk-0.4uk (k=1，2，3，4)相應(yīng)的動態(tài)規(guī)劃基本方程

27、: k=5時，0u5s5，因f6(s6)=0，有： 資源連續(xù)分配問題k=4時，0u4s4，由動態(tài)規(guī)劃基本方程得： k=3時，0u3s3，由動態(tài)規(guī)劃基本方程得： k=2時，0u2s2，由動態(tài)規(guī)劃基本方程得： k=1時，0u1s1，由狀態(tài)轉(zhuǎn)移方程知： 由于階段1的初始狀態(tài)s1是唯一給定的，s1=1000，因此，問題的最大總收益為f1(1000)12388.8 。 按計算順序反向推算，可求出最優(yōu)策略以及執(zhí)行最優(yōu)策略時各階段初的完好機(jī)床數(shù)： 二、二維資源分配問題 此問題可寫成如下數(shù)學(xué)模型： 在資源分配問題中，若考慮的資源有兩種時，便是二維資源分配問題。一般的二維資源分配問題可敘述如下：某部門具有總數(shù)分

28、別為 a 和 b 的兩種資源，現(xiàn)有 n 個項目提出對這兩種資源的需求。若把數(shù)量為 xk 的資源A和數(shù)量為 yk 的資源B分配給項目k ，可獲得收益vk(xk，yk)。問應(yīng)如何分配這兩種資源，使總收益最大？ 用動態(tài)規(guī)劃方法來求解，狀態(tài)變量和決策變量要取二維的。 設(shè)： (sk，tk)sk 和tk 分別為分配給第k 至第n 個項目的資源A和資源B的總量。 (xk，yk)xk 和yk 分別為分配給第k 個項目的資源A和資源B的總量。 vk(sk，tk，xk，yk)從sk 中取出數(shù)量為xk 的資源A，從tk 中取出數(shù)量為yk 的資源B分配給項目k 可獲得的收益。即： fk(sk，tk)將數(shù)量為sk 的資

29、源A和數(shù)量為tk 的資源B分配給第k至第n個項目可獲得的最大收益。 于是可得下面的狀態(tài)轉(zhuǎn)移方程和基本方程： 第四節(jié) 生產(chǎn)與存儲問題 【例6-7】某工廠生產(chǎn)并銷售某種產(chǎn)品，已知今后4個月的市場需求預(yù)測如表6-8，又每月生產(chǎn)j 單位產(chǎn)品的費(fèi)用為： 每月庫存j 單位產(chǎn)品的費(fèi)用為E(j)=0.5j(千元)，該廠最大庫存容量為3單位，每月最大生產(chǎn)能力為6單位，計劃開始和計劃期末庫存量都是零。試制定4個月的生產(chǎn)計劃，在滿足用戶需求條件下總費(fèi)用最小。 假設(shè)第i+1個月的庫存量是第i 個月可銷售量與該月用戶需求量之差；而第i 個月的可銷售量是本月初庫存量與產(chǎn)量之和。 4232gi(需求量)4321i(月)解：

30、將每個月視為一個階段，因此k=1，2，3，4。設(shè) 狀態(tài)變量sk：第k 個月月初的庫存量。 決策變量uk：第k 個月的產(chǎn)量。 一、生產(chǎn)瞬時完成 狀態(tài)轉(zhuǎn)移方程：sk+1skukgk 指標(biāo)函數(shù)：vk(sk，uk)第k 個月的生產(chǎn)和存儲費(fèi)用。即 最優(yōu)值函數(shù)fk(sk)：當(dāng)?shù)趉 個月月初的庫存量為sk 時，采取最佳策略生產(chǎn)，從本月到計劃結(jié)束(第4月末)的最低生產(chǎn)與存儲費(fèi)用。 則動態(tài)規(guī)劃基本方程為： 當(dāng)k=4時 因為s5=0，故本月產(chǎn)量應(yīng)為u4g4s44s4，又因為最大庫存量為3，故s4只能取0，1，2，3。 則u4 取值4，3，2，3。 列出 與u4(s4)，如表6-9所示：f4(s4)1234u4(s

31、4)3210s4當(dāng)k=3時 狀態(tài)變量s3的取值范圍，取決于庫存能力、產(chǎn)量和需求量。因為最大庫存量為3，故s3只能在0，1，2，3中取。 變量u3的允許決策集合，受最大生產(chǎn)能力、最大庫存量、需求量和計劃期末庫存量為0這幾個方面的限制，應(yīng)滿足： 76.565.5u3下限u3上限062-s35-s36-s3故有： 對s3=0，1，2，3分別求出f3(s3)的值。 計算過程如表6-10所示。 且取整數(shù) u3*(s3)f3(s3)C+E+f4u3(s3)3210s323451212.51313.5122123411.51212.51311.510123811.51212.580012811.51280當(dāng)

32、k=2時 類似地，有s2只能取0，1，2，3。 決策變量u2的允許決策集合，它同樣受最大生產(chǎn)能力、最大庫存量、需求量和計劃期末庫存量為0這幾個方面的限制，應(yīng)滿足： 15.53234u4*(s4)66.57f4(s4)210s4即：且取整數(shù) 根據(jù)基本方程： 對s2=0，1，2，3分別求出f2(s2)的值。 u2下限u2上限063-s26-s29-s2 u2*(s2) f2(s2)C+E+f3u2(s2)3210s234561818.51616165234517.51815.516.515.5412341717.51516153012313.51714.515.5013.5083012u3*(s3

33、)811.512f3(s3)210s3當(dāng)k=1時，由于s1=0，故u1的允許決策集合為 ：u1下限u1上限g263+g111即：根據(jù)基本方程： 可以列出f1(s1)與u1(s1)，如表6-12所示： 可知，4個月的最低費(fèi)用為f1(0)=21千元，第一個月的最優(yōu)產(chǎn)量為2單位。再由計算過程表6-11、表6-10、表6-9可推得最優(yōu)生產(chǎn)與存儲計劃為： u1*(s1)f1(s1)Cf25432u1(s1)0s1013.53345u2*(s2)1515.516f2(s2)210s22121.52221.5212083012u3*(s3)811.512f3(s3)210s315.53234u4*(s4)6

34、6.57f4(s4)210s4 即：第一個月生產(chǎn)2單位，第二個月庫存為0，生產(chǎn)5單位，第三個月庫存為2，不生產(chǎn)，第四個月庫存為0，生產(chǎn)4單位。 二、生產(chǎn)需要一定的時間 【例6-8】某工廠生產(chǎn)并銷售某種產(chǎn)品，有一個倉庫專門存放該產(chǎn)品，倉庫最大容量為1000單位。預(yù)計未來4個月該產(chǎn)品的需求將有極大的增長，存放的所有產(chǎn)品都能夠銷售出去。已知第k個月的單位成本為ck，銷售單價為pk，如表6-13所示。 1713812銷售單價（pk）1511910單位生產(chǎn)成本（ck）4321月份(k) 第一個月初該產(chǎn)品的庫存為500單位。由于產(chǎn)品生產(chǎn)周期較長，當(dāng)月開始生產(chǎn)的產(chǎn)品只能在下個月初入庫，因此工廠只能銷售倉庫現(xiàn)

35、有的貨。若不計庫存費(fèi)用，試確定未來4個月的生產(chǎn)與銷售計劃，使預(yù)期獲利最大。 解：將每個月視為一個階段，因此k=1，2，3，4。設(shè)： 狀態(tài)變量sk：第k個月月初倉庫的庫存量。 決策變量xk：第k個月的銷售量。 yk：第k個月開始生產(chǎn)的產(chǎn)量。 狀態(tài)轉(zhuǎn)移方程：sk+1sk-xkyk 指標(biāo)函數(shù)：vk(sk，xk，yk)第k個月的利潤。即： 最優(yōu)值函數(shù)fk(sk)：當(dāng)?shù)趉個月月初的庫存量為sk時，從本月到計劃結(jié)束(第4月末)的最大利潤。 則動態(tài)規(guī)劃基本方程為： 當(dāng)k=4時 顯然，當(dāng)x4*=s4，y4*=0時，f4(s4)取得最大值f4(s4)=17s4。 當(dāng)k=3時 這個階段需要求解一個線性規(guī)劃問題：

36、當(dāng)x3*=s3，y3*=1000-s3x3=1000時，f3(s3)取得最大值f3(s3)=6000+13s3。 當(dāng)k=2時 此階段也需要求解一個線性規(guī)劃問題： 解得：x2*=0， y2*=1000s2 故當(dāng)x2*=0， y2*=1000s2 時，f2(s2)取得最大值f2(s2)=10000+9s2。當(dāng)k=1時，由于s1=500，根據(jù)基本方程： 解線性規(guī)劃問題： 得：x1*=500， y1*=0，f1(500)=16000。 由上述過程逆推可得最優(yōu)生產(chǎn)與銷售計劃為： 第一個月月初庫存500單位，銷售500單位，不生產(chǎn)，第二個月月初庫存為0，銷售量為0，生產(chǎn)1000單位，第三個月月初庫存為10

37、00單位，銷售1000單位，生產(chǎn)1000，第四個月月初庫存為1000單位，銷售1000單位，不生產(chǎn)。 第五節(jié) 背包問題 背包問題的一般提法是：一位旅行者攜帶背包去登山，已知背包最大承重量為a 公斤，現(xiàn)有n 種物品可供他選擇裝入背包，第i 種物品的單件重量為ai 公斤，其價值(重要性系數(shù))是攜帶數(shù)量xi 的函數(shù)ci(xi)(i= 1，2，n)，問旅行者應(yīng)如何選擇攜帶各種物品的數(shù)量，使總價值最大？ 設(shè)xi 為第i 種物品的攜帶數(shù)量，則背包問題可歸結(jié)為如下形式的整數(shù)規(guī)劃模型： 下面用動態(tài)規(guī)劃的逆序解法求解背包問題： 階段k：將問題劃分為n 個階段，每階段裝入一種物品， k=1，2，n。 狀態(tài)變量sk

38、：第k 階段開始時背包中可裝入的第k 種到第n 種物品的重量。 決策變量xk：第k 種物品的攜帶數(shù)量。 狀態(tài)轉(zhuǎn)移方程：sk+1skakxk 指標(biāo)函數(shù)：vk(sk，xk)裝入的第k種物品的總價值。即 ： 最優(yōu)值函數(shù)fk(sk)：當(dāng)背包中可裝入的第k 種到第n 種物品的重量為sk 時，采用最優(yōu)策略所裝入的第k 種到第n 種物品的最大總價值。 則動態(tài)規(guī)劃基本方程為： 用動態(tài)規(guī)劃逆序解法逐步計算出最優(yōu)值及相應(yīng)的決策函數(shù)： 【例6-9】有一輛最大載重量為10噸的卡車，用以裝載3種貨物，每種貨物的單位重量及相應(yīng)的單位價值如表6-14所示。應(yīng)如何裝載可使總價值最大？ 654單位價值(ci)543單位重量(噸

39、)321貨物編號解：設(shè)第i種物品的攜帶數(shù)量為xi。則問題模型為： 按上述方法建立動態(tài)規(guī)劃模型，由于決策變量為離散值，故可用列表法求解。 當(dāng)k=3時： 狀態(tài)變量s3的可能取值范圍為0到10的整數(shù)，允許決策集為滿足05x3s3的整數(shù)。 由基本方程 可計算得如下結(jié)果： 00000 x3*(s3)00000f3(s3)210101010101000000 x3(s3)109876543210s 3當(dāng)k=2時： 狀態(tài)變量s2的可能取值范圍為0到10的整數(shù)，允許決策集為滿足04x2s2的整數(shù)。 由基本方程 可得如下結(jié)果： 01 2000 10000 x2*(s2)1211 10666 50000f2(s2

40、)101112101161056565656500000c2f 321021021010101010 0000 x2109876543210s206060606061206111112當(dāng)k=1時： 狀態(tài)變量s110，允許決策集為滿足03x110的整數(shù)，即x10，1，2，3。 由基本方程 可計算得如下結(jié)果： 2x1*(s1) 13f1(s1)1208546012c1f 23210 x1因此，f1(10)13，x1*2。再用逆向追蹤法求得最優(yōu)策略為： 即最優(yōu)策略是裝載第一種貨物2件，第二種貨物1件，不裝第三種貨物，可裝入的3種物品的最大價值為13。 第六節(jié) 其他動態(tài)規(guī)劃問題 設(shè)： 設(shè)備更新問題的一

41、般提法是：在已知一臺設(shè)備的收益函數(shù)r(t)，維修費(fèi)用函數(shù)u(t)及更新費(fèi)用函數(shù)c(t)的條件下，要求在n年內(nèi)的每年年初做出決策，是繼續(xù)使用舊設(shè)備還是更新設(shè)備，使n年總收益最大。 rk(t)：在第k年設(shè)備已使用過t 年(或稱役齡為t 年)，再使用1年時的收益。 uk(t)：在第k 年設(shè)備役齡為t 年，再使用一年的維修費(fèi)用。 ck(t)：在第k 年賣掉一臺役齡為t 年的設(shè)備，買進(jìn)一臺新設(shè)備的更新凈費(fèi)用。 為折扣因子(01)，表示一年以后的單位收入價值相當(dāng)于現(xiàn)年的單位。 用動態(tài)規(guī)劃方法求解如下： 階段k：將問題劃分為n 個階段，每年為一個階段， k=1，2，n。 狀態(tài)變量sk：第k年初，設(shè)備已使用過的年數(shù)，即役齡。 決策變量xk：第k年初更新設(shè)備還是繼續(xù)使用舊設(shè)備，分別用R或K表示。 狀態(tài)轉(zhuǎn)移方程： 階段指標(biāo)函數(shù)： 最優(yōu)值函數(shù)fk(sk)：第k年初設(shè)備役齡為sk 年時，采用最優(yōu)策略到第n 年末的最大收益。 則動態(tài)規(guī)劃基本方程為： 實(shí)際上 【例6-10】某臺新設(shè)備的年效益及年均維修費(fèi)、更新凈費(fèi)用如表