1、第四節 動態規劃在經濟管理中的應用 連續變量的離散化解法連續變量的離散化解法 先介紹連續變量離散化的概念。如投資分配問題先介紹連續變量離散化的概念。如投資分配問題的一般靜態模型為：的一般靜態模型為： niiixgz1)(max), 2 , 1(01nixaxinii模型中：階段數、總投資、各階段投資數、各階段收益、決策變量、狀模型中：階段數、總投資、各階段投資數、各階段收益、決策變量、狀態變量態變量 狀態轉移方程、基本方程、指標函數、最優指標函數狀態轉移方程、基本方程、指標函數、最優指標函數第1頁/共59頁建立它的動態規劃模型，其基本方程為：建立它的動態規劃模型，其基本方程為：0)(1 ,2,

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

3、割， 的大小可的大小可依據問題所要求的精度以及計算機的容依據問題所要求的精度以及計算機的容量來定。量來定。 amsk,2,0第3頁/共59頁 (2) (2) 規定狀態變量規定狀態變量 及決策變量及決策變量 只在離散點只在離散點 上取值，相應的指標上取值，相應的指標函數函數 就被定義在這些離散值上，于是遞推方就被定義在這些離散值上，于是遞推方程就變為：程就變為： kskxam,2,0)(kksf0)()()(max)(111,2, 1 ,0nnkkkqpkksfpsfpgsf其中 pxsqkk,第4頁/共59頁 作為離散化例子，在例作為離散化例子，在例5 5中規定狀態變量和決中規定狀態變量和決策

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

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

6、 230332max)(33xsxsf第8頁/共59頁式中式中 與與 的集合均為：的集合均為： 計算結果見表計算結果見表7-17-1。 3s3x10,8,6,4,2,03s)(33sf*3x02468100832721282000246810當k=3時， 表7-1 230332max)(33xsxsf第9頁/共59頁當k=2時， )(9max)(223202222xsfxsfsx0)(1 , 2 , 3)()(max)(4410sfkxsfxgsfkkkkksxkkkk計算結果見表計算結果見表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頁當k=1時， 0)(1 , 2 , 3)()(max)(4410sfkxsfxgsfkkkkksxkkkk計算結果見表計算結果見表7-37-3。 表7-3 )(4max)(1121100111xsfxsfx1s1x21fg 1f*1x 10 101010 10100246810200136886050402000第11頁/共59頁最大收益為最大收益為 ，與

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

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

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

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

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

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

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

15、：最優指標函數： 表示第表示第k k月狀態為月狀態為 時，采取時，采取最佳策略生產，從本月到計劃結束最佳策略生產，從本月到計劃結束( (第第4 4月末月末) )的生產與存貯最的生產與存貯最低費用。低費用。（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個月里，準備利用它的一個倉庫來專門經銷某種商個月里，準備利用它的一個倉庫來專門經銷某種商品，倉庫最大容量能貯存這種商

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

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

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

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

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

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

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

25、kES)17. 7()()17. 7(1 , 2 , 3 , 4,min)(55555bDsssfakDsSssfkkkEkkkkD為狀態集合500，600，700。 第30頁/共59頁當k=5時 因為若前四周尚未購買，則無論本周價格如何，該部門都必須購買，所以 )( 1700700)( 1600600)( 1500500)5(5*55*55*55采購當采購當采購當xsxsxssf第31頁/共59頁當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等待當采購當采購當xsxsxs第32頁/共59頁當k=3時 由于 所以 5746104 .06003 .05003 .0)700(4 .0)600(3 .0)500(3 .04443fffSE574,min,min)(3333333sSssfEDs07006005741500500*33*33xsxs或當當第33頁/共59頁當k=2時 同理 8 .551,min,min)(22222sSssfE07006008 .5511500500*22*22xsxs或當當第34頁/共59頁當k=1時 26.536,m

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

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

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

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

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

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

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

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

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

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

37、 1 (3fRx *3推出 ，查 14s) 1 (4fRx *415s) 1 (5fKx *5最優策略為： ，即第一年初購買的設備到第二、三、四年初各更新一次，用到第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頁 貨郎擔問題一般提法為：一個貨郎從某貨郎擔問題一般提法為：一個貨郎

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

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