運(yùn)籌學(xué)教材編寫組共編章PPT學(xué)習(xí)教案

1、會(huì)計(jì)學(xué)12本章內(nèi)容重點(diǎn)第1頁/共142頁3一、多階段決策問題(Multi-Stage decision process)多階段決策過程特點(diǎn)多階段決策過程特點(diǎn):狀態(tài)狀態(tài) x1階段階段1T1決策決策u1狀態(tài)狀態(tài) x2決策決策u2階段階段2T2狀態(tài)狀態(tài) x3.狀態(tài)狀態(tài) xk決策決策uk階段階段kTk狀態(tài)狀態(tài) xk+1.狀狀態(tài)態(tài) xn決策決策un階段階段nTn狀狀態(tài)態(tài) xn+1第2頁/共142頁4第3頁/共142頁5第4頁/共142頁6使用年限，使總的經(jīng)濟(jì)效益最好。第5頁/共142頁7第6頁/共142頁8第7頁/共142頁9論這個(gè)問題)。第8頁/共142頁10第9頁/共142頁11圖5-11 運(yùn)輸網(wǎng)絡(luò)

2、圖示第10頁/共142頁12第11頁/共142頁13第12頁/共142頁14取決策必是v1 v3 v5 v8 v10，全程長度是20；顯然，這種方法的結(jié)果常是錯(cuò)誤的第13頁/共142頁15考慮，然后逆著實(shí)際過程發(fā)展的順序，逐段向前遞推計(jì)算直至始點(diǎn)。第14頁/共142頁16優(yōu)決策是到v9,最優(yōu)后繼過程是v5v9 v1 0 ，最短距離是12同理，狀態(tài)v6的最優(yōu)決策是至v8；v7的最優(yōu)決策是到v9。第15頁/共142頁17線表示各點(diǎn)到的最優(yōu)路線，每點(diǎn)上方括號(hào)內(nèi)的數(shù)字表示該點(diǎn)到終點(diǎn)的最短路距離。第16頁/共142頁18的最優(yōu)策略和最優(yōu)路線。計(jì)算過程中，系統(tǒng)地刪去了所有中間非最優(yōu)的方案組合，從而使計(jì)算工

3、作量比窮舉法大為減少。第17頁/共142頁19第18頁/共142頁20第19頁/共142頁21k態(tài)記作sk，終止?fàn)顟B(tài)記為sk+1。但為了清楚起見，通常定義階段的狀態(tài)即指其初始狀態(tài)。第20頁/共142頁22第21頁/共142頁23第22頁/共142頁24第23頁/共142頁25)(,(1kkkkksusTs(5-1)第24頁/共142頁26第25頁/共142頁27)(,(kkkkspsR第26頁/共142頁28),(),(),(),(11111,nnnkkkkkknnkkkknknkusgusgusgusususRR (5-2)第27頁/共142頁29nkiiiikusgR),(nkiiiiku

4、sgR),(第28頁/共142頁30)(,(kkkkspsRnkspsRoptsfkkkksPpkkkKk, 2 , 1),(,()()()(,),(),(11nnkkkksususunksusususpnnkkkkkk, 2 , 1),(,),(),()(11nkuuupnkkk, 2 , 1,1第29頁/共142頁31,109731vvvvp)()(11111011ssfsfoptfSs,),()(211111nuusussp第30頁/共142頁32), 2 , 1(nkuknkUuSsusTstsusususRRoptfkkkkkkkknnuun, 2, 1),(. .),(122111

5、（5-5）第31頁/共142頁33,21nuuu,121nnssss第32頁/共142頁34第33頁/共142頁35號(hào)的點(diǎn)沿著最短距離所對(duì)應(yīng)的已標(biāo)號(hào)的點(diǎn)用粗箭線連接起來，表示出各剛標(biāo)號(hào)的點(diǎn)到終點(diǎn)的最短路線。第34頁/共142頁36第35頁/共142頁37圖5-2 某城市的局部道路分布圖第36頁/共142頁38第37頁/共142頁39第38頁/共142頁40ECBAS111ECBAS113ECBAS123第39頁/共142頁41圖見下頁ECBA111第40頁/共142頁42圖5-3某城市局部道路求最短路徑的過程第41頁/共142頁43)(),(,),(),()(221111nnkksususus

6、usp 則對(duì)上述策略中所隱含的任一狀態(tài)而言， 第k子過程上對(duì)應(yīng)于該狀態(tài)的最優(yōu)策略必然 包含在上述全過程最優(yōu)策略p1*中，即為)(,),(),()(11nnkkkkkksusususp第42頁/共142頁441 , 2 , 3 , 4),()(,(min)(0)(111)(55ksufsusgsfsfkkkkkkksUukkkkk)(,(kkkksusg0)(55sf第43頁/共142頁45)(,()()(kkkksPpkkspsRoptsfkKknkiiiiusg),(1 , 2 , 1,),()(,()(0)(11111nnksufsusgoptsfsfkkkkkkkUukknnkk第44頁

7、/共142頁46)(,()()(kkkksPpkkspsRoptsfkKknkiiiiusg),(1 , 2 , 1,),()(,()(1)(11111nnksufsusgoptsfsfkkkkkkkUukknnkk)(11nnsf第45頁/共142頁47第46頁/共142頁48有所不同的，動(dòng)態(tài)規(guī)劃中的狀態(tài)變量必須具備以下三個(gè)特征：第47頁/共142頁49第48頁/共142頁50第49頁/共142頁51),(,),(111111,nkkkkknkkkknkssRussususR),(,111nkkkkkssRus第50頁/共142頁52nkiiiikkusgsR),()(),(iiiusg),

8、(),(111nkkkkkkssRusgR第51頁/共142頁53第52頁/共142頁54第53頁/共142頁55)( 9 . 07 . 0)(1kkkkkkkusuusbaus第54頁/共142頁560)(kkkkkxuusU5),(kikkkkusgR)(max)(kUukkxsfkk)( 9 . 07 . 0 )( 581kkkkkkkusufusu第55頁/共142頁570)(1515sf , 5055max)(suksf)()( 586555ksfusu50maxsuk)( 58555usu)(44sf)( 9 . 07 . 0 )( 58max4445444044usufususu

9、)( 9 . 07 . 0 8)( 58max444444044usuususu)(2.126.13max444044ususu= = 因此，當(dāng)u4*=s4時(shí)，有最大值f4(s4)=13.6s4第56頁/共142頁58 =)(33sf)()( 58max44333033sfususu)(22.1755.17max333033ususu)()(58max33222022sfususu)( 58max222022ususu)(9 . 07 . 055.17222usu)(8.2025.20max222022ususu)(22sf第57頁/共142頁59)(11sf)(58max111011usus

10、u)(9 . 07 . 08 .20111usu)(7.2355.22max111011ususu01u10001s5000),(111usg23700)(11sf02u9002s4500),(222usg187208 .20)(222ssf第58頁/共142頁60產(chǎn)量最高？33su 8103s6480),(333usg1421655.17)(333ssf44su 5674s4536),(444usg77116 .13)(444ssf55su 3975s3176),(555usg31766 .13)(555ssf2787 . 0)(9 . 07 . 055556xusus第59頁/共142頁6

11、1500)(9.07.0)(1kkkkkkkusuusbaus)(9.07.05556usus25005.455su第60頁/共142頁62= 5055max)(suksf)( 58555usu)25005 . 4( 5)25005 . 4( 8555usu75005.185s = )(44sf)()( 58max55444044sfususu75005 .18)(58max5444044uususu7500)(9 . 07 . 0 5 .18)( 58max444444044usuususu750075. 07 .21max44044ussu = = 第61頁/共142頁63 = )(33s

12、f)()(58max44333033sfususu7500)( 9 . 07 . 0 7 .21)( 58max333333033usuususu75005 .243 . 1max33033susu = )(22sf)()(58max33222022sfususu)(58max222022ususu7500)( 9 . 07 . 0 5 .24222usu75001 .279 . 1max22022susu = = + 第62頁/共142頁64= )(11sf)()( 58max22111011sfususu7500)(9 . 07 . 0 1 .27)( 58max111111011usuu

13、susu75004.294.2max11011susu= 第63頁/共142頁65（臺(tái)）（臺(tái)）（臺(tái)）（臺(tái)）（臺(tái)）01u10001s02u9009 . 0)( 9 . 07 . 01*11*12susus03u8109 . 0)( 9 . 07 . 02*22*23susus04u7299 . 0)( 9 . 07 . 03*33*34susus6569 . 0)( 9 . 07 . 04*44*45susus2787 . 0)(9 . 07 . 055556xusus（臺(tái)）第64頁/共142頁66B3B2B1C3C2C1D3D2D1EA456343454742657109786第65頁/共14

14、2頁67第66頁/共142頁68 那么，從A出發(fā)經(jīng)過4個(gè)階段：A到B、B到C、C到D、D到E，逐次作出決策，構(gòu)成從A到E 的一條路線，記為 u 。 即 u = S1 X1 S2 X2 S3 X3 S4 X4 S5 其中 S1 = A ，S5 = E 記 d 為兩個(gè)相鄰節(jié)點(diǎn)之間的長度， 如 d（A，B 3）= 3 。 3.動(dòng)態(tài)規(guī)劃方法的基本步驟動(dòng)態(tài)規(guī)劃方法的基本步驟第67頁/共142頁69 記 fk(Sk)為從Sk到E的最短長度,稱為從Sk到E的距離。 那么，f1(A)是從A到E的最短距離，即最優(yōu)策略的值。3.動(dòng)態(tài)規(guī)劃方法的基本步驟動(dòng)態(tài)規(guī)劃方法的基本步驟第68頁/共142頁70第69頁/共142

15、頁71法、非線性規(guī)劃法或其它數(shù)值計(jì)算方法等。還有連續(xù)變量的離散化解法和高維問題的降維法及疏密格子點(diǎn)法等等。第70頁/共142頁72 學(xué)習(xí)方法建議： 第一步 先看問題，充分理解問題的條件、情況及求解目標(biāo)。 第二步 結(jié)合前面講到的理論和解題過程，考慮如何著手進(jìn)行求解該問題的工作。分析針對(duì)該動(dòng)態(tài)規(guī)劃問題的“四大要素、一個(gè)方程”這一步在開始時(shí)會(huì)感到困難，但是一定要下決心去思考，在思考過程中深入理解前文講到的概念和理論。4.動(dòng)態(tài)規(guī)劃方法應(yīng)用舉例動(dòng)態(tài)規(guī)劃方法應(yīng)用舉例第71頁/共142頁73 第三步 動(dòng)手把求解思路整理出來，或者說，把該問題作為習(xí)題獨(dú)立的來做。 第四步 把自己的求解放到一邊，看書中的求解方法

16、，要充分理解教材中的論述。 第五步 對(duì)照自己 的求解，分析成敗。 4.動(dòng)態(tài)規(guī)劃方法應(yīng)用舉例動(dòng)態(tài)規(guī)劃方法應(yīng)用舉例第72頁/共142頁744.動(dòng)態(tài)規(guī)劃方法應(yīng)用舉例動(dòng)態(tài)規(guī)劃方法應(yīng)用舉例第73頁/共142頁75 2. 動(dòng)態(tài)規(guī)劃基本方程 fn+1(xn+1) = 0 (邊界條件) fk(xk) = opt urk ( xk , uk ) + fk+1(xk+1) k = n,1返回返回4.動(dòng)態(tài)規(guī)劃方法應(yīng)用舉例動(dòng)態(tài)規(guī)劃方法應(yīng)用舉例第74頁/共142頁76第75頁/共142頁77BACBDBCDEC212312312511214106104131211396581052 階段 1 階段 2 階段 3 階段

17、4 階段 5 求 最 短 路 徑例5.5第76頁/共142頁78求 最 短 路 徑第77頁/共142頁79fxvxdfxdDx4444455444()min (,)()()從 f5(x5)到 f4(x4)的遞推過程用下表表示： x4D4(x4) x5v4(x4,d4) v4(x4,d4)+f5(x5) f4(x4) 最優(yōu)決策 d4*D1D1E E55+0=5*5D1ED2D2E E22+0=2*2D2E求 最 短 路 徑第78頁/共142頁80f4(x4) 的表達(dá)式 x4 f4(x4) 最優(yōu)決策 d4* D1 5 D1E D2 2 D2E 求 最 短 路 徑第79頁/共142頁81從 f4(x

18、4)到 f3(x3)的遞推過程用表格表示如下： x3 D3(x3) x4 v3(x3,d3) v3(x3,d3)+f4(x4) f3(x3) 最優(yōu)決策 d3* C1 C1D1 C1D2 D1 D2 3 9 3+5=8* 9+2=11 8 C1D1 C2 C2D1 C2D2 D1 D2 6 5 6+5=11 5+2=7* 7 C2D2 C3 C3D1 C3D2 D1 D2 8 10 8+5=13 10+2=12* 12 C3D2 )(),(min)(44333)(33333xfdxvxfxDd 求 最 短 路 徑第80頁/共142頁82x3 f3(x3) 最優(yōu)決策d3* C1 8 C1D1 C2

19、 7 C2D2 C3 12 C3D2 第二階段的遞推方程為： )(),(min)(33222)(22222xfdxvxfxDd從f3(x3)到f2(x2)的遞推過程用表格表示如下： 求 最 短 路 徑第81頁/共142頁83x2 D2(x2) x3 v2(x2,d2) v2(x2,d2)+f3(x3) f2(x2) 最優(yōu)決策 d2* B1 B1C1 B1C2 B1C3 C1 C2 C3 12 14 10 12+8=20* 14+7=21 10+12=22 20 B1C1 B2 B2C1 B2C2 B2C3 C1 C2 C3 6 10 4 6+8=14* 10+7=17 4+12=16 14 B

20、2C1 B3 B3C1 B3C2 B3C3 C1 C2 C3 13 12 11 13+8=21 12+7=19* 11+12=23 19 B3C2 求 最 短 路 徑第82頁/共142頁84x2 f2(x2) 最優(yōu)決策 d2* B1 20 B1C1 B2 14 B2C1 B3 19 B3C2 求 最 短 路 徑第83頁/共142頁85)(),(min)(22111)(11111xfdxvxfxDd 從f2(x2)到f1(x1)的遞推過程用表格表示如下： x1 D1(x1) x2 v1(x1,d1) v1(x1,d1)+f2(x2) f1(x1) 最優(yōu)決策 d1* A A B1 A B2 AB3

21、 B1 B2 B3 2 5 1 2+20=22 5+14=19* 1+19=20 19 A B 2 求 最 短 路 徑第84頁/共142頁86x1 f1(x1) 最優(yōu)決策 d1* A 19 A B2 從表達(dá)式f1(x1)可以看出，從A到E 的最短路徑長度為 19。由f1(x1)向 f4(x4)回朔，得到最短路徑為： A B2 C1 D1 E求 最 短 路 徑第85頁/共142頁87第86頁/共142頁88 項(xiàng)目投入資金ABC1 萬元15 萬噸13 萬噸11 萬噸2 萬元28 萬噸29 萬噸30 萬噸3 萬元40 萬噸43 萬噸45 萬噸4 萬元51 萬噸55 萬噸58 萬噸求對(duì)三個(gè)項(xiàng)目的最優(yōu)投

22、資分配，使總投資效益最大。資資 源源 分分 配配 問問 題題第87頁/共142頁89kkkk ,kk+1(xk+1)8.終端條件：f4(x4)=0資資 源源 分分 配配 問問 題題第88頁/共142頁90 x3D3(x3)x4v3(x3,d3)v3(x3,d3)+f4(x4)f3(x3)d3*00000+0=0000100+0=01101111+0=11*1110200+0=0111111+0=112203030+0=30*3020300+0=0121111+0=11213030+0=303304545+0=45*4530400+0=0131111+0=11223030+0=30314545+

23、0=454405858+0=58*584資資 源源 分分 配配 問問 題題第89頁/共142頁91x2D2(x2)x3v2(x2,d2)v2(x2,d2)+f3(x3)f2(x2)d2*00000+0=0000100+11=111101313+0=13*1310200+30=30*111313+11=242202929+0=293000300+45=45*121313+30=43212929+11=403304343+0=434500400+58=58131313+45=58222929+30=59*314343+11=544405555+0=55592資資 源源 分分 配配 問問 題題第90

24、頁/共142頁92x1D1(x1)x2v1(x1,d1)v1(x1,d1)+f2(x2)f1(x1)d1*0400+59=59131515+45=60*222828+30=58314040+13=534405151+0=51601最優(yōu)解為 x1=4, d1*=1, x2=x1-d1=3, d2*=0, x3=x2-d2*=3, d3=3, x4=x3-d3=0， 即項(xiàng)目 A 投資 1 萬元，項(xiàng)目 B 投資 0 萬元，項(xiàng)目 C 投資 3 萬元，最大效益為 60 萬噸。 資資 源源 分分 配配 問問 題題第91頁/共142頁93第92頁/共142頁94 設(shè)有n種物品，每一種物品數(shù)量無限。 第i種物

25、品每件重量為wi， 每件價(jià)值ci?，F(xiàn)有一只可裝載重量為 W 的背包，求各種物品應(yīng)各取多少件放入背包， 使背包中物品的價(jià)值最高。 這個(gè)問題可以用整數(shù)規(guī)劃模型來描述。 設(shè)第i種物品取xi件 （i=1,2,n，xi為非負(fù)整數(shù)） ，背包中物品的價(jià)值為z，則 背 包 問 題第93頁/共142頁95背 包 問 題第94頁/共142頁96背 包 問 題第95頁/共142頁9730max)(max)(3/04433/033333333dxfdcxfwxdwxd列出f3(x3)的數(shù)值表 背 包 問 題第96頁/共142頁98x3 D3(x3) x4 30d3+f4(x4) f3(x3) d3* 0 0 0 0+

26、0=0 0 0 1 0 1 1 0 0+0=0 30+0=30* 30 1 2 0 1 2 2 1 0 0+0=0 30+0=30 60+0=60* 60 2 3 0 1 2 3 3 2 1 0 0+0=0 30+0=30 60+0=60 90+0=90* 90 3 4 0 1 2 3 4 4 3 2 1 0 0+0=0 30+0=30 60+0=60 90+0=90 120+0=120* 120 4 5 0 1 2 3 4 5 5 4 3 2 1 0 0+0=0 30+0=30 60+0=60 90+0=90 120+0=120 150+0=150* 150 5 第97頁/共142頁99對(duì)于

27、k=2 )3(80max)(max)(22323/03322/02222222dxfdxfdcxfxdwxd 列出 f2(x2)的數(shù)值表 x2 D2(x2) x3 80d2+f3(x3) f2(x2) d2* 0 0 0 0+f3(0)=0+0=0* 0 0 1 0 1 0+f3(1)=0+30=30* 30 0 2 0 2 0+f2(2)=0+60=60* 60 0 3 0 1 3 0 0+f3(3)=0+90=90* 80+f3(0)=80+0=80 90 0 4 0 1 4 1 0+f3(4)=0+120=120* 80+f3(1)=80+30=110 120 0 5 0 1 5 2 0

28、+f3(5)=0+150=150* 80+f3(2)=80+60=140 150 0 第98頁/共142頁100對(duì)于k=1 )2(65max)(max)(11212/02211/01111111dxfdxfdcxfxdwxd 列出f1(x1)的數(shù)值 x1 D1(x1) x2 65d1+f2(x2) f1(x1) d1* 0 0 0 0+f2(0)=0+0=0* 0 0 1 0 1 0+f2(1)=0+30=30* 30 0 2 0 1 2 0 0+f2(2)=0+60=60 65+f2(0)=65+0=65* 65 1 3 0 1 3 1 0+f2(3)=0+90=90 65+f2(1)=65

29、+30=95* 95 1 4 0 1 2 4 2 0 0+f2(4)=0+120=120 65+f2(2)=65+60=125 130+f2(0)=130+0=130* 130 2 5 0 1 2 5 3 1 0+f2(5)=0+150=150 65+f2(3)=65+90=155 130+f2(1)=130+30=160* 160 2 第99頁/共142頁101由題意知，x1=5，由表f1(x1)、f2(x2)、f3(x3)，經(jīng)回朔可得： d1*=2，x2=x1-2d1=1，d2*=0，x3=x2-3d2=1，d3*=1，x4=x3-d3=0 即應(yīng)取第一種物品 2 件,第三種物品 1 件,最

30、高價(jià)值為 160 元,背包沒有余量。由f1(x1)得列表可以看出，如果背包得容量為W=4，W=3，W=2 和W=1 時(shí)，相應(yīng)的最優(yōu)解立即可以得到。 第100頁/共142頁102第101頁/共142頁103 最短路徑問題和背包問題的狀態(tài)變量和決策變量都只能取離散的整數(shù)值。 當(dāng)狀態(tài)變量和決策變量的取值范圍很大，或者這些變量是連續(xù)的，用列舉的方法就比較困難或者根本不可能了。 這就需要用連續(xù)變量的處理方法。 例例 5.5.8 8: :某種機(jī)器可以在高、低兩種負(fù)荷下生產(chǎn)。高負(fù)荷生產(chǎn)條件下機(jī)器完好率為 0.7，即如果年初有u臺(tái)完好機(jī)器投入生產(chǎn)，則年末完好的機(jī)器數(shù)量為0.7u臺(tái)。系數(shù) 0.7 稱為完好率。年

31、初投入高負(fù)荷運(yùn)行的u臺(tái)機(jī)器的年產(chǎn)量為 8u噸。系數(shù) 8 稱為單臺(tái)產(chǎn)量。低負(fù)荷運(yùn)行時(shí)，機(jī)器完好率為 0.9，單臺(tái)產(chǎn)量為5 噸。設(shè)開始時(shí)有 1000 臺(tái)完好機(jī)器，要制訂五年計(jì)劃，每年年初將完好的機(jī)器一部分分配到高負(fù)荷生產(chǎn)，剩下的機(jī)器分配到低負(fù)荷生產(chǎn)，使五年的總產(chǎn)量為最高。 第102頁/共142頁104 機(jī)器負(fù)荷分配問題機(jī)器負(fù)荷分配問題第103頁/共142頁105 根據(jù)題意，本題的決策允許集合應(yīng)該是一個(gè)整數(shù)集合，但由于決策允許集合中可取的決策數(shù)量很大，一一列舉計(jì)算量很大，不妨認(rèn)為狀態(tài)變量和決策變量都是連續(xù)的，得到最優(yōu)解后，再作取整處理。 機(jī)器負(fù)荷分配問題機(jī)器負(fù)荷分配問題第104頁/共142頁106

32、機(jī)器負(fù)荷分配問題機(jī)器負(fù)荷分配問題第105頁/共142頁107 機(jī)器負(fù)荷分配問題機(jī)器負(fù)荷分配問題第106頁/共142頁108 機(jī)器負(fù)荷分配問題機(jī)器負(fù)荷分配問題第107頁/共142頁109 機(jī)器負(fù)荷分配問題機(jī)器負(fù)荷分配問題第108頁/共142頁110 機(jī)器負(fù)荷分配問題機(jī)器負(fù)荷分配問題第109頁/共142頁111x5=0.7d4+0.9(x4-d4)=397nd5*=x5=397, x6=0.7d5+0.9(x5-d5)=278 機(jī)器負(fù)荷分配問題機(jī)器負(fù)荷分配問題第110頁/共142頁112 機(jī)器負(fù)荷分配問題機(jī)器負(fù)荷分配問題第111頁/共142頁113tniitniikkkpppk0112121)1(

33、01)( 機(jī)器負(fù)荷分配問題機(jī)器負(fù)荷分配問題第112頁/共142頁114第113頁/共142頁115月份(k) 1 2 3 4 5 6 7 生產(chǎn)成本(ck) 11 18 13 17 20 10 15 需求量(rk) 0 8 5 3 2 7 4 為了調(diào)節(jié)生產(chǎn)生產(chǎn)和需求， 工廠設(shè)有一個(gè)產(chǎn)品倉庫， 庫容量H=9。 已知期初庫存量為 2，要求期末（七月低）庫存量為 0。 每個(gè)月生產(chǎn)的產(chǎn)品在月末入庫，月初根據(jù)當(dāng)月需求發(fā)貨。求七個(gè)月的生產(chǎn)量，能滿足各月的需求，并使生產(chǎn)成本最低。 生生 產(chǎn)產(chǎn) 庫庫 存存 問問 題題第114頁/共142頁116nvkxk ,dkckdk；n終端條件：f8(x8)=0,x8=0；

34、生生 產(chǎn)產(chǎn) 庫庫 存存 問問 題題第115頁/共142頁117生生 產(chǎn)產(chǎn) 庫庫 存存 問問 題題第116頁/共142頁118生生 產(chǎn)產(chǎn) 庫庫 存存 問問 題題第117頁/共142頁119生生 產(chǎn)產(chǎn) 庫庫 存存 問問 題題第118頁/共142頁120生生 產(chǎn)產(chǎn) 庫庫 存存 問問 題題第119頁/共142頁121生生 產(chǎn)產(chǎn) 庫庫 存存 問問 題題第120頁/共142頁122 由于 在f4(x4)的表達(dá)式中d4的系數(shù)是-3， 因此d4在決策允許集合中應(yīng)取集合中的最大值，即d4=12-x4由此 f4(x4)=-3(12-x4)-20 x4+280 =-17x4+244生生 產(chǎn)產(chǎn) 庫庫 存存 問問 題題

35、第121頁/共142頁123生生 產(chǎn)產(chǎn) 庫庫 存存 問問 題題第122頁/共142頁124生生 產(chǎn)產(chǎn) 庫庫 存存 問問 題題第123頁/共142頁125生生 產(chǎn)產(chǎn) 庫庫 存存 問問 題題第124頁/共142頁126生生 產(chǎn)產(chǎn) 庫庫 存存 問問 題題第125頁/共142頁127k 1 2 3 4 5 6 7 ck 11 18 13 17 20 10 15 rk 0 8 5 3 2 7 4 xk 2 9 5 9 9 7 4 dk 7 13-x2=4 14-x3=9 12-x4=3 9-x5=0 11-x6=4 0 生生 產(chǎn)產(chǎn) 庫庫 存存 問問 題題第126頁/共142頁128第127頁/共142頁

36、129設(shè)設(shè) 備備 更更 新新 問問 題題第128頁/共142頁130階段k：運(yùn)行年份； 狀態(tài)變量xk：設(shè)備的役齡t； 決策變量dk： 繼續(xù)使用更新)()(ReKeepKplaceRdk 狀態(tài)轉(zhuǎn)移方程： KdxRdxkkkk111 階段指標(biāo)： KdtCRdtSCPKdxCRdxSCPvkkkkkkk)()()0()()()0( 第129頁/共142頁131遞推方程： KdtftCRdftSCPKdxfxCRdxfxSCPxfkkkkkkkkkkkkkk) 1()() 1 ()()0(min)()()()()0(min)(111111 終端條件： fn(t)=-R(t) 設(shè)設(shè) 備備 更更 新新 問

37、問 題題第130頁/共142頁132T 0 1 2 3 4 5 6 7 C(t) 10 13 20 40 70 100 100 - S(t) - 32 21 11 5 0 0 0 R(t) - 25 17 8 0 0 0 0 且 n=5，T=2，P=50 由上表開始，終端條件為： f6(1)=-25，f6(2)=-17，f6(3)=-8 f6(4)=f6(5)=f6(6)=f6(7)=0 設(shè)設(shè) 備備 更更 新新 問問 題題第131頁/共142頁133 對(duì)于k=5: KdRdtftCftSCPtf55665) 1()() 1 ()() 0(min)( KdfCfSCPf*5665, 443min

38、)17(13)25(321050min) 2() 1 () 1 () 1 () 0(min) 1 ( KdfCfSCPf*5665,121214min) 8(20)25(211050min) 3 () 2() 1 () 2() 0(min) 2( 第132頁/共142頁134RdfCfSCPf*5665,244024min040)25(111050min)4() 3 () 1 () 3 ()0(min) 3 ( RdfCfSCPf*5665,307030min070)25(51050min)5()4() 1 ()4()0(min)4(RdfCfSCPf*5665,3510035min0100)25(01050min) 6() 5 () 1 () 5 () 0(min) 5 (第133頁/共142頁135RdfCfSCPf*5665,3510035min0100)25(01050min)7 () 6 () 1 () 6 () 0 (min) 6 ( KdRdtftCftSCPtf44554) 1