運籌學(xué)5動態(tài)

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ī)劃”, 標志著運籌學(xué)的一 個新分支的創(chuàng)立。,例

2、 5 .1 求解最短路問題,動態(tài)規(guī)劃將復(fù)雜的多階段決策問題分解為一系列簡單的、離散的單階段決策問題, 采用順序求解方法, 通過解一系列小問題達到求解整個問題目的;動態(tài)規(guī)劃的各個決策階段不但要考慮本階段的決策目標, 還要兼顧整個決策過程的整體目標, 從而實現(xiàn)整體最優(yōu)決策.,動態(tài)規(guī)劃的分類:,離散確定型離散隨機型連續(xù)確定型連續(xù)隨機型,動態(tài)規(guī)劃的特點:,動態(tài)規(guī)劃沒有準確的數(shù)學(xué)表達式和定義精確的算法, 它強調(diào)具體問題具體分析, 依

3、賴分析者的經(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ī)劃方法求解的只是一類特殊的多階段決策問題，即具有“無后效性”的多階段決策過程。所謂無后效性，又稱馬爾柯夫性，是指系統(tǒng)從某個階

4、段往后的發(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)控制等問題;,拾火柴游戲: 桌子上

5、放30根火柴, 每人一次可拾起1－3根, 誰拾起最后一根火柴誰輸, 如果你先選擇, 如何保證你能贏得游戲？29－25－21－17－13－9－5－1,動態(tài)規(guī)劃與倒推求解:,使用動態(tài)規(guī)劃方法求解決策問題首先要將問題改造成符合動態(tài)規(guī)劃求解要求的形式,要涉及以下概念:(1)階段(2)狀態(tài)(3)決策與策略 (4)狀態(tài)轉(zhuǎn)移(5)指標函數(shù),§5.2 動態(tài)規(guī)劃的基本概念和基本思想,一、基本概念,(1) 劃分階段

6、 把一個復(fù)雜決策問題按時間或空間特征分解為若干(n)個相互聯(lián)系的階段(stage), 以便按順序求解; 階段變量描述當(dāng)前所處的階段位置，一般用下標 k 表示;,每階段有若干狀態(tài)(state), 表示某一階段決策面臨的條件或所處位置及運動特征的量,稱為狀態(tài)。反映狀態(tài)變化的量叫作狀態(tài)變量。 k 階段的狀態(tài)特征可用狀態(tài)變量 sk 或 xk描述;狀態(tài)有起始、中間、最終狀態(tài)之分，每一階段的全部狀態(tài)構(gòu)成該階段的狀態(tài)集合Sk，并有sk?Sk

7、或xk?Sk。每個階段的狀態(tài)可分為初始狀態(tài)和終止狀態(tài)，或稱輸入狀態(tài)和輸出狀態(tài)，階段的初始狀態(tài)記作sk ，終止狀態(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ù)，記以

8、 ，表示于 k 階段狀態(tài) sk 時的決策變量．,決策變量的取值往往也有一定的容許范圍，稱之允許決策集合．決策變量 uk(sk)的允許決策集用 UK(SK)表示， uk(sk) ?UK(SK) , 允許決策集合實際是決策的約束條件。,(4)策略和允許策略集合,,策略(Policy)也叫決策序列．策略有全過程策略和 k 部子策略之分，全過程策略是指具有n 個階段的全部過程，由依次進行的 n 個階段決策構(gòu)成的決策序列，簡稱策略，表示為

9、 。從 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); 狀態(tài)轉(zhuǎn)移方程在大多數(shù)情況下可以由數(shù)學(xué)公式表達, 如:

10、sk+1 = sk + uk；,(6) 指標函數(shù),用來衡量策略或子策略或決策的效果的某種數(shù)量指標，就稱為指標函數(shù)。它是定義在全過程或各子過程或各階段上的確定數(shù)量函數(shù)。對不同問題，指標函數(shù)可以是諸如費用、成本、產(chǎn)值、利潤、產(chǎn)量、耗量、距離、時間、效用，等等。,用gk(sk , uk)表示第 k 段處于狀態(tài) sk且所作決策為 uk 時的指標，則它就是第 k 段指標函數(shù)，簡記為gk 。,用RK(sk , uk)表示第k子過程的指標函數(shù)。表示處

11、于第 k 段 sk 狀態(tài)且所作決策為uk時，從 sk 點到終點的距離。由此可見， RK(sk , uk)不僅跟當(dāng)前狀態(tài) sk 有關(guān)，還跟,（2）過程指標函數(shù)（也稱目標函數(shù)）,（1）階段指標函數(shù)（也稱階段效應(yīng)）,還跟該子過程策略 pk(sk) 有關(guān),嚴格說來，應(yīng)表示為 Rk(sk , pk(sk)) 。它是由各階段的階段指標函數(shù) gk(sk , uk)累積形成的，對于 k 部子過程的指標函數(shù)可以表示為：,式中?，表示某種運算，可以是加、

12、減、、乘、除、開方等．,多階段決策問題中，常見的目標函數(shù)形式之一是取各階段效應(yīng)之和的形式，即:,有些問題，如系統(tǒng)可靠性問題，其目標函數(shù)是取各階段效應(yīng)的連乘積形式，,(7) 最優(yōu)解,用 fk(sk) 表示第 k 子過程指標函數(shù)Rk(sk , pk(sk))在狀態(tài) sk 下的最優(yōu)值，即:,稱 fk(sk) 為第 k 子過程上的最優(yōu)指標函數(shù)；與它相應(yīng)的子策略 pk(sk) 稱為狀態(tài) sk 下的最優(yōu)子策略，記為 pk*(sk),例 5 .2

13、用動態(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 = 4f4 (8) = 10, f4 (9) = 14 k = 3f3(

14、5)=min{6+f4(8)=16*, 8+f4(9)=22}=16 f3(6)=min{5+f4(8)=15*, 9+f4(9)=23}=15 f3(7)=min{8+f4(8)=18, 3+f4(9)=17*}=17 k = 2 f2(2) = min{6+ f3(5), 8+ f3(6), 11+ f3(7) } = min{22*, 23, 28} = 22,f2(3) = min{6+f3(5), 8

15、+f3(6), 7+ f3(7)} = min{22*, 23, 24 } = 22 f2(4) = min{5+f3(5), 7+f3(6), 8+f3(7)} = min{21*, 22, 25 } = 21 k = 1 f1(1) = min{5+f2(2), 9+f2(3), 7+f2(4)} = min{27*, 31, 28 } = 27 最短路是：1 ? 2 ? 5 ? 8 ? 10,計算效率分析:

16、對有 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)的影響, 過去的

17、歷史只能通過當(dāng)前狀態(tài)來影響今后的發(fā)展。,整個過程的最優(yōu)策略應(yīng)具有這樣的性質(zhì): 無論過去的狀態(tài)和決策如何, 對前面的決策所形成的狀態(tài)而言, 后續(xù)的諸決策必須構(gòu)成最優(yōu)策略；上一條成立的條件是損益遞推函數(shù)嚴格單調(diào)。,二、動態(tài)規(guī)劃的最優(yōu)性原理,在例5.1中，用標號法求解最短路線的計算公式可以概括寫成：,其中，gk 在這里表示從狀態(tài) sk 到由決策 uk 所決定的狀態(tài) sk+1 之間的距離。f5(s5)=0 是邊界條件，表示全過程到第四階段終

18、點結(jié)束。,一般地，對于 n 個階段的決策過程，假設(shè)只考慮指標函數(shù)是“和”與“積”的形式，第 k 階段和第 k+1 階段間的遞推公式可表示如下：,當(dāng)過程指標函數(shù)為下列“和”的形式時,相應(yīng)的函數(shù)基本方程為 :,當(dāng)過程指標函數(shù)為下列“積”的形式時,相應(yīng)的函數(shù)基本方程為 :,§5.3 動態(tài)規(guī)劃方法的基本步驟,1. 將問題按時間或空間劃分為滿足遞推關(guān)系的若干階段, 對非時序問題可人為地引入“時段”概念;2. 正確選擇狀態(tài)變量 sk,

19、滿足:可知性: 正確描述動態(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)嚴格單調(diào)。,例5.3

20、有某種機床，可以在高低兩種不同的負荷下進行生產(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 ( 0<b<2 ，設(shè) b= 0.9 )，

21、一般情況下 ( a < b )。,假設(shè)某廠開始有 x1=1000 臺完好的機床，現(xiàn)要制定一個五年生產(chǎn)計劃，問每年開始時如何重新分配完好的機床在兩種不同的負荷下生產(chǎn)的數(shù)量，以使在5年內(nèi)產(chǎn)品的總產(chǎn)量為最高。,解：首先構(gòu)造這個問題的動態(tài)規(guī)劃模型。,1．分階段：設(shè)階段變量 k 表示年度，因此，階段總數(shù) n = 5 。,2. 狀態(tài)變量：用 sk 表示第 k 年度初擁有的完好機床臺數(shù)，同時也是第 k-1 年度末時的完好機床數(shù)量。,3. 決

22、策變量：用 uk 表示第 k 年度中分配于高負荷下生產(chǎn)的機床臺數(shù)。于是 sk-uk 便為該年度中分配于低負荷下生產(chǎn)的機床臺數(shù)。,4．狀態(tài)轉(zhuǎn)移方程為：,５．決策變量的取值：在第 k 段為,6．條件最優(yōu)目標函數(shù)遞推方程,令 fk(sk ) 表示由第 k 年的狀態(tài) sk 出發(fā)，采取最優(yōu)分配方案到第5年度結(jié)束這段時間的產(chǎn)品產(chǎn)量，根據(jù)最優(yōu)化原理有以下遞推關(guān)系:,下面采用逆序遞推計算法,從第5年度開始遞推計算．,K=5 時有,顯然，當(dāng) u5*=s

23、5 時，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

24、(s1)=23.7s1 , 因為 s1=1000 , 故 f1(s1)=23700 個產(chǎn)品。,按照上述計算順序?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

25、=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 時有:,顯然，只有取 u2*=0 , f2(s2) 有最大值 f2(s2)=27.1s2-7500 。,當(dāng) k=1 時有:,,顯然，只有取 u1*=0 , f1(s1) 有最大值 f1(s1)

26、=29.4s1-7500 。,例5.4 某公司擁有資金 10 萬元，若投資于項目 i (i＝1，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ī)劃方法求解,解

27、：（解法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ù)量（單位：萬元）。,５．決策變量的取值：

28、 0 ? xk ? sk,4．狀態(tài)轉(zhuǎn)移方程為：,6. 基本方程為：,最優(yōu)指標函數(shù) fk(sk) 表示第 k 階段，初始狀態(tài)為 sk 時，從第 k 到第 3 個項目所獲最大收益,當(dāng) k=3 時：,當(dāng) k=2 時：,極大值只可能在 [0 ，s2] 端點取得，,當(dāng) k=1 時：,矛盾，所以舍去 sk < 9/2,故 極大值只能在 [0，10] 的端點取得，比較[0，10]兩個端點的函數(shù)值,即全部資金投于第3個項

29、目,(解法2) 用順序解法,1. 階段劃分: （同上） 和決策變量,2. 狀態(tài)變量: 用 sk 表示可用于第1到第 k-1個項目投資的金額，即對第 k 個項目到第3個項目投資后的剩余資金數(shù)量。,3. 決策變量: （同上）,4. 狀態(tài)轉(zhuǎn)移方程:,5. 決策變量的取值范圍：,6. 最優(yōu)指標函數(shù)：,令 fk(sk+1) 表示第 k 段投資額 sk+1 為時，第1到第 k 項目所獲的最大收益，此時順序解法的基本方程為：

30、,當(dāng) k=1 時，有,當(dāng) k=2 時，有,當(dāng) k＝3 時，有,? 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ī)劃的缺點,沒有標準的模型可供應(yīng)用, 構(gòu)模依賴于個人的經(jīng)驗和技巧;狀態(tài)變量需滿足無后效性, 有較大的局限性;動態(tài)規(guī)劃的維數(shù)災(zāi)難限制了

31、對規(guī)模較大問題的求解效率;,§6.3 動態(tài)規(guī)劃應(yīng)用舉例,1. 資源配置問題2. 生產(chǎn)與庫存問題3. 復(fù)合系統(tǒng)工作可靠性問題4. 二維背包問題5. 設(shè)備更新問題6. 貨郎擔(dān)問題,1. 資源配置問題,如何將有限的資源分配給若干種生產(chǎn)活動，并使資源利用的收益最大是經(jīng)濟活動中常見的問題，動態(tài)規(guī)劃可以求解一些線性規(guī)劃無法解決的資源配置問題。,一般的資源分配問題可以描述為如下的規(guī)劃問題：max: z = g1(x1) +

32、 g2(x2) + . . . + gn(xn)x1 + x2 + . . . + xn = axi ? 0 i = 1, . . ., n,例: 某工廠有4臺設(shè)備要投到三種生產(chǎn)線上，投到不同生產(chǎn)線的預(yù)期收入的函數(shù)關(guān)系如下： g1(x1) = 7x1+2 (x1>0); g1(x1) = 0 (x1= 0) g2(x2) = 3x2+7 (x2>0); g2(x2) = 0 (x2= 0) g

33、3(x3) = 4x3+5 (x3>0); 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

34、+1(sk+1)},s3 f3(s3) x3*0 f3(0) = maxx3=0{ 0 } = 0 01 f3(1) = maxx3?1{ 4x3+5} = 9 12 f3(2) = maxx3?2{ 4x3+5} = 13 23 f3(3) = maxx3?3{ 4x3+5} = 17

35、 34 f3(4) = maxx3?4{ 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)與庫存。

36、生產(chǎn)成本為: C(xt) = k + cxt (xt > 0) 或 C(xt) = 0 (xt = 0), k為開工所需費用, 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

37、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 + xt - dt,遞推函數(shù):ft(st) = min {Ct(xt) + Ht(st) + ft+1(st+1)}

38、以庫存表示系統(tǒng)狀態(tài)會大大增加系統(tǒng)狀態(tài)數(shù)量, 然而, 上述問題的最優(yōu)決策必須使每一階段庫存或者為零, 或者為后續(xù)一或幾個周期需求之和。,t= 5:f5(0) = k+cx5+hs5 = 250+2?270+1?0 = 790 (x5= 270) f5(270) = k+cx5+hs5 = 0+2?0+1?270 = 270 (x5= 0) t = 4: f4( 0 ) = min {250+2?140+ f5(0)

39、, 250+2?410+ f5(270)}= min {1320*, 1340} = 1320 (x4= 140)f4(140) = 1?140+ f5(0) = 140 + 790 = 930 (x4= 0) f4(410) = 1?410+ f5(270) = 410 + 270 = 680 (x4= 0),t = 3:f3(0) = min{250+2?360+f5(0), 25

40、0+2?500 + f4(140), 250+2?770+ f4(410)} = min {2290, 2180*, 2470} = 2180 (x3= 500)f3(360)=1?360+f4(0)=360+1320=1680 (x3=0)f3(500)=1?500+f4(140)=500+930=1430 (x3= 0)f3(770)=1?770+f4(410) = 770+680 =

41、1450 (x3= 0),t = 2:f2(0)=min{250+2?220+f3(0),250+2?580+f3(360), 250+2?720+f3(500), 250+2?990+ f3(770)} = min{2870*,3090,3120,3680}=2870(x2=220)f2(220)=1?220+f3(0) = 220+2180 = 2400 (x2= 0)f2(580)=1?580+f3(360)

42、=580+1680=2260 (x2= 0)f3(720)=1?720+f3(500)=720+1430=2150 (x2= 0),t = 1:f1(0)=min{250+2?280+f2(0),250+2?500+f2(220),250+2?860+ f2(580), 250+2?1000+ f2(720)} =min{3800,3650*,4290,4400}=3650 (x1= 500)最優(yōu)解為： x1= 50

43、0, x2= 0, x3= 500, x4= 0, x5= 270簡單判斷方法：只要固定費用大于后面發(fā)生的庫存費用，就值得一次生產(chǎn)滿足一或幾個周期的需求。,3. 復(fù)合系統(tǒng)的工作可靠性問題例: 為保證設(shè)備可靠運行, 一些關(guān)鍵部件往往由多個器件并聯(lián)運行, 如果器件 i 的失效概率為 pi, 則 xi 個器件并聯(lián)工作的可靠性為(1 - pixi), 假定每個器件的采購費用為 ci, 在滿足總采購費用不超過預(yù)算限制 C 的前提下, 使設(shè)備可

44、靠性最高的規(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

45、(si+1)}。,i = 1f1(120) = max1?x1?3{0.9f2(90), 0.99f2(60), 0.999f2(30)} = max{0.9?0.84*, 0.99?0.4, 0.999?0 } = 0.756i = 2f2(90) = max{0.8f3(75) , 0.96f3(60) , 0.992f3(45) , 0.9984f3(30)} = max{0.8?0.875 , 0.96?

46、0.875* , 0.992?0.75 , 0.9984?0.5} = 0.84,f2(60) = max {0.8f3(45), 0.96f3(30)} = max {0.8?0.75*, 0.96?0.5} = 0.6f2(30) = max {0.8f3(15), 0?f3(30)} = 0 f3(75) = 0.875, f3(60) = 0.875, f3(45) = 0.75, f3(30) =

47、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

48、噸和 4 噸, 體積分別為 1 和 5 立方米, 運費分別為 2 和 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)損益

49、函數(shù)為: fk(sk)=max{ckxk+fk+1(sk+1)},k = 2f2(12, 10) = maxx2=0,1,2{f1(12,10), 3+ f1(8, 5), 6+f2(4, 0)} = max { 8, 3+4, 6+0} = 8k = 1f1(12,10) = maxx1?4 {2x1 } = 8f1( 8, 5) = maxx1?2 {2x1 } = 4f1( 4, 0) = 0,動態(tài)規(guī)劃的維數(shù)

50、增加時, 求解的復(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è)

51、備是繼續(xù)使用還是更新的決策變量: xk = 1表示繼續(xù)使用, xk = 0表示更新;狀態(tài)轉(zhuǎn)移方程: sk+1 = skxk + 1;,k = 5 狀態(tài)變量 s5 可取 1, 2, 3, 4f5(1) = maxx1=0,1{r(0) - u(0) - c(1), r(1) - u(1)}= max {5-0.5-1.5, 4.5-1}= 3.5 (x5*=1)f5(

52、2)=max{5-0.5-2.2, 4-1.5}= 2.5 (x5*=1)f5(3)=max{5-0.5-2.5, 3.75-2}= 2 (x5*=0)f5(4)=max{5-0.5-3, 3-2.5} = 1.5 (x5*=0),k = 4狀態(tài)變量 s4 可取 1, 2, 3 f4(1) = max{r(0)-u(0)-c(1)+f5(1), r(1)-u(1)+ f5(2)}

53、 = max {5-0.5-1.5+3.5, 4.5-1+2.5} = 6.5 (x4* = 0) f4(2) = max {5-0.5-2.2+3.5, 4-1.5+2} = 5.8 (x4* = 0) f4(3) = max {5-0.5-2.5+3.5, 3.75-2+1.5} = 5.5 (x4* = 0),k = 3狀態(tài)變量 s3 可

54、取 1, 2, f3(1) = max{r(0) - u(0) - c(1) + f4(1), r(1) - u(1) + f4(2)} = max {5-0.5-1.5+6.5, 4.5-1+5.8} = 9.5 (x3* = 0) f3(2) = max {5-0.5-2.2+6.5, 4-1.5+5.5} = 8.8 (x3* = 0),

55、k = 2狀態(tài)變量 s2 可取 1, f2(1) = max{r(0) - u(0) - c(1) + f3(1), r(1) - u(1) + f3(2)} = max {5-0.5-1.5+9.5, 4.5-1+8.8} = 12.5 (x2* = 0) k = 1時狀態(tài)變量 s1 只能取 0 f1(0) = max{r(0) - u(0) - c(0)

56、 + f2(1), r(0) - u(0) + f2(1)} = max{5-0.5-0.5+12.5, 5-0.5+12.5} = 17 (x1* = 1),最優(yōu)策略為:k =12345 不更新 更新 更新 更新 不更新,一貨郎從某城市出發(fā)要經(jīng)過 n 個城市, 每個城市都要經(jīng)過且只能經(jīng)過一次, 最后還要回到

57、原先出發(fā)的城市, 問應(yīng)如何選擇旅行路線可使總行程最短。,6 貨郎擔(dān)問題,分析:與最短路徑問題不同, 由于后面所走的路徑與前面所經(jīng)過的城市相關(guān), 狀態(tài)變量不容易滿足無后效性原則;階段數(shù)與要旅行的城市數(shù)相關(guān);可以將貨郎擔(dān)問題轉(zhuǎn)化為一個最短路問題, 但存在維數(shù)災(zāi)難。,,1,,2,,3,,4,,3,,4,,2,,4,,2,,3,,1,,4,,3,,4,,2,,3,,2,,,,,,,,,,,,,,,,,,,,,,6,7,9,9,7,8,8,