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

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

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

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

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

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

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

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

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

9、k(sk)，uk+1(sk+1)，un(sn)。 動(dòng)態(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ī)律，所以稱(chēng)為狀態(tài)轉(zhuǎn)移方程。 5.指標(biāo)函數(shù) 階段指標(biāo)函數(shù) 階段指標(biāo)函數(shù)是指第k 階段，從狀態(tài)sk 出發(fā)，采取決策uk(sk)時(shí)的效益，用vk(sk，uk)表示。 過(guò)程指標(biāo)函數(shù) 過(guò)程指標(biāo)函數(shù)是指從第k階段的狀態(tài)sk(k1，2，n)出發(fā)，采取某種策略到第n階段的終止?fàn)顟B(tài)時(shí)的效益，它與所選取的策略有關(guān)，因此常記作： 常用的指標(biāo)

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

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

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

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

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

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

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

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

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

19、關(guān)系式：若s3=0，則：若s3=1，則：若s3=2，則：若s3=3，則：若s3=4，則：543210C742100B333220A利潤(rùn)增長(zhǎng)額543210投資數(shù)(百萬(wàn)元)若s3=5，則：用表格表示為：543210543210 u3s3012345012345012345 當(dāng)k=2時(shí)，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利潤(rùn)增長(zhǎng)額543210投資數(shù)(百萬(wàn)元) 若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利潤(rùn)增長(zhǎng)額543210投資數(shù)(百萬(wàn)元) 當(dāng)k=1時(shí)，s1的可能取值為5，這些投資全部分配給A工廠、B工廠和C工廠，即u1s1。因此有以下關(guān)系式：用表格表示為：5543210 u1s10+72+42+33+23+13+070543210C742100B333220A利潤(rùn)增長(zhǎng)額543210投資數(shù)(百萬(wàn)元)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ù)計(jì)劃安排，擬將某種高效率的設(shè)備五臺(tái)，分配給所屬的甲、乙、丙三個(gè)工廠，各工廠若獲得這種設(shè)備之后，可以為企業(yè)提供的盈利如下表所示。 問(wèn)：這五臺(tái)設(shè)備如何分配給各工廠，才能使企業(yè)得到的盈利最大。 121113512111241111936107245310000丙乙甲 工廠 盈利設(shè)備臺(tái)數(shù) 解：將問(wèn)題按工廠分為三個(gè)階段，即k=1、2、3。 設(shè)sk 表示為分配給第k 個(gè)工廠至第n

23、 個(gè)工廠的設(shè)備臺(tái)數(shù)。 狀態(tài)轉(zhuǎn)移方程為： 表示 sk 臺(tái)設(shè)備分配給第k個(gè)工廠至第n個(gè)工廠時(shí)所得到的最大盈利值。 因而可寫(xiě)出逆推關(guān)系式為：表示 uk 臺(tái)設(shè)備分配到第k個(gè)工廠所得的盈利值。 下面從最后一個(gè)階段開(kāi)始向前逆推計(jì)算。uk 表示為分配給第k 個(gè)工廠的設(shè)備臺(tái)數(shù)。121113512111241111936107245310000丙乙甲 543210543210u3*f3(s3)g3(u3)u3s3406111212406111212102345 第三階段： 設(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è)工廠

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

25、臺(tái)(這里只有s1=5的情況)設(shè)備分配給甲、乙、丙三個(gè)工廠時(shí)，則最大盈利值為：其中 因?yàn)榻o甲工廠u1臺(tái)，其盈利為g1(u1) ，剩下的5u1臺(tái)就分給乙和丙兩個(gè)工廠，則它的盈利最大值為f2(5u1) 。其數(shù)值計(jì)算如下表所示：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臺(tái)，乙工廠分配2臺(tái)，丙工

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

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

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

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

30、將每個(gè)月視為一個(gè)階段，因此k=1，2，3，4。設(shè) 狀態(tài)變量sk：第k 個(gè)月月初的庫(kù)存量。 決策變量uk：第k 個(gè)月的產(chǎn)量。 一、生產(chǎn)瞬時(shí)完成 狀態(tài)轉(zhuǎn)移方程：sk+1skukgk 指標(biāo)函數(shù)：vk(sk，uk)第k 個(gè)月的生產(chǎn)和存儲(chǔ)費(fèi)用。即 最優(yōu)值函數(shù)fk(sk)：當(dāng)?shù)趉 個(gè)月月初的庫(kù)存量為sk 時(shí)，采取最佳策略生產(chǎn)，從本月到計(jì)劃結(jié)束(第4月末)的最低生產(chǎn)與存儲(chǔ)費(fèi)用。 則動(dòng)態(tài)規(guī)劃基本方程為： 當(dāng)k=4時(shí) 因?yàn)閟5=0，故本月產(chǎn)量應(yīng)為u4g4s44s4，又因?yàn)樽畲髱?kù)存量為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時(shí) 狀態(tài)變量s3的取值范圍，取決于庫(kù)存能力、產(chǎn)量和需求量。因?yàn)樽畲髱?kù)存量為3，故s3只能在0，1，2，3中取。 變量u3的允許決策集合，受最大生產(chǎn)能力、最大庫(kù)存量、需求量和計(jì)劃期末庫(kù)存量為0這幾個(gè)方面的限制，應(yīng)滿足： 76.565.5u3下限u3上限062-s35-s36-s3故有： 對(duì)s3=0，1，2，3分別求出f3(s3)的值。 計(jì)算過(guò)程如表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時(shí) 類(lèi)似地，有s2只能取0，1，2，3。 決策變量u2的允許決策集合，它同樣受最大生產(chǎn)能力、最大庫(kù)存量、需求量和計(jì)劃期末庫(kù)存量為0這幾個(gè)方面的限制，應(yīng)滿足： 15.53234u4*(s4)66.57f4(s4)210s4即：且取整數(shù) 根據(jù)基本方程： 對(duì)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時(shí)，由于s1=0，故u1的允許決策集合為 ：u1下限u1上限g263+g111即：根據(jù)基本方程： 可以列出f1(s1)與u1(s1)，如表6-12所示： 可知，4個(gè)月的最低費(fèi)用為f1(0)=21千元，第一個(gè)月的最優(yōu)產(chǎn)量為2單位。再由計(jì)算過(guò)程表6-11、表6-10、表6-9可推得最優(yōu)生產(chǎn)與存儲(chǔ)計(jì)劃為： 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 即：第一個(gè)月生產(chǎn)2單位，第二個(gè)月庫(kù)存為0，生產(chǎn)5單位，第三個(gè)月庫(kù)存為2，不生產(chǎn)，第四個(gè)月庫(kù)存為0，生產(chǎn)4單位。 二、生產(chǎn)需要一定的時(shí)間 【例6-8】某工廠生產(chǎn)并銷(xiāo)售某種產(chǎn)品，有一個(gè)倉(cāng)庫(kù)專(zhuān)門(mén)存放該產(chǎn)品，倉(cāng)庫(kù)最大容量為1000單位。預(yù)計(jì)未來(lái)4個(gè)月該產(chǎn)品的需求將有極大的增長(zhǎng)，存放的所有產(chǎn)品都能夠銷(xiāo)售出去。已知第k個(gè)月的單位成本為ck，銷(xiāo)售單價(jià)為pk，如表6-13所示。 1713812銷(xiāo)售單價(jià)（pk）1511910單位生產(chǎn)成本（ck）4321月份(k) 第一個(gè)月初該產(chǎn)品的庫(kù)存為500單位。由于產(chǎn)品生產(chǎn)周期較長(zhǎng)，當(dāng)月開(kāi)始生產(chǎn)的產(chǎn)品只能在下個(gè)月初入庫(kù)，因此工廠只能銷(xiāo)售倉(cāng)庫(kù)現(xiàn)

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

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

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

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

39、)321貨物編號(hào)解：設(shè)第i種物品的攜帶數(shù)量為xi。則問(wèn)題模型為： 按上述方法建立動(dòng)態(tài)規(guī)劃模型，由于決策變量為離散值，故可用列表法求解。 當(dāng)k=3時(shí)： 狀態(tài)變量s3的可能取值范圍為0到10的整數(shù)，允許決策集為滿足05x3s3的整數(shù)。 由基本方程 可計(jì)算得如下結(jié)果： 00000 x3*(s3)00000f3(s3)210101010101000000 x3(s3)109876543210s 3當(dāng)k=2時(shí)： 狀態(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時(shí)： 狀態(tài)變量s110，允許決策集為滿足03x110的整數(shù)，即x10，1，2，3。 由基本方程 可計(jì)算得如下結(jié)果： 2x1*(s1) 13f1(s1)1208546012c1f 23210 x1因此，f1(10)13，x1*2。再用逆向追蹤法求得最優(yōu)策略為： 即最優(yōu)策略是裝載第一種貨物2件，第二種貨物1件，不裝第三種貨物，可裝入的3種物品的最大價(jià)值為13。 第六節(jié) 其他動(dòng)態(tài)規(guī)劃問(wèn)題 設(shè)： 設(shè)備更新問(wèn)題的一

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