1、主要內(nèi)容: 5.1多階段決策過程的最優(yōu)化 5.2 動態(tài)規(guī)劃的基本概念和基本原理 5.3 動態(tài)規(guī)劃方法的基本步驟 5.4 動態(tài)規(guī)劃應(yīng)用舉例,5.1多階段決策過程的最優(yōu)化,動態(tài)規(guī)劃是解決多階段最優(yōu)決策的方法, 由美國數(shù)學(xué)家貝爾曼(R. Bellman) 于 1951年首先提出; 1957年貝爾曼發(fā)表動態(tài)規(guī)劃方面的第一部專著“動態(tài)規(guī)劃”, 標(biāo)志著運籌學(xué)的一 個新分支的創(chuàng)立。,例 5 .1 求解最短路問題,動態(tài)規(guī)劃將復(fù)雜的多階段決策問題分解為一系列簡單的、離散的單階段決策問題, 采用順序求解方法, 通過解一系列小問題達到求解整個問題目的; 動態(tài)規(guī)劃的各個決策階段不但要考慮本階段的決策目標(biāo), 還要兼顧整

2、個決策過程的整體目標(biāo), 從而實現(xiàn)整體最優(yōu)決策.,動態(tài)規(guī)劃的分類:,離散確定型 離散隨機型 連續(xù)確定型 連續(xù)隨機型,動態(tài)規(guī)劃的特點:,動態(tài)規(guī)劃沒有準(zhǔn)確的數(shù)學(xué)表達式和定義精確的算法, 它強調(diào)具體問題具體分析, 依賴分析者的經(jīng)驗和技巧。 與運籌學(xué)其他方法有很好的互補關(guān)系, 尤其在處理非線性、離散性問題時有其獨到的特點。,通常多階段決策過程的發(fā)展是通過狀態(tài)的一系列變換來實現(xiàn)的。一般情況下，系統(tǒng)在某個階段的狀態(tài)轉(zhuǎn)移除與本階段的狀態(tài)和決策有關(guān)外，還可能與系統(tǒng)過去經(jīng)歷的狀態(tài)和決策有關(guān)。因此，問題的求解就比較困難復(fù)雜。而適合于用動態(tài)規(guī)劃方法求解的只是一類特殊的多階段決策問題，即具有“無后效性”的多階段決策過程

3、。所謂無后效性，又稱馬爾柯夫性，是指系統(tǒng)從某個階段往后的發(fā)展，,僅由本階段所處的狀態(tài)及其往后的決策所決定，與系統(tǒng)以前經(jīng)歷的狀態(tài)和決策(歷史)無關(guān)。,具有無后效性的多階段決策過程的特點是系統(tǒng)過去的歷史，只能通過現(xiàn)階段的狀態(tài)去影響系統(tǒng)的未來，當(dāng)前的狀態(tài)就是后過程發(fā)展的初始條件。,動態(tài)規(guī)劃的應(yīng)用,動態(tài)規(guī)劃在工程技術(shù), 企業(yè)管理, 軍事部門有廣泛的應(yīng)用; 可解決資源分配, 生產(chǎn)調(diào)度, 庫存管理, 路徑優(yōu)化, 設(shè)備更新, 投資規(guī)劃, 排序問題和生產(chǎn)過程的最優(yōu)控制等問題;,拾火柴游戲: 桌子上放30根火柴, 每人一次可拾起13根, 誰拾起最后一根火柴誰輸, 如果你先選擇, 如何保證你能贏得游戲？ 2925

4、211713951,動態(tài)規(guī)劃與倒推求解:,使用動態(tài)規(guī)劃方法求解決策問題首先要將問題改造成符合動態(tài)規(guī)劃求解要求的形式,要涉及以下概念: (1)階段(2)狀態(tài) (3)決策與策略 (4)狀態(tài)轉(zhuǎn)移 (5)指標(biāo)函數(shù),5.2 動態(tài)規(guī)劃的基本概念和基本思想,一、基本概念,(1) 劃分階段 把一個復(fù)雜決策問題按時間或空間特征分解為若干(n)個相互聯(lián)系的階段(stage), 以便按順序求解; 階段變量描述當(dāng)前所處的階段位置，一般用下標(biāo) k 表示;,每階段有若干狀態(tài)(state), 表示某一階段決策面臨的條件或所處位置及運動特征的量,稱為狀態(tài)。反映狀態(tài)變化的量叫作狀態(tài)變量。 k 階段的狀態(tài)特征可用狀態(tài)變量 sk

5、或 xk描述; 狀態(tài)有起始、中間、最終狀態(tài)之分，每一階段的全部狀態(tài)構(gòu)成該階段的狀態(tài)集合Sk，并有skSk或xkSk。每個階段的狀態(tài)可分為初始狀態(tài)和終止?fàn)顟B(tài)，或稱輸入狀態(tài)和輸出狀態(tài)，階段的初始狀態(tài)記作sk ，終止?fàn)顟B(tài)記為sk+1,(2) 確定狀態(tài),(3) 決策、決策變量,所謂決策就是確定系統(tǒng)過程發(fā)展的方案，決策的實質(zhì)是關(guān)于狀態(tài)的選擇，是決策者從給定階段狀態(tài)出發(fā)對下一階段狀態(tài)作出的選擇。,用以描述決策變化的量稱之決策變量，和狀態(tài)變量一樣，決策變量可以用一個數(shù)，一組數(shù)或一向量來描述也可以是狀態(tài)變量的函數(shù)，記以 ，表示于 k 階段狀態(tài) sk 時的決策變量,決策變量的取值往往也有一定的容許范圍，稱之允許

6、決策集合決策變量 uk(sk)的允許決策集用 UK(SK)表示， uk(sk) UK(SK) , 允許決策集合實際是決策的約束條件。,(4)策略和允許策略集合,策略(Policy)也叫決策序列策略有全過程策略和 k 部子策略之分，全過程策略是指具有n 個階段的全部過程，由依次進行的 n 個階段決策構(gòu)成的決策序列，簡稱策略，表示為 。從 k 階段到第 n 階段，依次進行的階段決策構(gòu)成的決策序列稱為 k 部子策略,表示為 ，顯然當(dāng) k=1時的 k 部子策略就是全過程策略。,(5) 狀態(tài)轉(zhuǎn)移方程,狀態(tài)轉(zhuǎn)移確定從一個狀態(tài)到另一個狀態(tài)的轉(zhuǎn)移過程, 由狀態(tài)轉(zhuǎn)移方程描述: sk+1 = T (sk, uk)

7、; 狀態(tài)轉(zhuǎn)移方程在大多數(shù)情況下可以由數(shù)學(xué)公式表達, 如: sk+1 = sk + uk；,(6) 指標(biāo)函數(shù),用來衡量策略或子策略或決策的效果的某種數(shù)量指標(biāo)，就稱為指標(biāo)函數(shù)。它是定義在全過程或各子過程或各階段上的確定數(shù)量函數(shù)。對不同問題，指標(biāo)函數(shù)可以是諸如費用、成本、產(chǎn)值、利潤、產(chǎn)量、耗量、距離、時間、效用，等等。,用gk(sk , uk)表示第 k 段處于狀態(tài) sk且所作決策為 uk 時的指標(biāo)，則它就是第 k 段指標(biāo)函數(shù)，簡記為gk 。,用RK(sk , uk)表示第k子過程的指標(biāo)函數(shù)。表示處于第 k 段 sk 狀態(tài)且所作決策為uk時，從 sk 點到終點的距離。由此可見， RK(sk , uk

8、)不僅跟當(dāng)前狀態(tài) sk 有關(guān)，還跟,（2）過程指標(biāo)函數(shù)（也稱目標(biāo)函數(shù)）,（1）階段指標(biāo)函數(shù)（也稱階段效應(yīng)）,還跟該子過程策略 pk(sk) 有關(guān),嚴(yán)格說來，應(yīng)表示為 Rk(sk , pk(sk) 。它是由各階段的階段指標(biāo)函數(shù) gk(sk , uk)累積形成的，對于 k 部子過程的指標(biāo)函數(shù)可以表示為：,式中，表示某種運算，可以是加、減、乘、除、開方等,多階段決策問題中，常見的目標(biāo)函數(shù)形式之一是取各階段效應(yīng)之和的形式，即:,有些問題，如系統(tǒng)可靠性問題，其目標(biāo)函數(shù)是取各階段效應(yīng)的連乘積形式，,(7) 最優(yōu)解,用 fk(sk) 表示第 k 子過程指標(biāo)函數(shù)Rk(sk , pk(sk)在狀態(tài) sk 下的最

9、優(yōu)值，即:,稱 fk(sk) 為第 k 子過程上的最優(yōu)指標(biāo)函數(shù)；與它相應(yīng)的子策略 pk(sk) 稱為狀態(tài) sk 下的最優(yōu)子策略，記為 pk*(sk),例 5 .2 用動態(tài)規(guī)劃求解最短路問題,最短路的求解: 階段: 可分為5個階段, k = 1, ., 5。 狀態(tài): 可用城市編號, S1=1, S2=2, 3, 4, S3=5, 6, 7, S4=8, 9, S5=10 決策: 決策變量也可用城市編號; 狀態(tài)轉(zhuǎn)移方程: sk+1= uk; 損益遞推函數(shù):,k = 4 f4 (8) = 10, f4 (9) = 14 k = 3 f3(5)=min6+f4(8)=16*, 8+f4(9)=22=1

10、6 f3(6)=min5+f4(8)=15*, 9+f4(9)=23=15 f3(7)=min8+f4(8)=18, 3+f4(9)=17*=17 k = 2 f2(2) = min6+ f3(5), 8+ f3(6), 11+ f3(7) = min22*, 23, 28 = 22,f2(3) = min6+f3(5), 8+f3(6), 7+ f3(7) = min22*, 23, 24 = 22 f2(4) = min5+f3(5), 7+f3(6), 8+f3(7) = min21*, 22, 25 = 21 k = 1 f1(1) = min5+f2(2), 9+f2(3), 7+f

11、2(4) = min27*, 31, 28 = 27 最短路是：1 2 5 8 10,計算效率分析: 對有 7 個階段, 每個階段有 5 種狀態(tài)的最短路徑問題, 用窮舉法計算要進行 56 = 15625 次加法和 3124 次比較, 而動態(tài)規(guī)劃只需105次加法和 84 次比較, 計算效率分別提高近150和40倍.,動態(tài)規(guī)劃的無后效性原則,對任何階段 k, 有sk+1= T (sk, uk), sk+1僅取決于當(dāng)前狀態(tài)sk和當(dāng)前決策uk, 與 k 階段前的狀態(tài)和決策無關(guān), 也即, k 階段以后的發(fā)展不受該階段以前狀態(tài)的影響, 過去的歷史只能通過當(dāng)前狀態(tài)來影響今后的發(fā)展。,整個過程的最優(yōu)策略應(yīng)具有

12、這樣的性質(zhì): 無論過去的狀態(tài)和決策如何, 對前面的決策所形成的狀態(tài)而言, 后續(xù)的諸決策必須構(gòu)成最優(yōu)策略； 上一條成立的條件是損益遞推函數(shù)嚴(yán)格單調(diào)。,二、動態(tài)規(guī)劃的最優(yōu)性原理,在例5.1中，用標(biāo)號法求解最短路線的計算公式可以概括寫成：,其中，gk 在這里表示從狀態(tài) sk 到由決策 uk 所決定的狀態(tài) sk+1 之間的距離。f5(s5)=0 是邊界條件，表示全過程到第四階段終點結(jié)束。,一般地，對于 n 個階段的決策過程，假設(shè)只考慮指標(biāo)函數(shù)是“和”與“積”的形式，第 k 階段和第 k+1 階段間的遞推公式可表示如下：,當(dāng)過程指標(biāo)函數(shù)為下列“和”的形式時,相應(yīng)的函數(shù)基本方程為 :,當(dāng)過程指標(biāo)函數(shù)為下列

13、“積”的形式時,相應(yīng)的函數(shù)基本方程為 :,5.3 動態(tài)規(guī)劃方法的基本步驟,1. 將問題按時間或空間劃分為滿足遞推關(guān)系的若干階段, 對非時序問題可人為地引入“時段”概念; 2. 正確選擇狀態(tài)變量 sk, 滿足: 可知性: 正確描述動態(tài)過程演變, 可直接或間接確定狀態(tài)變量的值; 無后效性: 后面的決策與前面的決策無關(guān);,3.確定決策變量uk(或xk)以及允許決策集合Dk; 4. 寫出狀態(tài)轉(zhuǎn)移方程 sk+1 = T (sk , dk); 5. 決策變量的取值范圍 6.寫出損益函數(shù)的遞推關(guān)系, 應(yīng)滿足: a) 是定義在所有階段上的數(shù)量函數(shù)； b) 具有可分離性，并滿足遞推關(guān)系； c) 損益函數(shù)應(yīng)嚴(yán)格單

14、調(diào)。,例5.3 有某種機床，可以在高低兩種不同的負荷下進行生產(chǎn)，在高負荷下生產(chǎn)時，產(chǎn)品的年產(chǎn)量為 g ，與年初投入生產(chǎn)的機床數(shù)量 u1 的關(guān)系為 g=g(u1)=8u1 ，這時，年終機床完好臺數(shù)將為，au1 ( a為機床完好率， 0 a 1 ，設(shè) a=0.7 )。在低負荷下生產(chǎn)時，產(chǎn)品的年產(chǎn)量為 h ，和投入生產(chǎn)的機床數(shù)量的關(guān)系為 h=h(u2)=5u2 ，相應(yīng)的機床完好率為 b ( 0b2 ，設(shè) b= 0.9 )，一般情況下 ( a b )。,假設(shè)某廠開始有 x1=1000 臺完好的機床，現(xiàn)要制定一個五年生產(chǎn)計劃，問每年開始時如何重新分配完好的機床在兩種不同的負荷下生產(chǎn)的數(shù)量，以使在5年內(nèi)產(chǎn)

15、品的總產(chǎn)量為最高。,解：首先構(gòu)造這個問題的動態(tài)規(guī)劃模型。,1分階段：設(shè)階段變量 k 表示年度，因此，階段總數(shù) n = 5 。,2. 狀態(tài)變量：用 sk 表示第 k 年度初擁有的完好機床臺數(shù)，同時也是第 k-1 年度末時的完好機床數(shù)量。,3. 決策變量：用 uk 表示第 k 年度中分配于高負荷下生產(chǎn)的機床臺數(shù)。于是 sk-uk 便為該年度中分配于低負荷下生產(chǎn)的機床臺數(shù)。,4狀態(tài)轉(zhuǎn)移方程為：,決策變量的取值：在第 k 段為,6條件最優(yōu)目標(biāo)函數(shù)遞推方程,令 fk(sk ) 表示由第 k 年的狀態(tài) sk 出發(fā)，采取最優(yōu)分配方案到第5年度結(jié)束這段時間的產(chǎn)品產(chǎn)量，根據(jù)最優(yōu)化原理有以下遞推關(guān)系:,下面采用逆

16、序遞推計算法,從第5年度開始遞推計算,K=5 時有,顯然，當(dāng) u5*=s5 時，f5(s5) 有最大值，相應(yīng)的有 f5(s5) = 8s5 。,K=4 時有：,因此，當(dāng) u4*= s4 時，有最大值 f4(s4)=13.6s4,K=3 時有：,可見，當(dāng) u3*= s3 時，有最大值 f3(s3) =17.55s3 。,K=2 時有：,此時，當(dāng) u2*= 0 時有最大值，即 f2(s2)=20.8s2,其中 s2=0.7u1+0.9(s1-u1),K=1 時有：,當(dāng) u1*= 0 時, 有最大值，即 f1(s1)=23.7s1 , 因為 s1=1000 , 故 f1(s1)=23700 個產(chǎn)品。

17、,按照上述計算順序?qū)ほ櫟玫较率鲇嬎憬Y(jié)果：,上面所討論的最優(yōu)決策過程是所謂始端狀態(tài)固定，終端狀態(tài)自由如果終端也附加上一定的約束條件，那么計算結(jié)果將會與之有所差別例如，若規(guī)定在第五個年度結(jié)束時，完好的機床數(shù)量為500臺(上面只有278臺)，問應(yīng)該如何安排五年的生產(chǎn)，使之在滿足這一終端要求的情況下產(chǎn)量最高？,解：由狀態(tài)轉(zhuǎn)移方程,有,由此式得,當(dāng) k=5 時有,當(dāng) k=4 時有,顯然，只有取 u4*=0 , 有最大值 f4(s4)=21.4s4-7500,當(dāng) k=3 時有:,顯然，只有取 u3*=0 , f3(s3) 有最大值 f3(s3)=24.5s3-7500 。,當(dāng) k=2 時有:,顯然，只有取

18、 u2*=0 , f2(s2) 有最大值 f2(s2)=27.1s2-7500 。,當(dāng) k=1 時有:,顯然，只有取 u1*=0 , f1(s1) 有最大值 f1(s1)=29.4s1-7500 。,例5.4 某公司擁有資金 10 萬元，若投資于項目 i (i1，2，3) 的投資額為 xi 時，其收益分別為 g1(x1)=4x1 , g2(x2)=9x2 , g3(x3)=2x32 ,問應(yīng)如何分配投資數(shù)額才能使總收益最大?,這是一個與時間無明顯關(guān)系的靜態(tài)最優(yōu)化問題，可列出其靜態(tài)模型為：,求 x1 , x2 , x3 的值使,滿足,我們可以人為地賦予它“時段”的概念，用動態(tài)規(guī)劃方法求解,解：（解

19、法1）首先用逆序構(gòu)造動態(tài)規(guī)劃模型。,1分階段：設(shè)階段變量 k 表示依次對第 k 個項目投資，因此，階段總數(shù) n = 3。 ( k = 1 , 2 , 3 ),2. 狀態(tài)變量：用 sk 表示已經(jīng)對第 1 至 第 k-1 個項目投資后的剩余資金；即第 k 段初擁有的可以分配給第 k 到第3個項目的資金額 （單位：萬元） 。,3. 決策變量：用 xk 表示對第 k 個項目投資 的資金數(shù)量（單位：萬元）。,決策變量的取值： 0 xk sk,4狀態(tài)轉(zhuǎn)移方程為：,6. 基本方程為：,最優(yōu)指標(biāo)函數(shù) fk(sk) 表示第 k 階段，初始狀態(tài)為 sk 時，從第 k 到第 3 個項目所獲最大收益,當(dāng) k=3 時：

20、,當(dāng) k=2 時：,極大值只可能在 0 ，s2 端點取得，,當(dāng) k=1 時：,矛盾，所以舍去 sk 9/2,故 極大值只能在 0，10 的端點取得，比較0，10兩個端點的函數(shù)值,即全部資金投于第3個項目,(解法2) 用順序解法,1. 階段劃分: （同上） 和決策變量,2. 狀態(tài)變量: 用 sk 表示可用于第1到第 k-1個項目投資的金額，即對第 k 個項目到第3個項目投資后的剩余資金數(shù)量。,3. 決策變量: （同上）,4. 狀態(tài)轉(zhuǎn)移方程:,5. 決策變量的取值范圍：,6. 最優(yōu)指標(biāo)函數(shù)：,令 fk(sk+1) 表示第 k 段投資額 sk+1 為時，第1到第 k 項目所獲的最大收益，此時順序解法

21、的基本方程為：,當(dāng) k=1 時，有,當(dāng) k=2 時，有,當(dāng) k3 時，有, x3 = 9/4 為極小點。,極大值應(yīng)在0，s4 0，10 端點取得,再由狀態(tài)轉(zhuǎn)移方程逆推：,動態(tài)規(guī)劃的優(yōu)點,可以解決線性, 非線性, 整數(shù)規(guī)劃無法有效求解的復(fù)雜問題; 容易找到全局最優(yōu)解; 可以得到一組解;,動態(tài)規(guī)劃的缺點,沒有標(biāo)準(zhǔn)的模型可供應(yīng)用, 構(gòu)模依賴于個人的經(jīng)驗和技巧; 狀態(tài)變量需滿足無后效性, 有較大的局限性; 動態(tài)規(guī)劃的維數(shù)災(zāi)難限制了對規(guī)模較大問題的求解效率;,6.3 動態(tài)規(guī)劃應(yīng)用舉例,1. 資源配置問題 2. 生產(chǎn)與庫存問題 3. 復(fù)合系統(tǒng)工作可靠性問題 4. 二維背包問題 5. 設(shè)備更新問題 6. 貨

22、郎擔(dān)問題,1. 資源配置問題,如何將有限的資源分配給若干種生產(chǎn)活動，并使資源利用的收益最大是經(jīng)濟活動中常見的問題，動態(tài)規(guī)劃可以求解一些線性規(guī)劃無法解決的資源配置問題。,一般的資源分配問題可以描述為如下的規(guī)劃問題： max: z = g1(x1) + g2(x2) + . . . + gn(xn) x1 + x2 + . . . + xn = a xi 0 i = 1, . . ., n,例: 某工廠有4臺設(shè)備要投到三種生產(chǎn)線上，投到不同生產(chǎn)線的預(yù)期收入的函數(shù)關(guān)系如下： g1(x1) = 7x1+2 (x10); g1(x1) = 0 (x1= 0) g2(x2) = 3x2+7 (x20);

23、g2(x2) = 0 (x2= 0) g3(x3) = 4x3+5 (x30); g3(x3) = 0 (x3= 0) 設(shè)備如何分配可使工廠的收益最大？,分析： 1.階段與生產(chǎn)線相聯(lián)系, 階段 k 只考慮分配到生產(chǎn)線 k 的設(shè)備臺數(shù); 2.狀態(tài)變量 sk 表示 k 生產(chǎn)線可分配的設(shè)備數(shù); 3.決策變量 xk 表示決定在 k 生產(chǎn)線上使用的設(shè)備數(shù); 4.狀態(tài)轉(zhuǎn)移方程: sk+1 = sk - xk; 5.損益函數(shù): fk(sk)=max gk(xk)+fk+1(sk+1),s3 f3(s3) x3* 0 f3(0) = maxx3=0 0 = 0 0 1 f3(1) = maxx31 4x3+5

24、 = 9 1 2 f3(2) = maxx32 4x3+5 = 13 2 3 f3(3) = maxx33 4x3+5 = 17 3 4 f3(4) = maxx34 4x3+5 = 21 4,求解： k = 3: g3(x3) = 4x3 + 5,k = 2: g2(x2) = 3x2 + 7 s3 = s2 - x2,k = 1:g1(x1) = 7x1 + 2 s2 = s1 - x1,因此得到：x1 = 2 , x2 = 1 , x3 = 1,離散的時間段內(nèi)如何安排生產(chǎn)與庫存。 生產(chǎn)成本為: C(xt) = k + cxt (xt 0) 或 C(xt) = 0 (xt = 0), k為

25、開工所需費用, c 是變動成本, xt為 t 期的生產(chǎn)數(shù)量; 庫存成本為：H(yt) = hyt, h為單位庫存成本，yt為 t 期期初庫存數(shù)量。,2. 生產(chǎn)與庫存問題,例: 假定k = 250, c = 2, h = 1, y1 = 0, T = 5, 需求數(shù)據(jù)如下表, 如何安排生產(chǎn)才能使總成本最小?,t 1 2 3 4 5 需求(dt)220280360140270,分析: 階段可按周期 t 劃分, t = 1, 2, 3, 4, 5 每周期期初的庫存量為該階段的狀態(tài), 狀態(tài)變量 st 表示 t 周期期初庫存； 決策變量 xt 表示 t 期的生產(chǎn)數(shù)量; 狀態(tài)轉(zhuǎn)移方程為: st+1 = st

26、 + xt - dt,遞推函數(shù): ft(st) = min Ct(xt) + Ht(st) + ft+1(st+1) 以庫存表示系統(tǒng)狀態(tài)會大大增加系統(tǒng)狀態(tài)數(shù)量, 然而, 上述問題的最優(yōu)決策必須使每一階段庫存或者為零, 或者為后續(xù)一或幾個周期需求之和。,t= 5: f5(0) = k+cx5+hs5 = 250+2270+10 = 790 (x5= 270) f5(270) = k+cx5+hs5 = 0+20+1270 = 270 (x5= 0) t = 4: f4( 0 ) = min 250+2140+ f5(0), 250+2410+ f5(270)= min 1320*, 1340 =

27、 1320 (x4= 140) f4(140) = 1140+ f5(0) = 140 + 790 = 930 (x4= 0) f4(410) = 1410+ f5(270) = 410 + 270 = 680 (x4= 0),t = 3: f3(0) = min250+2360+f5(0), 250+2500 + f4(140), 250+2770+ f4(410) = min 2290, 2180*, 2470 = 2180 (x3= 500) f3(360)=1360+f4(0)=360+1320=1680 (x3=0) f3(500)=1500+f4(140)=500+930=1430

28、 (x3= 0) f3(770)=1770+f4(410) = 770+680 = 1450 (x3= 0),t = 2: f2(0)=min250+2220+f3(0),250+2580+f3(360), 250+2720+f3(500), 250+2990+ f3(770) = min2870*,3090,3120,3680=2870(x2=220) f2(220)=1220+f3(0) = 220+2180 = 2400 (x2= 0) f2(580)=1580+f3(360)=580+1680=2260 (x2= 0) f3(720)=1720+f3(500)=720+1430=215

29、0 (x2= 0),t = 1: f1(0)=min250+2280+f2(0),250+2500+f2(220),250+2860+ f2(580), 250+21000+ f2(720) =min3800,3650*,4290,4400=3650 (x1= 500) 最優(yōu)解為： x1= 500, x2= 0, x3= 500, x4= 0, x5= 270 簡單判斷方法：只要固定費用大于后面發(fā)生的庫存費用，就值得一次生產(chǎn)滿足一或幾個周期的需求。,3. 復(fù)合系統(tǒng)的工作可靠性問題 例: 為保證設(shè)備可靠運行, 一些關(guān)鍵部件往往由多個器件并聯(lián)運行, 如果器件 i 的失效概率為 pi, 則 xi 個

30、器件并聯(lián)工作的可靠性為(1 - pixi), 假定每個器件的采購費用為 ci, 在滿足總采購費用不超過預(yù)算限制 C 的前提下, 使設(shè)備可靠性最高的規(guī)劃問題可以描述為:,該問題為整數(shù)非線性規(guī)劃，可以用動態(tài)規(guī)劃求解，設(shè)關(guān)鍵器件數(shù)n = 3，總費用為120萬元。器件的單價與可靠性如下表：,分析： 階段與器件掛鉤，第 i 階段僅考慮器件 i 的采購數(shù)量; si 表示 i 階段可使用的采購費用; xi 表示 i 階段決定購買 i 器件的數(shù)量； 狀態(tài)轉(zhuǎn)移方程: si+1 = si - ci xi； 遞推損益函數(shù): fi(si) = max ( 1 - pixi ) fi+1(si+1)。,i = 1 f1

31、(120) = max1x130.9f2(90), 0.99f2(60), 0.999f2(30) = max0.90.84*, 0.990.4, 0.9990 = 0.756 i = 2 f2(90) = max0.8f3(75) , 0.96f3(60) , 0.992f3(45) , 0.9984f3(30) = max0.80.875 , 0.960.875* , 0.9920.75 , 0.99840.5 = 0.84,f2(60) = max 0.8f3(45), 0.96f3(30) = max 0.80.75*, 0.960.5 = 0.6 f2(30) = max 0.8f3

32、(15), 0f3(30) = 0 f3(75) = 0.875, f3(60) = 0.875, f3(45) = 0.75, f3(30) = 0.5, 因此, 最優(yōu)解為: x1 = 1, x2 = 2, x3 = 3,4 二維背包問題,當(dāng)背包問題中有兩個限制條件時(如重量和體積限制), 所形成的問題為 二維背包問題, 問題的一般形式為: max z = i ci xi s.t.i ai xi b xi 0 且為整數(shù),例: 卡車的最大運貨重量為 12 噸, 容積為 10 立方米, 現(xiàn)有A , B 兩種貨物, 重量分別為 3 噸和 4 噸, 體積分別為 1 和 5 立方米, 運費分別為 2

33、和 3 元, 如何裝載使所得運費最大。 由資源條件可知最多可裝載 4 件 A 或 2 件 B。,分析: 階段可按貨物種類劃分, k = 1, 2 每階段剩余的載貨能力(重量與容積)為該階段的狀態(tài), 狀態(tài)變量 sk = (s1k, s2k); 決策變量 xk 表示 k 階段資源的占用量; 狀態(tài)轉(zhuǎn)移方程: sk+1= sk-akxk , ak=(a1k, a2k) 損益函數(shù)為: fk(sk)=maxckxk+fk+1(sk+1),k = 2 f2(12, 10) = maxx2=0,1,2f1(12,10), 3+ f1(8, 5), 6+f2(4, 0) = max 8, 3+4, 6+0 =

34、8 k = 1 f1(12,10) = maxx14 2x1 = 8 f1( 8, 5) = maxx12 2x1 = 4 f1( 4, 0) = 0,動態(tài)規(guī)劃的維數(shù)增加時, 求解的復(fù)雜程度也會增加。如果狀態(tài)變量的維數(shù)為 m, 離散的決策變量有 n 個取值, 則在每個階段需要存儲 nm 個數(shù)據(jù), 這就是所謂的維數(shù)災(zāi)難。,5 設(shè)備更新問題,設(shè)備在使用全過程中會遭受磨損, 使用一段時間后就要維修, 而且使用的時間越長, 維修費用越高, 設(shè)備使用多少時間在經(jīng)濟上最合算, 就是設(shè)備更新問題。,分析： 階段 k = 1, 2, 3, 4, 5; sk 表示 k 年初設(shè)備已使用的年限; xk 為 k 年初決定設(shè)備是繼續(xù)使用還是更新的決策變量: xk = 1表示繼續(xù)使用, xk = 0表示更新; 狀態(tài)轉(zhuǎn)移方程: sk+1 = skxk + 1;,k = 5 狀態(tài)變量 s5 可取 1, 2, 3, 4 f5(1) = maxx1=0,1r(0) - u(0) - c(1), r(1) - u(1) = max 5-0.5-1.5, 4.5-1= 3.5 (x5*=1) f5(2)=max5-0.5-2.2, 4-1.5= 2.5 (x5*=1) f5(3)=max5-0.5-2.5, 3