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

1、第七章第七章 動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃 n多階段決策過程的最優(yōu)化多階段決策過程的最優(yōu)化n動(dòng)態(tài)規(guī)劃的基本概念和基本原理動(dòng)態(tài)規(guī)劃的基本概念和基本原理 n動(dòng)態(tài)規(guī)劃模型的建立與求解動(dòng)態(tài)規(guī)劃模型的建立與求解n動(dòng)態(tài)規(guī)劃在經(jīng)濟(jì)管理中的應(yīng)用動(dòng)態(tài)規(guī)劃在經(jīng)濟(jì)管理中的應(yīng)用 第四節(jié)第四節(jié) 動(dòng)態(tài)規(guī)劃在經(jīng)濟(jì)管理中的應(yīng)用動(dòng)態(tài)規(guī)劃在經(jīng)濟(jì)管理中的應(yīng)用 連續(xù)變量的離散化解法連續(xù)變量的離散化解法 先介紹連續(xù)變量離散化的概念。如投資分配問題先介紹連續(xù)變量離散化的概念。如投資分配問題的一般靜態(tài)模型為：的一般靜態(tài)模型為： niiixgz1)(max), 2 , 1(01nixaxinii模型中：階段數(shù)、總投資、各階段投資數(shù)、各階段收益、決策變量

2、、狀模型中：階段數(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ù)建立它的動(dòng)態(tài)規(guī)劃模型，其基本方程為：建立它的動(dòng)態(tài)規(guī)劃模型，其基本方程為：0)(1 ,2, 1,)()(max)(11110nnkkkksxkksfnnksfxgsfkk其狀態(tài)轉(zhuǎn)移方程為其狀態(tài)轉(zhuǎn)移方程為: :kkkxss1 由于由于 與與 都是連續(xù)變量，當(dāng)各階段指標(biāo)都是連續(xù)變量，當(dāng)各階段指標(biāo) 沒沒有特殊性而較為復(fù)雜時(shí)，有特殊性而較為復(fù)雜時(shí)， 要求出要求出 會(huì)比較困難，因而求會(huì)比較困難，因而求全過程的最優(yōu)策略也就相當(dāng)不容易，這時(shí)

3、常常采用把連續(xù)變量全過程的最優(yōu)策略也就相當(dāng)不容易，這時(shí)常常采用把連續(xù)變量離散化的辦法求其數(shù)值解。具體做法如下：離散化的辦法求其數(shù)值解。具體做法如下： kskx)(kkxg)(kksf（1 1） 令令 ，把區(qū)間把區(qū)間 0 0，aa進(jìn)行分割，進(jìn)行分割， 的大小可的大小可依據(jù)問題所要求的精度以及計(jì)算機(jī)的容依據(jù)問題所要求的精度以及計(jì)算機(jī)的容量來定。量來定。 amsk,2,0 (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)椋?kskx

4、am,2,0)(kksf0)()()(max)(111,2, 1 ,0nnkkkqpkksfpsfpgsf其中其中 pxsqkk, 作為離散化例子，在例作為離散化例子，在例5 5中規(guī)定狀態(tài)變量和決中規(guī)定狀態(tài)變量和決策變量只在給出的離散點(diǎn)上取值，見例策變量只在給出的離散點(diǎn)上取值，見例6 6。 （ 3 3 ） 按 逆 序 方 法 ， 逐 步 遞 推 求按 逆 序 方 法 ， 逐 步 遞 推 求出出 ，最后求出最，最后求出最優(yōu)資金分配方案。優(yōu)資金分配方案。)(,),(11sfsfnn問如何分配投資數(shù)額才能使總效益最大問如何分配投資數(shù)額才能使總效益最大? ?23332221112)(,9)(,4)(x

5、xgxxgxxg例例5 5 某公司有資金某公司有資金1010萬元，若投資于項(xiàng)目萬元，若投資于項(xiàng)目i(i=1,2,3)i(i=1,2,3)的投資額為的投資額為x xi i時(shí)，其效益分別為：時(shí)，其效益分別為： 例例6 6 連續(xù)變量的離散化解法連續(xù)變量的離散化解法)3,2, 1(,010.294max3212321ixxxxtsxxxZi解解 令令 ，將區(qū)間，將區(qū)間00，1010分割成分割成0 0，2 2，4 4，6 6，8 8，1010六個(gè)點(diǎn)，即狀態(tài)變量六個(gè)點(diǎn)，即狀態(tài)變量 集合為集合為 2ks10,8,6,4,2,0允許允許決策集合為決策集合為 ， 與與 均在分割點(diǎn)上取值。均在分割點(diǎn)上取值。 kk

6、sx0kxks動(dòng)態(tài)規(guī)劃基本方程為：動(dòng)態(tài)規(guī)劃基本方程為： 0)(1 ,2, 3)()(max)(4410sfkxsfxgsfkkkkksxkkkk當(dāng)當(dāng)k=3k=3時(shí)，時(shí)， 230332max)(33xsxsf式中式中 與與 的集合均為：的集合均為： 計(jì)算結(jié)果見表計(jì)算結(jié)果見表7-17-1。 3s3x10,8,6,4,2,03s)(33sf*3x02468100832721282000246810當(dāng)當(dāng)k=3時(shí)，時(shí)， 表表7-1 230332max)(33xsxsf當(dāng)當(dāng)k=2時(shí)，時(shí)， )(9max)(223202222xsfxsfsx0)(1 , 2 , 3)()(max)(4410sfkxsfxgs

7、fkkkkksxkkkk計(jì)算結(jié)果見表計(jì)算結(jié)果見表7-27-2。 2s2x32fg 2f*2x024681000 20 2 40 2 4 60 2 4 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 當(dāng)當(dāng)k=1時(shí)，時(shí)， 0)(1 , 2 , 3)()(max)(4410sfkxsfxgsfkkkkksxkkkk計(jì)算結(jié)果見表計(jì)算結(jié)果見表7-37-3。 表表7-3 )(4max)(1121100111xsfxsfx1s1x21

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

9、擇裝入背包，第i種種物品的單件重量為物品的單件重量為ai kg，其價(jià)值是攜帶數(shù)量，其價(jià)值是攜帶數(shù)量xi的函數(shù)的函數(shù)ci(xi)(i=1,2,n)，問旅行者應(yīng)如何選擇攜帶各種物品的件，問旅行者應(yīng)如何選擇攜帶各種物品的件數(shù)，以使總價(jià)值最大？數(shù)，以使總價(jià)值最大？ ), 2 , 1(0)(max11nixaxaxcziniiiniii且為整數(shù)例例1 有一輛最大貨運(yùn)量為有一輛最大貨運(yùn)量為10t的卡車，用以裝載的卡車，用以裝載3種貨物，種貨物，每種貨物的單位重量及相應(yīng)單位價(jià)值見下表，應(yīng)如何裝載可每種貨物的單位重量及相應(yīng)單位價(jià)值見下表，應(yīng)如何裝載可使總價(jià)值最大？使總價(jià)值最大？ ) 3 , 2 , 1(010

10、543654max321321ixxxxxxxzi且為整數(shù)貨物編號(hào)i123單位重量(t)345單位價(jià)值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種貨物所獲得的種貨物所獲得的最大價(jià)值。最大價(jià)值?；痉匠蹋夯痉匠蹋?)(1 , 2 , 3)()(max)(4411

11、/ , 1 , 0sfksfxcsfkkkkasxkkkkk當(dāng)階段當(dāng)階段k=3時(shí)，有時(shí)，有6max)(35/, 03333xsfsxs3012345678910 x3000000 10 10 10 10 10 1 2c3+f4000000 60 60 60 60 60 6 12f3000006666612x3*00000111112當(dāng)階段當(dāng)階段k=2時(shí)，有時(shí)，有)(5max)(3324/, 02222sfxsfsx s2012345678910 x200000 10 10 10 10 1 20 1 20 1 2c2+f300000 5+06 56 56 56 5 106 5+6 1012 5+

12、6 10f200005666101112x2*000010002102234xss當(dāng)階段當(dāng)階段k=1時(shí)，有時(shí)，有)(3max)(2213/10, 0111sfxsfx s110 x10 1 2 3c1+f312 4+6 8+5 12f213x1*21123xss二、生產(chǎn)經(jīng)營問題二、生產(chǎn)經(jīng)營問題 在生產(chǎn)和經(jīng)營管理中，經(jīng)常遇到如何合在生產(chǎn)和經(jīng)營管理中，經(jīng)常遇到如何合理地安排生產(chǎn)計(jì)劃、采購計(jì)劃以及倉庫的存理地安排生產(chǎn)計(jì)劃、采購計(jì)劃以及倉庫的存貨計(jì)劃和銷售計(jì)劃，使總效益最高的問題。貨計(jì)劃和銷售計(jì)劃，使總效益最高的問題。下面通過例子來說明對(duì)不同特點(diǎn)問題的不同下面通過例子來說明對(duì)不同特點(diǎn)問題的不同處理技巧

13、處理技巧。 例例2 生產(chǎn)與存貯問題生產(chǎn)與存貯問題 某工廠生產(chǎn)并銷售某種產(chǎn)品，已知今后四個(gè)月市場需求預(yù)測如表，又每月某工廠生產(chǎn)并銷售某種產(chǎn)品，已知今后四個(gè)月市場需求預(yù)測如表，又每月生產(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單位，計(jì)劃開始和計(jì)劃期末庫存量都是單位，計(jì)劃開始和計(jì)劃期末庫存量都是零零。試制定試制定四個(gè)月四個(gè)月的生產(chǎn)計(jì)劃，在滿足用戶需求條件下總費(fèi)用最小。假設(shè)第的生產(chǎn)計(jì)劃，在滿足用戶需求

14、條件下總費(fèi)用最小。假設(shè)第i+1i+1個(gè)月的庫個(gè)月的庫存量是第存量是第i i個(gè)月個(gè)月可銷售量可銷售量與該月用戶需求量之差；而第與該月用戶需求量之差；而第i i個(gè)月的可銷售量是本個(gè)月的可銷售量是本月初庫存量與產(chǎn)量之和。月初庫存量與產(chǎn)量之和。 )(5 . 0)(千元jjE)(月i)(需求ig12342324用動(dòng)態(tài)規(guī)劃方法求解時(shí)，對(duì)有關(guān)概念作如下分析：用動(dòng)態(tài)規(guī)劃方法求解時(shí)，對(duì)有關(guān)概念作如下分析：(1) (1) 階段：每個(gè)月為一個(gè)階段，階段：每個(gè)月為一個(gè)階段，k k1 1，2 2，3 3，4 4。 (2) (2)狀態(tài)變量：狀態(tài)變量： 為第為第k k個(gè)月初的庫存量。個(gè)月初的庫存量。 ks(3)(3)決策變

15、量：決策變量： 為第為第k k個(gè)月的生產(chǎn)量。個(gè)月的生產(chǎn)量。 ku(4)(4)狀態(tài)轉(zhuǎn)移方程：狀態(tài)轉(zhuǎn)移方程： kkkkguss1(5)(5)最優(yōu)指標(biāo)函數(shù)：最優(yōu)指標(biāo)函數(shù)： 表示第表示第k k月狀態(tài)為月狀態(tài)為 時(shí)，采取時(shí)，采取最佳策略生產(chǎn)，從本月到計(jì)劃結(jié)束最佳策略生產(chǎn)，從本月到計(jì)劃結(jié)束( (第第4 4月末月末) )的生產(chǎn)與存貯最的生產(chǎn)與存貯最低費(fèi)用。低費(fèi)用。（6 6）基本方程：）基本方程： )(kksfks0)(1 , 2 , 3 , 4)()()(min)(5511sfksfsEuCsfkkkkukkk k4，s5=s4+u4-g4=0，所以，所以u(píng)4=g4-s4=4-s4，s4可取可取0，1，2，

16、3。 0)()(min)(443 , 2, 1 , 0444sEuCsfus40123u44321C+E+f576+0.55+14+1.5f476.565.5u4*4321 k3，s4=s3+u3-g3，所以，所以u(píng)3=s4+ g3-s3，s3可取可取0，1，2，3。 s30123u32 3 4 51 2 3 40 1 2 30 1 2C+E+f45+7 6+6.5 7+6 8+5.5 4.5+7 5.5+6.5 6.5+6 7.5+5.51+7 5+6.5 6+6 7+5.5 1.5+6.5 5.5+6 6.5+5.5f31211.588u3*2100 k2，s3=s2+u2-g2，所以，所

17、以u(píng)2=s3+ g2-s2， s2可取可取0，1，2，3。 s20123u23 4 5 62 3 4 51 2 3 40 1 2 3C+E+f36+12 7+11.5 8+8 9+85.5+12 6.5+11.5 7.5+8 8.5+85+12 6+11.5 7+8 8+8 1.5+12 5.5+11.5 6.5+8 7.5+8 f21615.51513.5u2*5430 k1，s2=s1+u1-g1，所以，所以u(píng)1=s2+ g1-s1， s1可取可取0。 s10u12 3 4 5C+E+f25+16 6+15.5 7+15 8+13.5f121u1*2反推回去，反推回去， u1*=2， u2

18、*=5， u3*=0， u4*=4。例例3 3 采購與銷售問題采購與銷售問題 某商店在未來的某商店在未來的4 4個(gè)月里，準(zhǔn)備利用它的一個(gè)倉庫來專門經(jīng)銷某種商個(gè)月里，準(zhǔn)備利用它的一個(gè)倉庫來專門經(jīng)銷某種商品，倉庫最大容量能貯存這種商品品，倉庫最大容量能貯存這種商品l000l000單位。假定該商店每月只能出賣倉單位。假定該商店每月只能出賣倉庫現(xiàn)有的貨。當(dāng)商店在某月購貨時(shí)，下月初才能到貨。預(yù)測該商品未來四庫現(xiàn)有的貨。當(dāng)商店在某月購貨時(shí)，下月初才能到貨。預(yù)測該商品未來四個(gè)月的買賣價(jià)格如表個(gè)月的買賣價(jià)格如表7 7_12_12所示，假定商店在所示，假定商店在1 1月開始經(jīng)銷時(shí)，倉庫貯有該月開始經(jīng)銷時(shí)，倉庫貯

19、有該商品商品500500單位。試問若不計(jì)庫存費(fèi)用，該商店應(yīng)如何制定單位。試問若不計(jì)庫存費(fèi)用，該商店應(yīng)如何制定1 1月至月至4 4月的訂購月的訂購與銷售計(jì)劃，使預(yù)期獲利最大。與銷售計(jì)劃，使預(yù)期獲利最大。 月份（月份（k）購買單價(jià)（購買單價(jià)（ck）銷售單價(jià)（銷售單價(jià)（pk）110122983111341517解解 按月份劃分為按月份劃分為4個(gè)階段，個(gè)階段，k=l，2，3，4狀態(tài)變量狀態(tài)變量 ：第：第k月初時(shí)倉庫中的存貨量月初時(shí)倉庫中的存貨量(含上月訂貨含上月訂貨)。決策變量決策變量 ：第：第k月賣出的貨物數(shù)量。月賣出的貨物數(shù)量。 ：第：第k月訂購的貨物數(shù)量。月訂購的貨物數(shù)量。 狀態(tài)轉(zhuǎn)移方程：狀態(tài)轉(zhuǎn)

20、移方程： kskxky最優(yōu)指標(biāo)函數(shù)最優(yōu)指標(biāo)函數(shù) ：第：第k k月初存貨量為月初存貨量為 時(shí)，從第時(shí)，從第k k月到月到4 4月末所獲最大月末所獲最大利潤。利潤。則則有逆序遞推關(guān)系式為：有逆序遞推關(guān)系式為： kkkkxyss1)(kksfks0)(1 , 2 , 3 , 4)(max)(5511)(100000sfksfycxpsfkkkkkkxsysxkkkkkkk當(dāng)當(dāng)k=4時(shí)時(shí) 顯然，決策應(yīng)取顯然，決策應(yīng)取 時(shí)才有最大值時(shí)才有最大值1517max)(44)(1000004444444yxsfxsysx0,*44*4ysx44417)(ssf0)(1 , 2 , 3 , 4)(max)(551

21、1)(100000sfksfycxpsfkkkkkkxsysxkkkkkkk當(dāng)當(dāng)k=3時(shí)時(shí) 這個(gè)階段需解一個(gè)線性規(guī)劃問題：這個(gè)階段需解一個(gè)線性規(guī)劃問題： 1764max)(171113max)(1113max)(333)(10000033333)(1000004433)(10000033333333333333333syxxysyxsfyxsfxsysxxsysxxsysx因?yàn)橹挥袃蓚€(gè)變量因?yàn)橹挥袃蓚€(gè)變量x3, y3 ，可以用圖解法，也可以用單純形法，求解得到：，可以用圖解法，也可以用單純形法，求解得到： 時(shí)有最大值時(shí)有最大值 0,10001764max3333333333yxsxysxsyx

22、z1000,*33*3ysx333136000)(ssf當(dāng)當(dāng)k=2時(shí)時(shí) 求解線性規(guī)劃問題：求解線性規(guī)劃問題： 得得45136000max)(13600098max)(98max)(222)(10000022222)(100000222322)(10000022222222222222222yxsxysyxxysfyxsfxsysxxsysxxsysx0,100045136000max2222222222yxsxysxyxsz2222291000044000136000)(ssssf2*2*21000,0syx當(dāng)當(dāng)k=1時(shí)時(shí) 求解一個(gè)線性規(guī)劃問題：求解一個(gè)線性規(guī)劃問題： 得得)(1012max)

23、(111211)(1000001111111xysfyxsfxsysx 5001s145003max)(9100001012max)500(115000500011111500050001111111yxxysyxfxyxxyx0,500500314500max1111111yxxyxyxz16000500314500)500(, 0,5001*1*1fyx最優(yōu)策略見下表。最大利潤為最優(yōu)策略見下表。最大利潤為1600016000。 月份月份期前存貨期前存貨售出量售出量購進(jìn)量購進(jìn)量15005000200100031000100010004100010000例例4 4 限期采購問題限期采購問題(

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

25、狀態(tài)變量狀態(tài)變量 ：第：第k k周的原料實(shí)際價(jià)格。周的原料實(shí)際價(jià)格。 kx 決策變量決策變量 ：第：第k周如采購周如采購 則則 1，若不采購，若不采購 則則 =0 =0。 另外用另外用 表示：當(dāng)?shù)诒硎荆寒?dāng)?shù)趉周決定等待，而在以后采購時(shí)的采購價(jià)格期望值。周決定等待，而在以后采購時(shí)的采購價(jià)格期望值。 最優(yōu)指標(biāo)函數(shù)最優(yōu)指標(biāo)函數(shù) ：第：第k周實(shí)際價(jià)格為周實(shí)際價(jià)格為 時(shí)，從第時(shí)，從第k周至第周至第5周采取最周采取最優(yōu)策略所花費(fèi)的最低期望價(jià)格。優(yōu)策略所花費(fèi)的最低期望價(jià)格。則則有逆序遞推關(guān)系式為：有逆序遞推關(guān)系式為： )(kksfks解解 本例與前面所討論的確定型問題不同，狀態(tài)的轉(zhuǎn)移不能完全確定，而本例與前

26、面所討論的確定型問題不同，狀態(tài)的轉(zhuǎn)移不能完全確定，而按某種已知的按某種已知的概率分布概率分布取值，即屬于取值，即屬于隨機(jī)型隨機(jī)型動(dòng)態(tài)規(guī)劃問題。動(dòng)態(tài)規(guī)劃問題。 kskxkxkES)17. 7()()17. 7(1 , 2 , 3 , 4,min)(55555bDsssfakDsSssfkkkEkkkkD為狀態(tài)集合為狀態(tài)集合500，600，700。 當(dāng)當(dāng)k=5時(shí)時(shí) 因?yàn)槿羟八闹苌形促徺I，則無論本周價(jià)格如何，該部門都因?yàn)槿羟八闹苌形促徺I，則無論本周價(jià)格如何，該部門都必須購買，所以必須購買，所以 )( 1700700)( 1600600)( 1500500)5(5*55*55*55采購當(dāng)采購當(dāng)采購當(dāng)x

27、sxsxssf當(dāng)當(dāng)k=4時(shí)時(shí) 由于由于 所以所以 6107004 . 06003 . 05003 . 0)700(4 . 0)600(3 . 0)500(3 . 05554fffSE610,min,min)(4444444sSssfEDs)(0700610)( 1600600)( 1500500*44*44*44等待當(dāng)采購當(dāng)采購當(dāng)xsxsxs當(dāng)當(dāng)k=3時(shí)時(shí) 由于由于 所以所以 5746104 .06003 .05003 .0)700(4 .0)600(3 .0)500(3 .04443fffSE574,min,min)(3333333sSssfEDs07006005741500500*33*3

28、3xsxs或當(dāng)當(dāng)當(dāng)當(dāng)k=2時(shí)時(shí) 同理同理 8 .551,min,min)(22222sSssfE07006008 .5511500500*22*22xsxs或當(dāng)當(dāng)當(dāng)當(dāng)k=1時(shí)時(shí) 26.536,min,min)(11111sSssfE070060026.5361500500*11*11xsxs或當(dāng)當(dāng) 所以，最優(yōu)采購策略為：若第一、二、三周原料價(jià)格所以，最優(yōu)采購策略為：若第一、二、三周原料價(jià)格為為500500，則立即采購，否則在以后的幾周內(nèi)再采購。若第四，則立即采購，否則在以后的幾周內(nèi)再采購。若第四周價(jià)格為周價(jià)格為500500或或600600，則立即采購，否則等第五周再采購。，則立即采購，否則等第

29、五周再采購。而第五周時(shí)無論當(dāng)時(shí)價(jià)格為多少都必須采購。而第五周時(shí)無論當(dāng)時(shí)價(jià)格為多少都必須采購。 按照以上策略進(jìn)行采購，期望價(jià)格為：按照以上策略進(jìn)行采購，期望價(jià)格為： 525382.52526.5364 . 026.5363 . 05003 . 0)700(4 . 0)600(3 . 0)500(3 . 0)(11111fffsf三、設(shè)備更新問題三、設(shè)備更新問題 從經(jīng)濟(jì)上分析，一臺(tái)設(shè)備應(yīng)該從經(jīng)濟(jì)上分析，一臺(tái)設(shè)備應(yīng)該 使用多少年更新最使用多少年更新最合算，這就是設(shè)備更新問題。一般來說，一臺(tái)設(shè)備在比合算，這就是設(shè)備更新問題。一般來說，一臺(tái)設(shè)備在比較新時(shí)，年運(yùn)轉(zhuǎn)量大，經(jīng)濟(jì)收入高，故障少，維修費(fèi)用較新時(shí)，

30、年運(yùn)轉(zhuǎn)量大，經(jīng)濟(jì)收入高，故障少，維修費(fèi)用少，但隨著使用年限的增加，年運(yùn)轉(zhuǎn)量減少因而收入減少，但隨著使用年限的增加，年運(yùn)轉(zhuǎn)量減少因而收入減少，故障變多少，故障變多, ,維修費(fèi)用增加。如果更新可提高年凈收維修費(fèi)用增加。如果更新可提高年凈收入，但是當(dāng)年要支出一筆數(shù)額較大的購買費(fèi)，為了比較入，但是當(dāng)年要支出一筆數(shù)額較大的購買費(fèi)，為了比較不同決策的優(yōu)劣，常常要在一個(gè)較長的時(shí)間內(nèi)考慮更新不同決策的優(yōu)劣，常常要在一個(gè)較長的時(shí)間內(nèi)考慮更新決策問題。決策問題。 設(shè)備更新問題一般提法：在已知一臺(tái)設(shè)備的效益函數(shù)設(shè)備更新問題一般提法：在已知一臺(tái)設(shè)備的效益函數(shù)r(t)，維修費(fèi)用函數(shù)維修費(fèi)用函數(shù)u(t)及更新費(fèi)用函數(shù)及更

31、新費(fèi)用函數(shù)c(t)條件下，要求在條件下，要求在n年內(nèi)的年內(nèi)的每年年初作出決策，是繼續(xù)使用舊設(shè)備還是更換一臺(tái)新的，使每年年初作出決策，是繼續(xù)使用舊設(shè)備還是更換一臺(tái)新的，使n年總效益最大。年總效益最大。 rk(t)：在第：在第k年設(shè)備已使用過年設(shè)備已使用過t年年(或稱役齡為或稱役齡為t年年)，再使用，再使用1年時(shí)的年時(shí)的效益。效益。 uk(t) ：在第：在第k年設(shè)備役齡為年設(shè)備役齡為t年，再使用一年的維修費(fèi)用。年，再使用一年的維修費(fèi)用。 ck(t) ：在第：在第k年賣掉年賣掉臺(tái)役齡為臺(tái)役齡為t年的設(shè)備，買進(jìn)一臺(tái)新設(shè)備的更年的設(shè)備，買進(jìn)一臺(tái)新設(shè)備的更新凈費(fèi)用。新凈費(fèi)用。 為折扣因子為折扣因子(01)

32、 ，表示一年以后的單位收入價(jià)值相當(dāng)于現(xiàn)，表示一年以后的單位收入價(jià)值相當(dāng)于現(xiàn)年的年的 單位。單位。 動(dòng)態(tài)規(guī)劃模型動(dòng)態(tài)規(guī)劃模型階段變量階段變量k：k=1,2,n，表示計(jì)劃使用該設(shè)備的年限數(shù)。，表示計(jì)劃使用該設(shè)備的年限數(shù)。 狀態(tài)變量狀態(tài)變量sk: 第第k年初，設(shè)備年初，設(shè)備已使用過已使用過的年數(shù)，即役齡。的年數(shù)，即役齡。決策變量決策變量xk: 是第是第k年初更新（年初更新（Replacement），還是保留使用（，還是保留使用（keep）舊設(shè)備，分別用舊設(shè)備，分別用R與與K表示。表示。 狀態(tài)轉(zhuǎn)移方程為：狀態(tài)轉(zhuǎn)移方程為： 階段指標(biāo)為：階段指標(biāo)為： 111kkssRxKxkk當(dāng)當(dāng)指標(biāo)函數(shù)為：指標(biāo)函數(shù)為：

33、 )()0()0()()(),(kkkkkkkkkkjscursusrxsvRxKxkk當(dāng)當(dāng)), 2 , 1(),(,nkxsvVnkjkkjnk 最優(yōu)指標(biāo)函數(shù)最優(yōu)指標(biāo)函數(shù)fk(sk)表示第表示第k年初，使用一臺(tái)已用了年初，使用一臺(tái)已用了sk年的設(shè)備，到第年的設(shè)備，到第n年年末的最大收益，則可得如下的逆序動(dòng)態(tài)規(guī)劃方程：末的最大收益，則可得如下的逆序動(dòng)態(tài)規(guī)劃方程： 實(shí)際上實(shí)際上， 0)()(),(max)(1111nnkkkkRKkkksfsfxsvxsfk或)18. 7()18. 7(ba)()()0()0()()()(max)(1111kkkkkkkkkkkkkksfscursfsusrsf

34、RxKxkk當(dāng)當(dāng)例例5 5 設(shè)某臺(tái)新設(shè)備的年效益及年均維修費(fèi)、更新凈費(fèi)用如表設(shè)某臺(tái)新設(shè)備的年效益及年均維修費(fèi)、更新凈費(fèi)用如表7-7-1515所示。試確定今后所示。試確定今后5 5年內(nèi)的更新策略，使總收益最大。年內(nèi)的更新策略，使總收益最大。（設(shè)（設(shè) ） 1)(trk)(tuk)(tck役齡役齡項(xiàng)目項(xiàng)目012345效益效益54.543.7532.5維修費(fèi)維修費(fèi)0.5 11.522.53更新費(fèi)更新費(fèi)0.51.52.22.533.5解解 如前述建立動(dòng)態(tài)規(guī)劃模型，如前述建立動(dòng)態(tài)規(guī)劃模型，n=5 當(dāng)當(dāng)k=5時(shí)時(shí)， )()0()0()()(max)(5555555555scursusrsfRxKx55當(dāng)當(dāng)狀

35、態(tài)變量狀態(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.52 . 25 . 055 . 14max)2(5fK)2(x5當(dāng)=25 . 25 . 05275. 3max)3(5fR)3(x5當(dāng)=1.535 .055 .23max)4(5fR)2(x5當(dāng) 役齡役齡項(xiàng)目項(xiàng)目012345效益效益54.543.7532.5維修費(fèi)維修費(fèi)0.5 11.522.53更新費(fèi)更新費(fèi)0.51.52.22.533.5當(dāng)當(dāng)k=4時(shí)時(shí)， 狀態(tài)變量狀態(tài)變量s4可取可取

36、1，2，3。 =6.5 役齡役齡項(xiàng)目項(xiàng)目012345效益效益54.543.7532.5維修費(fèi)維修費(fèi)0.5 11.522.53更新費(fèi)更新費(fèi)0.51.52.22.533.5) 1 ()()0()0() 1()()(max)(5444445444444fscursfsusrsfRxKx44當(dāng)當(dāng)) 1 (4f5 . 35 . 15 . 055 . 215 . 4maxR) 1 (x4當(dāng))2(4f=5 . 32 . 25 . 05215 . 4max=5.8R)2(x4當(dāng)) 3(4f=5 . 35 . 25 . 055 . 1275. 3max=5.5R) 3(x4當(dāng)當(dāng)當(dāng)k=3時(shí)時(shí)， 狀態(tài)變量狀態(tài)變量s

37、3可取可取1，2。 =9.5 役齡役齡項(xiàng)目項(xiàng)目012345效益效益54.543.7532.5維修費(fèi)維修費(fèi)0.5 11.522.53更新費(fèi)更新費(fèi)0.51.52.22.533.5) 1 ()()0()0() 1()()(max)(4333334333333fscursfsusrsfRxKx33當(dāng)當(dāng)) 1 (3f5 . 65 . 15 . 058 . 515 . 4maxR) 1 (x3當(dāng))2(3f=5 . 62 . 25 . 055 . 515 . 4max=8.8R)2(x3當(dāng)當(dāng)當(dāng)k=2時(shí)時(shí)， 狀態(tài)變量狀態(tài)變量s2只能取只能取1 役齡役齡項(xiàng)目項(xiàng)目012345效益效益54.543.7532.5維修

38、費(fèi)維修費(fèi)0.5 11.522.53更新費(fèi)更新費(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) 1 (x2當(dāng)當(dāng)當(dāng)k=1時(shí)時(shí)， 狀態(tài)變量狀態(tài)變量s1只能取只能取0 役齡役齡項(xiàng)目項(xiàng)目012345效益效益54.543.7532.5維修費(fèi)維修費(fèi)0.5 11.522.53更新費(fèi)更新費(fèi)0.51.52.22.533.5=17 ) 1 ()()0()0() 1()()(max)(2111112111111fscursfs

39、usrsfRxKx11當(dāng)當(dāng)5 .125 . 05 . 055 .125 . 05max)0(1fKx)0(1 上述計(jì)算遞推回去，當(dāng)上述計(jì)算遞推回去，當(dāng) 時(shí)，由狀態(tài)轉(zhuǎn)移方程，時(shí)，由狀態(tài)轉(zhuǎn)移方程， 則則 則查則查 得：得：狀態(tài)狀態(tài) ，查：，查： Kx)0(1RxRxfsKxss1*2221121)1(11得，查知RxsKxss23223111推出) 1 (3fRx *3推出推出 ，查，查 14s) 1 (4fRx *415s) 1 (5fKx *5最優(yōu)策略為：最優(yōu)策略為： ，即第一年初購買的設(shè)備到第二、三、四年初，即第一年初購買的設(shè)備到第二、三、四年初各更新一次，用到第各更新一次，用到第5年末，其

40、總效益為年末，其總效益為17萬元。萬元。 KRRRK, k5，s5可取可取1,2,3,4。 s51234u5K RK RK RK Rv5+f64.5-1 5-0.5-1.54-1.5 5-0.5-2.23.75-2 5-0.5-2.53-2.5 5-0.5-3f53.52.521.5u5*KKRR k4, s4可取可取1,2,3。 s4123u4K RK RK Rv4+f54.5-1+2.5 5-0.5-1.5+3.54-1.5+2 5-0.5-2.2+3.53.75-2+1.5 5-0.5-2.5+3.5f46.55.85.5u4*RRR k3，s3可取可取1,2。 s312u3K RK R

41、v3+f44.5-1+5.8 5-0.5-1.5+6.54-1.5+5.5 5-0.5-2.2+6.5f49.58.8u4*RR k2, s2可取可取1。 s21u2K Rv3+f24.5-1+8.8 5-0.5-1.5+9.5f212.5u2*R k1, s2可取可取0。 s10u1K Rv1+f25-0.5+12.5 5-0.5-0.5+12.5f117u1*K 貨郎擔(dān)問題一般提法為：一個(gè)貨郎從某貨郎擔(dān)問題一般提法為：一個(gè)貨郎從某城鎮(zhèn)出發(fā)，經(jīng)過若干個(gè)城鎮(zhèn)一次，且僅一次，城鎮(zhèn)出發(fā)，經(jīng)過若干個(gè)城鎮(zhèn)一次，且僅一次，最后仍回到原出發(fā)的城鎮(zhèn)，問應(yīng)如何選擇行最后仍回到原出發(fā)的城鎮(zhèn)，問應(yīng)如何選擇行走路線

42、可使總行程最短，這是運(yùn)籌學(xué)的一個(gè)走路線可使總行程最短，這是運(yùn)籌學(xué)的一個(gè)著名問題，實(shí)際中有很多問題可以歸結(jié)為這著名問題，實(shí)際中有很多問題可以歸結(jié)為這類問題。類問題。四、貨郎擔(dān)問題四、貨郎擔(dān)問題 設(shè)設(shè) 是已知的是已知的n n個(gè)城鎮(zhèn)，城鎮(zhèn)個(gè)城鎮(zhèn)，城鎮(zhèn) 到城鎮(zhèn)到城鎮(zhèn) 的距離為的距離為 ，現(xiàn)求從，現(xiàn)求從 出發(fā)，經(jīng)各城鎮(zhèn)一次且僅一次出發(fā)，經(jīng)各城鎮(zhèn)一次且僅一次返回返回 的最短路程。若對(duì)的最短路程。若對(duì)n n個(gè)城鎮(zhèn)進(jìn)行排列，有個(gè)城鎮(zhèn)進(jìn)行排列，有 (n(n一一1)!1)!2 2種方案，所以窮舉法是不現(xiàn)實(shí)的，這里介紹一種方案，所以窮舉法是不現(xiàn)實(shí)的，這里介紹一種動(dòng)態(tài)規(guī)劃方法。種動(dòng)態(tài)規(guī)劃方法。 貨郎擔(dān)問題也是求最短路徑問題，但與例貨郎擔(dān)問題也是求最短路徑問題，但與例4 4的最短路的最短路問題有很大不同，建動(dòng)態(tài)規(guī)劃模型時(shí)，雖然也可按城鎮(zhèn)數(shù)問題有很大不同，建動(dòng)態(tài)規(guī)劃模型時(shí)，雖然也可按城鎮(zhèn)數(shù)目目n n將問題分為將問題分為n n個(gè)階段。但是狀態(tài)變量不好選擇，不容易個(gè)階段。但是狀態(tài)變量不好選擇，不容易滿足無后效性。為保持狀態(tài)間相互獨(dú)立，可按以下方法建滿足無后效性。為保持狀態(tài)間相互獨(dú)立，可按以下方法建模：模：nvvv,21jvijd1viv1v 設(shè)設(shè)S S表示從