運(yùn)籌學(xué)動態(tài)規(guī)劃應(yīng)用舉例PPT課件

1、第四節(jié) 動態(tài)規(guī)劃在經(jīng)濟(jì)管理中的應(yīng)用 連續(xù)變量的離散化解法連續(xù)變量的離散化解法 先介紹連續(xù)變量離散化的概念。如投資分配問題先介紹連續(xù)變量離散化的概念。如投資分配問題的一般靜態(tài)模型為：的一般靜態(tài)模型為： niiixgz1)(max), 2 , 1(01nixaxinii模型中：階段數(shù)、總投資、各階段投資數(shù)、各階段收益、決策變量、狀模型中：階段數(shù)、總投資、各階段投資數(shù)、各階段收益、決策變量、狀態(tài)變量態(tài)變量 狀態(tài)轉(zhuǎn)移方程、基本方程、指標(biāo)函數(shù)、最優(yōu)指標(biāo)函數(shù)狀態(tài)轉(zhuǎn)移方程、基本方程、指標(biāo)函數(shù)、最優(yōu)指標(biāo)函數(shù)第1頁/共59頁建立它的動態(tài)規(guī)劃模型，其基本方程為：建立它的動態(tài)規(guī)劃模型，其基本方程為：0)(1 ,2,

2、 1,)()(max)(11110nnkkkksxkksfnnksfxgsfkk其狀態(tài)轉(zhuǎn)移方程為其狀態(tài)轉(zhuǎn)移方程為: :kkkxss1 由于由于 與與 都是連續(xù)變量，當(dāng)各階段指標(biāo)都是連續(xù)變量，當(dāng)各階段指標(biāo) 沒沒有特殊性而較為復(fù)雜時，有特殊性而較為復(fù)雜時， 要求出要求出 會比較困難，因而求會比較困難，因而求全過程的最優(yōu)策略也就相當(dāng)不容易，這時常常采用把連續(xù)變量全過程的最優(yōu)策略也就相當(dāng)不容易，這時常常采用把連續(xù)變量離散化的辦法求其數(shù)值解。具體做法如下：離散化的辦法求其數(shù)值解。具體做法如下： kskx)(kkxg)(kksf第2頁/共59頁（1 1） 令令 ，把區(qū)間把區(qū)間 0 0，aa進(jìn)行分割，進(jìn)行分

3、割， 的大小可的大小可依據(jù)問題所要求的精度以及計算機(jī)的容依據(jù)問題所要求的精度以及計算機(jī)的容量來定。量來定。 amsk,2,0第3頁/共59頁 (2) (2) 規(guī)定狀態(tài)變量規(guī)定狀態(tài)變量 及決策變量及決策變量 只在離散點(diǎn)只在離散點(diǎn) 上取值，相應(yīng)的指標(biāo)上取值，相應(yīng)的指標(biāo)函數(shù)函數(shù) 就被定義在這些離散值上，于是遞推方就被定義在這些離散值上，于是遞推方程就變?yōu)椋撼叹妥優(yōu)椋?kskxam,2,0)(kksf0)()()(max)(111,2, 1 ,0nnkkkqpkksfpsfpgsf其中 pxsqkk,第4頁/共59頁 作為離散化例子，在例作為離散化例子，在例5 5中規(guī)定狀態(tài)變量和決中規(guī)定狀態(tài)變量和決策

4、變量只在給出的離散點(diǎn)上取值，見例策變量只在給出的離散點(diǎn)上取值，見例6 6。 （ 3 3 ） 按 逆 序 方 法 ， 逐 步 遞 推 求按 逆 序 方 法 ， 逐 步 遞 推 求出出 ，最后求出最，最后求出最優(yōu)資金分配方案。優(yōu)資金分配方案。)(,),(11sfsfnn第5頁/共59頁問如何分配投資數(shù)額才能使總效益最大問如何分配投資數(shù)額才能使總效益最大? ?23332221112)(,9)(,4)(xxgxxgxxg例例5 5 某公司有資金某公司有資金1010萬元，若投資于項(xiàng)目萬元，若投資于項(xiàng)目i(i=1,2,3)i(i=1,2,3)的投資額為的投資額為x xi i時，其效益分別為：時，其效益分別

5、為： 第6頁/共59頁例例6 6 連續(xù)變量的離散化解法連續(xù)變量的離散化解法)3,2, 1(,010.294max3212321ixxxxtsxxxZi第7頁/共59頁解解 令令 ，將區(qū)間，將區(qū)間00，1010分割成分割成0 0，2 2，4 4，6 6，8 8，1010六個點(diǎn)，即狀態(tài)變量六個點(diǎn)，即狀態(tài)變量 集合為集合為 2ks10,8,6,4,2,0允許允許決策集合為決策集合為 ， 與與 均在分割點(diǎn)上取值。均在分割點(diǎn)上取值。 kksx0kxks動態(tài)規(guī)劃基本方程為：動態(tài)規(guī)劃基本方程為： 0)(1 ,2, 3)()(max)(4410sfkxsfxgsfkkkkksxkkkk當(dāng)當(dāng)k=3k=3時，時，

6、 230332max)(33xsxsf第8頁/共59頁式中式中 與與 的集合均為：的集合均為： 計算結(jié)果見表計算結(jié)果見表7-17-1。 3s3x10,8,6,4,2,03s)(33sf*3x02468100832721282000246810當(dāng)k=3時， 表7-1 230332max)(33xsxsf第9頁/共59頁當(dāng)k=2時， )(9max)(223202222xsfxsfsx0)(1 , 2 , 3)()(max)(4410sfkxsfxgsfkkkkksxkkkk計算結(jié)果見表計算結(jié)果見表7-27-2。 2s2x32fg 2f*2x024681000 20 2 40 2 4 60 2 4

7、6 80 2 4 6 8 1008 1832 26 3672 50 44 54128 90 68 62 72200 146 108 86 80 900 18 36 72 128 2000 24 0 0 0表表7-2 7-2 第10頁/共59頁當(dāng)k=1時， 0)(1 , 2 , 3)()(max)(4410sfkxsfxgsfkkkkksxkkkk計算結(jié)果見表計算結(jié)果見表7-37-3。 表7-3 )(4max)(1121100111xsfxsfx1s1x21fg 1f*1x 10 101010 10100246810200136886050402000第11頁/共59頁最大收益為最大收益為 ，與

8、例，與例5 5結(jié)論完全相同。結(jié)論完全相同。 10,0,0*3*2*1xxx200)10(1f計算結(jié)果表明，最優(yōu)決策為：計算結(jié)果表明，最優(yōu)決策為： 應(yīng)指出的是：這種方法有可能丟失最優(yōu)解，應(yīng)指出的是：這種方法有可能丟失最優(yōu)解，一般得到原問題的近似解。一般得到原問題的近似解。 第12頁/共59頁一、背包問題一、背包問題 一位旅行者攜帶背包去登山，已知他所能承受的背包重一位旅行者攜帶背包去登山，已知他所能承受的背包重量限度為量限度為a kg，現(xiàn)有，現(xiàn)有n種物品可供他選擇裝入背包，第種物品可供他選擇裝入背包，第i種種物品的單件重量為物品的單件重量為ai kg，其價值是攜帶數(shù)量，其價值是攜帶數(shù)量xi的函數(shù)

9、的函數(shù)ci(xi)(i=1,2,n)，問旅行者應(yīng)如何選擇攜帶各種物品的件，問旅行者應(yīng)如何選擇攜帶各種物品的件數(shù)，以使總價值最大？數(shù)，以使總價值最大？ ), 2 , 1(0)(max11nixaxaxcziniiiniii且為整數(shù)第13頁/共59頁例例1 有一輛最大貨運(yùn)量為有一輛最大貨運(yùn)量為10t的卡車，用以裝載的卡車，用以裝載3種貨物，種貨物，每種貨物的單位重量及相應(yīng)單位價值見下表，應(yīng)如何裝載可每種貨物的單位重量及相應(yīng)單位價值見下表，應(yīng)如何裝載可使總價值最大？使總價值最大？ ) 3 , 2 , 1(010543654max321321ixxxxxxxzi且為整數(shù)貨物編號i123單位重量(t)3

10、45單位價值ci456逆序解法：逆序解法：階段階段k： k=1,2,3狀態(tài)變量狀態(tài)變量sk:第第k階段可以裝載第階段可以裝載第k種到第種到第3種貨物的重量。種貨物的重量。決策變量決策變量xk:決定裝載第決定裝載第k種貨物的數(shù)量。種貨物的數(shù)量。狀態(tài)轉(zhuǎn)移方程狀態(tài)轉(zhuǎn)移方程:sk+1=sk-akxk最優(yōu)指標(biāo)函數(shù)最優(yōu)指標(biāo)函數(shù)fk(sk):當(dāng)可裝載重量為當(dāng)可裝載重量為sk,裝載第裝載第k種到第種到第3種貨物所獲得的種貨物所獲得的最大價值。最大價值。基本方程：基本方程：0)(1 , 2 , 3)()(max)(4411/ , 1 , 0sfksfxcsfkkkkasxkkkkk第14頁/共59頁當(dāng)階段k=3

11、時，有6max)(35/, 03333xsfsxs3012345678910 x3000000101010101012c3+f40000006060606060612f3000006666612x3*00000111112當(dāng)階段k=2時，有)(5max)(3324/, 02222sfxsfsx s2012345678910 x2000001010101012012012c2+f3000005+0656565651065+610125+610f200005666101112x2*000010002102234xss第15頁/共59頁當(dāng)階段k=1時，有)(3max)(2213/10, 0111sf

12、xsfx s110 x10123c1+f3124+68+512f213x1*21123xss第16頁/共59頁二、生產(chǎn)經(jīng)營問題 在生產(chǎn)和經(jīng)營管理中，經(jīng)常遇到如何合在生產(chǎn)和經(jīng)營管理中，經(jīng)常遇到如何合理地安排生產(chǎn)計劃、采購計劃以及倉庫的存理地安排生產(chǎn)計劃、采購計劃以及倉庫的存貨計劃和銷售計劃，使總效益最高的問題。貨計劃和銷售計劃，使總效益最高的問題。下面通過例子來說明對不同特點(diǎn)問題的不同下面通過例子來說明對不同特點(diǎn)問題的不同處理技巧處理技巧。 第17頁/共59頁例2 生產(chǎn)與存貯問題 某工廠生產(chǎn)并銷售某種產(chǎn)品，已知今后四個月市場需求預(yù)測如表，又每月某工廠生產(chǎn)并銷售某種產(chǎn)品，已知今后四個月市場需求預(yù)測

13、如表，又每月生產(chǎn)生產(chǎn)j單位產(chǎn)品費(fèi)用為：單位產(chǎn)品費(fèi)用為： )()6,2, 1(3)0(0)(千元jjjjC 每月庫存每月庫存j j單位產(chǎn)品的費(fèi)用為單位產(chǎn)品的費(fèi)用為 ，該廠最大庫存容量為該廠最大庫存容量為3 3單單位，每月最大生產(chǎn)能力為位，每月最大生產(chǎn)能力為6 6單位，計劃開始和計劃期末庫存量都是單位，計劃開始和計劃期末庫存量都是零零。試制定試制定四個月四個月的生產(chǎn)計劃，在滿足用戶需求條件下總費(fèi)用最小。假設(shè)第的生產(chǎn)計劃，在滿足用戶需求條件下總費(fèi)用最小。假設(shè)第i+1i+1個月的庫個月的庫存量是第存量是第i i個月個月可銷售量可銷售量與該月用戶需求量之差；而第與該月用戶需求量之差；而第i i個月的可銷

14、售量是本個月的可銷售量是本月初庫存量與產(chǎn)量之和。月初庫存量與產(chǎn)量之和。 )(5 . 0)(千元jjE)(月i)(需求ig12342324第18頁/共59頁用動態(tài)規(guī)劃方法求解時，對有關(guān)概念作如下分析：用動態(tài)規(guī)劃方法求解時，對有關(guān)概念作如下分析：(1) (1) 階段：每個月為一個階段，階段：每個月為一個階段，k k1 1，2 2，3 3，4 4。 (2) (2)狀態(tài)變量：狀態(tài)變量： 為第為第k k個月初的庫存量。個月初的庫存量。 ks(3)(3)決策變量：決策變量： 為第為第k k個月的生產(chǎn)量。個月的生產(chǎn)量。 ku(4)(4)狀態(tài)轉(zhuǎn)移方程：狀態(tài)轉(zhuǎn)移方程： kkkkguss1(5)(5)最優(yōu)指標(biāo)函數(shù)

15、：最優(yōu)指標(biāo)函數(shù)： 表示第表示第k k月狀態(tài)為月狀態(tài)為 時，采取時，采取最佳策略生產(chǎn)，從本月到計劃結(jié)束最佳策略生產(chǎn)，從本月到計劃結(jié)束( (第第4 4月末月末) )的生產(chǎn)與存貯最的生產(chǎn)與存貯最低費(fèi)用。低費(fèi)用。（6 6）基本方程：）基本方程： )(kksfks0)(1 , 2 , 3 , 4)()()(min)(5511sfksfsEuCsfkkkkukkk第19頁/共59頁 k4，s5=s4+u4-g4=0，所以，所以u4=g4-s4=4-s4，s4可取可取0，1，2，3。 0)()(min)(443 , 2, 1 , 0444sEuCsfus40123u44321C+E+f576+0.55+14

16、+1.5f476.565.5u4*4321 k3，s4=s3+u3-g3，所以，所以u3=s4+ g3-s3，s3可取可取0，1，2，3。 s30123u3234512340123012C+E+f45+76+6.57+68+5.54.5+75.5+6.56.5+67.5+5.51+75+6.56+67+5.51.5+6.55.5+66.5+5.5f31211.588u3*2100第20頁/共59頁 k2，s3=s2+u2-g2，所以，所以u2=s3+ g2-s2， s2可取可取0，1，2，3。 s20123u23456234512340123C+E+f36+127+11.58+89+85.5+

17、126.5+11.57.5+88.5+85+126+11.57+88+81.5+125.5+11.56.5+87.5+8f21615.51513.5u2*5430 k1，s2=s1+u1-g1，所以，所以u1=s2+ g1-s1， s1可取可取0。 s10u12345C+E+f25+166+15.57+158+13.5f121u1*2反推回去，反推回去， u1*=2，u2*=5，u3*=0，u4*=4。第21頁/共59頁例3 3 采購與銷售問題 某商店在未來的某商店在未來的4 4個月里，準(zhǔn)備利用它的一個倉庫來專門經(jīng)銷某種商個月里，準(zhǔn)備利用它的一個倉庫來專門經(jīng)銷某種商品，倉庫最大容量能貯存這種商

18、品品，倉庫最大容量能貯存這種商品l000l000單位。假定該商店每月只能出賣倉單位。假定該商店每月只能出賣倉庫現(xiàn)有的貨。當(dāng)商店在某月購貨時，下月初才能到貨。預(yù)測該商品未來四庫現(xiàn)有的貨。當(dāng)商店在某月購貨時，下月初才能到貨。預(yù)測該商品未來四個月的買賣價格如表個月的買賣價格如表7 7_12_12所示，假定商店在所示，假定商店在1 1月開始經(jīng)銷時，倉庫貯有該月開始經(jīng)銷時，倉庫貯有該商品商品500500單位。試問若不計庫存費(fèi)用，該商店應(yīng)如何制定單位。試問若不計庫存費(fèi)用，該商店應(yīng)如何制定1 1月至月至4 4月的訂購月的訂購與銷售計劃，使預(yù)期獲利最大。與銷售計劃，使預(yù)期獲利最大。 月份（k）購買單價（ck）

19、銷售單價（pk）110122983111341517第22頁/共59頁解 按月份劃分為4個階段，k=l，2，3，4狀態(tài)變量 ：第k月初時倉庫中的存貨量(含上月訂貨)。決策變量 ：第k月賣出的貨物數(shù)量。 ：第k月訂購的貨物數(shù)量。 狀態(tài)轉(zhuǎn)移方程： kskxky最優(yōu)指標(biāo)函數(shù) ：第k k月初存貨量為 時，從第k k月到4 4月末所獲最大利潤。則有逆序遞推關(guān)系式為： kkkkxyss1)(kksfks0)(1 , 2 , 3 , 4)(max)(5511)(100000sfksfycxpsfkkkkkkxsysxkkkkkkk第23頁/共59頁當(dāng)k=4時 顯然，決策應(yīng)取 時才有最大值1517max)(4

20、4)(1000004444444yxsfxsysx0,*44*4ysx44417)(ssf0)(1 , 2 , 3 , 4)(max)(5511)(100000sfksfycxpsfkkkkkkxsysxkkkkkkk第24頁/共59頁當(dāng)k=3時 這個階段需解一個線性規(guī)劃問題： 1764max)(171113max)(1113max)(333)(10000033333)(1000004433)(10000033333333333333333syxxysyxsfyxsfxsysxxsysxxsysx因?yàn)橹挥袃蓚€變量x3, y3 ，可以用圖解法，也可以用單純形法，求解得到： 時有最大值 0,100

21、01764max3333333333yxsxysxsyxz1000,*33*3ysx333136000)(ssf第25頁/共59頁當(dāng)k=2時 求解線性規(guī)劃問題： 得45136000max)(13600098max)(98max)(222)(10000022222)(100000222322)(10000022222222222222222yxsxysyxxysfyxsfxsysxxsysxxsysx0,100045136000max2222222222yxsxysxyxsz2222291000044000136000)(ssssf2*2*21000,0syx第26頁/共59頁當(dāng)k=1時 求解一

22、個線性規(guī)劃問題： 得)(1012max)(111211)(1000001111111xysfyxsfxsysx 5001s145003max)(9100001012max)500(115000500011111500050001111111yxxysyxfxyxxyx0,500500314500max1111111yxxyxyxz16000500314500)500(, 0,5001*1*1fyx第27頁/共59頁最優(yōu)策略見下表。最大利潤為1600016000。 月份期前存貨售出量購進(jìn)量15005000200100031000100010004100010000第28頁/共59頁例例4 4 限

23、期采購問題限期采購問題( (隨機(jī)型隨機(jī)型) ) 某部門欲采購一批原料，原料價格在五周內(nèi)可能有某部門欲采購一批原料，原料價格在五周內(nèi)可能有所變動，已預(yù)測得該種原料今后五周內(nèi)取不同單價的概所變動，已預(yù)測得該種原料今后五周內(nèi)取不同單價的概率如表率如表7-147-14所示。試確定該部門在五周內(nèi)購進(jìn)這批原料所示。試確定該部門在五周內(nèi)購進(jìn)這批原料的最優(yōu)策略，使采購價格的的最優(yōu)策略，使采購價格的期望值期望值最小。最小。 原材料單價（元）概率5006007000.30.30.4表7-14 第29頁/共59頁 階段階段k k：可按采購期限可按采購期限( (周周) )分為分為5 5段，段，k k1 1，2 2，3

24、 3，4 4，5 5。 狀態(tài)變量狀態(tài)變量 ：第：第k k周的原料實(shí)際價格。周的原料實(shí)際價格。 kx 決策變量 ：第k周如采購 則 1，若不采購 則 =0 =0。 另外用 表示：當(dāng)?shù)趉周決定等待，而在以后采購時的采購價格期望值。 最優(yōu)指標(biāo)函數(shù) ：第k周實(shí)際價格為 時，從第k周至第5周采取最優(yōu)策略所花費(fèi)的最低期望價格。則有逆序遞推關(guān)系式為： )(kksfks解解 本例與前面所討論的確定型問題不同，狀態(tài)的轉(zhuǎn)移不能完全確定，而本例與前面所討論的確定型問題不同，狀態(tài)的轉(zhuǎn)移不能完全確定，而按某種已知的按某種已知的概率分布概率分布取值，即屬于取值，即屬于隨機(jī)型隨機(jī)型動態(tài)規(guī)劃問題。動態(tài)規(guī)劃問題。 kskxkx

25、kES)17. 7()()17. 7(1 , 2 , 3 , 4,min)(55555bDsssfakDsSssfkkkEkkkkD為狀態(tài)集合500，600，700。 第30頁/共59頁當(dāng)k=5時 因?yàn)槿羟八闹苌形促徺I，則無論本周價格如何，該部門都必須購買，所以 )( 1700700)( 1600600)( 1500500)5(5*55*55*55采購當(dāng)采購當(dāng)采購當(dāng)xsxsxssf第31頁/共59頁當(dāng)k=4時 由于 所以 6107004 . 06003 . 05003 . 0)700(4 . 0)600(3 . 0)500(3 . 05554fffSE610,min,min)(4444444s

26、SssfEDs)(0700610)( 1600600)( 1500500*44*44*44等待當(dāng)采購當(dāng)采購當(dāng)xsxsxs第32頁/共59頁當(dāng)k=3時 由于 所以 5746104 .06003 .05003 .0)700(4 .0)600(3 .0)500(3 .04443fffSE574,min,min)(3333333sSssfEDs07006005741500500*33*33xsxs或當(dāng)當(dāng)?shù)?3頁/共59頁當(dāng)k=2時 同理 8 .551,min,min)(22222sSssfE07006008 .5511500500*22*22xsxs或當(dāng)當(dāng)?shù)?4頁/共59頁當(dāng)k=1時 26.536,m

27、in,min)(11111sSssfE070060026.5361500500*11*11xsxs或當(dāng)當(dāng)?shù)?5頁/共59頁 所以，最優(yōu)采購策略為：若第一、二、三周原料價格所以，最優(yōu)采購策略為：若第一、二、三周原料價格為為500500，則立即采購，否則在以后的幾周內(nèi)再采購。若第四，則立即采購，否則在以后的幾周內(nèi)再采購。若第四周價格為周價格為500500或或600600，則立即采購，否則等第五周再采購。，則立即采購，否則等第五周再采購。而第五周時無論當(dāng)時價格為多少都必須采購。而第五周時無論當(dāng)時價格為多少都必須采購。 按照以上策略進(jìn)行采購，期望價格為：按照以上策略進(jìn)行采購，期望價格為： 525382

28、.52526.5364 . 026.5363 . 05003 . 0)700(4 . 0)600(3 . 0)500(3 . 0)(11111fffsf第36頁/共59頁三、設(shè)備更新問題 從經(jīng)濟(jì)上分析，一臺設(shè)備應(yīng)該從經(jīng)濟(jì)上分析，一臺設(shè)備應(yīng)該 使用多少年更新最使用多少年更新最合算，這就是設(shè)備更新問題。一般來說，一臺設(shè)備在比合算，這就是設(shè)備更新問題。一般來說，一臺設(shè)備在比較新時，年運(yùn)轉(zhuǎn)量大，經(jīng)濟(jì)收入高，故障少，維修費(fèi)用較新時，年運(yùn)轉(zhuǎn)量大，經(jīng)濟(jì)收入高，故障少，維修費(fèi)用少，但隨著使用年限的增加，年運(yùn)轉(zhuǎn)量減少因而收入減少，但隨著使用年限的增加，年運(yùn)轉(zhuǎn)量減少因而收入減少，故障變多少，故障變多, ,維修費(fèi)用

29、增加。如果更新可提高年凈收維修費(fèi)用增加。如果更新可提高年凈收入，但是當(dāng)年要支出一筆數(shù)額較大的購買費(fèi)，為了比較入，但是當(dāng)年要支出一筆數(shù)額較大的購買費(fèi)，為了比較不同決策的優(yōu)劣，常常要在一個較長的時間內(nèi)考慮更新不同決策的優(yōu)劣，常常要在一個較長的時間內(nèi)考慮更新決策問題。決策問題。 第37頁/共59頁 設(shè)備更新問題一般提法：在已知一臺設(shè)備的效益函數(shù)r(t)，維修費(fèi)用函數(shù)u(t)及更新費(fèi)用函數(shù)c(t)條件下，要求在n年內(nèi)的每年年初作出決策，是繼續(xù)使用舊設(shè)備還是更換一臺新的，使n年總效益最大。 rk(t)：在第k年設(shè)備已使用過t年(或稱役齡為t年)，再使用1年時的效益。 uk(t) ：在第k年設(shè)備役齡為t年

30、，再使用一年的維修費(fèi)用。 ck(t) ：在第k年賣掉臺役齡為t年的設(shè)備，買進(jìn)一臺新設(shè)備的更新凈費(fèi)用。 為折扣因子(01) ，表示一年以后的單位收入價值相當(dāng)于現(xiàn)年的 單位。 第38頁/共59頁動態(tài)規(guī)劃模型階段變量k：k=1,2,n，表示計劃使用該設(shè)備的年限數(shù)。 狀態(tài)變量sk: 第k年初，設(shè)備已使用過的年數(shù)，即役齡。決策變量xk: 是第k年初更新（Replacement），還是保留使用（keep）舊設(shè)備，分別用R與K表示。 狀態(tài)轉(zhuǎn)移方程為： 階段指標(biāo)為： 111kkssRxKxkk當(dāng)當(dāng)指標(biāo)函數(shù)為： )()0()0()()(),(kkkkkkkkkkjscursusrxsvRxKxkk當(dāng)當(dāng)), 2

31、, 1(),(,nkxsvVnkjkkjnk第39頁/共59頁 最優(yōu)指標(biāo)函數(shù)fk(sk)表示第k年初，使用一臺已用了sk年的設(shè)備，到第n年末的最大收益，則可得如下的逆序動態(tài)規(guī)劃方程： 實(shí)際上， 0)()(),(max)(1111nnkkkkRKkkksfsfxsvxsfk或)18. 7()18. 7(ba)()()0()0()()()(max)(1111kkkkkkkkkkkkkksfscursfsusrsfRxKxkk當(dāng)當(dāng)?shù)?0頁/共59頁例例5 5 設(shè)某臺新設(shè)備的年效益及年均維修費(fèi)、更新凈費(fèi)用如表設(shè)某臺新設(shè)備的年效益及年均維修費(fèi)、更新凈費(fèi)用如表7-7-1515所示。試確定今后所示。試確定今

32、后5 5年內(nèi)的更新策略，使總收益最大。年內(nèi)的更新策略，使總收益最大。（設(shè)（設(shè) ） 1)(trk)(tuk)(tck役齡項(xiàng)目012345效益54.543.7532.5維修費(fèi)0.5 11.522.53更新費(fèi)0.51.52.22.533.5第41頁/共59頁解 如前述建立動態(tài)規(guī)劃模型，n=5 當(dāng)k=5時， )()0()0()()(max)(5555555555scursusrsfRxKx55當(dāng)當(dāng)狀態(tài)變量s5可取1，2，3，4。 )1 ()0()0() 1 () 1 (max) 1 (555555cururfRxKx55當(dāng)當(dāng)5 . 35 . 15 . 0515 . 4maxK) 1 (x5當(dāng)=2.5

33、2 . 25 . 055 . 14max)2(5fK)2(x5當(dāng)=2 5 . 25 . 05275. 3max)3(5fR)3(x5當(dāng)=1.5 35 .055 .23max)4(5fR)2(x5當(dāng) 役齡項(xiàng)目012345效益54.543.7532.5維修費(fèi)0.5 11.522.53更新費(fèi)0.51.52.22.533.5第42頁/共59頁當(dāng)k=4時， 狀態(tài)變量s4可取1，2，3。 = 6.5 役齡項(xiàng)目012345效益54.543.7532.5維修費(fèi)0.5 11.522.53更新費(fèi)0.51.52.22.533.5) 1 ()()0()0() 1()()(max)(5444445444444fscur

34、sfsusrsfRxKx44當(dāng)當(dāng)) 1 (4f5 . 35 . 15 . 055 . 215 . 4maxR) 1 (x4當(dāng))2(4f=5 . 32 . 25 . 05215 . 4max= 5.8 R)2(x4當(dāng)) 3(4f=5 . 35 . 25 . 055 . 1275. 3max= 5.5 R) 3(x4當(dāng)?shù)?3頁/共59頁當(dāng)k=3時， 狀態(tài)變量s3可取1，2。 = 9.5 役齡項(xiàng)目012345效益54.543.7532.5維修費(fèi)0.5 11.522.53更新費(fèi)0.51.52.22.533.5) 1 ()()0()0() 1()()(max)(4333334333333fscursfs

35、usrsfRxKx33當(dāng)當(dāng)) 1 (3f5 . 65 . 15 . 058 . 515 . 4maxR) 1 (x3當(dāng))2(3f=5 . 62 . 25 . 055 . 515 . 4max= 8.8 R)2(x3當(dāng)?shù)?4頁/共59頁當(dāng)k=2時， 狀態(tài)變量s2只能取1 役齡項(xiàng)目012345效益54.543.7532.5維修費(fèi)0.5 11.522.53更新費(fèi)0.51.52.22.533.5= 12.5 ) 1 ()()0()0() 1()()(max)(3222223222222fscursfsusrsfRxKx22當(dāng)當(dāng)) 1 (2f5 . 95 . 15 . 058 . 815 . 4maxR

36、) 1 (x2當(dāng)?shù)?5頁/共59頁當(dāng)k=1時， 狀態(tài)變量s1只能取0 役齡項(xiàng)目012345效益54.543.7532.5維修費(fèi)0.5 11.522.53更新費(fèi)0.51.52.22.533.5= 17 ) 1 ()()0()0() 1()()(max)(2111112111111fscursfsusrsfRxKx11當(dāng)當(dāng)5 .125 . 05 . 055 .125 . 05max)0(1fKx)0(1第46頁/共59頁 上述計算遞推回去，當(dāng) 時，由狀態(tài)轉(zhuǎn)移方程， 則 則查 得：狀態(tài) ，查： Kx)0(1RxRxfsKxss1*2221121)1 (11得，查知RxsKxss23223111推出)

37、 1 (3fRx *3推出 ，查 14s) 1 (4fRx *415s) 1 (5fKx *5最優(yōu)策略為： ，即第一年初購買的設(shè)備到第二、三、四年初各更新一次，用到第5年末，其總效益為17萬元。 KRRRK,第47頁/共59頁 k5，s5可取可取1,2,3,4。 s51234u5KRKRKRKRv5+f64.5-15-0.5-1.54-1.55-0.5-2.23.75-25-0.5-2.53-2.55-0.5-3f53.52.521.5u5*KKRR k4, s4可取可取1,2,3。 s4123u4KRKRKRv4+f54.5-1+2.55-0.5-1.5+3.5 4-1.5+25-0.5-2

38、.2+3.53.75-2+1.55-0.5-2.5+3.5f46.55.85.5u4*RRR第48頁/共59頁 k3，s3可取可取1,2。 s312u3KRKRv3+f44.5-1+5.85-0.5-1.5+6.54-1.5+5.55-0.5-2.2+6.5f49.58.8u4*RR k2, s2可取可取1。 s21u2KRv3+f24.5-1+8.85-0.5-1.5+9.5f212.5u2*R k1, s2可取可取0。 s10u1KRv1+f25-0.5+12.55-0.5-0.5+12.5f117u1*K第49頁/共59頁 貨郎擔(dān)問題一般提法為：一個貨郎從某貨郎擔(dān)問題一般提法為：一個貨郎

39、從某城鎮(zhèn)出發(fā)，經(jīng)過若干個城鎮(zhèn)一次，且僅一次，城鎮(zhèn)出發(fā)，經(jīng)過若干個城鎮(zhèn)一次，且僅一次，最后仍回到原出發(fā)的城鎮(zhèn)，問應(yīng)如何選擇行最后仍回到原出發(fā)的城鎮(zhèn)，問應(yīng)如何選擇行走路線可使總行程最短，這是運(yùn)籌學(xué)的一個走路線可使總行程最短，這是運(yùn)籌學(xué)的一個著名問題，實(shí)際中有很多問題可以歸結(jié)為這著名問題，實(shí)際中有很多問題可以歸結(jié)為這類問題。類問題。四、貨郎擔(dān)問題第50頁/共59頁 設(shè)設(shè) 是已知的是已知的n n個城鎮(zhèn)，城鎮(zhèn)個城鎮(zhèn)，城鎮(zhèn) 到城到城鎮(zhèn)鎮(zhèn) 的距離為的距離為 ，現(xiàn)求從，現(xiàn)求從 出發(fā)，經(jīng)各城鎮(zhèn)一出發(fā)，經(jīng)各城鎮(zhèn)一次且僅一次返回次且僅一次返回 的最短路程。若對的最短路程。若對n n個城鎮(zhèn)進(jìn)行排個城鎮(zhèn)進(jìn)行排列，有列，

40、有 (n(n一一1)!1)!2 2種方案，所以窮舉法是不現(xiàn)種方案，所以窮舉法是不現(xiàn)實(shí)的，這里介紹一種動態(tài)規(guī)劃方法。實(shí)的，這里介紹一種動態(tài)規(guī)劃方法。 貨郎擔(dān)問題也是求最短路徑問題，但與例貨郎擔(dān)問題也是求最短路徑問題，但與例4 4的最短的最短路問題有很大不同，建動態(tài)規(guī)劃模型時，雖然也可按城路問題有很大不同，建動態(tài)規(guī)劃模型時，雖然也可按城鎮(zhèn)數(shù)目鎮(zhèn)數(shù)目n n將問題分為將問題分為n n個階段。但是狀態(tài)變量不好選擇，個階段。但是狀態(tài)變量不好選擇，不容易滿足無后效性。為保持狀態(tài)間相互獨(dú)立，可按以不容易滿足無后效性。為保持狀態(tài)間相互獨(dú)立，可按以下方法建模：下方法建模：nvvv,21jvijd1viv1v第51頁/共59頁 設(shè)設(shè)S S表示從表示從 到到 中間所有可能經(jīng)過的城中間所有可能經(jīng)過的城市集合，市集合，S S實(shí)際上是包含除實(shí)際上是包含除 與與 兩個點(diǎn)之外其兩個點(diǎn)之外其余點(diǎn)的集合，但余點(diǎn)的集合，但S S中的點(diǎn)的個數(shù)要隨階段數(shù)改變。中的點(diǎn)的個數(shù)要隨階段數(shù)改變。 狀態(tài)變量狀態(tài)變量 表示：從表