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

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

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

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

4、608070110國(guó)外機(jī)器制造廠國(guó)外機(jī)器制造廠 出口港出口港 進(jìn)口港進(jìn)口港 國(guó)內(nèi)城市國(guó)內(nèi)城市 國(guó)內(nèi)某工廠國(guó)內(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ù)第六章 動(dòng)態(tài)規(guī)劃（1）110 運(yùn)籌學(xué)運(yùn)籌學(xué)動(dòng)態(tài)規(guī)劃的基本概念：動(dòng)態(tài)規(guī)劃的基本概念：1. 階段：把問(wèn)題分為互相聯(lián)系有一定次序的階段階段：把問(wèn)題分為互相聯(lián)系有一定次序的階段(上例，四個(gè)階段上例，四個(gè)階段)狀態(tài)：每個(gè)階段開(kāi)始所處自然狀況或客觀條件，不可控制（第狀態(tài)：每個(gè)階段開(kāi)始所處自然狀況或客觀條件，不可控制（第1階階段狀態(tài)：段狀態(tài)：A，第，第2階段狀態(tài)：階段

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

6、動(dòng)態(tài)規(guī)劃最優(yōu)性原理與最優(yōu)性定理：動(dòng)態(tài)規(guī)劃與靜態(tài)規(guī)劃的關(guān)系：動(dòng)態(tài)規(guī)劃非線性規(guī)劃運(yùn)輸問(wèn)題規(guī)劃整數(shù)規(guī)劃線性規(guī)劃靜態(tài)規(guī)劃數(shù)字規(guī)劃10第六章 動(dòng)態(tài)規(guī)劃（1） 運(yùn)籌學(xué)運(yùn)籌學(xué)1.資源分配問(wèn)題資源分配問(wèn)題引例：某種原料總數(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)移方程：第六章 動(dòng)態(tài)規(guī)劃（1） 運(yùn)籌學(xué)

7、運(yùn)籌學(xué)動(dòng)態(tài)規(guī)劃順序解法：動(dòng)態(tài)規(guī)劃順序解法：第一步：劃分階段第一步：劃分階段第二步：選擇狀態(tài)變量第二步：選擇狀態(tài)變量第三步：確定決策變量第三步：確定決策變量第四步：寫(xiě)狀態(tài)轉(zhuǎn)移方程第四步：寫(xiě)狀態(tài)轉(zhuǎn)移方程第五步：第五步： 指標(biāo)函數(shù)指標(biāo)函數(shù)第六章 動(dòng)態(tài)規(guī)劃（1） 運(yùn)籌學(xué)運(yùn)籌學(xué)第六章 動(dòng)態(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 求最大利潤(rùn)求最大利潤(rùn)maxZ=4x1

8、+9x2+2x32 三階段投資總額共有三階段投資總額共有10單位單位 非線性規(guī)劃問(wèn)題求解非線性規(guī)劃問(wèn)題求解 第一階段投資總額第一階段投資總額S1（狀態(tài)變量）（狀態(tài)變量） 第一二階段投資總額第一二階段投資總額S2 （狀態(tài)變量）（狀態(tài)變量） 第一二三階段投資總額第一二三階段投資總額S3 （狀態(tài)變量）（狀態(tài)變量）x1x2x3S3S2S1S1 = X1 S2 = X1 +X2 S3 = X1+X2+X3動(dòng)態(tài)規(guī)劃應(yīng)用之二：資源分配問(wèn)題資源分配問(wèn)題-P207 -P207 例例3 3 運(yùn)籌學(xué)運(yùn)籌學(xué)第六章 動(dòng)態(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時(shí)時(shí) 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. 運(yùn)籌學(xué)運(yùn)籌學(xué)第六章 動(dòng)態(tài)規(guī)劃（1）X3H3(S3,X3)109/4在在X3=9/4, F3(S3)有最小值有最小值, F3(S3) 最大值最大值 X3 10 運(yùn)

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

12、序算法逆序算法解下列問(wèn)題（解下列問(wèn)題（二維背包問(wèn)題二維背包問(wèn)題）：）：Max Z= 8 X1 +7X2 （最大效益，重量限制，體積限制）（最大效益，重量限制，體積限制） S.T. 2X1 + X2 8 (重量重量) 5X1 +2X2 15 (體積體積)X1 , X2 為非負(fù)整數(shù)為非負(fù)整數(shù)解：解：用逆序算法用逆序算法。設(shè)：。設(shè)： 階段：分成兩個(gè)階段，分別對(duì)應(yīng)第階段：分成兩個(gè)階段，分別對(duì)應(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 對(duì)應(yīng)第對(duì)應(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 (體積體積) 運(yùn)籌學(xué)運(yùn)籌學(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 第六章 動(dòng)態(tài)規(guī)劃（1） 運(yùn)籌學(xué)運(yùn)籌學(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第六章 動(dòng)態(tài)規(guī)劃（1） 運(yùn)籌學(xué)運(yùn)籌學(xué)第六章 動(dòng)態(tài)規(guī)劃（1）基本定理：基本定理： 如果如果A到到F的最短路程是的最短路程是ABCDEF，那么那么C到到F的最短路程一定是的最短路程一定是 CDEF (Bellman最優(yōu)化原理）最優(yōu)化原理）總結(jié)總結(jié)動(dòng)態(tài)規(guī)劃的基本概念：動(dòng)態(tài)規(guī)劃的基本概念：1。階段：把問(wèn)題分為互相聯(lián)系有一定次序的階段。階段：把問(wèn)題分為互相聯(lián)系有一定次序的階段2。狀態(tài)：每個(gè)階段開(kāi)始所

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

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

18、既可以順序編號(hào)也可以逆序編號(hào)，常用順序編號(hào)。既可以順序編號(hào)也可以逆序編號(hào)，常用順序編號(hào)。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ù) 運(yùn)籌學(xué)運(yùn)籌學(xué)第六章 動(dòng)態(tài)規(guī)劃（3）知識(shí)要點(diǎn)知識(shí)要點(diǎn)(3)狀態(tài)是某階段決策的出發(fā)點(diǎn)，又是前個(gè)階段決策的結(jié)果，因此它是階段狀態(tài)是某階段決策的出發(fā)點(diǎn)，又是前個(gè)階段決策的結(jié)果，因此它是階段信息的傳遞點(diǎn)與結(jié)合點(diǎn)。第信息的傳遞點(diǎn)與結(jié)合點(diǎn)。第k階段的狀態(tài)常用狀態(tài)變量階段的狀態(tài)常用狀態(tài)變量xk表示，表示，xk應(yīng)包含第應(yīng)包含第k個(gè)階段之前決策過(guò)程的全部信息，使該階段后作出的決策同以前的狀態(tài)和個(gè)階

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

20、策集合記為時(shí)的允許決策集合記為Dk(xk)，它相當(dāng)于線性規(guī)劃中的約束條件。決策變量的取值可以是離散的，也可以它相當(dāng)于線性規(guī)劃中的約束條件。決策變量的取值可以是離散的，也可以是連續(xù)的。是連續(xù)的。（5）n個(gè)階段的決策問(wèn)題可看成是從第個(gè)階段的決策問(wèn)題可看成是從第1個(gè)階段直到第個(gè)階段直到第n個(gè)階段決策的全過(guò)個(gè)階段決策的全過(guò)程，而從第程，而從第k個(gè)階段直到第個(gè)階段直到第n個(gè)階段可看作是子過(guò)程。動(dòng)態(tài)規(guī)劃問(wèn)題各階段個(gè)階段可看作是子過(guò)程。動(dòng)態(tài)規(guī)劃問(wèn)題各階段決策組成的序列稱為一個(gè)策略。決策組成的序列稱為一個(gè)策略。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ù) 運(yùn)籌學(xué)運(yùn)籌學(xué)第六章 動(dòng)態(tài)規(guī)劃（3）知識(shí)要點(diǎn)知識(shí)要點(diǎn)(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個(gè)階段的狀態(tài)變量個(gè)階段的狀態(tài)變量xk+1是第是第k個(gè)階段狀態(tài)變量個(gè)階段狀態(tài)變量xk和決策變量和決策變量uk(xk)的函數(shù)的函數(shù).（7）指標(biāo)函數(shù)可分為階段的指標(biāo)函數(shù)與過(guò)程的指標(biāo)函數(shù)兩種。階）指標(biāo)函數(shù)可分為階段的指標(biāo)函數(shù)與過(guò)程的指標(biāo)函數(shù)兩種。階段的指標(biāo)函數(shù)是指第段的指標(biāo)函數(shù)是指第k個(gè)階段從狀態(tài)個(gè)階段從狀態(tài)xk出發(fā)采取決策出發(fā)采取決策uk時(shí)

22、的效益，時(shí)的效益，用用uk（xk，uk）表示。而過(guò)程的指標(biāo)函數(shù)是指從第）表示。而過(guò)程的指標(biāo)函數(shù)是指從第k個(gè)階段的某個(gè)個(gè)階段的某個(gè)狀態(tài)狀態(tài)xk出發(fā)，采取子策略出發(fā)，采取子策略u(píng)k ，uk+1,un時(shí)所得到的效益，它既與時(shí)所得到的效益，它既與xk有關(guān)，又與以后的子策略有關(guān)，是兩者的函數(shù)有關(guān)，又與以后的子策略有關(guān)，是兩者的函數(shù).（8）最優(yōu)指標(biāo)函數(shù)是指從第）最優(yōu)指標(biāo)函數(shù)是指從第k個(gè)階段的狀態(tài)個(gè)階段的狀態(tài)xk出發(fā)采取最優(yōu)子策出發(fā)采取最優(yōu)子策略后得到的過(guò)程指標(biāo)函數(shù)值，即對(duì)應(yīng)最優(yōu)子策略的效益值略后得到的過(guò)程指標(biāo)函數(shù)值，即對(duì)應(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ù) 運(yùn)籌學(xué)運(yùn)籌學(xué)動(dòng)態(tài)規(guī)劃在經(jīng)濟(jì)管理中應(yīng)用：動(dòng)態(tài)規(guī)劃應(yīng)用之一：最優(yōu)路徑問(wèn)題（已講）最優(yōu)路徑問(wèn)題（已講）動(dòng)態(tài)規(guī)劃應(yīng)用之二：資源分配問(wèn)題（已講）資源分配問(wèn)題（已講）動(dòng)態(tài)規(guī)劃應(yīng)用之三：生產(chǎn)計(jì)劃調(diào)度問(wèn)題（？）生產(chǎn)計(jì)劃調(diào)度問(wèn)題（？）動(dòng)態(tài)規(guī)劃應(yīng)用之四：庫(kù)存問(wèn)題，采購(gòu)問(wèn)題（？）庫(kù)存問(wèn)題，采購(gòu)問(wèn)題（？）動(dòng)態(tài)規(guī)劃應(yīng)用之五：設(shè)備更新問(wèn)題（？）設(shè)備更新問(wèn)題（？）動(dòng)態(tài)規(guī)劃應(yīng)用之六： 生產(chǎn)過(guò)程最優(yōu)控制問(wèn)題（？）生產(chǎn)過(guò)程最優(yōu)控制問(wèn)題（？）動(dòng)態(tài)規(guī)劃應(yīng)用之七： . 運(yùn)籌學(xué)運(yùn)籌學(xué)動(dòng)態(tài)規(guī)劃（動(dòng)態(tài)規(guī)劃（2 2） 運(yùn)籌學(xué)運(yùn)籌學(xué)第六章 動(dòng)態(tài)規(guī)劃（2）P216 例例1 一維資

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

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

26、配到注意：分配到3廠的設(shè)備總臺(tái)數(shù)廠的設(shè)備總臺(tái)數(shù) S3 = 分配到分配到3廠的設(shè)備臺(tái)數(shù)廠的設(shè)備臺(tái)數(shù) X3第六章 動(dòng)態(tài)規(guī)劃（2） 運(yùn)籌學(xué)運(yùn)籌學(xué)第六章 動(dòng)態(tài)規(guī)劃（2）分配到分配到2廠的設(shè)備廠的設(shè)備臺(tái)數(shù)臺(tái)數(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è)備總臺(tái)數(shù)總臺(tái)數(shù)

27、S2 = X2 X3由已知表：第由已知表：第2廠分配廠分配3臺(tái)設(shè)備得效益臺(tái)設(shè)備得效益11由上表：第由上表：第3廠分配廠分配2 臺(tái)設(shè)備得效益臺(tái)設(shè)備得效益6 運(yùn)籌學(xué)運(yùn)籌學(xué)第六章 動(dòng)態(tài)規(guī)劃（2）分配到分配到1廠的設(shè)備廠的設(shè)備臺(tái)數(shù)臺(tái)數(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è)備總臺(tái)數(shù)的設(shè)備總臺(tái)數(shù) S1 = 5由已知表：第由已知表：第1廠分配廠分配4臺(tái)設(shè)備得效益臺(tái)設(shè)備得效益12，由上表：第由上表：

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

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

30、何化歸為多階段的決策問(wèn)題。2 準(zhǔn)確、熟練地掌握動(dòng)態(tài)規(guī)劃的基本概念，特別是狀態(tài)變量、準(zhǔn)確、熟練地掌握動(dòng)態(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.會(huì)判定動(dòng)態(tài)規(guī)劃問(wèn)題的類型。會(huì)判定動(dòng)態(tài)規(guī)劃問(wèn)題的類型。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ù) 運(yùn)籌學(xué)運(yùn)籌學(xué)第六章 動(dòng)態(tài)規(guī)劃（2）出租汽車(chē)高負(fù)荷運(yùn)行

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

32、好率年完好率 B = 0. 9, 如果初始投入生產(chǎn)的機(jī)器如果初始投入生產(chǎn)的機(jī)器1000臺(tái)，臺(tái)，問(wèn)如何安排生產(chǎn)，使在問(wèn)如何安排生產(chǎn)，使在5年內(nèi)生產(chǎn)的產(chǎn)品總量達(dá)到最大？年內(nèi)生產(chǎn)的產(chǎn)品總量達(dá)到最大？第六章 動(dòng)態(tài)規(guī)劃（2）高負(fù)荷生產(chǎn)高負(fù)荷生產(chǎn)低負(fù)荷生產(chǎn)低負(fù)荷生產(chǎn) 運(yùn)籌學(xué)運(yùn)籌學(xué)動(dòng)態(tài)規(guī)劃建模動(dòng)態(tài)規(guī)劃建模1 劃分階段：年度劃分階段：年度2 狀態(tài)變量：狀態(tài)變量： SK為為K 年度完好的機(jī)器數(shù)年度完好的機(jī)器數(shù)3 決策變量：決策變量： UK為為K 年度分配高負(fù)荷生產(chǎn)的機(jī)器數(shù)，年度分配高負(fù)荷生產(chǎn)的機(jī)器數(shù)， SK UK為為K 年度年度 低負(fù)荷生產(chǎn)的機(jī)器數(shù)低負(fù)荷生產(chǎn)的機(jī)器數(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年度完好的機(jī)器數(shù)年度完好的機(jī)器數(shù)S6時(shí)，從時(shí)，從6年到年到5年最大產(chǎn)量年最大產(chǎn)量 FK (SK) = MAX8 UK + 5 ( SK UK ) + FK+1 0.7 UK + 0. 9 ( SK UK ) 第六章 動(dòng)態(tài)規(guī)劃（2）FK (SK)表示當(dāng)表示當(dāng)K 年度完好的機(jī)器數(shù)年度完好的機(jī)器數(shù)SK時(shí)，從時(shí)，從k年到年到5年最大產(chǎn)

34、量年最大產(chǎn)量 運(yùn)籌學(xué)運(yùn)籌學(xué)K5F5 (S5) = MAX8 U5 + 5 ( S5 U5 ) + F60.7 U5 + 0. 9 ( S5 U5 ) 因?yàn)橐驗(yàn)镕60.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第六章 動(dòng)態(tài)規(guī)劃（2） 運(yùn)籌學(xué)運(yùn)籌學(xué)最優(yōu)解：前兩年完好機(jī)器全部低負(fù)最優(yōu)解：前兩年完好機(jī)器全部低負(fù)荷生產(chǎn)，后三年完好機(jī)器全部高負(fù)荷生產(chǎn)，后三年完好機(jī)器全部高負(fù)荷生產(chǎn)，最優(yōu)產(chǎn)量荷生產(chǎn)，最優(yōu)產(chǎn)量23700臺(tái)臺(tái)第六章 動(dòng)態(tài)規(guī)劃（2） 運(yùn)籌學(xué)運(yùn)籌學(xué)動(dòng)態(tài)規(guī)劃（動(dòng)態(tài)規(guī)劃（3 3） 運(yùn)籌學(xué)運(yùn)籌學(xué)P226 應(yīng)用

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

37、之二：資源分配問(wèn)題資源分配問(wèn)題 運(yùn)籌學(xué)運(yùn)籌學(xué)有有N個(gè)企業(yè)，個(gè)企業(yè)， 都需要兩種資源，對(duì)于第都需要兩種資源，對(duì)于第K個(gè)企業(yè)，如果用第個(gè)企業(yè)，如果用第1種資種資源源 XK ，用第，用第2種資源種資源 YK ,可以得到利潤(rùn)可以得到利潤(rùn) RK (XK , YK) , 第第1種資源種資源 的的單位價(jià)格為單位價(jià)格為A, 第第2種資源種資源 的單位價(jià)格為的單位價(jià)格為B, 現(xiàn)有資金現(xiàn)有資金Z, 問(wèn)應(yīng)該購(gòu)買(mǎi)問(wèn)應(yīng)該購(gòu)買(mǎi)第第1種資源（設(shè)為種資源（設(shè)為X） 和第和第2種資源（設(shè)為種資源（設(shè)為Y） 各多少單位分配到各多少單位分配到N個(gè)企業(yè)，可以使總利潤(rùn)達(dá)到最大？個(gè)企業(yè)，可以使總利潤(rùn)達(dá)到最大？建立模型：目標(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 第六章 動(dòng)態(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ù)動(dòng)態(tài)規(guī)劃求解動(dòng)態(tài)規(guī)劃求解（略）（略） 運(yùn)籌學(xué)運(yùn)籌學(xué)第六章 動(dòng)態(tài)規(guī)劃（3）公司要對(duì)某種產(chǎn)品制定一個(gè)生產(chǎn)計(jì)劃或者采購(gòu)計(jì)劃，已知初始庫(kù)存為零公司要對(duì)某種產(chǎn)品制定一個(gè)生產(chǎn)計(jì)劃或者采購(gòu)計(jì)劃，已知初始庫(kù)存為零每階段生產(chǎn)數(shù)量有上限（生產(chǎn)能力限制），每階段需求已知，在每階段生產(chǎn)數(shù)量有上限

39、（生產(chǎn)能力限制），每階段需求已知，在N階段階段末庫(kù)存為零，問(wèn)如何制定生產(chǎn)或者采購(gòu)計(jì)劃，使生產(chǎn)和庫(kù)存成本最??？末庫(kù)存為零，問(wèn)如何制定生產(chǎn)或者采購(gòu)計(jì)劃，使生產(chǎn)和庫(kù)存成本最??？企業(yè)企業(yè)階段生產(chǎn)計(jì)劃？階段生產(chǎn)計(jì)劃？階段采購(gòu)計(jì)劃？階段采購(gòu)計(jì)劃？已知階段需求（定單）已知階段需求（定單）已知內(nèi)部庫(kù)存已知內(nèi)部庫(kù)存動(dòng)態(tài)規(guī)劃應(yīng)用之三：生產(chǎn)計(jì)劃調(diào)度問(wèn)題生產(chǎn)計(jì)劃調(diào)度問(wèn)題 運(yùn)籌學(xué)運(yùn)籌學(xué)動(dòng)態(tài)規(guī)劃應(yīng)用舉例動(dòng)態(tài)規(guī)劃應(yīng)用舉例 ( P229 例例3) 生產(chǎn)計(jì)劃（采購(gòu)計(jì)劃）與存貯問(wèn)題：生產(chǎn)計(jì)劃（采購(gòu)計(jì)劃）與存貯問(wèn)題： Min生產(chǎn)費(fèi)用生產(chǎn)費(fèi)用+存貯費(fèi)用存貯費(fèi)用 存貯量存貯量=生產(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)移方程?第六章 動(dòng)態(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ù) 運(yùn)籌學(xué)運(yùn)籌學(xué)動(dòng)態(tài)規(guī)劃應(yīng)用舉例動(dòng)態(tài)規(guī)劃應(yīng)用舉例 ( P229 例例3) 生產(chǎn)計(jì)劃（采購(gòu)計(jì)劃）與存貯問(wèn)題：生產(chǎn)計(jì)劃（采購(gòu)計(jì)劃）與存貯問(wèn)題： Min生產(chǎn)費(fèi)用生產(chǎn)費(fèi)用+存貯費(fèi)用存貯費(fèi)用 存貯量存貯量=生產(chǎn)量生產(chǎn)量 - 需求量需求量 生產(chǎn)量生產(chǎn)量 MHK (VK) 表示表示K 階段結(jié)束時(shí)庫(kù)存量為階段結(jié)束時(shí)庫(kù)存量為VK 時(shí)的庫(kù)存成本時(shí)的庫(kù)存成本K 階段總成本階段總成本 CK (

41、XK) HK (VK) 第六章 動(dòng)態(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ù) 運(yùn)籌學(xué)運(yùn)籌學(xué)動(dòng)態(tài)規(guī)劃模型為：動(dòng)態(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) 第六章 動(dòng)態(tài)規(guī)劃（3） 運(yùn)籌學(xué)運(yùn)籌學(xué)動(dòng)態(tài)規(guī)劃應(yīng)用之四：庫(kù)存問(wèn)題，采購(gòu)問(wèn)題庫(kù)存問(wèn)題，采購(gòu)問(wèn)題 (P234 例例6)不確定性采購(gòu)問(wèn)題

42、（隨機(jī)動(dòng)態(tài)規(guī)劃）：不確定性采購(gòu)問(wèn)題（隨機(jī)動(dòng)態(tài)規(guī)劃）：特點(diǎn)特點(diǎn)價(jià)格是隨機(jī)的，狀態(tài)以一定的概率出現(xiàn)價(jià)格是隨機(jī)的，狀態(tài)以一定的概率出現(xiàn)購(gòu)買(mǎi)決策特點(diǎn)購(gòu)買(mǎi)決策特點(diǎn)市場(chǎng)價(jià)格低于最優(yōu)價(jià)格時(shí)買(mǎi)市場(chǎng)價(jià)格低于最優(yōu)價(jià)格時(shí)買(mǎi) 市場(chǎng)價(jià)格高于最優(yōu)價(jià)格時(shí)不買(mǎi)市場(chǎng)價(jià)格高于最優(yōu)價(jià)格時(shí)不買(mǎi) 最后期限如果還沒(méi)購(gòu)買(mǎi)，無(wú)論什么價(jià)格都要買(mǎi)最后期限如果還沒(méi)購(gòu)買(mǎi)，無(wú)論什么價(jià)格都要買(mǎi)第六章 動(dòng)態(tài)規(guī)劃（3）答案應(yīng)該滿足：開(kāi)始幾周時(shí)間充分，非最低價(jià)不買(mǎi)，到中間幾周有點(diǎn)著急答案應(yīng)該滿足：開(kāi)始幾周時(shí)間充分，非最低價(jià)不買(mǎi)，到中間幾周有點(diǎn)著急 中等價(jià)也買(mǎi)，最后時(shí)刻則沒(méi)有談判的余地。中等價(jià)也買(mǎi)，最后時(shí)刻則沒(méi)有談判的余地。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ù) 運(yùn)籌學(xué)運(yùn)籌學(xué)第六章 動(dòng)態(tài)規(guī)劃（3） 單單 價(jià)價(jià) 概概 率率 500 0.3 600 0.3 700 0.4P234 例例6 某工廠在最近五周內(nèi)需要采購(gòu)一批原料，估計(jì)五周內(nèi)有價(jià)某工廠在最近五周內(nèi)需要采購(gòu)一批原料，估計(jì)五周內(nèi)有價(jià) 格波動(dòng)如下表，求那一周以什么價(jià)格購(gòu)買(mǎi)最好格波動(dòng)如下表，求那一周以什么價(jià)格購(gòu)買(mǎi)最好YK為狀態(tài)變量，表示第為狀態(tài)變量，表示第K周實(shí)際價(jià)格周實(shí)際價(jià)格XK為決策變量，取為決策變量，取0或者或者1，表示第，表示第K周購(gòu)買(mǎi)或者不買(mǎi)周購(gòu)買(mǎi)或者不買(mǎi)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ù) 運(yùn)籌學(xué)運(yùn)籌學(xué)第六章 動(dòng)態(tài)規(guī)劃（3）分析：采購(gòu)期分析：采購(gòu)期5周分成周分成5個(gè)階段：每周價(jià)格看成為狀態(tài)變量個(gè)階段：每周價(jià)格看成為狀態(tài)變量 YK為狀態(tài)變量，表示第為狀態(tài)變量，表示第K周實(shí)際價(jià)格周實(shí)際價(jià)格 XK為決策變量，取為決策變量，取0或者或者1，表示第，表示第K周購(gòu)買(mǎi)或者不買(mǎi)周購(gòu)買(mǎi)或者不買(mǎi) YKE表示第表示第K周實(shí)際價(jià)格為周實(shí)際價(jià)格為YK時(shí)，而在以后采取最優(yōu)策略時(shí)，采購(gòu)時(shí)，而在以后采取最優(yōu)策略時(shí)，采購(gòu) 價(jià)格的期望值（最可能的值）價(jià)格的期望值（最可能的值） FK(YK) 表示第表示第K周實(shí)際價(jià)格為周實(shí)際價(jià)格為Y

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

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ù) 運(yùn)籌學(xué)運(yùn)籌學(xué) 500 Y4 =500F4(Y4)Min Y4 , Y4E = Min Y4 , 610 = 600 Y4 =600 610 Y4=700 第四周最優(yōu)策略為第四周最優(yōu)策略為X4 = 1 采購(gòu)采購(gòu) 如如Y4 =500或者或者Y4 =6000 等待等待 如如Y4 =700同理同理 K=3, 期望價(jià)格期望價(jià)格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 采購(gòu)采購(gòu) 如如Y3 =5000 等待等待 如如Y3 =600或者或者Y3 =700第六章 動(dòng)態(tài)規(guī)劃（3）F3(Y3)Min Y3 , Y3E = Min Y3 , 574 =F4(Y4)表示第表示第4周實(shí)際價(jià)格為周實(shí)際價(jià)格為Y4時(shí)時(shí) , 從第從第4周到第周到第5周采用最優(yōu)策略時(shí)，價(jià)格的最小期望值周采用最優(yōu)策略時(shí)，價(jià)格的最小期望值實(shí)際價(jià)格實(shí)際價(jià)格Y4期望價(jià)格期望價(jià)格Y4E實(shí)際價(jià)格實(shí)際價(jià)格Y3期望價(jià)格期望價(jià)格Y3E 運(yùn)籌學(xué)運(yùn)籌學(xué)F2(Y2)Min Y2 , Y2E = Mi

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

49、價(jià)也買(mǎi)，中等價(jià)也買(mǎi)，第五第五 周則沒(méi)有談周則沒(méi)有談 判的余地。判的余地。實(shí)際價(jià)格實(shí)際價(jià)格Y2期望價(jià)格期望價(jià)格Y2E實(shí)際價(jià)格實(shí)際價(jià)格Y1期望價(jià)格期望價(jià)格Y1E答案的確滿足：開(kāi)始幾周時(shí)間充分，非最低價(jià)不買(mǎi)，到中間幾周有點(diǎn)著急答案的確滿足：開(kāi)始幾周時(shí)間充分，非最低價(jià)不買(mǎi)，到中間幾周有點(diǎn)著急 中等價(jià)也買(mǎi)，最后時(shí)刻則沒(méi)有談判的余地。中等價(jià)也買(mǎi)，最后時(shí)刻則沒(méi)有談判的余地。 運(yùn)籌學(xué)運(yùn)籌學(xué)期望價(jià)格價(jià)期望價(jià)格價(jià)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期望價(jià)格期望價(jià)格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 第六章 動(dòng)態(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 ）動(dòng)態(tài)規(guī)劃解動(dòng)態(tài)規(guī)劃解-決策效果：期望價(jià)格決策效果：期望價(jià)格 525 元元 運(yùn)籌學(xué)運(yùn)籌學(xué)動(dòng)態(tài)規(guī)劃（動(dòng)態(tài)規(guī)劃（4 4） 運(yùn)籌學(xué)運(yùn)籌學(xué)第六章 動(dòng)態(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階段階段 運(yùn)籌學(xué)運(yùn)籌學(xué)動(dòng)態(tài)規(guī)劃應(yīng)用之五：設(shè)備更新問(wèn)題設(shè)備更新問(wèn)題舉例舉例： （P244 例例 10）第六章 動(dòng)態(tài)規(guī)劃（4）狀態(tài)變量？狀態(tài)變量？決策變量？決策變量？指標(biāo)函數(shù)？指標(biāo)函數(shù)？逆推關(guān)系？逆推關(guān)系？一臺(tái)設(shè)備，使用到某年，是買(mǎi)新的，還是繼續(xù)使用？一臺(tái)設(shè)備，使用到某年，是買(mǎi)新的，還是繼續(xù)使用？是買(mǎi)新的（更新費(fèi)用）是買(mǎi)新的（更新費(fèi)用） ，繼續(xù)使用（維護(hù)費(fèi)用），繼續(xù)使用（維護(hù)費(fèi)用） 運(yùn)籌學(xué)運(yùn)籌學(xué)動(dòng)態(tài)規(guī)劃應(yīng)用之五：設(shè)備更新問(wèn)題設(shè)備更新問(wèn)題舉例舉例： （P244 例例 10）狀態(tài)變量狀態(tài)變量機(jī)齡機(jī)齡 t決策變量決策變量設(shè)備更新，保留設(shè)備

53、設(shè)備更新，保留設(shè)備第第i階段階段 收入收入 Ii(t)第第i階段階段 運(yùn)行費(fèi)用運(yùn)行費(fèi)用 Oi(t) 第第i階段到第階段到第n階段收益階段收益Gi (t) 第第i階段到第階段到第n階段階段 =第第i階段階段+ 第第i+1階段到第階段到第n階段階段指標(biāo)函數(shù)指標(biāo)函數(shù)收益收益 = 收入收入-運(yùn)行費(fèi)用運(yùn)行費(fèi)用-更新費(fèi)用更新費(fèi)用 Ii(t) - Oi(t) - Ci(t)逆推關(guān)系：逆推關(guān)系：第六章 動(dòng)態(tài)規(guī)劃（4） 運(yùn)籌學(xué)運(yùn)籌學(xué)動(dòng)態(tài)規(guī)劃應(yīng)用舉例動(dòng)態(tài)規(guī)劃應(yīng)用舉例設(shè)備更新問(wèn)題設(shè)備更新問(wèn)題： （P244 例例 10）逆推關(guān)系：逆推關(guān)系：第六章 動(dòng)態(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)因子機(jī)齡為機(jī)齡為t保留機(jī)器后，下一階段機(jī)齡為保留機(jī)器后，下一階段機(jī)齡為t1更換機(jī)器后，下一階段機(jī)齡為更換機(jī)器后，下一階段機(jī)齡為1年年 運(yùn)籌學(xué)運(yùn)籌學(xué)第六章 動(dòng)態(tài)規(guī)劃（4）機(jī)器第一年購(gòu)買(mǎi)機(jī)器第一年購(gòu)買(mǎi)機(jī)器第二年購(gòu)買(mǎi)機(jī)器第二年購(gòu)買(mǎi)第三年購(gòu)買(mǎi)第三年購(gòu)買(mǎi)四年購(gòu)四年購(gòu)買(mǎi)買(mǎi)五五年年買(mǎi)買(mǎi)幾年前購(gòu)買(mǎi)機(jī)器幾年前購(gòu)買(mǎi)機(jī)器t=01234012301201012345收收入入I2221201816272524222926243028321816161414運(yùn)運(yùn)行行費(fèi)費(fèi)66881056895564

55、54889910更更新新費(fèi)費(fèi)2729323437293134363132333233343234363638O5(3)=9 :表示第表示第5年開(kāi)始機(jī)齡為年開(kāi)始機(jī)齡為3年的機(jī)器，購(gòu)買(mǎi)年年的機(jī)器，購(gòu)買(mǎi)年5 3 =2 年年 , 運(yùn)行費(fèi)用運(yùn)行費(fèi)用 9 運(yùn)行費(fèi)用運(yùn)行費(fèi)用 Oj(t) 表示第表示第j年開(kāi)始機(jī)齡為年開(kāi)始機(jī)齡為t年的機(jī)器，購(gòu)買(mǎi)年年的機(jī)器，購(gòu)買(mǎi)年j t 運(yùn)籌學(xué)運(yùn)籌學(xué)第六章 動(dòng)態(tài)規(guī)劃（4） i= 機(jī)器第一年購(gòu)買(mǎi)機(jī)器第一年購(gòu)買(mǎi) 幾年前購(gòu)買(mǎi)的機(jī)器幾年前購(gòu)買(mǎi)的機(jī)器機(jī)齡機(jī)齡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)運(yùn)行運(yùn)行費(fèi)費(fèi)Oi (t)6O1(0)6O2(1)8O3(2)8O4(3)10O5(4)8O1(1)8O1(2)9O1(3)9O1(4)10O1(5)更新更新費(fèi)費(fèi)Ci (t)27C1(0)29C2(1)32C3(2)34C4(3)37C5(4)32C1(1)34C1(2)36C1(3)36C1(4)38C1(5)說(shuō)明符號(hào)對(duì)應(yīng)：說(shuō)明符號(hào)對(duì)應(yīng)：I5(4)16 ： 機(jī)器已經(jīng)使用了機(jī)器已經(jīng)使用了4年，購(gòu)買(mǎi)年為年，購(gòu)買(mǎi)年為541年，在第年，在第5年的年的 收入為收入為16萬(wàn)元萬(wàn)元O1(5)10 ：機(jī)器已經(jīng)使用了：機(jī)器已經(jīng)使用了5年，購(gòu)買(mǎi)年為年，購(gòu)買(mǎi)年為514

57、年前，第年前，第1年使用機(jī)器運(yùn)行費(fèi)為年使用機(jī)器運(yùn)行費(fèi)為10萬(wàn)元萬(wàn)元 運(yùn)籌學(xué)運(yùn)籌學(xué)第六章 動(dòng)態(tài)規(guī)劃（4） j=5, 從第從第5年開(kāi)始計(jì)算時(shí)，機(jī)器使用了年開(kāi)始計(jì)算時(shí)，機(jī)器使用了t= 1，2，3，4，5年年 G5（t）表示從第表示從第5年開(kāi)始計(jì)算時(shí)，機(jī)器使用了年開(kāi)始計(jì)算時(shí)，機(jī)器使用了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年開(kāi)始，年開(kāi)始，5-1=4年購(gòu)買(mǎi)，機(jī)齡年購(gòu)買(mǎi)，機(jī)齡1年年= 23X5（1）= 保持保持 運(yùn)籌學(xué)運(yùn)籌學(xué)第六章 動(dòng)態(tài)規(guī)劃（4）同理，同理， G5（3）=13 ， X5（3）= 保持保持 G5（4）=6 ， X5（4）= 保持保持 G5（5）=4 ， X5（5）= 保持：第保持：第5年使用機(jī)齡年使用機(jī)齡5年，最好不更新，年，最好不更新， 因?yàn)楦碌漠?dāng)年利潤(rùn)為負(fù)，反正因?yàn)楦碌漠?dāng)年利潤(rùn)為負(fù)，反正 最后一年了。最后一年了。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年開(kāi)始，年開(kāi)始，5-2=3年購(gòu)買(mǎi)，機(jī)齡年購(gòu)買(mǎi)，機(jī)齡2年年=18X5（2）