運籌學74動態(tài)規(guī)劃應用舉例

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

2、各階段投資數(shù)、各階段收益、決策變量、狀模型中：階段數(shù)、總投資、各階段投資數(shù)、各階段收益、決策變量、狀 態(tài)變量態(tài)變量 狀態(tài)轉移方程、基本方程、指標函數(shù)、最優(yōu)指標函數(shù)狀態(tài)轉移方程、基本方程、指標函數(shù)、最優(yōu)指標函數(shù) 建立它的動態(tài)規(guī)劃模型，其基本方程為：建立它的動態(tài)規(guī)劃模型，其基本方程為： 0)( 1 ,2, 1,)()(max)( 11 11 0 nn kkkk sx kk sf nnksfxgsf kk 其狀態(tài)轉移方程為其狀態(tài)轉移方程為: : kkk xss 1 由于由于 與與 都是連續(xù)變量，當各階段指標都是連續(xù)變量，當各階段指標 沒沒 有特殊性而較為復雜時，有特殊性而較為復雜時， 要求出要求出

3、會比較困難，因而求會比較困難，因而求 全過程的最優(yōu)策略也就相當不容易，這時常常采用把連續(xù)變量全過程的最優(yōu)策略也就相當不容易，這時常常采用把連續(xù)變量 離散化的辦法求其數(shù)值解。具體做法如下：離散化的辦法求其數(shù)值解。具體做法如下： k s k x)( kk xg )( kk sf （1 1） 令令 ， 把區(qū)間把區(qū)間 0 0，aa進行分割，進行分割， 的大小可的大小可 依據(jù)問題所要求的精度以及計算機的容依據(jù)問題所要求的精度以及計算機的容 量來定。量來定。 ams k ,2,0 (2) (2) 規(guī)定狀態(tài)變量規(guī)定狀態(tài)變量 及決策變量及決策變量 只在離散點只在離散點 上取值，相應的指標上取值，相應的指標 函

4、數(shù)函數(shù) 就被定義在這些離散值上，于是遞推方就被定義在這些離散值上，于是遞推方 程就變?yōu)椋撼叹妥優(yōu)椋?k s k x am,2,0 )( kk sf 0)( )()(max)( 11 1 ,2, 1 ,0 nn kkk qp kk sf psfpgsf 其中其中 pxsq kk , 作為離散化例子，在例作為離散化例子，在例5 5中規(guī)定狀態(tài)變量和決中規(guī)定狀態(tài)變量和決 策變量只在給出的離散點上取值，見例策變量只在給出的離散點上取值，見例6 6。 （ 3 3 ） 按 逆 序 方 法 ， 逐 步 遞 推 求按 逆 序 方 法 ， 逐 步 遞 推 求 出出 ，最后求出最，最后求出最 優(yōu)資金分配方案。優(yōu)資金

5、分配方案。 )(,),( 11 sfsf nn 問如何分配投資數(shù)額才能使總效益最大問如何分配投資數(shù)額才能使總效益最大? ? 2 333222111 2)(,9)(,4)(xxgxxgxxg 例例5 5 某公司有資金某公司有資金1010萬元，若投資于項目萬元，若投資于項目 i(i=1,2,3)i(i=1,2,3)的投資額為的投資額為x xi i時，其效益分別為：時，其效益分別為： 例例6 6 連續(xù)變量的離散化解法連續(xù)變量的離散化解法 )3,2, 1(,0 10 . 294max 321 2 321 ix xxx ts xxxZ i 解解 令令 ，將區(qū)間，將區(qū)間00，1010分割成分割成0 0，2

6、 2，4 4，6 6，8 8， 1010六個點，即狀態(tài)變量六個點，即狀態(tài)變量 集合為集合為 2 k s 10,8,6,4,2,0 允許允許決策集合為決策集合為 ， 與與 均在分割點上取值。均在分割點上取值。 kk sx0 k x k s 動態(tài)規(guī)劃基本方程為：動態(tài)規(guī)劃基本方程為： 0)( 1 ,2, 3)()(max)( 44 1 0 sf kxsfxgsf kkkkk sx kk kk 當當k=3k=3時，時， 2 3 0 33 2max)( 33 x sx sf 式中式中 與與 的集合均為：的集合均為： 計算結果見表計算結果見表7-17-1。 3 s 3 x10,8,6,4,2,0 3 s

7、)( 33 sf * 3 x 0246810 083272128200 0246810 當當k=3時，時， 表表7-1 2 3 0 33 2max)( 33 x sx sf 當當k=2時，時， )(9max)( 2232 0 22 22 xsfxsf sx 0)( 1 , 2 , 3)()(max)( 44 1 0 sf kxsfxgsf kkkkk sx kk kk 計算結果見表計算結果見表7-27-2。 2 s 2 x 32 fg 2 f * 2 x 0246810 00 20 2 40 2 4 60 2 4 6 80 2 4 6 8 10 0 8 18 32 26 3672 50 44

8、54128 90 68 62 72200 146 108 86 80 90 0 18 36 72 128 200 0 24 0 0 0 表表7-2 7-2 當當k=1時，時， 0)( 1 , 2 , 3)()(max)( 44 1 0 sf kxsfxgsf kkkkk sx kk kk 計算結果見表計算結果見表7-37-3。 表表7-3 )(4max)( 1121 100 11 1 xsfxsf x 1 s 1 x 21 fg 1 f * 1 x 10 1010 10 1010 0246810 20013688605040 200 0 最大收益為最大收益為 ，與例，與例5 5結論完全相同。結

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

10、(i=1,2,n)，問旅行者應如何選擇攜帶各種物品的件，問旅行者應如何選擇攜帶各種物品的件 數(shù)，以使總價值最大？數(shù)，以使總價值最大？ ), 2 , 1(0 )(max 1 1 nix axa xcz i n i ii n i ii 且為整數(shù) 例例1 有一輛最大貨運量為有一輛最大貨運量為10t的卡車，用以裝載的卡車，用以裝載3種貨物，種貨物， 每種貨物的單位重量及相應單位價值見下表，應如何裝載可每種貨物的單位重量及相應單位價值見下表，應如何裝載可 使總價值最大？使總價值最大？ ) 3 , 2 , 1(0 10543 654max 321 321 ix xxx xxxz i 且為整數(shù) 貨物編號i1

11、23 單位重量(t)345 單位價值ci456 逆序解法：逆序解法： 階段階段k： k=1,2,3 狀態(tài)變量狀態(tài)變量sk:第第k階段可以裝載第階段可以裝載第k種到第種到第3種貨物的重量。種貨物的重量。 決策變量決策變量xk:決定裝載第決定裝載第k種貨物的數(shù)量。種貨物的數(shù)量。 狀態(tài)轉移方程狀態(tài)轉移方程:sk+1=sk-akxk 最優(yōu)指標函數(shù)最優(yōu)指標函數(shù)fk(sk):當可裝載重量為當可裝載重量為sk,裝載第裝載第k種到第種到第3種貨物所獲得的種貨物所獲得的 最大價值。最大價值。 基本方程：基本方程： 0)( 1 , 2 , 3)()(max)( 44 11 / , 1 , 0 sf ksfxcsf

12、 kkkk asx kk kkk 當階段當階段k=3時，有時，有6max)( 3 5/, 0 33 33 xsf sx s3012345678910 x3000000 10 10 10 10 10 1 2 c3+f4000000 60 60 60 60 60 6 12 f3000006666612 x3*00000111112 當階段當階段k=2時，有時，有)(5max)( 332 4/, 0 22 22 sfxsf sx s2012345678910 x200000 10 10 10 10 1 20 1 20 1 2 c2+f300000 5+06 56 56 56 5 106 5+6 10

13、12 5+6 10 f200005666101112 x2*00001000210 223 4xss 當階段當階段k=1時，有時，有)(3max)( 221 3/10, 0 11 1 sfxsf x s110 x10 1 2 3 c1+f312 4+6 8+5 12 f213 x1*2 112 3xss 二、生產經營問題二、生產經營問題 在生產和經營管理中，經常遇到如何合在生產和經營管理中，經常遇到如何合 理地安排生產計劃、采購計劃以及倉庫的存理地安排生產計劃、采購計劃以及倉庫的存 貨計劃和銷售計劃，使總效益最高的問題。貨計劃和銷售計劃，使總效益最高的問題。 下面通過例子來說明對不同特點問題的

14、不同下面通過例子來說明對不同特點問題的不同 處理技巧處理技巧。 例例2 生產與存貯問題生產與存貯問題 某工廠生產并銷售某種產品，已知今后四個月市場需求預測如表，又每月某工廠生產并銷售某種產品，已知今后四個月市場需求預測如表，又每月 生產生產j單位產品費用為：單位產品費用為： )()6,2, 1(3 )0(0 )( 千元jj j jC 每月庫存每月庫存j j單位產品的費用為單位產品的費用為 ，該廠最大庫存容量為該廠最大庫存容量為3 3單單 位，每月最大生產能力為位，每月最大生產能力為6 6單位，計劃開始和計劃期末庫存量都是單位，計劃開始和計劃期末庫存量都是零零。試制定試制定 四個月四個月的生產計

15、劃，在滿足用戶需求條件下總費用最小。假設第的生產計劃，在滿足用戶需求條件下總費用最小。假設第i+1i+1個月的庫個月的庫 存量是第存量是第i i個月個月可銷售量可銷售量與該月用戶需求量之差；而第與該月用戶需求量之差；而第i i個月的可銷售量是本個月的可銷售量是本 月初庫存量與產量之和。月初庫存量與產量之和。 )(5 . 0)(千元jjE )(月i )(需求 i g 1234 2324 用動態(tài)規(guī)劃方法求解時，對有關概念作如下分析：用動態(tài)規(guī)劃方法求解時，對有關概念作如下分析： (1) (1) 階段：每個月為一個階段，階段：每個月為一個階段，k k1 1，2 2，3 3，4 4。 (2) (2)狀態(tài)

16、變量：狀態(tài)變量： 為第為第k k個月初的庫存量。個月初的庫存量。 k s (3)(3)決策變量：決策變量： 為第為第k k個月的生產量。個月的生產量。 k u (4)(4)狀態(tài)轉移方程：狀態(tài)轉移方程： kkkk guss 1 (5)(5)最優(yōu)指標函數(shù)：最優(yōu)指標函數(shù)： 表示第表示第k k月狀態(tài)為月狀態(tài)為 時，采取時，采取 最佳策略生產，從本月到計劃結束最佳策略生產，從本月到計劃結束( (第第4 4月末月末) )的生產與存貯最的生產與存貯最 低費用。低費用。 （6 6）基本方程：）基本方程： )( kk sf k s 0)( 1 , 2 , 3 , 4)()()(min)( 55 11 sf ks

17、fsEuCsf kkkk u kk k k4，s5=s4+u4-g4=0，所以，所以u4=g4-s4=4-s4，s4可取可取0，1，2，3。 0)()(min)( 44 3 , 2, 1 , 0 44 4 sEuCsf u s40123 u44321 C+E+f576+0.55+14+1.5 f476.565.5 u4*4321 k3，s4=s3+u3-g3，所以，所以u3=s4+ g3-s3，s3可取可取0，1，2，3。 s30123 u32 3 4 51 2 3 40 1 2 30 1 2 C+E+f45+7 6+6.5 7+6 8+5.5 4.5+7 5.5+6.5 6.5+6 7.5+

18、5.51+7 5+6.5 6+6 7+5.5 1.5+6.5 5.5+6 6.5+5.5 f31211.588 u3*2100 k2，s3=s2+u2-g2，所以，所以u2=s3+ g2-s2， s2可取可取0，1，2，3。 s20123 u23 4 5 62 3 4 51 2 3 40 1 2 3 C+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.5 u2*5430 k1，s2=s1+u1-g1，所以，所以u1=s2+

19、 g1-s1， s1可取可取0。 s10 u12 3 4 5 C+E+f25+16 6+15.5 7+15 8+13.5 f121 u1*2 反推回去，反推回去， u1*=2， u2*=5， u3*=0， u4*=4。 例例3 3 采購與銷售問題采購與銷售問題 某商店在未來的某商店在未來的4 4個月里，準備利用它的一個倉庫來專門經銷某種商個月里，準備利用它的一個倉庫來專門經銷某種商 品，倉庫最大容量能貯存這種商品品，倉庫最大容量能貯存這種商品l000l000單位。假定該商店每月只能出賣倉單位。假定該商店每月只能出賣倉 庫現(xiàn)有的貨。當商店在某月購貨時，下月初才能到貨。預測該商品未來四庫現(xiàn)有的貨。

20、當商店在某月購貨時，下月初才能到貨。預測該商品未來四 個月的買賣價格如表個月的買賣價格如表7 7_12_12所示，假定商店在所示，假定商店在1 1月開始經銷時，倉庫貯有該月開始經銷時，倉庫貯有該 商品商品500500單位。試問若不計庫存費用，該商店應如何制定單位。試問若不計庫存費用，該商店應如何制定1 1月至月至4 4月的訂購月的訂購 與銷售計劃，使預期獲利最大。與銷售計劃，使預期獲利最大。 月份（月份（k） 購買單價（購買單價（ck）銷售單價（銷售單價（pk） 11012 298 31113 41517 解解 按月份劃分為按月份劃分為4個階段，個階段，k=l，2，3，4 狀態(tài)變量狀態(tài)變量 ：

21、第：第k月初時倉庫中的存貨量月初時倉庫中的存貨量(含上月訂貨含上月訂貨)。 決策變量決策變量 ：第：第k月賣出的貨物數(shù)量。月賣出的貨物數(shù)量。 ：第：第k月訂購的貨物數(shù)量。月訂購的貨物數(shù)量。 狀態(tài)轉移方程：狀態(tài)轉移方程： k s k x k y 最優(yōu)指標函數(shù)最優(yōu)指標函數(shù) ：第：第k k月初存貨量為月初存貨量為 時，從第時，從第k k月到月到4 4月末所獲最大月末所獲最大 利潤。利潤。 則則有逆序遞推關系式為：有逆序遞推關系式為： kkkk xyss 1 )( kk sfk s 0)( 1 , 2 , 3 , 4)(max)( 55 11 )(10000 0 sf ksfycxpsf kkkkkk

22、 xsy sx kk kkk kk 當當k=4時時 顯然，決策應取顯然，決策應取 時才有最大值時才有最大值 1517max)( 44 )(10000 0 44 444 44 yxsf xsy sx 0, * 44 * 4 ysx 444 17)(ssf 0)( 1 , 2 , 3 , 4)(max)( 55 11 )(10000 0 sf ksfycxpsf kkkkkk xsy sx kk kkk kk 當當k=3時時 這個階段需解一個線性規(guī)劃問題：這個階段需解一個線性規(guī)劃問題： 1764max )(171113max )(1113max)( 333 )(10000 0 33333 )(10

23、000 0 4433 )(10000 0 33 333 33 333 33 333 33 syx xysyx sfyxsf xsy sx xsy sx xsy sx 因為只有兩個變量因為只有兩個變量x3, y3 ，可以用圖解法，也可以用單純形法，求解得到：，可以用圖解法，也可以用單純形法，求解得到： 時有最大值時有最大值 0, 1000 1764max 33 333 33 333 yx sxy sx syxz 1000, * 33 * 3 ysx 333 136000)(ssf 當當k=2時時 求解線性規(guī)劃問題：求解線性規(guī)劃問題： 得得 45136000max )(13600098max )(

24、98max)( 222 )(10000 0 22222 )(10000 0 222322 )(10000 0 22 222 22 222 22 222 22 yxs xysyx xysfyxsf xsy sx xsy sx xsy sx 0, 1000 45136000max 22 222 22 222 yx sxy sx yxsz 22222 91000044000136000)(ssssf 2 * 2 * 2 1000,0syx 當當k=1時時 求解一個線性規(guī)劃問題：求解一個線性規(guī)劃問題： 得得 )(1012max)( 111211 )(10000 0 11 111 11 xysfyxsf

25、 xsy sx 500 1 s 145003max )(9100001012max)500( 11 5000 5000 11111 5000 5000 1 11 1 11 1 yx xysyxf xy x xy x 0, 500 500 314500max 11 11 1 11 yx xy x yxz 16000500314500)500(, 0,500 1 * 1 * 1 fyx 最優(yōu)策略見下表。最大利潤為最優(yōu)策略見下表。最大利潤為1600016000。 月份月份期前存貨期前存貨售出量售出量購進量購進量 15005000 2001000 3100010001000 4100010000 例例

26、4 4 限期采購問題限期采購問題( (隨機型隨機型) ) 某部門欲采購一批原料，原料價格在五周內可能有某部門欲采購一批原料，原料價格在五周內可能有 所變動，已預測得該種原料今后五周內取不同單價的概所變動，已預測得該種原料今后五周內取不同單價的概 率如表率如表7-147-14所示。試確定該部門在五周內購進這批原料所示。試確定該部門在五周內購進這批原料 的最優(yōu)策略，使采購價格的的最優(yōu)策略，使采購價格的期望值期望值最小。最小。 原材料單價（元）原材料單價（元）概率概率 500 600 700 0.3 0.3 0.4 表表7-14 階段階段k k：可按采購期限可按采購期限( (周周) )分為分為5 5

27、段，段，k k1 1，2 2，3 3，4 4，5 5。 狀態(tài)變量狀態(tài)變量 ：第：第k k周的原料實際價格。周的原料實際價格。 k x 決策變量決策變量 ：第：第k周如采購周如采購 則則 1，若不采購，若不采購 則則 =0 =0。 另外用另外用 表示：當?shù)诒硎荆寒數(shù)趉周決定等待，而在以后采購時的采購價格期望值。周決定等待，而在以后采購時的采購價格期望值。 最優(yōu)指標函數(shù)最優(yōu)指標函數(shù) ：第：第k周實際價格為周實際價格為 時，從第時，從第k周至第周至第5周采取最周采取最 優(yōu)策略所花費的最低期望價格。優(yōu)策略所花費的最低期望價格。 則則有逆序遞推關系式為：有逆序遞推關系式為： )( kk sfk s 解解

28、 本例與前面所討論的確定型問題不同，狀態(tài)的轉移不能完全確定，而本例與前面所討論的確定型問題不同，狀態(tài)的轉移不能完全確定，而 按某種已知的按某種已知的概率分布概率分布取值，即屬于取值，即屬于隨機型隨機型動態(tài)規(guī)劃問題。動態(tài)規(guī)劃問題。 k s k xk x kE S )17. 7()( )17. 7(1 , 2 , 3 , 4,min)( 55555 bDsssf akDsSssf kkkEkkk k D為狀態(tài)集合為狀態(tài)集合500，600，700。 當當k=5時時 因為若前四周尚未購買，則無論本周價格如何，該部門都因為若前四周尚未購買，則無論本周價格如何，該部門都 必須購買，所以必須購買，所以 )(

29、 1700700 )( 1600600 )( 1500500 )5(5 * 55 * 55 * 55 采購當 采購當 采購當 xs xs xs sf 當當k=4時時 由于由于 所以所以 6107004 . 06003 . 05003 . 0 )700(4 . 0)600(3 . 0)500(3 . 0 5554 fffS E 610,min,min)( 44444 44 sSssf E Ds )(0700610 )( 1600600 )( 1500500 * 44 * 44 * 44 等待當 采購當 采購當 xs xs xs 當當k=3時時 由于由于 所以所以 5746104 .06003 .

30、05003 .0 )700(4 .0)600(3 .0)500(3 .0 4443 fffS E 574,min,min)( 33333 33 sSssf E Ds 0700600574 1500500 * 33 * 33 xs xs 或當 當 當當k=2時時 同理同理 8 .551,min,min)( 22222 sSssf E 07006008 .551 1500500 * 22 * 22 xs xs 或當 當 當當k=1時時 26.536,min,min)( 11111 sSssf E 070060026.536 1500500 * 11 * 11 xs xs 或當 當 所以，最優(yōu)采購策

31、略為：若第一、二、三周原料價格所以，最優(yōu)采購策略為：若第一、二、三周原料價格 為為500500，則立即采購，否則在以后的幾周內再采購。若第四，則立即采購，否則在以后的幾周內再采購。若第四 周價格為周價格為500500或或600600，則立即采購，否則等第五周再采購。，則立即采購，否則等第五周再采購。 而第五周時無論當時價格為多少都必須采購。而第五周時無論當時價格為多少都必須采購。 按照以上策略進行采購，期望價格為：按照以上策略進行采購，期望價格為： 525382.525 26.5364 . 026.5363 . 05003 . 0 )700(4 . 0)600(3 . 0)500(3 . 0)

32、( 11111 fffsf 三、設備更新問題三、設備更新問題 從經濟上分析，一臺設備應該從經濟上分析，一臺設備應該 使用多少年更新最使用多少年更新最 合算，這就是設備更新問題。一般來說，一臺設備在比合算，這就是設備更新問題。一般來說，一臺設備在比 較新時，年運轉量大，經濟收入高，故障少，維修費用較新時，年運轉量大，經濟收入高，故障少，維修費用 少，但隨著使用年限的增加，年運轉量減少因而收入減少，但隨著使用年限的增加，年運轉量減少因而收入減 少，故障變多少，故障變多, ,維修費用增加。如果更新可提高年凈收維修費用增加。如果更新可提高年凈收 入，但是當年要支出一筆數(shù)額較大的購買費，為了比較入，但是

33、當年要支出一筆數(shù)額較大的購買費，為了比較 不同決策的優(yōu)劣，常常要在一個較長的時間內考慮更新不同決策的優(yōu)劣，常常要在一個較長的時間內考慮更新 決策問題。決策問題。 設備更新問題一般提法：在已知一臺設備的效益函數(shù)設備更新問題一般提法：在已知一臺設備的效益函數(shù)r(t)， 維修費用函數(shù)維修費用函數(shù)u(t)及更新費用函數(shù)及更新費用函數(shù)c(t)條件下，要求在條件下，要求在n年內的年內的 每年年初作出決策，是繼續(xù)使用舊設備還是更換一臺新的，使每年年初作出決策，是繼續(xù)使用舊設備還是更換一臺新的，使 n年總效益最大。年總效益最大。 rk(t)：在第：在第k年設備已使用過年設備已使用過t年年(或稱役齡為或稱役齡為

34、t年年)，再使用，再使用1年時的年時的 效益。效益。 uk(t) ：在第：在第k年設備役齡為年設備役齡為t年，再使用一年的維修費用。年，再使用一年的維修費用。 ck(t) ：在第：在第k年賣掉年賣掉臺役齡為臺役齡為t年的設備，買進一臺新設備的更年的設備，買進一臺新設備的更 新凈費用。新凈費用。 為折扣因子為折扣因子(01) ，表示一年以后的單位收入價值相當于現(xiàn)，表示一年以后的單位收入價值相當于現(xiàn) 年的年的 單位。單位。 動態(tài)規(guī)劃模型動態(tài)規(guī)劃模型 階段變量階段變量k：k=1,2,n，表示計劃使用該設備的年限數(shù)。，表示計劃使用該設備的年限數(shù)。 狀態(tài)變量狀態(tài)變量sk: 第第k年初，設備年初，設備已使

35、用過已使用過的年數(shù)，即役齡。的年數(shù)，即役齡。 決策變量決策變量xk: 是第是第k年初更新（年初更新（Replacement），還是保留使用（，還是保留使用（keep） 舊設備，分別用舊設備，分別用R與與K表示。表示。 狀態(tài)轉移方程為：狀態(tài)轉移方程為： 階段指標為：階段指標為： 1 1 1 k k s s Rx Kx k k 當 當 指標函數(shù)為：指標函數(shù)為： )()0()0( )()( ),( kkkk kkkk kkj scur susr xsv Rx Kx k k 當 當 ), 2 , 1(),( , nkxsvV n kj kkjnk 最優(yōu)指標函數(shù)最優(yōu)指標函數(shù)fk(sk)表示第表示第k年初

36、，使用一臺已用了年初，使用一臺已用了sk年的設備，到第年的設備，到第n年年 末的最大收益，則可得如下的逆序動態(tài)規(guī)劃方程：末的最大收益，則可得如下的逆序動態(tài)規(guī)劃方程： 實際上實際上， 0)( )(),(max)( 11 11 nn kkkk RK k kk sf sfxsv x sf k 或 )18. 7( )18. 7( b a )()()0()0( )()()( max)( 11 11 kkkkkk kkkkkk kk sfscur sfsusr sf Rx Kx k k 當 當 例例5 5 設某臺新設備的年效益及年均維修費、更新凈費用如表設某臺新設備的年效益及年均維修費、更新凈費用如表7-

37、7- 1515所示。試確定今后所示。試確定今后5 5年內的更新策略，使總收益最大。年內的更新策略，使總收益最大。 （設（設 ） 1 )(trk )(tuk )(tck 役齡役齡 項目項目 012345 效益效益54.543.7532.5 維修費維修費0.5 11.522.53 更新費更新費0.51.52.22.533.5 解解 如前述建立動態(tài)規(guī)劃模型，如前述建立動態(tài)規(guī)劃模型，n=5 當當k=5時時， )()0()0( )()( max)( 5555 5555 55 scur susr sf Rx Kx 5 5 當 當 狀態(tài)變量狀態(tài)變量s5可取可取1，2，3，4。 )1 ()0()0( ) 1

38、() 1 ( max) 1 ( 555 55 5 cur ur f Rx Kx 5 5 當 當 5 . 3 5 . 15 . 05 15 . 4 max K) 1 (x5當 =2.5 2 . 25 . 05 5 . 14 max)2( 5 fK)2(x5當 =2 5 . 25 . 05 275. 3 max)3( 5 f R)3(x5當 =1.5 35 .05 5 .23 max)4( 5 fR)2(x 5 當 役齡役齡 項目項目 012345 效益效益 54.54 3.7 5 32.5 維修費維修費0.5 11.522.53 更新費更新費 0.51.52.22.533.5 當當k=4時時，

39、狀態(tài)變量狀態(tài)變量s4可取可取1，2，3。 =6.5 役齡役齡 項目項目 012345 效益效益 54.54 3.7 5 32.5 維修費維修費0.5 11.522.53 更新費更新費 0.51.52.22.533.5 ) 1 ()()0()0( ) 1()()( max)( 54444 454444 44 fscur sfsusr sf Rx Kx 4 4 當 當 ) 1 ( 4 f 5 . 35 . 15 . 05 5 . 215 . 4 max R) 1 (x4當 )2( 4 f = 5 . 32 . 25 . 05 215 . 4 max=5.8R)2(x4當 ) 3( 4 f = 5

40、. 35 . 25 . 05 5 . 1275. 3 max=5.5R) 3(x 4 當 當當k=3時時， 狀態(tài)變量狀態(tài)變量s3可取可取1，2。 =9.5 役齡役齡 項目項目 012345 效益效益 54.54 3.7 5 32.5 維修費維修費0.5 11.522.53 更新費更新費 0.51.52.22.533.5 ) 1 ()()0()0( ) 1()()( max)( 43333 343333 33 fscur sfsusr sf Rx Kx 3 3 當 當 ) 1 ( 3 f 5 . 65 . 15 . 05 8 . 515 . 4 maxR) 1 (x3當 )2( 3 f= 5 .

41、 62 . 25 . 05 5 . 515 . 4 max =8.8 R)2(x3當 當當k=2時時， 狀態(tài)變量狀態(tài)變量s2只能取只能取1 役齡役齡 項目項目 012345 效益效益 54.54 3.7 5 32.5 維修費維修費0.5 11.522.53 更新費更新費 0.51.52.22.533.5 =12.5 ) 1 ()()0()0( ) 1()()( max)( 32222 232222 22 fscur sfsusr sf Rx Kx 2 2 當 當 ) 1 ( 2 f 5 . 95 . 15 . 05 8 . 815 . 4 maxR) 1 (x2當 當當k=1時時， 狀態(tài)變量狀

42、態(tài)變量s1只能取只能取0 役齡役齡 項目項目 012345 效益效益 54.54 3.7 5 32.5 維修費維修費0.5 11.522.53 更新費更新費 0.51.52.22.533.5 =17 ) 1 ()()0()0( ) 1()()( max)( 21111 121111 11 fscur sfsusr sf Rx Kx 1 1 當 當 5 .125 . 05 . 05 5 .125 . 05 max)0( 1 f Kx)0( 1 上述計算遞推回去，當上述計算遞推回去，當 時，由狀態(tài)轉移方程，時，由狀態(tài)轉移方程， 則則 則查則查 得：得： 狀態(tài)狀態(tài) ，查：，查： Kx )0( 1 R

43、x RxfsKxs s 1 * 22211 2 1 )1 (11得，查知 Rx sKxs s 2 322 3 1 11推出 ) 1 ( 3 f Rx * 3 推出推出 ，查，查 1 4 s ) 1 ( 4 f Rx * 4 1 5 s) 1 ( 5 fKx * 5 最優(yōu)策略為：最優(yōu)策略為： ，即第一年初購買的設備到第二、三、四年初，即第一年初購買的設備到第二、三、四年初 各更新一次，用到第各更新一次，用到第5年末，其總效益為年末，其總效益為17萬元。萬元。 KRRRK, k5，s5可取可取1,2,3,4。 s51234 u5K RK RK RK R v5+f64.5-1 5-0.5-1.54-

44、1.5 5-0.5-2.23.75-2 5-0.5-2.53-2.5 5-0.5-3 f53.52.521.5 u5*KKRR k4, s4可取可取1,2,3。 s4123 u4K RK RK R v4+f54.5-1+2.5 5-0.5-1.5+3.5 4-1.5+2 5-0.5-2.2+3.53.75-2+1.5 5-0.5-2.5+3.5 f46.55.85.5 u4*RRR k3，s3可取可取1,2。 s312 u3K RK R v3+f44.5-1+5.8 5-0.5-1.5+6.54-1.5+5.5 5-0.5-2.2+6.5 f49.58.8 u4*RR k2, s2可取可取1。

45、 s21 u2K R v3+f24.5-1+8.8 5-0.5-1.5+9.5 f212.5 u2*R k1, s2可取可取0。 s10 u1K R v1+f25-0.5+12.5 5-0.5-0.5+12.5 f117 u1*K 貨郎擔問題一般提法為：一個貨郎從某貨郎擔問題一般提法為：一個貨郎從某 城鎮(zhèn)出發(fā)，經過若干個城鎮(zhèn)一次，且僅一次，城鎮(zhèn)出發(fā)，經過若干個城鎮(zhèn)一次，且僅一次， 最后仍回到原出發(fā)的城鎮(zhèn)，問應如何選擇行最后仍回到原出發(fā)的城鎮(zhèn)，問應如何選擇行 走路線可使總行程最短，這是運籌學的一個走路線可使總行程最短，這是運籌學的一個 著名問題，實際中有很多問題可以歸結為這著名問題，實際中有很多

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