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

1、第七章第七章 動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃 n多階段決策過(guò)程的最優(yōu)化多階段決策過(guò)程的最優(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ù)變量離散化的概念。如投資分配問(wèn)題先介紹連續(xù)變量離散化的概念。如投資分配問(wèn)題 的一般靜態(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)轉(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)( 11 11 0 nn kkkk sx kk sf nnksfxgsf kk 其狀態(tài)轉(zhuǎn)移方程為其狀態(tài)轉(zhuǎn)移方程為: : kkk xss 1 由于由于 與與 都是連續(xù)變量，當(dāng)各階段指標(biāo)都是連續(xù)變量，當(dāng)各階段指標(biāo) 沒(méi)沒(méi) 有特殊性而較為復(fù)雜時(shí)，有特殊性而較為復(fù)雜時(shí)， 要求出要求出

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

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)變量和決 策變量只在給出的離散點(diǎn)上取值，見例策變量只在給出的離散點(diǎn)上取值，見例6 6。 （ 3 3 ） 按 逆 序 方 法 ， 逐 步 遞 推 求按 逆 序 方 法 ， 逐 步 遞 推 求 出出 ，最后求出最，最后求出最 優(yōu)資金分配方案。優(yōu)資金

5、分配方案。 )(,),( 11 sfsf nn 問(wèn)如何分配投資數(shù)額才能使總效益最大問(wèn)如何分配投資數(shù)額才能使總效益最大? ? 2 333222111 2)(,9)(,4)(xxgxxgxxg 例例5 5 某公司有資金某公司有資金1010萬(wàn)元，若投資于項(xiàng)目萬(wàn)元，若投資于項(xiàng)目 i(i=1,2,3)i(i=1,2,3)的投資額為的投資額為x xi i時(shí)，其效益分別為：時(shí)，其效益分別為： 例例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六個(gè)點(diǎn)，即狀態(tài)變量六個(gè)點(diǎn)，即狀態(tài)變量 集合為集合為 2 k s 10,8,6,4,2,0 允許允許決策集合為決策集合為 ， 與與 均在分割點(diǎn)上取值。均在分割點(diǎn)上取值。 kk sx0 k x k s 動(dòng)態(tài)規(guī)劃基本方程為：動(dòng)態(tài)規(guī)劃基本方程為： 0)( 1 ,2, 3)()(max)( 44 1 0 sf kxsfxgsf kkkkk sx kk kk 當(dāng)當(dāng)k=3k=3時(shí)，時(shí)， 2 3 0 33 2max)( 33 x sx sf 式中式中 與與 的集合均為：的集合均為： 計(jì)算結(jié)果見表計(jì)算結(jié)果見表7-17-1。 3 s 3 x10,8,6,4,2,0 3 s

7、)( 33 sf * 3 x 0246810 083272128200 0246810 當(dāng)當(dāng)k=3時(shí)，時(shí)， 表表7-1 2 3 0 33 2max)( 33 x sx sf 當(dāng)當(dāng)k=2時(shí)，時(shí)， )(9max)( 2232 0 22 22 xsfxsf sx 0)( 1 , 2 , 3)()(max)( 44 1 0 sf kxsfxgsf kkkkk sx kk kk 計(jì)算結(jié)果見表計(jì)算結(jié)果見表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 當(dāng)當(dāng)k=1時(shí)，時(shí)， 0)( 1 , 2 , 3)()(max)( 44 1 0 sf kxsfxgsf kkkkk sx kk kk 計(jì)算結(jié)果見表計(jì)算結(jié)果見表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結(jié)論完全相同。結(jié)

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

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

11、23 單位重量(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à)值。 基本方程：基本方程： 0)( 1 , 2 , 3)()(max)( 44 11 / , 1 , 0 sf ksfxcsf

12、 kkkk asx kk kkk 當(dāng)階段當(dāng)階段k=3時(shí)，有時(shí)，有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 當(dāng)階段當(dāng)階段k=2時(shí)，有時(shí)，有)(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 當(dāng)階段當(dāng)階段k=1時(shí)，有時(shí)，有)(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 二、生產(chǎn)經(jīng)營(yíng)問(wèn)題二、生產(chǎn)經(jīng)營(yíng)問(wèn)題 在生產(chǎn)和經(jīng)營(yíng)管理中，經(jīng)常遇到如何合在生產(chǎn)和經(jīng)營(yíng)管理中，經(jīng)常遇到如何合 理地安排生產(chǎn)計(jì)劃、采購(gòu)計(jì)劃以及倉(cāng)庫(kù)的存理地安排生產(chǎn)計(jì)劃、采購(gòu)計(jì)劃以及倉(cāng)庫(kù)的存 貨計(jì)劃和銷售計(jì)劃，使總效益最高的問(wèn)題。貨計(jì)劃和銷售計(jì)劃，使總效益最高的問(wèn)題。 下面通過(guò)例子來(lái)說(shuō)明對(duì)不同特點(diǎn)問(wèn)題的

14、不同下面通過(guò)例子來(lái)說(shuō)明對(duì)不同特點(diǎn)問(wèn)題的不同 處理技巧處理技巧。 例例2 生產(chǎn)與存貯問(wèn)題生產(chǎn)與存貯問(wèn)題 某工廠生產(chǎn)并銷售某種產(chǎn)品，已知今后四個(gè)月市場(chǎng)需求預(yù)測(cè)如表，又每月某工廠生產(chǎn)并銷售某種產(chǎn)品，已知今后四個(gè)月市場(chǎng)需求預(yù)測(cè)如表，又每月 生產(chǎn)生產(chǎn)j單位產(chǎn)品費(fèi)用為：?jiǎn)挝划a(chǎn)品費(fèi)用為： )()6,2, 1(3 )0(0 )( 千元jj j jC 每月庫(kù)存每月庫(kù)存j j單位產(chǎn)品的費(fèi)用為單位產(chǎn)品的費(fèi)用為 ，該廠最大庫(kù)存容量為該廠最大庫(kù)存容量為3 3單單 位，每月最大生產(chǎn)能力為位，每月最大生產(chǎn)能力為6 6單位，計(jì)劃開始和計(jì)劃期末庫(kù)存量都是單位，計(jì)劃開始和計(jì)劃期末庫(kù)存量都是零零。試制定試制定 四個(gè)月四個(gè)月的生產(chǎn)計(jì)

15、劃，在滿足用戶需求條件下總費(fèi)用最小。假設(shè)第的生產(chǎn)計(jì)劃，在滿足用戶需求條件下總費(fèi)用最小。假設(shè)第i+1i+1個(gè)月的庫(kù)個(gè)月的庫(kù) 存量是第存量是第i i個(gè)月個(gè)月可銷售量可銷售量與該月用戶需求量之差；而第與該月用戶需求量之差；而第i i個(gè)月的可銷售量是本個(gè)月的可銷售量是本 月初庫(kù)存量與產(chǎn)量之和。月初庫(kù)存量與產(chǎn)量之和。 )(5 . 0)(千元jjE )(月i )(需求 i g 1234 2324 用動(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)

16、變量：狀態(tài)變量： 為第為第k k個(gè)月初的庫(kù)存量。個(gè)月初的庫(kù)存量。 k s (3)(3)決策變量：決策變量： 為第為第k k個(gè)月的生產(chǎn)量。個(gè)月的生產(chǎn)量。 k u (4)(4)狀態(tài)轉(zhuǎn)移方程：狀態(tài)轉(zhuǎn)移方程： kkkk guss 1 (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）基本方程：）基本方程： )( 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，所以，所以u(píng)4=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，所以，所以u(píng)3=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，所以，所以u(píng)2=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，所以，所以u(píng)1=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 采購(gòu)與銷售問(wèn)題采購(gòu)與銷售問(wèn)題 某商店在未來(lái)的某商店在未來(lái)的4 4個(gè)月里，準(zhǔn)備利用它的一個(gè)倉(cāng)庫(kù)來(lái)專門經(jīng)銷某種商個(gè)月里，準(zhǔn)備利用它的一個(gè)倉(cāng)庫(kù)來(lái)專門經(jīng)銷某種商 品，倉(cāng)庫(kù)最大容量能貯存這種商品品，倉(cāng)庫(kù)最大容量能貯存這種商品l000l000單位。假定該商店每月只能出賣倉(cāng)單位。假定該商店每月只能出賣倉(cāng) 庫(kù)現(xiàn)有的貨。當(dāng)商店在某月購(gòu)貨時(shí)，下月初才能到貨。預(yù)測(cè)該商品未來(lái)四庫(kù)現(xiàn)有的貨。

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

21、第：第k月初時(shí)倉(cāng)庫(kù)中的存貨量月初時(shí)倉(cāng)庫(kù)中的存貨量(含上月訂貨含上月訂貨)。 決策變量決策變量 ：第：第k月賣出的貨物數(shù)量。月賣出的貨物數(shù)量。 ：第：第k月訂購(gòu)的貨物數(shù)量。月訂購(gòu)的貨物數(shù)量。 狀態(tài)轉(zhuǎn)移方程：狀態(tài)轉(zhuǎn)移方程： k s k x k y 最優(yōu)指標(biāo)函數(shù)最優(yōu)指標(biāo)函數(shù) ：第：第k k月初存貨量為月初存貨量為 時(shí)，從第時(shí)，從第k k月到月到4 4月末所獲最大月末所獲最大 利潤(rùn)。利潤(rùn)。 則則有逆序遞推關(guān)系式為：有逆序遞推關(guān)系式為： 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 當(dāng)當(dāng)k=4時(shí)時(shí) 顯然，決策應(yīng)取顯然，決策應(yīng)取 時(shí)才有最大值時(shí)才有最大值 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 當(dāng)當(dāng)k=3時(shí)時(shí) 這個(gè)階段需解一個(gè)線性規(guī)劃問(wèn)題：這個(gè)階段需解一個(gè)線性規(guī)劃問(wèn)題： 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 因?yàn)橹挥袃蓚€(gè)變量因?yàn)橹挥袃蓚€(gè)變量x3, y3 ，可以用圖解法，也可以用單純形法，求解得到：，可以用圖解法，也可以用單純形法，求解得到： 時(shí)有最大值時(shí)有最大值 0, 1000 1764max 33 333 33 333 yx sxy sx syxz 1000, * 33 * 3 ysx 333 136000)(ssf 當(dāng)當(dāng)k=2時(shí)時(shí) 求解線性規(guī)劃問(wèn)題：求解線性規(guī)劃問(wèn)題： 得得 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 當(dāng)當(dāng)k=1時(shí)時(shí) 求解一個(gè)線性規(guī)劃問(wèn)題：求解一個(gè)線性規(guī)劃問(wèn)題： 得得 )(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)策略見下表。最大利潤(rùn)為最優(yōu)策略見下表。最大利潤(rùn)為1600016000。 月份月份期前存貨期前存貨售出量售出量購(gòu)進(jìn)量購(gòu)進(jìn)量 15005000 2001000 3100010001000 4100010000 例例

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

27、段，段，k k1 1，2 2，3 3，4 4，5 5。 狀態(tài)變量狀態(tài)變量 ：第：第k k周的原料實(shí)際價(jià)格。周的原料實(shí)際價(jià)格。 k x 決策變量決策變量 ：第：第k周如采購(gòu)周如采購(gòu) 則則 1，若不采購(gòu)，若不采購(gòu) 則則 =0 =0。 另外用另外用 表示：當(dāng)?shù)诒硎荆寒?dāng)?shù)趉周決定等待，而在以后采購(gòu)時(shí)的采購(gòu)價(jià)格期望值。周決定等待，而在以后采購(gòu)時(shí)的采購(gòu)價(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)系式為： )( kk sfk s 解解

28、 本例與前面所討論的確定型問(wèn)題不同，狀態(tài)的轉(zhuǎn)移不能完全確定，而本例與前面所討論的確定型問(wèn)題不同，狀態(tài)的轉(zhuǎn)移不能完全確定，而 按某種已知的按某種已知的概率分布概率分布取值，即屬于取值，即屬于隨機(jī)型隨機(jī)型動(dòng)態(tài)規(guī)劃問(wèn)題。動(dòng)態(tài)規(guī)劃問(wèn)題。 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。 當(dāng)當(dāng)k=5時(shí)時(shí) 因?yàn)槿羟八闹苌形促?gòu)買，則無(wú)論本周價(jià)格如何，該部門都因?yàn)槿羟八闹苌形促?gòu)買，則無(wú)論本周價(jià)格如何，該部門都 必須購(gòu)買，所以必須購(gòu)買，所以 )(

29、 1700700 )( 1600600 )( 1500500 )5(5 * 55 * 55 * 55 采購(gòu)當(dāng) 采購(gòu)當(dāng) 采購(gòu)當(dāng) xs xs xs sf 當(dāng)當(dāng)k=4時(shí)時(shí) 由于由于 所以所以 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 等待當(dāng) 采購(gòu)當(dāng) 采購(gòu)當(dāng) xs xs xs 當(dāng)當(dāng)k=3時(shí)時(shí) 由于由于 所以所以 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 或當(dāng) 當(dāng) 當(dāng)當(dāng)k=2時(shí)時(shí) 同理同理 8 .551,min,min)( 22222 sSssf E 07006008 .551 1500500 * 22 * 22 xs xs 或當(dāng) 當(dāng) 當(dāng)當(dāng)k=1時(shí)時(shí) 26.536,min,min)( 11111 sSssf E 070060026.536 1500500 * 11 * 11 xs xs 或當(dāng) 當(dāng) 所以，最優(yōu)采購(gòu)策

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

32、( 11111 fffsf 三、設(shè)備更新問(wèn)題三、設(shè)備更新問(wèn)題 從經(jīng)濟(jì)上分析，一臺(tái)設(shè)備應(yīng)該從經(jīng)濟(jì)上分析，一臺(tái)設(shè)備應(yīng)該 使用多少年更新最使用多少年更新最 合算，這就是設(shè)備更新問(wèn)題。一般來(lái)說(shuō)，一臺(tái)設(shè)備在比合算，這就是設(shè)備更新問(wèn)題。一般來(lái)說(shuō)，一臺(tái)設(shè)備在比 較新時(shí)，年運(yùn)轉(zhuǎn)量大，經(jīng)濟(jì)收入高，故障少，維修費(fèi)用較新時(shí)，年運(yùn)轉(zhuǎn)量大，經(jīng)濟(jì)收入高，故障少，維修費(fèi)用 少，但隨著使用年限的增加，年運(yùn)轉(zhuǎn)量減少因而收入減少，但隨著使用年限的增加，年運(yùn)轉(zhuǎn)量減少因而收入減 少，故障變多少，故障變多, ,維修費(fèi)用增加。如果更新可提高年凈收維修費(fèi)用增加。如果更新可提高年凈收 入，但是當(dāng)年要支出一筆數(shù)額較大的購(gòu)買費(fèi)，為了比較入，但是

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

34、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) ，表示一年以后的單位收入價(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è)備已使

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

36、，使用一臺(tái)已用了年初，使用一臺(tái)已用了sk年的設(shè)備，到第年的設(shè)備，到第n年年 末的最大收益，則可得如下的逆序動(dòng)態(tài)規(guī)劃方程：末的最大收益，則可得如下的逆序動(dòng)態(tài)規(guī)劃方程： 實(shí)際上實(shí)際上， 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 當(dāng) 當(dāng) 例例5 5 設(shè)某臺(tái)新設(shè)備的年效益及年均維修費(fèi)、更新凈費(fèi)用如表設(shè)某臺(tái)新設(shè)備的年效益及年均維修費(fèi)、更新凈費(fèi)用如表7-

37、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)( 5555 5555 55 scur susr sf Rx Kx 5 5 當(dāng) 當(dāng) 狀態(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 當(dāng) 當(dāng) 5 . 3 5 . 15 . 05 15 . 4 max K) 1 (x5當(dāng) =2.5 2 . 25 . 05 5 . 14 max)2( 5 fK)2(x5當(dāng) =2 5 . 25 . 05 275. 3 max)3( 5 f R)3(x5當(dāng) =1.5 35 .05 5 .23 max)4( 5 fR)2(x 5 當(dāng) 役齡役齡 項(xiàng)目項(xiàng)目 012345 效益效益 54.54 3.7 5 32.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í)，

39、狀態(tài)變量狀態(tài)變量s4可取可取1，2，3。 =6.5 役齡役齡 項(xiàng)目項(xiàng)目 012345 效益效益 54.54 3.7 5 32.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)( 54444 454444 44 fscur sfsusr sf Rx Kx 4 4 當(dāng) 當(dāng) ) 1 ( 4 f 5 . 35 . 15 . 05 5 . 215 . 4 max R) 1 (x4當(dāng) )2( 4 f = 5 . 32 . 25 . 05 215 . 4 max=5.8R)2(x4當(dāng) ) 3( 4 f = 5

40、. 35 . 25 . 05 5 . 1275. 3 max=5.5R) 3(x 4 當(dāng) 當(dāng)當(dāng)k=3時(shí)時(shí)， 狀態(tài)變量狀態(tài)變量s3可取可取1，2。 =9.5 役齡役齡 項(xiàng)目項(xiàng)目 012345 效益效益 54.54 3.7 5 32.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)( 43333 343333 33 fscur sfsusr sf Rx Kx 3 3 當(dāng) 當(dāng) ) 1 ( 3 f 5 . 65 . 15 . 05 8 . 515 . 4 maxR) 1 (x3當(dāng) )2( 3 f= 5 .

41、 62 . 25 . 05 5 . 515 . 4 max =8.8 R)2(x3當(dāng) 當(dāng)當(dāng)k=2時(shí)時(shí)， 狀態(tài)變量狀態(tài)變量s2只能取只能取1 役齡役齡 項(xiàng)目項(xiàng)目 012345 效益效益 54.54 3.7 5 32.5 維修費(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)( 32222 232222 22 fscur sfsusr sf Rx Kx 2 2 當(dāng) 當(dāng) ) 1 ( 2 f 5 . 95 . 15 . 05 8 . 815 . 4 maxR) 1 (x2當(dāng) 當(dāng)當(dāng)k=1時(shí)時(shí)， 狀態(tài)變量狀

42、態(tài)變量s1只能取只能取0 役齡役齡 項(xiàng)目項(xiàng)目 012345 效益效益 54.54 3.7 5 32.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)( 21111 121111 11 fscur sfsusr sf Rx Kx 1 1 當(dāng) 當(dāng) 5 .125 . 05 . 05 5 .125 . 05 max)0( 1 f Kx)0( 1 上述計(jì)算遞推回去，當(dāng)上述計(jì)算遞推回去，當(dāng) 時(shí)，由狀態(tài)轉(zhuǎn)移方程，時(shí)，由狀態(tài)轉(zhuǎn)移方程， 則則 則查則查 得：得： 狀態(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)策略為： ，即第一年初購(gòu)買的設(shè)備到第二、三、四年初，即第一年初購(gòu)買的設(shè)備到第二、三、四年初 各更新一次，用到第各更新一次，用到第5年末，其總效益為年末，其總效益為17萬(wàn)元。萬(wàn)元。 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 貨郎擔(dān)問(wèn)題一般提法為：一個(gè)貨郎從某貨郎擔(dān)問(wèn)題一般提法為：一個(gè)貨郎從某 城鎮(zhèn)出發(fā)，經(jīng)過(guò)若干個(gè)城鎮(zhèn)一次，且僅一次，城鎮(zhèn)出發(fā)，經(jīng)過(guò)若干個(gè)城鎮(zhèn)一次，且僅一次， 最后仍回到原出發(fā)的城鎮(zhèn)，問(wèn)應(yīng)如何選擇行最后仍回到原出發(fā)的城鎮(zhèn)，問(wèn)應(yīng)如何選擇行 走路線可使總行程最短，這是運(yùn)籌學(xué)的一個(gè)走路線可使總行程最短，這是運(yùn)籌學(xué)的一個(gè) 著名問(wèn)題，實(shí)際中有很多問(wèn)題可以歸結(jié)為這著名問(wèn)題，實(shí)際中有很多

46、問(wèn)題可以歸結(jié)為這 類問(wèn)題。類問(wèn)題。 四、貨郎擔(dān)問(wèn)題四、貨郎擔(dān)問(wè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)問(wèn)題也是求最短路徑問(wèn)題，但與例貨郎擔(dān)問(wèn)題也是求最短路徑問(wèn)題，但與例4 4的最短路的最短路 問(wèn)題有很大不同，建動(dòng)態(tài)規(guī)劃模型時(shí)，雖然也可按城鎮(zhèn)數(shù)問(wèn)題有很大不同，建動(dòng)態(tài)規(guī)劃模型時(shí)，雖然也可按城鎮(zhèn)數(shù) 目目n n將問(wèn)題分為將問(wèn)題分為n n個(gè)階段。但是狀態(tài)變量不好選擇，不容易個(gè)階段。但是狀態(tài)變量不好選擇，不容易 滿足無(wú)后效性。為保持狀態(tài)間相互獨(dú)立，可按以下方法建滿足無(wú)后效性。為保持狀態(tài)間相互獨(dú)立，可按以下方法建 模：模： n vvv, 21