運(yùn)籌學(xué)5動(dòng)態(tài)

1、主要內(nèi)容:§5.1多階段決策過(guò)程的最優(yōu)化 §5.2 動(dòng)態(tài)規(guī)劃的基本概念和基本原理§5.3 動(dòng)態(tài)規(guī)劃方法的基本步驟 §5.4 動(dòng)態(tài)規(guī)劃應(yīng)用舉例,§5.1多階段決策過(guò)程的最優(yōu)化,動(dòng)態(tài)規(guī)劃是解決多階段最優(yōu)決策的方法, 由美國(guó)數(shù)學(xué)家貝爾曼(R. Bellman) 于 1951年首先提出;1957年貝爾曼發(fā)表動(dòng)態(tài)規(guī)劃方面的第一部專著“動(dòng)態(tài)規(guī)劃”, 標(biāo)志著運(yùn)籌學(xué)的一 個(gè)新分支的創(chuàng)立。,例

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

3、賴分析者的經(jīng)驗(yàn)和技巧。與運(yùn)籌學(xué)其他方法有很好的互補(bǔ)關(guān)系, 尤其在處理非線性、離散性問(wèn)題時(shí)有其獨(dú)到的特點(diǎn)。,通常多階段決策過(guò)程的發(fā)展是通過(guò)狀態(tài)的一系列變換來(lái)實(shí)現(xiàn)的。一般情況下，系統(tǒng)在某個(gè)階段的狀態(tài)轉(zhuǎn)移除與本階段的狀態(tài)和決策有關(guān)外，還可能與系統(tǒng)過(guò)去經(jīng)歷的狀態(tài)和決策有關(guān)。因此，問(wèn)題的求解就比較困難復(fù)雜。而適合于用動(dòng)態(tài)規(guī)劃方法求解的只是一類特殊的多階段決策問(wèn)題，即具有“無(wú)后效性”的多階段決策過(guò)程。所謂無(wú)后效性，又稱馬爾柯夫性，是指系統(tǒng)從某個(gè)階

4、段往后的發(fā)展，,僅由本階段所處的狀態(tài)及其往后的決策所決定，與系統(tǒng)以前經(jīng)歷的狀態(tài)和決策(歷史)無(wú)關(guān)。,具有無(wú)后效性的多階段決策過(guò)程的特點(diǎn)是系統(tǒng)過(guò)去的歷史，只能通過(guò)現(xiàn)階段的狀態(tài)去影響系統(tǒng)的未來(lái)，當(dāng)前的狀態(tài)就是后過(guò)程發(fā)展的初始條件。,動(dòng)態(tài)規(guī)劃的應(yīng)用,動(dòng)態(tài)規(guī)劃在工程技術(shù), 企業(yè)管理, 軍事部門(mén)有廣泛的應(yīng)用; 可解決資源分配, 生產(chǎn)調(diào)度, 庫(kù)存管理, 路徑優(yōu)化, 設(shè)備更新, 投資規(guī)劃, 排序問(wèn)題和生產(chǎn)過(guò)程的最優(yōu)控制等問(wèn)題;,拾火柴游戲: 桌子上

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

6、 把一個(gè)復(fù)雜決策問(wèn)題按時(shí)間或空間特征分解為若干(n)個(gè)相互聯(lián)系的階段(stage), 以便按順序求解; 階段變量描述當(dāng)前所處的階段位置，一般用下標(biāo) k 表示;,每階段有若干狀態(tài)(state), 表示某一階段決策面臨的條件或所處位置及運(yùn)動(dòng)特征的量,稱為狀態(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。每個(gè)階段的狀態(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)過(guò)程發(fā)展的方案，決策的實(shí)質(zhì)是關(guān)于狀態(tài)的選擇，是決策者從給定階段狀態(tài)出發(fā)對(duì)下一階段狀態(tài)作出的選擇。,用以描述決策變化的量稱之決策變量，和狀態(tài)變量一樣，決策變量可以用一個(gè)數(shù)，一組數(shù)或一向量來(lái)描述．也可以是狀態(tài)變量的函數(shù)，記以

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

9、 。從 k 階段到第 n 階段，依次進(jìn)行的階段決策構(gòu)成的決策序列稱為 k 部子策略,表示為 ，顯然當(dāng) k=1時(shí)的 k 部子策略就是全過(guò)程策略。,(5) 狀態(tài)轉(zhuǎn)移方程,狀態(tài)轉(zhuǎn)移確定從一個(gè)狀態(tài)到另一個(gè)狀態(tài)的轉(zhuǎn)移過(guò)程, 由狀態(tài)轉(zhuǎn)移方程描述: sk+1 = T (sk, uk); 狀態(tài)轉(zhuǎn)移方程在大多數(shù)情況下可以由數(shù)學(xué)公式表達(dá), 如:

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

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

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

13、用動(dòng)態(tài)規(guī)劃求解最短路問(wèn)題,最短路的求解: 階段: 可分為5個(gè)階段, k = 1, ..., 5。 狀態(tài): 可用城市編號(hào), S1={1}, S2={2, 3, 4}, S3={5, 6, 7}, S4={8, 9}, S5={10} 決策: 決策變量也可用城市編號(hào); 狀態(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,計(jì)算效率分析:

16、對(duì)有 7 個(gè)階段, 每個(gè)階段有 5 種狀態(tài)的最短路徑問(wèn)題, 用窮舉法計(jì)算要進(jìn)行 56 = 15625 次加法和 3124 次比較, 而動(dòng)態(tài)規(guī)劃只需105次加法和 84 次比較, 計(jì)算效率分別提高近150和40倍.,動(dòng)態(tài)規(guī)劃的無(wú)后效性原則,對(duì)任何階段 k, 有sk+1= T (sk, uk), sk+1僅取決于當(dāng)前狀態(tài)sk和當(dāng)前決策uk, 與 k 階段前的狀態(tài)和決策無(wú)關(guān), 也即, k 階段以后的發(fā)展不受該階段以前狀態(tài)的影響, 過(guò)去的

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

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

19、滿足:可知性: 正確描述動(dòng)態(tài)過(guò)程演變, 可直接或間接確定狀態(tài)變量的值;無(wú)后效性: 后面的決策與前面的決策無(wú)關(guān);,3.確定決策變量uk(或xk)以及允許決策集合Dk;4. 寫(xiě)出狀態(tài)轉(zhuǎn)移方程 sk+1 = T (sk , dk);5. 決策變量的取值范圍 6.寫(xiě)出損益函數(shù)的遞推關(guān)系, 應(yīng)滿足:a) 是定義在所有階段上的數(shù)量函數(shù)；b) 具有可分離性，并滿足遞推關(guān)系；c) 損益函數(shù)應(yīng)嚴(yán)格單調(diào)。,例5.3

20、有某種機(jī)床，可以在高低兩種不同的負(fù)荷下進(jìn)行生產(chǎn)，在高負(fù)荷下生產(chǎn)時(shí)，產(chǎn)品的年產(chǎn)量為 g ，與年初投入生產(chǎn)的機(jī)床數(shù)量 u1 的關(guān)系為 g=g(u1)=8u1 ，這時(shí)，年終機(jī)床完好臺(tái)數(shù)將為，au1 ( a為機(jī)床完好率， 0 < a< 1 ，設(shè) a=0.7 )。在低負(fù)荷下生產(chǎn)時(shí)，產(chǎn)品的年產(chǎn)量為 h ，和投入生產(chǎn)的機(jī)床數(shù)量的關(guān)系為 h=h(u2)=5u2 ，相應(yīng)的機(jī)床完好率為 b ( 0<b<2 ，設(shè) b= 0.9 )，

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

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

23、5 時(shí)，f5(s5) 有最大值，相應(yīng)的有 f5(s5) = 8s5 。,K=4 時(shí)有：,因此，當(dāng) u4*= s4 時(shí)，有最大值 f4(s4)=13.6s4,K=3 時(shí)有：,可見(jiàn)，當(dāng) u3*= s3 時(shí)，有最大值 f3(s3) =17.55s3 。,K=2 時(shí)有：,此時(shí)，當(dāng) u2*= 0 時(shí)有最大值，即 f2(s2)=20.8s2,其中 s2=0.7u1+0.9(s1-u1),K=1 時(shí)有：,當(dāng) u1*= 0 時(shí), 有最大值，即 f1

24、(s1)=23.7s1 , 因?yàn)?s1=1000 , 故 f1(s1)=23700 個(gè)產(chǎn)品。,按照上述計(jì)算順序?qū)ほ櫟玫较率鲇?jì)算結(jié)果：,上面所討論的最優(yōu)決策過(guò)程是所謂始端狀態(tài)固定，終端狀態(tài)自由．如果終端也附加上一定的約束條件，那么計(jì)算結(jié)果將會(huì)與之有所差別．例如，若規(guī)定在第五個(gè)年度結(jié)束時(shí)，完好的機(jī)床數(shù)量為500臺(tái)(上面只有278臺(tái))，問(wèn)應(yīng)該如何安排五年的生產(chǎn)，使之在滿足這一終端要求的情況下產(chǎn)量最高？,解：由狀態(tài)轉(zhuǎn)移方程,有,由此式得,當(dāng) k

25、=5 時(shí)有,當(dāng) k=4 時(shí)有,顯然，只有取 u4*=0 , 有最大值 f4(s4)=21.4s4-7500,當(dāng) k=3 時(shí)有:,顯然，只有取 u3*=0 , f3(s3) 有最大值 f3(s3)=24.5s3-7500 。,當(dāng) k=2 時(shí)有:,顯然，只有取 u2*=0 , f2(s2) 有最大值 f2(s2)=27.1s2-7500 。,當(dāng) k=1 時(shí)有:,,顯然，只有取 u1*=0 , f1(s1) 有最大值 f1(s1)

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

27、：（解法1）首先用逆序構(gòu)造動(dòng)態(tài)規(guī)劃模型。,1．分階段：設(shè)階段變量 k 表示依次對(duì)第 k 個(gè)項(xiàng)目投資，因此，階段總數(shù) n = 3。( k = 1 , 2 , 3 ),2. 狀態(tài)變量：用 sk 表示已經(jīng)對(duì)第 1 至 第 k-1 個(gè)項(xiàng)目投資后的剩余資金；即第 k 段初擁有的可以分配給第 k 到第3個(gè)項(xiàng)目的資金額 （單位：萬(wàn)元） 。,3. 決策變量：用 xk 表示對(duì)第 k 個(gè)項(xiàng)目投資 的資金數(shù)量（單位：萬(wàn)元）。,５．決策變量的取值：

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

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

30、,當(dāng) k=1 時(shí)，有,當(dāng) k=2 時(shí)，有,當(dāng) k＝3 時(shí)，有,? x3 = 9/4 為極小點(diǎn)。,極大值應(yīng)在[0，s4] ＝[ 0，10 ] 端點(diǎn)取得,再由狀態(tài)轉(zhuǎn)移方程逆推：,,動(dòng)態(tài)規(guī)劃的優(yōu)點(diǎn),可以解決線性, 非線性, 整數(shù)規(guī)劃無(wú)法有效求解的復(fù)雜問(wèn)題;容易找到全局最優(yōu)解;可以得到一組解;,動(dòng)態(tài)規(guī)劃的缺點(diǎn),沒(méi)有標(biāo)準(zhǔn)的模型可供應(yīng)用, 構(gòu)模依賴于個(gè)人的經(jīng)驗(yàn)和技巧;狀態(tài)變量需滿足無(wú)后效性, 有較大的局限性;動(dòng)態(tài)規(guī)劃的維數(shù)災(zāi)難限制了

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

32、 g2(x2) + . . . + gn(xn)x1 + x2 + . . . + xn = axi ? 0 i = 1, . . ., n,例: 某工廠有4臺(tái)設(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è)備臺(tái)數(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,離散的時(shí)間段內(nèi)如何安排生產(chǎn)與庫(kù)存。

36、生產(chǎn)成本為: C(xt) = k + cxt (xt > 0) 或 C(xt) = 0 (xt = 0), k為開(kāi)工所需費(fèi)用, c 是變動(dòng)成本, xt為 t 期的生產(chǎn)數(shù)量;庫(kù)存成本為：H(yt) = hyt, h為單位庫(kù)存成本，yt為 t 期期初庫(kù)存數(shù)量。,2. 生產(chǎn)與庫(kù)存問(wè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每周期期初的庫(kù)存量為該階段的狀態(tài), 狀態(tài)變量 st 表示 t 周期期初庫(kù)存；決策變量 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、以庫(kù)存表示系統(tǒng)狀態(tài)會(huì)大大增加系統(tǒng)狀態(tài)數(shù)量, 然而, 上述問(wèn)題的最優(yōu)決策必須使每一階段庫(kù)存或者為零, 或者為后續(xù)一或幾個(gè)周期需求之和。,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簡(jiǎn)單判斷方法：只要固定費(fèi)用大于后面發(fā)生的庫(kù)存費(fèi)用，就值得一次生產(chǎn)滿足一或幾個(gè)周期的需求。,3. 復(fù)合系統(tǒng)的工作可靠性問(wèn)題例: 為保證設(shè)備可靠運(yùn)行, 一些關(guān)鍵部件往往由多個(gè)器件并聯(lián)運(yùn)行, 如果器件 i 的失效概率為 pi, 則 xi 個(gè)器件并聯(lián)工作的可靠性為(1 - pixi), 假定每個(gè)器件的采購(gòu)費(fèi)用為 ci, 在滿足總采購(gòu)費(fèi)用不超過(guò)預(yù)算限制 C 的前提下, 使設(shè)備可

44、靠性最高的規(guī)劃問(wèn)題可以描述為:,該問(wèn)題為整數(shù)非線性規(guī)劃，可以用動(dòng)態(tài)規(guī)劃求解，設(shè)關(guān)鍵器件數(shù)n = 3，總費(fèi)用為120萬(wàn)元。器件的單價(jià)與可靠性如下表：,分析：階段與器件掛鉤，第 i 階段僅考慮器件 i 的采購(gòu)數(shù)量;si 表示 i 階段可使用的采購(gòu)費(fèi)用;xi 表示 i 階段決定購(gòu)買 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 二維背包問(wèn)題,當(dāng)背包問(wèn)題中有兩個(gè)限制條件時(shí)(如重量和體積限制), 所形成的問(wèn)題為 二維背包問(wèn)題, 問(wèn)題的一般形式為:max z = ?i ci xi s.t.?i ai xi ? b xi ? 0 且為整數(shù),例: 卡車的最大運(yùn)貨重量為 12 噸, 容積為 10 立方米, 現(xiàn)有A , B 兩種貨物, 重量分別為 3

48、噸和 4 噸, 體積分別為 1 和 5 立方米, 運(yùn)費(fèi)分別為 2 和 3 元, 如何裝載使所得運(yùn)費(fèi)最大。 由資源條件可知最多可裝載 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,動(dòng)態(tài)規(guī)劃的維數(shù)

50、增加時(shí), 求解的復(fù)雜程度也會(huì)增加。如果狀態(tài)變量的維數(shù)為 m, 離散的決策變量有 n 個(gè)取值, 則在每個(gè)階段需要存儲(chǔ) nm 個(gè)數(shù)據(jù), 這就是所謂的維數(shù)災(zāi)難。,5 設(shè)備更新問(wèn)題,設(shè)備在使用全過(guò)程中會(huì)遭受磨損, 使用一段時(shí)間后就要維修, 而且使用的時(shí)間越長(zhǎng), 維修費(fèi)用越高, 設(shè)備使用多少時(shí)間在經(jīng)濟(jì)上最合算, 就是設(shè)備更新問(wèn)題。,分析：階段 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時(shí)狀態(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)過(guò) n 個(gè)城市, 每個(gè)城市都要經(jīng)過(guò)且只能經(jīng)過(guò)一次, 最后還要回到

57、原先出發(fā)的城市, 問(wèn)應(yīng)如何選擇旅行路線可使總行程最短。,6 貨郎擔(dān)問(wèn)題,分析:與最短路徑問(wèn)題不同, 由于后面所走的路徑與前面所經(jīng)過(guò)的城市相關(guān), 狀態(tài)變量不容易滿足無(wú)后效性原則;階段數(shù)與要旅行的城市數(shù)相關(guān);可以將貨郎擔(dān)問(wèn)題轉(zhuǎn)化為一個(gè)最短路問(wè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,