第8章動(dòng)態(tài)規(guī)劃第1,2節(jié)學(xué)習(xí)教案

1、會(huì)計(jì)學(xué)1第第8章動(dòng)態(tài)章動(dòng)態(tài)(dngti)規(guī)劃第規(guī)劃第1,2節(jié)節(jié)第一頁(yè)，共78頁(yè)。2設(shè)備更新問(wèn)題、復(fù)合系統(tǒng)可靠性問(wèn)題及生產(chǎn)過(guò)程最優(yōu)控制等，并且取得了顯著的效果。第1頁(yè)/共78頁(yè)第二頁(yè)，共78頁(yè)。3 動(dòng)態(tài)規(guī)劃是用來(lái)解決多階段決策過(guò)程最優(yōu)化的一動(dòng)態(tài)規(guī)劃是用來(lái)解決多階段決策過(guò)程最優(yōu)化的一種數(shù)量方法。其特點(diǎn)在于，它可以種數(shù)量方法。其特點(diǎn)在于，它可以(ky)把一個(gè)把一個(gè)n 維維決策問(wèn)題變換為幾個(gè)一維最優(yōu)化問(wèn)題，從而一個(gè)一個(gè)決策問(wèn)題變換為幾個(gè)一維最優(yōu)化問(wèn)題，從而一個(gè)一個(gè)地去解決。地去解決。 需指出：動(dòng)態(tài)規(guī)劃是求解某類問(wèn)題的一種方法，需指出：動(dòng)態(tài)規(guī)劃是求解某類問(wèn)題的一種方法，是考察問(wèn)題的一種途徑，而不是一種算

2、法。必須對(duì)具是考察問(wèn)題的一種途徑，而不是一種算法。必須對(duì)具體問(wèn)題進(jìn)行具體分析，運(yùn)用動(dòng)態(tài)規(guī)劃的原理和方法，體問(wèn)題進(jìn)行具體分析，運(yùn)用動(dòng)態(tài)規(guī)劃的原理和方法，建立相應(yīng)的模型，然后再用動(dòng)態(tài)規(guī)劃方法去求解。建立相應(yīng)的模型，然后再用動(dòng)態(tài)規(guī)劃方法去求解。第2頁(yè)/共78頁(yè)第三頁(yè)，共78頁(yè)。412n狀態(tài)狀態(tài)決策決策狀態(tài)狀態(tài)決策決策狀態(tài)狀態(tài)狀態(tài)狀態(tài)決策決策第3頁(yè)/共78頁(yè)第四頁(yè)，共78頁(yè)。5第4頁(yè)/共78頁(yè)第五頁(yè)，共78頁(yè)。6所以多階段決策問(wèn)題也稱為序貫決策問(wèn)題。第5頁(yè)/共78頁(yè)第六頁(yè)，共78頁(yè)。7C4AB2B1C3C2C1D3D2D1E3E2E1F1F2G53136387668522552233333663441

3、8第6頁(yè)/共78頁(yè)第七頁(yè)，共78頁(yè)。8第7頁(yè)/共78頁(yè)第八頁(yè)，共78頁(yè)。9第8頁(yè)/共78頁(yè)第九頁(yè)，共78頁(yè)。10C4AB2B1C3C2C1D3D2D1E3E2E1F1F2G5313638766852255223333366344181階段2階段5階段3階段4階段6階段第9頁(yè)/共78頁(yè)第十頁(yè)，共78頁(yè)。11n窮舉法2*3*2*2*2*1=48第10頁(yè)/共78頁(yè)第十一頁(yè)，共78頁(yè)。12第11頁(yè)/共78頁(yè)第十二頁(yè)，共78頁(yè)。13第12頁(yè)/共78頁(yè)第十三頁(yè)，共78頁(yè)。14n如D2（B1）C1,C2,C3，若從B1出發(fā)選取C2，則C2是狀態(tài)B1在決策u2(B1)作用下的一個(gè)新的狀態(tài)，記為u2(B1)=C

4、2 第13頁(yè)/共78頁(yè)第十四頁(yè)，共78頁(yè)。15第14頁(yè)/共78頁(yè)第十五頁(yè)，共78頁(yè)。16的難點(diǎn)之一。第15頁(yè)/共78頁(yè)第十六頁(yè)，共78頁(yè)。17211132112211122( , )( , , , )( , , , , , )kkkksT s usT s u s usT s u s us u 圖示如下圖示如下(rxi)：狀態(tài)轉(zhuǎn)移方程是確定過(guò)狀態(tài)轉(zhuǎn)移方程是確定過(guò)程程(guchng)(guchng)由一個(gè)由一個(gè)狀態(tài)到另一個(gè)狀態(tài)的演狀態(tài)到另一個(gè)狀態(tài)的演變過(guò)程變過(guò)程(guchng)(guchng)。如果第如果第k k階段狀態(tài)變量階段狀態(tài)變量sksk的值、該階段的決策變的值、該階段的決策變量一經(jīng)確定，第

5、量一經(jīng)確定，第k+1k+1階段階段狀態(tài)變量狀態(tài)變量sk+1sk+1的值也就的值也就確定。確定。其狀態(tài)轉(zhuǎn)移方程其狀態(tài)轉(zhuǎn)移方程(fngchng)如下（一般形式）如下（一般形式）12ks1u1s2u2s3skuksk+1 能用動(dòng)態(tài)規(guī)劃方法求解的多階段決策過(guò)程是一類特殊的多階段決策過(guò)程，即能用動(dòng)態(tài)規(guī)劃方法求解的多階段決策過(guò)程是一類特殊的多階段決策過(guò)程，即具有無(wú)后效性具有無(wú)后效性的多階段決策過(guò)程。的多階段決策過(guò)程。第16頁(yè)/共78頁(yè)第十七頁(yè)，共78頁(yè)。18如果如果(rgu)(rgu)狀態(tài)變量不能滿足無(wú)后效性的要求，應(yīng)適當(dāng)?shù)馗淖儬顟B(tài)的定義或規(guī)定方法。狀態(tài)變量不能滿足無(wú)后效性的要求，應(yīng)適當(dāng)?shù)馗淖儬顟B(tài)的定義或

6、規(guī)定方法。),(),(),(122231112kkkkusTsusTsusTs 動(dòng)態(tài)規(guī)劃中能動(dòng)態(tài)規(guī)劃中能處理的狀態(tài)轉(zhuǎn)移處理的狀態(tài)轉(zhuǎn)移方程方程(fngchng)(fngchng)的形式。的形式。狀態(tài)具有無(wú)后效性的多階段決策狀態(tài)具有無(wú)后效性的多階段決策(juc)(juc)過(guò)程的狀態(tài)轉(zhuǎn)移方程如下過(guò)程的狀態(tài)轉(zhuǎn)移方程如下無(wú)后效性無(wú)后效性( (馬爾可夫性馬爾可夫性) )如果某階段狀態(tài)給定后，則在這個(gè)階段以后過(guò)程的發(fā)展不受這個(gè)階段以前各段狀態(tài)的影響；如果某階段狀態(tài)給定后，則在這個(gè)階段以后過(guò)程的發(fā)展不受這個(gè)階段以前各段狀態(tài)的影響；過(guò)程的過(guò)去歷史只能通過(guò)當(dāng)前的狀態(tài)去影響它未來(lái)的發(fā)展；過(guò)程的過(guò)去歷史只能通過(guò)當(dāng)前的

7、狀態(tài)去影響它未來(lái)的發(fā)展；構(gòu)造動(dòng)態(tài)規(guī)劃模型時(shí)，要充分注意是否滿足無(wú)后效性的要求；即構(gòu)造動(dòng)態(tài)規(guī)劃模型時(shí)，要充分注意是否滿足無(wú)后效性的要求；即狀態(tài)變量要滿足無(wú)后效性的要求狀態(tài)變量要滿足無(wú)后效性的要求；第17頁(yè)/共78頁(yè)第十八頁(yè)，共78頁(yè)。19推關(guān)系，即：nVk，n（sk，uk，sk+1，uk+1 ,，sn+1）=ksk，uk，Vk+1，n（sk+1， uk+1 ,，sn+1） 第18頁(yè)/共78頁(yè)第十九頁(yè)，共78頁(yè)。20(,)njjjj kv s u(,)njjjj kv s u第19頁(yè)/共78頁(yè)第二十頁(yè)，共78頁(yè)。21,1,()(,)knkkk nkknuufsopt Vs us第20頁(yè)/共78頁(yè)第

8、二十一頁(yè)，共78頁(yè)。22小結(jié)小結(jié)(xioji):(xioji):),()(1,susVoptsfnkknkkkuunk),(,111,1nkknkkkksusVus方程方程 : :狀態(tài)轉(zhuǎn)移方程狀態(tài)轉(zhuǎn)移方程),(1kkkkusTs概念概念 : : 階段變量階段變量k k狀態(tài)變量狀態(tài)變量s sk k決策變量決策變量u uk k; ;指標(biāo)指標(biāo): : ),(111,nkkkknknksususVV動(dòng)態(tài)規(guī)劃本質(zhì)上是多階段決策過(guò)程動(dòng)態(tài)規(guī)劃本質(zhì)上是多階段決策過(guò)程; ; 效益效益指標(biāo)函數(shù)指標(biāo)函數(shù)(hnsh)(hnsh)形式形式: : 和、和、積積無(wú)后效性無(wú)后效性),(111,nkkkknksususV可遞推可

9、遞推第21頁(yè)/共78頁(yè)第二十二頁(yè)，共78頁(yè)。23第22頁(yè)/共78頁(yè)第二十三頁(yè)，共78頁(yè)。24始點(diǎn)到終點(diǎn)的最短路線。ABC第23頁(yè)/共78頁(yè)第二十四頁(yè)，共78頁(yè)。25第24頁(yè)/共78頁(yè)第二十五頁(yè)，共78頁(yè)。26511615151151262521615252252262531615353262(,)()34()minmin7,()(,)()53(,)()54()minmin5,()(,)()23(,)()()min(,)()dEFfFfEuEFdEFfFdEFfFfEuEFdEFfFdEFfFfEdEFfF53264min9,()63uEF1階段2階段3階段4階段5階段6階段C4AB2B1C3C

10、2C1D3D2D1E3E2E1F1F2G531363876685225522333336634418第25頁(yè)/共78頁(yè)第二十六頁(yè)，共78頁(yè)。27411514141251252422524242252353432524353353(,)()2 7()minmin7,()(,)()2 5(,)()1 5()minmin6,()(,)()2 9(,)()()min(,)()d D Ef Ef Du DEd D Ef Ed D Ef Ef Du DEd D Ef Ed D Ef Ef Dd D Ef E4323 5min8,()3 9u DE1階段2階段3階段4階段5階段6階段C4AB2B1C3C2C

11、1D3D2D1E3E2E1F1F2G531363876685225522333336634418第26頁(yè)/共78頁(yè)第二十七頁(yè)，共78頁(yè)。283131151413251141221321425221214222211334322333243234343()13()()7()7()10()()()13()()6()5()()18()()16()()9()8()()()()12()fCuCDfEfDfCuEFuDEfBuCDfDfEuBCfAuDEfBuABfCufDuBCuCDuDEfCuCD6161522625362532()4()()()3()9()()fFuFGEFfFfEuFGuEF1階段

12、2階段3階段4階段5階段6階段C4AB2B1C3C2C1D3D2D1E3E2E1F1F2G531363876685225522333336634418第27頁(yè)/共78頁(yè)第二十八頁(yè)，共78頁(yè)。29C4AB2B1C3C2C1D3D2D1E3E2E1F1F2G5313638766852255223333366344180第28頁(yè)/共78頁(yè)第二十九頁(yè)，共78頁(yè)。30C4AB2B1C3C2C1D3D2D1E3E2E1F1F2G5313638766852255223333366344181813131216109768759403第29頁(yè)/共78頁(yè)第三十頁(yè)，共78頁(yè)。31C4AB2B1C3C2C1D3D2

13、D1E3E2E1F1F2G5313638766852255223333366344180第30頁(yè)/共78頁(yè)第三十一頁(yè)，共78頁(yè)。32C4AB2B1C3C2C1D3D2D1E3E2E1F1F2G53136387668522552233333663441805693810111313131315161815第31頁(yè)/共78頁(yè)第三十二頁(yè)，共78頁(yè)。33第32頁(yè)/共78頁(yè)第三十三頁(yè)，共78頁(yè)。34均利用了它前面的子問(wèn)題的最優(yōu)化結(jié)果，依次進(jìn)行，最后一個(gè)子問(wèn)題所得的最優(yōu)解，就是整個(gè)問(wèn)題的最優(yōu)解。第33頁(yè)/共78頁(yè)第三十四頁(yè)，共78頁(yè)。35第34頁(yè)/共78頁(yè)第三十五頁(yè)，共78頁(yè)。36第35頁(yè)/共78頁(yè)第三十

14、六頁(yè)，共78頁(yè)。37ksku)(kkxD),(1kkkuxTx),(kkkuxv,kVk),(,),(11111nnkkkkkknnkkkkkuxuxVuxuxuxuxV),(1kkkkVux1,knV第36頁(yè)/共78頁(yè)第三十七頁(yè)，共78頁(yè)。38n8、設(shè)備更新問(wèn)題第37頁(yè)/共78頁(yè)第三十八頁(yè)，共78頁(yè)。39第38頁(yè)/共78頁(yè)第三十九頁(yè)，共78頁(yè)。401v1(s1,u1)x1s1s22x2s3skkxksk+1snnxnsn+1輸輸入入輸出輸出v2(s2,u2)vk(sk,uk)vn(sn,un)1(,)kkkksT sx解得最優(yōu)解x1=x1(s1)和最優(yōu)值f1(s1) 。11()1()()(,

15、)*() (,)*(,),1,1kkkkkkkkkkkkkxDskkkkkkkxDsfsoptv sxfsoptv sxfT sxkn n于是s2=T1(s1,x1)和f2(s2),順序推算確定每階段決策(juc)和效益。第39頁(yè)/共78頁(yè)第四十頁(yè)，共78頁(yè)。411(,)rkkkksTsx解得最優(yōu)解xn=xn(sn+1)和最優(yōu)值fn(sn+1) 。11()11()()(,)*() (,)*(,),1,2,kkkkkkkkkkkkkxDsrkkkkkkkxDsfsoptv sxfsoptv sxfTsxkn于是sn=Trn(sn+1,xn)和fn-1(sn),逆序推算(tu sun)確定每階段決

16、策和效益。k=1f1(s2)x1s1s2k=2f2(s3)x2s3skk=kfk(sk+1)xksk+1snk=nfn(sn+1)xnsn+1輸輸入入輸出輸出第40頁(yè)/共78頁(yè)第四十一頁(yè)，共78頁(yè)。42Max Z=x1.(x2)2.x3x1+x2+x3=c ( 0 )xi0 i=1,2,30 i=1,2,3第41頁(yè)/共78頁(yè)第四十二頁(yè)，共78頁(yè)。4333123122334s1 | 2 | 3 | 4 ss ss ss xcxxx 階段 223112ss xsxsc 按問(wèn)題的變量個(gè)數(shù)劃分階段，把它看作按問(wèn)題的變量個(gè)數(shù)劃分階段，把它看作(kn zu)一個(gè)一個(gè)三階段決策問(wèn)題，三階段決策問(wèn)題，k=1，

17、2，3第42頁(yè)/共78頁(yè)第四十三頁(yè)，共78頁(yè)。44v3（x3）=x3 ，各指標(biāo)函，各指標(biāo)函數(shù)數(shù)(hnsh)以乘積方式結(jié)合以乘積方式結(jié)合第43頁(yè)/共78頁(yè)第四十四頁(yè)，共78頁(yè)。45第44頁(yè)/共78頁(yè)第四十五頁(yè)，共78頁(yè)。46狀態(tài)轉(zhuǎn)移方程為狀態(tài)轉(zhuǎn)移方程為：s3=x3s3+x2=s2s2+x1=s1=c指標(biāo)指標(biāo)(zhbio)函函數(shù)為：數(shù)為：v1（x1）=x1v2（x2）=x22v3（x3）=x322222222223302232202222032*22(2) f ()m ax ()() = m ax () = m ax () = 4/ 27 x2/ 3xsxsxssvxfsxfsxxsxss3333

18、33334433*33(1) f ()max()() = max(1) xxsxssvxfsxss11111111220121031104*1(3) f ()m ax()() = m ax () = m ax (4()/ 27 ) =/ 64 x/ 4xscxcxcsvxfsxfcxxcxcc2223222222222222223232(032620 xsxsxxsxxsxsxs222222222令 hd h由d x得 舍 去 ）dh又d xdh而 故 是 極 大 值 點(diǎn)d x第45頁(yè)/共78頁(yè)第四十六頁(yè)，共78頁(yè)。47*411111*3321122222*32233333*112111 x

19、f ( )446432141x x f ()s4322716111x x f ( )s444112xx443scscscsscscscsscscscsc所以最優(yōu)解為： *233*411 x 24164scsczc第46頁(yè)/共78頁(yè)第四十七頁(yè)，共78頁(yè)。4821322123122334ss1 | 2 | 3 | 4 = c ss ss ss xxsxxx 階段 433s xsc 第47頁(yè)/共78頁(yè)第四十八頁(yè)，共78頁(yè)。49第48頁(yè)/共78頁(yè)第四十九頁(yè)，共78頁(yè)。50第49頁(yè)/共78頁(yè)第五十頁(yè)，共78頁(yè)。51由后向前(xin qin)逐段遞推，f1（a）即為所求問(wèn)題的最大收益。 第50頁(yè)/共78頁(yè)

20、第五十一頁(yè)，共78頁(yè)。52第51頁(yè)/共78頁(yè)第五十二頁(yè)，共78頁(yè)。53 工廠工廠 贏利贏利設(shè)備臺(tái)數(shù)設(shè)備臺(tái)數(shù)甲甲(1) 乙乙(2) 丙丙(3)012345037912130510111111046111212第52頁(yè)/共78頁(yè)第五十三頁(yè)，共78頁(yè)。54fk(sk)= M a x Pk (xk) +fk+1(sk+1) ，k=3,2,1;f4(s4)= 0 （邊界條件）（邊界條件）0 xxk kssk k第53頁(yè)/共78頁(yè)第五十四頁(yè)，共78頁(yè)。55 x3s3P3(x3)f3(s3) x*30123450000114126623111134121245121253333333( )max()0,1,

21、2,3,4,5xf sP xss其中第54頁(yè)/共78頁(yè)第五十五頁(yè)，共78頁(yè)。56 x2S2P2(x2)+f3(s2-x2)f2(s2) x*201234500+00010+4 5+05120+6 5+4 10+010230+115+6 10+4 11+014240+125+1110+6 11+411+0161,250+125+1210+11 11+611+4 11+0 21222222232202()max()()0,1,2,3,4,5xsfsP xf sx其中s =第55頁(yè)/共78頁(yè)第五十六頁(yè)，共78頁(yè)。57 x1S1P1(x1)+f2(5-x1)f1(5) x*101234550+213+

22、167+14 9+1012+5 13+0 210,211111112101( )(5)max()(5)5xsf sfP xfx其中s =按計(jì)算表格的順序反推算(tu sun)，可得兩個(gè)最優(yōu)方案方案(fng n)(1) x*1=0, s2=s1-x*1=5x*2=2, s3=s2-x*2=3x*3=s3=3方案(fng n)(2) x*1=2, s2=s1-x*1=3x*2=2, s3=s2-x*2=1x*3=s3=1第56頁(yè)/共78頁(yè)第五十七頁(yè)，共78頁(yè)。58第57頁(yè)/共78頁(yè)第五十八頁(yè)，共78頁(yè)。59第58頁(yè)/共78頁(yè)第五十九頁(yè)，共78頁(yè)。60kkk0 x0()3 1* x1,2,.,6 x

23、6()0.5()()kkkkkkkxxkvvvkxvkkkk當(dāng)?shù)趉期生產(chǎn)成本 c當(dāng)當(dāng)?shù)?期末庫(kù)存量為 時(shí)的存儲(chǔ)費(fèi)用 h第 期總成本為ch狀態(tài)狀態(tài)(zhungti)轉(zhuǎn)移方程為：轉(zhuǎn)移方程為： vk-1+ xk- dk= vk第59頁(yè)/共78頁(yè)第六十頁(yè)，共78頁(yè)。61每期生產(chǎn)量每期生產(chǎn)量x k ：每期生產(chǎn)量不超過(guò)生產(chǎn)能力每期生產(chǎn)量不超過(guò)生產(chǎn)能力6（用（用m表示）；表示）；又因?yàn)橛忠驗(yàn)?yn wi) v k-1 +x k -d k = v k, 所以所以v k-1 = v k+ d k-x k 0,即即 x k v k+ d k; 0 x kMin v k+ d k,6 = k 每期期末庫(kù)存量每期期末

24、庫(kù)存量v k：不大于今后各期需求量之和不大于今后各期需求量之和不大于不大于m- d k 。410min(,6)kjkj kvdd 第60頁(yè)/共78頁(yè)第六十一頁(yè)，共78頁(yè)。62指標(biāo)函數(shù)循序遞推關(guān)系為（指標(biāo)函數(shù)循序遞推關(guān)系為（順推法順推法) ： f k (vk )= M i n c k(xk)+0.5vk + f k-1 (vk-1 ) = M i n c k(xk)+0.5 vk + f k-1 (vk + dk - xk) 其中其中 k = min(vk+ dk, 6 ) ;k=2,3,4 f 0(v0 )=0 （邊界條件）（邊界條件）k=1,2,3,4.0 xxk k 0 xxk k 第61

25、頁(yè)/共78頁(yè)第六十二頁(yè)，共78頁(yè)。63f 1(v1 )= M i n c 1(x1)+0.5 v1 + f 0(v0)x x1 = min(v1+ d1, 6 )41120min(,6)min(9,62)4jjvdd1111120(0)min(30.5*0)5,2xvfxx時(shí)，1111131(1)min(30.5*1)6.5,3xvfxx時(shí)，1111142(2)min(30.5*2)8,4xvfxx時(shí)，1111153(3)min(30.5*3)9.5,5xvfxx時(shí)，1111164(4)min(30.5*6)11,6xvfxx時(shí)，第62頁(yè)/共78頁(yè)第六十三頁(yè)，共78頁(yè)。642222222212

26、2022224223()min ()()(3)min(,6)min(3,6) 0vmin(,6)min(6,3)3xjjf vc xh vf vxvdvdd 其中：2222212032212212221221(0)min()(0)(3)c (0)(0)(3)09.5c (1)(0)(2)48 =minmin9.5,0c (2)(0)(1)56.565c (3)(0)(0)xfc xhfxhfhfxhfhf所以2222212204(1)min()(1)(4)=11.5,0 xfc xhfxx所以2222212205(2)min()(2)(5)=14,5xfc xhfxx所以2222212206(

27、3)min()(3)(6)=15.5,6xfc xhfxx所以第63頁(yè)/共78頁(yè)第六十四頁(yè)，共78頁(yè)。653333333323303333343()min ()()(2)min(,6)min(2,6) 0vmin(,6)min(4,4)4xf vc xh vf vxvdvdd其中：3333333333(0)14,0(1)16,03(2)17.5,4(3)19,5(4)20.5,6fxfxfxfxfx所以所以或所以所以所以第64頁(yè)/共78頁(yè)第六十五頁(yè)，共78頁(yè)。664444443404434343443430(0)min ( )(0)(4)c (0)(4)0 20.5c (1)(3)4 19 =min c (2)(2)min 5 17.520.5,06 16c (3)(1)7 14c (4)(0)xvfc xhfxfffxff所以第65頁(yè)/共78頁(yè)第六十六頁(yè)，共78頁(yè)。67k-1kkkv = v + d -x 階段需求量di庫(kù)存量vi生產(chǎn)量xi440032462300123