f第七章動態(tài)規(guī)劃

1、 運籌學(xué)運籌學(xué)動態(tài)規(guī)劃（動態(tài)規(guī)劃（1 1） 運籌學(xué)運籌學(xué)定理：定理： 如果如果A到到F的最短路程是的最短路程是:ABCDEF 那么那么C到到F的最短路程一定是的最短路程一定是: CDEF (Bellman最優(yōu)化原理）最優(yōu)化原理）第六章 動態(tài)規(guī)劃（1） 運籌學(xué)運籌學(xué)第六章 動態(tài)規(guī)劃（1）動態(tài)規(guī)劃在經(jīng)濟管理中應(yīng)用：動態(tài)規(guī)劃應(yīng)用之一：最優(yōu)路徑問題最優(yōu)路徑問題動態(tài)規(guī)劃應(yīng)用之二：資源分配問題資源分配問題動態(tài)規(guī)劃應(yīng)用之三：生產(chǎn)計劃調(diào)度問題生產(chǎn)計劃調(diào)度問題動態(tài)規(guī)劃應(yīng)用之四：庫存問題，采購問題庫存問題，采購問題動態(tài)規(guī)劃應(yīng)用之五：設(shè)備更新問題設(shè)備更新問題動態(tài)規(guī)劃應(yīng)用之六： 生產(chǎn)過程最優(yōu)控制問題生產(chǎn)過程最優(yōu)控制問

2、題動態(tài)規(guī)劃應(yīng)用之七： . 運籌學(xué)運籌學(xué)動態(tài)規(guī)劃應(yīng)用之一：最優(yōu)路徑問題：最優(yōu)路徑問題：類似類似P201例題：例題： 某某工廠從國外進口一部精密設(shè)備，由機器制造廠到出口港有三個港口可供選擇，工廠從國外進口一部精密設(shè)備，由機器制造廠到出口港有三個港口可供選擇，而進口港又有三個港口可供選擇，進口后可以經(jīng)兩個城市到達目的地，其運而進口港又有三個港口可供選擇，進口后可以經(jīng)兩個城市到達目的地，其運輸成本輸成本 如圖所示，求運費最低的路線如圖所示，求運費最低的路線AB3B2B1D2D1C3C2C1E2040403020304010604070503030306040104030第六章 動態(tài)規(guī)劃（1）運輸成本運

3、輸成本國外機器制造廠國外機器制造廠 出口港出口港 進口港進口港 國內(nèi)城市國內(nèi)城市 國內(nèi)某工廠國內(nèi)某工廠 運籌學(xué)運籌學(xué)AB3B2B1D2D1C3C2C1E2040403020304010604070503030306040104030400307040608070110110第六章 動態(tài)規(guī)劃（1）從從C1到終點最短路到終點最短路兩點間運輸成本兩點間運輸成本國外機器制造廠國外機器制造廠 出口港出口港 進口港進口港 國內(nèi)城市國內(nèi)城市 國內(nèi)某工廠國內(nèi)某工廠 運籌學(xué)運籌學(xué)AB3B2B1D2D1C3C2C1E2040403020304010604070503030306040104030400307040

4、608070110國外機器制造廠國外機器制造廠 出口港出口港 進口港進口港 國內(nèi)城市國內(nèi)城市 國內(nèi)某工廠國內(nèi)某工廠1.階段階段 2.狀態(tài)狀態(tài) 3.決策決策 4.策略策略 5.狀態(tài)轉(zhuǎn)移方程狀態(tài)轉(zhuǎn)移方程 6.指標(biāo)函數(shù)和最優(yōu)值函指標(biāo)函數(shù)和最優(yōu)值函數(shù)數(shù)第六章 動態(tài)規(guī)劃（1）110 運籌學(xué)運籌學(xué)動態(tài)規(guī)劃的基本概念：動態(tài)規(guī)劃的基本概念：1. 階段：把問題分為互相聯(lián)系有一定次序的階段階段：把問題分為互相聯(lián)系有一定次序的階段(上例，四個階段上例，四個階段)狀態(tài)：每個階段開始所處自然狀況或客觀條件，不可控制（第狀態(tài)：每個階段開始所處自然狀況或客觀條件，不可控制（第1階階段狀態(tài)：段狀態(tài)：A，第，第2階段狀態(tài)：階段

5、狀態(tài)：B1，B2，B3） 無后效性（馬爾科夫性）無后效性（馬爾科夫性）3. 決策：某個階段的某個狀態(tài)決定下一個階段的狀態(tài)（從決策：某個階段的某個狀態(tài)決定下一個階段的狀態(tài)（從A出發(fā)，三出發(fā)，三種不同決策：種不同決策： B1，B2，B3 ）4. 策略：按順序排列的決策組成的集合（序列）策略：按順序排列的決策組成的集合（序列）5. 狀態(tài)轉(zhuǎn)移方程：確定由一個狀態(tài)轉(zhuǎn)到另一個狀態(tài)的過程狀態(tài)轉(zhuǎn)移方程：確定由一個狀態(tài)轉(zhuǎn)到另一個狀態(tài)的過程指標(biāo)函數(shù)和最優(yōu)值函數(shù)：衡量過程優(yōu)劣的數(shù)量指標(biāo)指標(biāo)函數(shù)和最優(yōu)值函數(shù)：衡量過程優(yōu)劣的數(shù)量指標(biāo)2.閱讀：閱讀：P196-P198 基本概念基本概念第六章 動態(tài)規(guī)劃（1） 運籌學(xué)運籌學(xué)

6、動態(tài)規(guī)劃最優(yōu)性原理與最優(yōu)性定理：動態(tài)規(guī)劃與靜態(tài)規(guī)劃的關(guān)系：動態(tài)規(guī)劃非線性規(guī)劃運輸問題規(guī)劃整數(shù)規(guī)劃線性規(guī)劃靜態(tài)規(guī)劃數(shù)字規(guī)劃10第六章 動態(tài)規(guī)劃（1） 運籌學(xué)運籌學(xué)1.資源分配問題資源分配問題引例：某種原料總數(shù)為引例：某種原料總數(shù)為a分配給分配給n種產(chǎn)品，分配數(shù)量種產(chǎn)品，分配數(shù)量Xi用于生產(chǎn)第用于生產(chǎn)第i種產(chǎn)品，種產(chǎn)品，效益為效益為gi(xi)0.)(.)()(212211innnxaxxxxgxgxgMaxZ種產(chǎn)品原料量第k種產(chǎn)品原料數(shù)量種產(chǎn)品到第第nk1種產(chǎn)品原料數(shù)量種產(chǎn)品到第第nk0)(1kkkkkkkkkkkSXUUSDXSUSS：允許決策集合：狀態(tài)轉(zhuǎn)移方程：第六章 動態(tài)規(guī)劃（1） 運籌學(xué)

7、運籌學(xué)動態(tài)規(guī)劃順序解法：動態(tài)規(guī)劃順序解法：第一步：劃分階段第一步：劃分階段第二步：選擇狀態(tài)變量第二步：選擇狀態(tài)變量第三步：確定決策變量第三步：確定決策變量第四步：寫狀態(tài)轉(zhuǎn)移方程第四步：寫狀態(tài)轉(zhuǎn)移方程第五步：第五步： 指標(biāo)函數(shù)指標(biāo)函數(shù)第六章 動態(tài)規(guī)劃（1） 運籌學(xué)運籌學(xué)第六章 動態(tài)規(guī)劃（1）類似類似P 208例例4 順推法求解非線性規(guī)劃：順推法求解非線性規(guī)劃： maxZ=4x1+9x2+2x32 x1+x2+x3=10 xi=0 I=1,2,3分析：理解為分析：理解為 第一階段投資第一階段投資x1， 第二階段投資第二階段投資x2 第三階段投資第三階段投資x3 求最大利潤求最大利潤maxZ=4x1

8、+9x2+2x32 三階段投資總額共有三階段投資總額共有10單位單位 非線性規(guī)劃問題求解非線性規(guī)劃問題求解 第一階段投資總額第一階段投資總額S1（狀態(tài)變量）（狀態(tài)變量） 第一二階段投資總額第一二階段投資總額S2 （狀態(tài)變量）（狀態(tài)變量） 第一二三階段投資總額第一二三階段投資總額S3 （狀態(tài)變量）（狀態(tài)變量）x1x2x3S3S2S1S1 = X1 S2 = X1 +X2 S3 = X1+X2+X3動態(tài)規(guī)劃應(yīng)用之二：資源分配問題資源分配問題-P207 -P207 例例3 3 運籌學(xué)運籌學(xué)第六章 動態(tài)規(guī)劃（1）解解:設(shè)狀態(tài)變量設(shè)狀態(tài)變量S1=X1 ,S2=S1+X2, S3=S2+X3F1(S1)=

9、4X1=4S1 ( 第一階段投資第一階段投資x1產(chǎn)生的效益產(chǎn)生的效益4X1 ）第一二階段投資總量為第一二階段投資總量為S2產(chǎn)生的效益產(chǎn)生的效益 第一階段投資第一階段投資x1產(chǎn)生的效益第二階段投資產(chǎn)生的效益第二階段投資X2產(chǎn)生的效益產(chǎn)生的效益S1=S2-X2 F2(S2)=9X2+F1(S1)= 9X2 + 4S2 -4X2 = 5X2 + 4S2 X2 S2當(dāng)當(dāng)X2=S2時時 maxF2(S2)=9S2第一二三階段投資總量為第一二三階段投資總量為S3產(chǎn)生的效益產(chǎn)生的效益 第一二階段投資第一二階段投資S2產(chǎn)生的效益第三階段投資產(chǎn)生的效益第三階段投資X3產(chǎn)生的效益產(chǎn)生的效益S2=S3-X3F3(S

10、3)= 2X32 +F2(S2)= 2X32 + 9(S3 -X3 ) = 2X32-9X3+9S3 =h3(S3,X3) 0=X3 =10d h3(S3,X3) /dX3=4X3-9=0 且且兩階導(dǎo)數(shù)大于零兩階導(dǎo)數(shù)大于零因此：因此：X3=9/4 在在X3=9/4, F3(S3)有最小值有最小值, F3(S3) 最大值最大值 X3 10max F3(S3)=2*102=200即即X3=10,則則 X1,X2為為0 max Z=200. 運籌學(xué)運籌學(xué)第六章 動態(tài)規(guī)劃（1）X3H3(S3,X3)109/4在在X3=9/4, F3(S3)有最小值有最小值, F3(S3) 最大值最大值 X3 10 運

11、籌學(xué)運籌學(xué)背包問題背包問題：類似：類似P236 例例7： 用動態(tài)規(guī)劃解下列問題：用動態(tài)規(guī)劃解下列問題：Max Z= 8 X1 +7X2 S.T. 2X1 +X2 8 5X1 +2X2 15X1 , X2 為非負整數(shù)為非負整數(shù) 經(jīng)濟意義：經(jīng)濟意義： X1 , X2為物品數(shù)量，為物品數(shù)量，8，7為單位物品的價值，為單位物品的價值，2，1為單位物品的體積，為單位物品的體積，5，2為單為單位物品的重量位物品的重量. 8為背包的最大容積，為背包的最大容積，15為背包的最大承受重量為背包的最大承受重量第六章 動態(tài)規(guī)劃（1） 運籌學(xué)運籌學(xué)第六章 動態(tài)規(guī)劃（1）類似類似P207 例例3 用動態(tài)規(guī)劃用動態(tài)規(guī)劃逆

12、序算法逆序算法解下列問題（解下列問題（二維背包問題二維背包問題）：）：Max Z= 8 X1 +7X2 （最大效益，重量限制，體積限制）（最大效益，重量限制，體積限制） S.T. 2X1 + X2 8 (重量重量) 5X1 +2X2 15 (體積體積)X1 , X2 為非負整數(shù)為非負整數(shù)解：解：用逆序算法用逆序算法。設(shè)：。設(shè)： 階段：分成兩個階段，分別對應(yīng)第階段：分成兩個階段，分別對應(yīng)第1種物體的數(shù)量種物體的數(shù)量X1 ，第，第2種物體的數(shù)量種物體的數(shù)量X2 逆序算法先決定背包中第逆序算法先決定背包中第2種物體的數(shù)量種物體的數(shù)量決策變量：決策變量：X1 ，X2 為背包中兩種物體的數(shù)量為背包中兩種

13、物體的數(shù)量狀態(tài)變量：狀態(tài)變量：V1 為第為第1 階段階段 可供分配重量，可供分配重量， V1 8 W1 為第為第1 階段可供分配體積，階段可供分配體積， W1 15，V2 ，W2 對應(yīng)第對應(yīng)第2 階段階段于是，于是， F*2（V2 ，W2 ）= Max 7 X2 0X2 V2 (重量重量) 02X2 W2 (體積體積)x1x2V1 ， W1V2 ， W2V1 = 8 ， W1 = 15V2 = V1 -2X1 ( 重量重量)W2 = W1 - 5X1 (體積體積) 運籌學(xué)運籌學(xué)X2 為整數(shù)為整數(shù) = 7min V2, W2/2(V是小于等于是小于等于V的最大整數(shù)的最大整數(shù)) F*1（V1 ，W

14、1 ）= Max 8 X1 + F*2（V1 -2X1 ，W1 - 5X1） 02X1 V1 (重量重量) 05X1 W1 (體積體積) X1 為整數(shù)為整數(shù) 而而V1 =8，W1=15 因此因此 F*1（8 ，15 ）= Max 8 X1 + 7min 8 -2X1, (15 - 5X1)/2 02X18 05X1 15 X1 為整數(shù)為整數(shù)由于由于 X1 min 8 /2, (15/5)=3 (X1 為為0，1，2，3，分別代入下式，分別代入下式) F*1（V1 ，W1 ）= Max 8 X1 + 7min 8 -2X1, (15 - 5X1)/2 第六章 動態(tài)規(guī)劃（1） 運籌學(xué)運籌學(xué)X*1

15、=0 X*2 = min V2, W2/2 V2=V1 - 2X1=8， W2=W1 -5X1 =15 X*2 = 7因此因此, 最優(yōu)解為最優(yōu)解為X*1 =0, X*2 = 7 , 最優(yōu)最優(yōu)值值:Z*= 49第六章 動態(tài)規(guī)劃（1） 運籌學(xué)運籌學(xué)第六章 動態(tài)規(guī)劃（1）基本定理：基本定理： 如果如果A到到F的最短路程是的最短路程是ABCDEF，那么那么C到到F的最短路程一定是的最短路程一定是 CDEF (Bellman最優(yōu)化原理）最優(yōu)化原理）總結(jié)總結(jié)動態(tài)規(guī)劃的基本概念：動態(tài)規(guī)劃的基本概念：1。階段：把問題分為互相聯(lián)系有一定次序的階段。階段：把問題分為互相聯(lián)系有一定次序的階段2。狀態(tài)：每個階段開始所

16、處自然狀況或客觀條件，不可控制。狀態(tài)：每個階段開始所處自然狀況或客觀條件，不可控制3。決策：某個階段的某個狀態(tài)決定下一個階段的狀態(tài)。決策：某個階段的某個狀態(tài)決定下一個階段的狀態(tài)4。策略：某個階段的某個狀態(tài)所有可能的決策。策略：某個階段的某個狀態(tài)所有可能的決策5。狀態(tài)轉(zhuǎn)移方程：確定由一個狀態(tài)轉(zhuǎn)到另一個狀態(tài)的過程。狀態(tài)轉(zhuǎn)移方程：確定由一個狀態(tài)轉(zhuǎn)到另一個狀態(tài)的過程6。指標(biāo)函數(shù)和最優(yōu)值函數(shù)：衡量過程優(yōu)劣的數(shù)量指標(biāo)。指標(biāo)函數(shù)和最優(yōu)值函數(shù)：衡量過程優(yōu)劣的數(shù)量指標(biāo) 運籌學(xué)運籌學(xué)第六章 動態(tài)規(guī)劃（3）知識要點知識要點 概念概念(1)多階段決策問題是指這樣的問題多階段決策問題是指這樣的問題,它可分為若干個互相聯(lián)

17、系的它可分為若干個互相聯(lián)系的階段階段,每一階段都對應(yīng)著一組可供選擇的決策每一階段都對應(yīng)著一組可供選擇的決策,每個階段的決策選每個階段的決策選定之后定之后,就構(gòu)成一個決策序列就構(gòu)成一個決策序列,稱為一個策略稱為一個策略,它對應(yīng)一個確定的效它對應(yīng)一個確定的效果。多階段的決策問題果。多階段的決策問題,就是要尋求使此效果最好的策略。就是要尋求使此效果最好的策略。(2)階段是指總的需要作出決策的步數(shù)。階段總數(shù)常記為階段是指總的需要作出決策的步數(shù)。階段總數(shù)常記為n，相應(yīng)，相應(yīng)的是的是n個階段的決策問題。階段的序號常記為個階段的決策問題。階段的序號常記為k,稱為階段變量，稱為階段變量，k=1,2, ，n。k

18、既可以順序編號也可以逆序編號，常用順序編號。既可以順序編號也可以逆序編號，常用順序編號。1.階段階段 2.狀態(tài)狀態(tài) 3.決策決策 4.策略策略 5.狀態(tài)轉(zhuǎn)移方程狀態(tài)轉(zhuǎn)移方程 6.指標(biāo)函數(shù)和最優(yōu)值函數(shù)指標(biāo)函數(shù)和最優(yōu)值函數(shù) 運籌學(xué)運籌學(xué)第六章 動態(tài)規(guī)劃（3）知識要點知識要點(3)狀態(tài)是某階段決策的出發(fā)點，又是前個階段決策的結(jié)果，因此它是階段狀態(tài)是某階段決策的出發(fā)點，又是前個階段決策的結(jié)果，因此它是階段信息的傳遞點與結(jié)合點。第信息的傳遞點與結(jié)合點。第k階段的狀態(tài)常用狀態(tài)變量階段的狀態(tài)常用狀態(tài)變量xk表示，表示，xk應(yīng)包含第應(yīng)包含第k個階段之前決策過程的全部信息，使該階段后作出的決策同以前的狀態(tài)和個階

19、段之前決策過程的全部信息，使該階段后作出的決策同以前的狀態(tài)和決策相互獨立。狀態(tài)變量根據(jù)實際問題可以表述為一維或多維的向量，其決策相互獨立。狀態(tài)變量根據(jù)實際問題可以表述為一維或多維的向量，其取值可以是離散的，也可以是連續(xù)的。取值可以是離散的，也可以是連續(xù)的。（4）決策是指從某階段的某個狀態(tài)出發(fā)，在若干個不同方案中做出的選擇。）決策是指從某階段的某個狀態(tài)出發(fā)，在若干個不同方案中做出的選擇。第第k階段狀態(tài)為階段狀態(tài)為xk時的決策用決策變量時的決策用決策變量uk（xk）表示。決策變量允許的取值）表示。決策變量允許的取值范圍稱為允許決策集合，第范圍稱為允許決策集合，第k階段狀態(tài)為階段狀態(tài)為xk時的允許決

20、策集合記為時的允許決策集合記為Dk(xk)，它相當(dāng)于線性規(guī)劃中的約束條件。決策變量的取值可以是離散的，也可以它相當(dāng)于線性規(guī)劃中的約束條件。決策變量的取值可以是離散的，也可以是連續(xù)的。是連續(xù)的。（5）n個階段的決策問題可看成是從第個階段的決策問題可看成是從第1個階段直到第個階段直到第n個階段決策的全過個階段決策的全過程，而從第程，而從第k個階段直到第個階段直到第n個階段可看作是子過程。動態(tài)規(guī)劃問題各階段個階段可看作是子過程。動態(tài)規(guī)劃問題各階段決策組成的序列稱為一個策略。決策組成的序列稱為一個策略。1.階段階段 2.狀態(tài)狀態(tài) 3.決策決策 4.策略策略 5.狀態(tài)轉(zhuǎn)移方程狀態(tài)轉(zhuǎn)移方程 6.指標(biāo)函數(shù)和

21、最優(yōu)值函數(shù)指標(biāo)函數(shù)和最優(yōu)值函數(shù) 運籌學(xué)運籌學(xué)第六章 動態(tài)規(guī)劃（3）知識要點知識要點(6)狀態(tài)轉(zhuǎn)移律是從上一階段的某一狀態(tài)值轉(zhuǎn)變?yōu)橄露文骋粻顟B(tài)值狀態(tài)轉(zhuǎn)移律是從上一階段的某一狀態(tài)值轉(zhuǎn)變?yōu)橄露文骋粻顟B(tài)值的轉(zhuǎn)移規(guī)律的轉(zhuǎn)移規(guī)律,常用數(shù)學(xué)等式描述。第常用數(shù)學(xué)等式描述。第k+1個階段的狀態(tài)變量個階段的狀態(tài)變量xk+1是第是第k個階段狀態(tài)變量個階段狀態(tài)變量xk和決策變量和決策變量uk(xk)的函數(shù)的函數(shù).（7）指標(biāo)函數(shù)可分為階段的指標(biāo)函數(shù)與過程的指標(biāo)函數(shù)兩種。階）指標(biāo)函數(shù)可分為階段的指標(biāo)函數(shù)與過程的指標(biāo)函數(shù)兩種。階段的指標(biāo)函數(shù)是指第段的指標(biāo)函數(shù)是指第k個階段從狀態(tài)個階段從狀態(tài)xk出發(fā)采取決策出發(fā)采取決策uk時

22、的效益，時的效益，用用uk（xk，uk）表示。而過程的指標(biāo)函數(shù)是指從第）表示。而過程的指標(biāo)函數(shù)是指從第k個階段的某個個階段的某個狀態(tài)狀態(tài)xk出發(fā)，采取子策略出發(fā)，采取子策略uk ，uk+1,un時所得到的效益，它既與時所得到的效益，它既與xk有關(guān)，又與以后的子策略有關(guān)，是兩者的函數(shù)有關(guān)，又與以后的子策略有關(guān)，是兩者的函數(shù).（8）最優(yōu)指標(biāo)函數(shù)是指從第）最優(yōu)指標(biāo)函數(shù)是指從第k個階段的狀態(tài)個階段的狀態(tài)xk出發(fā)采取最優(yōu)子策出發(fā)采取最優(yōu)子策略后得到的過程指標(biāo)函數(shù)值，即對應(yīng)最優(yōu)子策略的效益值略后得到的過程指標(biāo)函數(shù)值，即對應(yīng)最優(yōu)子策略的效益值.1.階段階段 2.狀態(tài)狀態(tài) 3.決策決策 4.策略策略 5.狀態(tài)

23、轉(zhuǎn)移方程狀態(tài)轉(zhuǎn)移方程 6.指標(biāo)函數(shù)和最優(yōu)值函數(shù)指標(biāo)函數(shù)和最優(yōu)值函數(shù) 運籌學(xué)運籌學(xué)動態(tài)規(guī)劃在經(jīng)濟管理中應(yīng)用：動態(tài)規(guī)劃應(yīng)用之一：最優(yōu)路徑問題（已講）最優(yōu)路徑問題（已講）動態(tài)規(guī)劃應(yīng)用之二：資源分配問題（已講）資源分配問題（已講）動態(tài)規(guī)劃應(yīng)用之三：生產(chǎn)計劃調(diào)度問題（？）生產(chǎn)計劃調(diào)度問題（？）動態(tài)規(guī)劃應(yīng)用之四：庫存問題，采購問題（？）庫存問題，采購問題（？）動態(tài)規(guī)劃應(yīng)用之五：設(shè)備更新問題（？）設(shè)備更新問題（？）動態(tài)規(guī)劃應(yīng)用之六： 生產(chǎn)過程最優(yōu)控制問題（？）生產(chǎn)過程最優(yōu)控制問題（？）動態(tài)規(guī)劃應(yīng)用之七： . 運籌學(xué)運籌學(xué)動態(tài)規(guī)劃（動態(tài)規(guī)劃（2 2） 運籌學(xué)運籌學(xué)第六章 動態(tài)規(guī)劃（2）P216 例例1 一維資

24、源分配問題：一維資源分配問題：要把五臺高效率的設(shè)備調(diào)配給自己的三家分廠，要把五臺高效率的設(shè)備調(diào)配給自己的三家分廠，各個工廠得到這些設(shè)備所產(chǎn)生的利潤如下表，各個工廠得到這些設(shè)備所產(chǎn)生的利潤如下表，問如何調(diào)配可以獲得最大利潤？問如何調(diào)配可以獲得最大利潤？產(chǎn)生利潤產(chǎn)生利潤工廠工廠1工廠工廠2工廠工廠30臺臺0001臺臺3542臺臺71063臺臺911114臺臺1211125臺臺131112階段、決策變量、階段、決策變量、狀態(tài)變量狀態(tài)變量?動態(tài)規(guī)劃應(yīng)用之二：資源分配問題資源分配問題 運籌學(xué)運籌學(xué)第六章 動態(tài)規(guī)劃（2）P216 例例1 一維資源分配問題：一維資源分配問題：階段階段,決策變量與狀態(tài)變量決策

25、變量與狀態(tài)變量分配到分配到k廠的設(shè)備臺數(shù)廠的設(shè)備臺數(shù) Xk分配到分配到k廠到廠到3廠的設(shè)備總臺廠的設(shè)備總臺數(shù)數(shù) Sk, 產(chǎn)生利潤產(chǎn)生利潤工廠工廠1工廠工廠2工廠工廠30臺臺0001臺臺3542臺臺71063臺臺911114臺臺1211125臺臺131112X1 X2 X3 S1S2S3S3 = X3 S2 = X2 +X3 S1 = X1+X2+X3 運籌學(xué)運籌學(xué) P3(X3) F3(S3)X*3X3 =0X3 = 1X3 = 2X3 = 3X3 = 4X3 = 5S3 = 0000S3 = 1441S3 = 2662S3 = 311113S3 = 412124S3 = 512125 注意：分

26、配到注意：分配到3廠的設(shè)備總臺數(shù)廠的設(shè)備總臺數(shù) S3 = 分配到分配到3廠的設(shè)備臺數(shù)廠的設(shè)備臺數(shù) X3第六章 動態(tài)規(guī)劃（2） 運籌學(xué)運籌學(xué)第六章 動態(tài)規(guī)劃（2）分配到分配到2廠的設(shè)備廠的設(shè)備臺數(shù)臺數(shù) X2 P2(X2) F3 ( S2 X2)F2 ( S2)X*2X2 =0X2 =1X2 =2X2 =3X2 =4X2 =5S2 = 0000S2 = 1045051S2 = 20654100102S2 = 301156104110142S2 = 4012511106114110161，2S2 = 50125121011116114110212分配到分配到2廠到廠到3廠的設(shè)備廠的設(shè)備總臺數(shù)總臺數(shù)

27、S2 = X2 X3由已知表：第由已知表：第2廠分配廠分配3臺設(shè)備得效益臺設(shè)備得效益11由上表：第由上表：第3廠分配廠分配2 臺設(shè)備得效益臺設(shè)備得效益6 運籌學(xué)運籌學(xué)第六章 動態(tài)規(guī)劃（2）分配到分配到1廠的設(shè)備廠的設(shè)備臺數(shù)臺數(shù) X1 P1(X1) F2(5 - X1)F1(5 )X*1X1 =0X1 = 1X1 = 2X1 = 3X1 = 4X1 = 5 S1 = 5021=21316=19714=21910=19125130=13210，2分配給分配給1廠到廠到3廠廠的設(shè)備總臺數(shù)的設(shè)備總臺數(shù) S1 = 5由已知表：第由已知表：第1廠分配廠分配4臺設(shè)備得效益臺設(shè)備得效益12，由上表：第由上表：

28、第2，3廠分配廠分配 1臺設(shè)備得效益臺設(shè)備得效益5由第三表知：總利潤由第三表知：總利潤21萬元萬元X1 0，第，第1工廠不分配，工廠不分配， 第第2，3 工廠分配工廠分配 5 臺，臺， S2 = X2 +X3 5由第二表對應(yīng)由第二表對應(yīng) S2 5知：知： X2 2，第，第2工廠分配工廠分配2臺，臺， 于是第于是第3工廠分配工廠分配 3臺臺 最優(yōu)分配一：第最優(yōu)分配一：第1廠廠 分配分配0臺；臺； 第第2廠廠 分配分配2臺；第臺；第3廠分配廠分配3臺；臺； 總利潤總利潤21萬元萬元 運籌學(xué)運籌學(xué)第六章 動態(tài)規(guī)劃（2）另一個結(jié)果是，由第三表知：總利潤也是另一個結(jié)果是，由第三表知：總利潤也是21萬元萬

29、元X1 2，第，第1工廠分配工廠分配2臺，臺， 第第2，3 工廠分配工廠分配 3 臺，臺， S2 = X2 +X3 3由第二表由第二表 對應(yīng)對應(yīng) S2 3 知：知： X2 2，第，第2工廠分配工廠分配2臺，臺，于是第于是第3工廠分配工廠分配 1臺臺最優(yōu)分配二：第最優(yōu)分配二：第1廠廠 分配分配2臺；第臺；第2廠廠 分配分配2臺；第臺；第3廠廠 分配分配1臺；總利潤臺；總利潤21萬元萬元 運籌學(xué)運籌學(xué)第六章 動態(tài)規(guī)劃（3）基本要求基本要求 1.明確什么是多階段的決策問題，特別要注意沒有明顯的時段明確什么是多階段的決策問題，特別要注意沒有明顯的時段 背景的問題如何化歸為多階段的決策問題。背景的問題如

30、何化歸為多階段的決策問題。2 準(zhǔn)確、熟練地掌握動態(tài)規(guī)劃的基本概念，特別是狀態(tài)變量、準(zhǔn)確、熟練地掌握動態(tài)規(guī)劃的基本概念，特別是狀態(tài)變量、 決決 策變量、狀態(tài)轉(zhuǎn)移律、指標(biāo)函數(shù)、基本方程等。策變量、狀態(tài)轉(zhuǎn)移律、指標(biāo)函數(shù)、基本方程等。.3.掌握最優(yōu)化原理的內(nèi)容。掌握最優(yōu)化原理的內(nèi)容。4.掌握逆序解法與順序解法，主要是逆序解法。掌握逆序解法與順序解法，主要是逆序解法。5.會判定動態(tài)規(guī)劃問題的類型。會判定動態(tài)規(guī)劃問題的類型。1.階段階段 2.狀態(tài)狀態(tài) 3.決策決策 4.策略策略 5.狀態(tài)轉(zhuǎn)移方程狀態(tài)轉(zhuǎn)移方程 6.指標(biāo)函數(shù)和最優(yōu)值函數(shù)指標(biāo)函數(shù)和最優(yōu)值函數(shù) 運籌學(xué)運籌學(xué)第六章 動態(tài)規(guī)劃（2）出租汽車高負荷運行

31、效果？出租汽車高負荷運行效果？出租汽車低負荷運行效果？出租汽車低負荷運行效果？動態(tài)規(guī)劃應(yīng)用之三：生產(chǎn)計劃調(diào)度問題生產(chǎn)計劃調(diào)度問題 運籌學(xué)運籌學(xué)P 219 例例2 動態(tài)規(guī)劃應(yīng)用舉例動態(tài)規(guī)劃應(yīng)用舉例 動態(tài)規(guī)劃求解動態(tài)規(guī)劃求解 機器負荷分配問題機器負荷分配問題 某種機器可以在高低兩種不同的負荷下生產(chǎn)，高負荷生產(chǎn)產(chǎn)某種機器可以在高低兩種不同的負荷下生產(chǎn)，高負荷生產(chǎn)產(chǎn)量函數(shù)為量函數(shù)為G= 8 U1 其中其中U1 表示投入生產(chǎn)的機器數(shù)量，表示投入生產(chǎn)的機器數(shù)量， 年完年完好率好率A=0.7低負荷生產(chǎn)產(chǎn)量函數(shù)為低負荷生產(chǎn)產(chǎn)量函數(shù)為H=5Y, 其中其中Y 表示投入生產(chǎn)的機器表示投入生產(chǎn)的機器數(shù)量，數(shù)量， 年完

32、好率年完好率 B = 0. 9, 如果初始投入生產(chǎn)的機器如果初始投入生產(chǎn)的機器1000臺，臺，問如何安排生產(chǎn)，使在問如何安排生產(chǎn)，使在5年內(nèi)生產(chǎn)的產(chǎn)品總量達到最大？年內(nèi)生產(chǎn)的產(chǎn)品總量達到最大？第六章 動態(tài)規(guī)劃（2）高負荷生產(chǎn)高負荷生產(chǎn)低負荷生產(chǎn)低負荷生產(chǎn) 運籌學(xué)運籌學(xué)動態(tài)規(guī)劃建模動態(tài)規(guī)劃建模1 劃分階段：年度劃分階段：年度2 狀態(tài)變量：狀態(tài)變量： SK為為K 年度完好的機器數(shù)年度完好的機器數(shù)3 決策變量：決策變量： UK為為K 年度分配高負荷生產(chǎn)的機器數(shù)，年度分配高負荷生產(chǎn)的機器數(shù)， SK UK為為K 年度年度 低負荷生產(chǎn)的機器數(shù)低負荷生產(chǎn)的機器數(shù)4 狀態(tài)轉(zhuǎn)移方程：狀態(tài)轉(zhuǎn)移方程： SK1 0.

33、7 UK + 0. 9 ( SK UK )5 指標(biāo)函數(shù)：指標(biāo)函數(shù)： VK為為K 年度產(chǎn)量年度產(chǎn)量 ， VK8 UK + 5 ( SK UK ) MAXV1 + V2 + V3 + V4 + V5 6 遞推公式：遞推公式： F6 (S6) =0 F6 (S6)表示當(dāng)表示當(dāng)6年度完好的機器數(shù)年度完好的機器數(shù)S6時，從時，從6年到年到5年最大產(chǎn)量年最大產(chǎn)量 FK (SK) = MAX8 UK + 5 ( SK UK ) + FK+1 0.7 UK + 0. 9 ( SK UK ) 第六章 動態(tài)規(guī)劃（2）FK (SK)表示當(dāng)表示當(dāng)K 年度完好的機器數(shù)年度完好的機器數(shù)SK時，從時，從k年到年到5年最大產(chǎn)

34、量年最大產(chǎn)量 運籌學(xué)運籌學(xué)K5F5 (S5) = MAX8 U5 + 5 ( S5 U5 ) + F60.7 U5 + 0. 9 ( S5 U5 ) 因為因為F60.7 U5 + 0. 9 ( S5 U5 ) 0F5 (S5) = MAX8 U5 + 5 ( S5 U5 ) MAX3 U5 + 5 S5 U5 = S5 , 當(dāng)當(dāng)U5 = S5 , F5 (S5) 8 S5K4F4 (S4) = MAX8 U4 + 5 ( S4 U4 ) + F50.7 U4 + 0. 9 ( S4 U4 ) = MAX8 U4 + 5 ( S4 U4 ) + 80.7 U4 + 0. 9 ( S4 U4 )

35、= MAX1. 4 U4 + 12 . 2 S4 U4 = S4 , 當(dāng)當(dāng)U4 = S4 , F4 (S4) 13 . 6 S4 同理，當(dāng)同理，當(dāng)U3 = S3 F3 (S3) 17 . 5 S3當(dāng)當(dāng)U2 =0 , F2 (S2) 20 . 8 S2 當(dāng)當(dāng)U1 = 0 , F1 (S1) 23 .7 S1第六章 動態(tài)規(guī)劃（2） 運籌學(xué)運籌學(xué)最優(yōu)解：前兩年完好機器全部低負最優(yōu)解：前兩年完好機器全部低負荷生產(chǎn)，后三年完好機器全部高負荷生產(chǎn)，后三年完好機器全部高負荷生產(chǎn)，最優(yōu)產(chǎn)量荷生產(chǎn)，最優(yōu)產(chǎn)量23700臺臺第六章 動態(tài)規(guī)劃（2） 運籌學(xué)運籌學(xué)動態(tài)規(guī)劃（動態(tài)規(guī)劃（3 3） 運籌學(xué)運籌學(xué)P226 應(yīng)用

36、舉例應(yīng)用舉例 固定資金分配固定資金分配有有N個企業(yè)，個企業(yè)， 都需要兩種資源，對于第都需要兩種資源，對于第K個企業(yè)，如果用第個企業(yè)，如果用第1種資種資源源 XK ，用第，用第2種資源種資源 YK ,可以得到利潤可以得到利潤 RK (XK , YK) , 第第1種資源種資源 的的單位價格為單位價格為A, 第第2種資源種資源 的單位價格為的單位價格為B, 現(xiàn)有資金現(xiàn)有資金Z, 問應(yīng)該購買問應(yīng)該購買第第1種資源（設(shè)為種資源（設(shè)為X） 和第和第2種資源（設(shè)為種資源（設(shè)為Y） 各多少單位分配到各多少單位分配到N個企業(yè)，可以使總利潤達到最大？個企業(yè)，可以使總利潤達到最大？第六章 動態(tài)規(guī)劃（3）動態(tài)規(guī)劃應(yīng)用

37、之二：資源分配問題資源分配問題 運籌學(xué)運籌學(xué)有有N個企業(yè)，個企業(yè)， 都需要兩種資源，對于第都需要兩種資源，對于第K個企業(yè)，如果用第個企業(yè)，如果用第1種資種資源源 XK ，用第，用第2種資源種資源 YK ,可以得到利潤可以得到利潤 RK (XK , YK) , 第第1種資源種資源 的的單位價格為單位價格為A, 第第2種資源種資源 的單位價格為的單位價格為B, 現(xiàn)有資金現(xiàn)有資金Z, 問應(yīng)該購買問應(yīng)該購買第第1種資源（設(shè)為種資源（設(shè)為X） 和第和第2種資源（設(shè)為種資源（設(shè)為Y） 各多少單位分配到各多少單位分配到N個企業(yè)，可以使總利潤達到最大？個企業(yè)，可以使總利潤達到最大？建立模型：目標(biāo)建立模型：目標(biāo)

38、 MAXR1 (X1 , Y1)+ R2 (X2 , Y2) +RN (XN , YN) 約束約束 X1 + X2 +XN X Y1+ Y2 + +YN Y AX+BY =Z 第六章 動態(tài)規(guī)劃（3）1.階段階段 2.狀態(tài)狀態(tài) 3.決策決策 4.策略策略 5.狀態(tài)轉(zhuǎn)移方程狀態(tài)轉(zhuǎn)移方程 6.指標(biāo)函數(shù)和最優(yōu)值函數(shù)指標(biāo)函數(shù)和最優(yōu)值函數(shù)動態(tài)規(guī)劃求解動態(tài)規(guī)劃求解（略）（略） 運籌學(xué)運籌學(xué)第六章 動態(tài)規(guī)劃（3）公司要對某種產(chǎn)品制定一個生產(chǎn)計劃或者采購計劃，已知初始庫存為零公司要對某種產(chǎn)品制定一個生產(chǎn)計劃或者采購計劃，已知初始庫存為零每階段生產(chǎn)數(shù)量有上限（生產(chǎn)能力限制），每階段需求已知，在每階段生產(chǎn)數(shù)量有上限

39、（生產(chǎn)能力限制），每階段需求已知，在N階段階段末庫存為零，問如何制定生產(chǎn)或者采購計劃，使生產(chǎn)和庫存成本最?。磕齑鏋榱?，問如何制定生產(chǎn)或者采購計劃，使生產(chǎn)和庫存成本最??？企業(yè)企業(yè)階段生產(chǎn)計劃？階段生產(chǎn)計劃？階段采購計劃？階段采購計劃？已知階段需求（定單）已知階段需求（定單）已知內(nèi)部庫存已知內(nèi)部庫存動態(tài)規(guī)劃應(yīng)用之三：生產(chǎn)計劃調(diào)度問題生產(chǎn)計劃調(diào)度問題 運籌學(xué)運籌學(xué)動態(tài)規(guī)劃應(yīng)用舉例動態(tài)規(guī)劃應(yīng)用舉例 ( P229 例例3) 生產(chǎn)計劃（采購計劃）與存貯問題：生產(chǎn)計劃（采購計劃）與存貯問題： Min生產(chǎn)費用生產(chǎn)費用+存貯費用存貯費用 存貯量存貯量=生產(chǎn)量生產(chǎn)量 - 需求量需求量 生產(chǎn)量生產(chǎn)量= 最大生產(chǎn)量

40、最大生產(chǎn)量 決策變量決策變量? 狀態(tài)變量狀態(tài)變量? 狀態(tài)轉(zhuǎn)移方程狀態(tài)轉(zhuǎn)移方程?第六章 動態(tài)規(guī)劃（3）1.階段階段 2.狀態(tài)狀態(tài) 3.決策決策 4.策略策略 5.狀態(tài)轉(zhuǎn)移方程狀態(tài)轉(zhuǎn)移方程 6.指標(biāo)函數(shù)和最優(yōu)值函數(shù)指標(biāo)函數(shù)和最優(yōu)值函數(shù) 運籌學(xué)運籌學(xué)動態(tài)規(guī)劃應(yīng)用舉例動態(tài)規(guī)劃應(yīng)用舉例 ( P229 例例3) 生產(chǎn)計劃（采購計劃）與存貯問題：生產(chǎn)計劃（采購計劃）與存貯問題： Min生產(chǎn)費用生產(chǎn)費用+存貯費用存貯費用 存貯量存貯量=生產(chǎn)量生產(chǎn)量 - 需求量需求量 生產(chǎn)量生產(chǎn)量 MHK (VK) 表示表示K 階段結(jié)束時庫存量為階段結(jié)束時庫存量為VK 時的庫存成本時的庫存成本K 階段總成本階段總成本 CK (

41、XK) HK (VK) 第六章 動態(tài)規(guī)劃（3）1.階段階段 2.狀態(tài)狀態(tài) 3.決策決策 4.策略策略 5.狀態(tài)轉(zhuǎn)移方程狀態(tài)轉(zhuǎn)移方程 6.指標(biāo)函數(shù)和最優(yōu)值函數(shù)指標(biāo)函數(shù)和最優(yōu)值函數(shù) 運籌學(xué)運籌學(xué)動態(tài)規(guī)劃模型為：動態(tài)規(guī)劃模型為：MinG=C1 (X1) H1 (V1) +CN (XN) HN (VN) V0 = VN = 0 VK = X1 - D1+ XK - DK =0 0 =XK 6K=1F1 (V1) = Min C1 (X1) H1 (V1) + F0 (V0) 第六章 動態(tài)規(guī)劃（3） 運籌學(xué)運籌學(xué)動態(tài)規(guī)劃應(yīng)用之四：庫存問題，采購問題庫存問題，采購問題 (P234 例例6)不確定性采購問題

42、（隨機動態(tài)規(guī)劃）：不確定性采購問題（隨機動態(tài)規(guī)劃）：特點特點價格是隨機的，狀態(tài)以一定的概率出現(xiàn)價格是隨機的，狀態(tài)以一定的概率出現(xiàn)購買決策特點購買決策特點市場價格低于最優(yōu)價格時買市場價格低于最優(yōu)價格時買 市場價格高于最優(yōu)價格時不買市場價格高于最優(yōu)價格時不買 最后期限如果還沒購買，無論什么價格都要買最后期限如果還沒購買，無論什么價格都要買第六章 動態(tài)規(guī)劃（3）答案應(yīng)該滿足：開始幾周時間充分，非最低價不買，到中間幾周有點著急答案應(yīng)該滿足：開始幾周時間充分，非最低價不買，到中間幾周有點著急 中等價也買，最后時刻則沒有談判的余地。中等價也買，最后時刻則沒有談判的余地。1.階段階段 2.狀態(tài)狀態(tài) 3.決策

43、決策 4.策略策略 5.狀態(tài)轉(zhuǎn)移方程狀態(tài)轉(zhuǎn)移方程 6.指標(biāo)函數(shù)和最優(yōu)值函數(shù)指標(biāo)函數(shù)和最優(yōu)值函數(shù) 運籌學(xué)運籌學(xué)第六章 動態(tài)規(guī)劃（3） 單單 價價 概概 率率 500 0.3 600 0.3 700 0.4P234 例例6 某工廠在最近五周內(nèi)需要采購一批原料，估計五周內(nèi)有價某工廠在最近五周內(nèi)需要采購一批原料，估計五周內(nèi)有價 格波動如下表，求那一周以什么價格購買最好格波動如下表，求那一周以什么價格購買最好YK為狀態(tài)變量，表示第為狀態(tài)變量，表示第K周實際價格周實際價格XK為決策變量，取為決策變量，取0或者或者1，表示第，表示第K周購買或者不買周購買或者不買1.階段階段 2.狀態(tài)狀態(tài) 3.決策決策 4.

44、策略策略 5.狀態(tài)轉(zhuǎn)移方程狀態(tài)轉(zhuǎn)移方程 6.指標(biāo)函數(shù)和最優(yōu)值函數(shù)指標(biāo)函數(shù)和最優(yōu)值函數(shù) 運籌學(xué)運籌學(xué)第六章 動態(tài)規(guī)劃（3）分析：采購期分析：采購期5周分成周分成5個階段：每周價格看成為狀態(tài)變量個階段：每周價格看成為狀態(tài)變量 YK為狀態(tài)變量，表示第為狀態(tài)變量，表示第K周實際價格周實際價格 XK為決策變量，取為決策變量，取0或者或者1，表示第，表示第K周購買或者不買周購買或者不買 YKE表示第表示第K周實際價格為周實際價格為YK時，而在以后采取最優(yōu)策略時，采購時，而在以后采取最優(yōu)策略時，采購 價格的期望值（最可能的值）價格的期望值（最可能的值） FK(YK) 表示第表示第K周實際價格為周實際價格為Y

45、K時時,從第從第K周到第周到第5周采用最優(yōu)策略周采用最優(yōu)策略 時，價格的最小期望值。時，價格的最小期望值。從最后一周開始計算，對于最后一周如果還沒有購買，按市場價格購買，從最后一周開始計算，對于最后一周如果還沒有購買，按市場價格購買，K=5, F5(500) = 500, F5(600) = 600, F5(700) = 700根據(jù)根據(jù)YKE 和和FK(YK) 的定義，的定義，K=4, 期望價格期望價格Y4E = 0.3 F5(500)+0.3F5(600) +0.4 F5(700) = 610價格為價格為500的概率為的概率為0.3, 價格為價格為600的概率為的概率為0.3, 價格為價格為

46、700的概率為的概率為0.4, 1.階段階段 2.狀態(tài)狀態(tài) 3.決策決策 4.策略策略 5.狀態(tài)轉(zhuǎn)移方程狀態(tài)轉(zhuǎn)移方程 6.指標(biāo)函數(shù)和最優(yōu)值函數(shù)指標(biāo)函數(shù)和最優(yōu)值函數(shù) 運籌學(xué)運籌學(xué) 500 Y4 =500F4(Y4)Min Y4 , Y4E = Min Y4 , 610 = 600 Y4 =600 610 Y4=700 第四周最優(yōu)策略為第四周最優(yōu)策略為X4 = 1 采購采購 如如Y4 =500或者或者Y4 =6000 等待等待 如如Y4 =700同理同理 K=3, 期望價格期望價格Y3E = 0.3 F4(500)+0.3F4(600) +0.4 F4(700) = 0.3 500 + 0. 36

47、00 + 0.4 610574 Y3 =500574 Y3=600或者或者700第三周最優(yōu)策略為第三周最優(yōu)策略為X3 = 1 采購采購 如如Y3 =5000 等待等待 如如Y3 =600或者或者Y3 =700第六章 動態(tài)規(guī)劃（3）F3(Y3)Min Y3 , Y3E = Min Y3 , 574 =F4(Y4)表示第表示第4周實際價格為周實際價格為Y4時時 , 從第從第4周到第周到第5周采用最優(yōu)策略時，價格的最小期望值周采用最優(yōu)策略時，價格的最小期望值實際價格實際價格Y4期望價格期望價格Y4E實際價格實際價格Y3期望價格期望價格Y3E 運籌學(xué)運籌學(xué)F2(Y2)Min Y2 , Y2E = Mi

48、n Y2 , 552 = Y2 =500552 Y2=600或者或者700第二周最優(yōu)策略為第二周最優(yōu)策略為X2 = 1 采購采購 如如Y3 =5000 等待等待 如如Y3 =600或者或者Y3 =700F1(Y1)Min Y1 , Y1E = Min Y1 , 536 = Y2 =500536 Y2=600或者或者700第一周最優(yōu)策略為第一周最優(yōu)策略為X2 = 1 采購采購 如如Y3 =5000 等待等待 如如Y3 =600或者或者Y3 =700第六章 動態(tài)規(guī)劃（3）動態(tài)規(guī)劃解動態(tài)規(guī)劃解：開始一二三周時間充分，非最低價不買，第四周：開始一二三周時間充分，非最低價不買，第四周有點著急有點著急中等

49、價也買，中等價也買，第五第五 周則沒有談周則沒有談 判的余地。判的余地。實際價格實際價格Y2期望價格期望價格Y2E實際價格實際價格Y1期望價格期望價格Y1E答案的確滿足：開始幾周時間充分，非最低價不買，到中間幾周有點著急答案的確滿足：開始幾周時間充分，非最低價不買，到中間幾周有點著急 中等價也買，最后時刻則沒有談判的余地。中等價也買，最后時刻則沒有談判的余地。 運籌學(xué)運籌學(xué)期望價格價期望價格價500概率概率0.3第第1周出現(xiàn)周出現(xiàn)500第第2周出現(xiàn)周出現(xiàn)500第第3周出現(xiàn)周出現(xiàn)500第第4周周出現(xiàn)出現(xiàn)500第第5周出現(xiàn)周出現(xiàn)500 第第2周出現(xiàn)周出現(xiàn)500=（第（第1周出現(xiàn)周出現(xiàn)600或者或者

50、700）并且（第）并且（第2周出現(xiàn)周出現(xiàn)500 ） （ 0.3 + 0.4 ） 0.3 0.7 0.3 第第5周出現(xiàn)周出現(xiàn)500=（第（第1,2,3周出現(xiàn)周出現(xiàn)600或者或者700）并且（第）并且（第4周出現(xiàn)周出現(xiàn)700） 并且（第并且（第5周出現(xiàn)周出現(xiàn)500 ） 0.7 0.7 0.7 0.40.3期望價格期望價格5000.3 1+ 0.7+ 0.7 0.7 + 0.7 0.7 0.7 + 0.7 0.7 0.7 0.4 + 6000.30.7 0.7 0.7+ 0.7 0.7 0.7 0.4 + 700 0.7 0.7 0.7 0.4 0.4 = 525 第六章 動態(tài)規(guī)劃（3）（第（第5周

51、出現(xiàn)周出現(xiàn)700第第1，2，3周出現(xiàn)周出現(xiàn)600和和700 ，第，第4周出現(xiàn)周出現(xiàn) 700，第，第5周出現(xiàn)周出現(xiàn) 700 700 0.7 0.7 0.7 0.4 0.4 ）動態(tài)規(guī)劃解動態(tài)規(guī)劃解-決策效果：期望價格決策效果：期望價格 525 元元 運籌學(xué)運籌學(xué)動態(tài)規(guī)劃（動態(tài)規(guī)劃（4 4） 運籌學(xué)運籌學(xué)第六章 動態(tài)規(guī)劃（4）第第1階段到第階段到第K階段階段=第第1階段到第階段到第K-1階段階段 + 第第K階段階段第第k階段到第階段到第n階段階段=第第k+1階段到第階段到第n階段階段 + 第第K階段階段第第1階段到第階段到第4階段階段=第第1階段到第階段到第3階段階段 + 第第4階段階段第第3階段到

52、第階段到第5階段階段=第第4階段到第階段到第5階段階段 + 第第3階段階段 運籌學(xué)運籌學(xué)動態(tài)規(guī)劃應(yīng)用之五：設(shè)備更新問題設(shè)備更新問題舉例舉例： （P244 例例 10）第六章 動態(tài)規(guī)劃（4）狀態(tài)變量？狀態(tài)變量？決策變量？決策變量？指標(biāo)函數(shù)？指標(biāo)函數(shù)？逆推關(guān)系？逆推關(guān)系？一臺設(shè)備，使用到某年，是買新的，還是繼續(xù)使用？一臺設(shè)備，使用到某年，是買新的，還是繼續(xù)使用？是買新的（更新費用）是買新的（更新費用） ，繼續(xù)使用（維護費用），繼續(xù)使用（維護費用） 運籌學(xué)運籌學(xué)動態(tài)規(guī)劃應(yīng)用之五：設(shè)備更新問題設(shè)備更新問題舉例舉例： （P244 例例 10）狀態(tài)變量狀態(tài)變量機齡機齡 t決策變量決策變量設(shè)備更新，保留設(shè)備

53、設(shè)備更新，保留設(shè)備第第i階段階段 收入收入 Ii(t)第第i階段階段 運行費用運行費用 Oi(t) 第第i階段到第階段到第n階段收益階段收益Gi (t) 第第i階段到第階段到第n階段階段 =第第i階段階段+ 第第i+1階段到第階段到第n階段階段指標(biāo)函數(shù)指標(biāo)函數(shù)收益收益 = 收入收入-運行費用運行費用-更新費用更新費用 Ii(t) - Oi(t) - Ci(t)逆推關(guān)系：逆推關(guān)系：第六章 動態(tài)規(guī)劃（4） 運籌學(xué)運籌學(xué)動態(tài)規(guī)劃應(yīng)用舉例動態(tài)規(guī)劃應(yīng)用舉例設(shè)備更新問題設(shè)備更新問題： （P244 例例 10）逆推關(guān)系：逆推關(guān)系：第六章 動態(tài)規(guī)劃（4）Gi(t)=Max更新收益收益: Ii(0)- Oi(0

54、)- Ci(t)+aGi+1(1)保留收益保留收益: Ii(t)- Oi(t) +a Gi+1(t+1)a表示折現(xiàn)因子表示折現(xiàn)因子機齡為機齡為t保留機器后，下一階段機齡為保留機器后，下一階段機齡為t1更換機器后，下一階段機齡為更換機器后，下一階段機齡為1年年 運籌學(xué)運籌學(xué)第六章 動態(tài)規(guī)劃（4）機器第一年購買機器第一年購買機器第二年購買機器第二年購買第三年購買第三年購買四年購四年購買買五五年年買買幾年前購買機器幾年前購買機器t=01234012301201012345收收入入I2221201816272524222926243028321816161414運運行行費費66881056895564

55、54889910更更新新費費2729323437293134363132333233343234363638O5(3)=9 :表示第表示第5年開始機齡為年開始機齡為3年的機器，購買年年的機器，購買年5 3 =2 年年 , 運行費用運行費用 9 運行費用運行費用 Oj(t) 表示第表示第j年開始機齡為年開始機齡為t年的機器，購買年年的機器，購買年j t 運籌學(xué)運籌學(xué)第六章 動態(tài)規(guī)劃（4） i= 機器第一年購買機器第一年購買 幾年前購買的機器幾年前購買的機器機齡機齡t=0123412345收入收入Ii(t)22I1(0)21I2(1)20I3(2)18I4(3)16I5(4)18I1(1)16I1

56、(2)16I1(3)14I1(4)14I1(5)運行運行費費Oi (t)6O1(0)6O2(1)8O3(2)8O4(3)10O5(4)8O1(1)8O1(2)9O1(3)9O1(4)10O1(5)更新更新費費Ci (t)27C1(0)29C2(1)32C3(2)34C4(3)37C5(4)32C1(1)34C1(2)36C1(3)36C1(4)38C1(5)說明符號對應(yīng)：說明符號對應(yīng)：I5(4)16 ： 機器已經(jīng)使用了機器已經(jīng)使用了4年，購買年為年，購買年為541年，在第年，在第5年的年的 收入為收入為16萬元萬元O1(5)10 ：機器已經(jīng)使用了：機器已經(jīng)使用了5年，購買年為年，購買年為514

57、年前，第年前，第1年使用機器運行費為年使用機器運行費為10萬元萬元 運籌學(xué)運籌學(xué)第六章 動態(tài)規(guī)劃（4） j=5, 從第從第5年開始計算時，機器使用了年開始計算時，機器使用了t= 1，2，3，4，5年年 G5（t）表示從第表示從第5年開始計算時，機器使用了年開始計算時，機器使用了t年最佳總收入：年最佳總收入：G5（t）=Max更新更新收益收益：I5（0）- O5（0）- C5（0）+ G6（1）保持保持收益收益： I5（t）- O5（t）+ G6（t+1）G5（1）=Max更新：更新：I5（0）- O5（0）- C5（0）+ G6（1） =32 4 - 33 + 0 = -5保持：保持： I5（

58、1）- O5（1）+ G6（1+1） = 28-5+0=23I5（1）=第第5年開始，年開始，5-1=4年購買，機齡年購買，機齡1年年= 23X5（1）= 保持保持 運籌學(xué)運籌學(xué)第六章 動態(tài)規(guī)劃（4）同理，同理， G5（3）=13 ， X5（3）= 保持保持 G5（4）=6 ， X5（4）= 保持保持 G5（5）=4 ， X5（5）= 保持：第保持：第5年使用機齡年使用機齡5年，最好不更新，年，最好不更新， 因為更新的當(dāng)年利潤為負，反正因為更新的當(dāng)年利潤為負，反正 最后一年了。最后一年了。G5（2）=Max更新：更新：I5（0）- O5（0）- C5（0）+ G6（1） =32 4 - 33 + 0 = -5保持：保持： I5（2）- O5（2）+ G6（2+1） = 24-6+0=18I5（2）=第第5年開始，年開始，5-2=3年購買，機齡年購買，機齡2年年=18X5（2）