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

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

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

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

4、2 第13頁/共78頁第十四頁，共78頁。15第14頁/共78頁第十五頁，共78頁。16的難點之一。第15頁/共78頁第十六頁，共78頁。17211132112211122( , )( , , , )( , , , , , )kkkksT s usT s u s usT s u s us u 圖示如下圖示如下(rxi)：狀態(tài)轉(zhuǎn)移方程是確定過狀態(tài)轉(zhuǎn)移方程是確定過程程(guchng)(guchng)由一個由一個狀態(tài)到另一個狀態(tài)的演狀態(tài)到另一個狀態(tài)的演變過程變過程(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 能用動態(tài)規(guī)劃方法求解的多階段決策過程是一類特殊的多階段決策過程，即能用動態(tài)規(guī)劃方法求解的多階段決策過程是一類特殊的多階段決策過程，即具有無后效性具有無后效性的多階段決策過程。的多階段決策過程。第16頁/共78頁第十七頁，共78頁。18如果如果(rgu)(rgu)狀態(tài)變量不能滿足無后效性的要求，應(yīng)適當(dāng)?shù)馗淖儬顟B(tài)的定義或規(guī)定方法。狀態(tài)變量不能滿足無后效性的要求，應(yīng)適當(dāng)?shù)馗淖儬顟B(tài)的定義或

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

7、狀態(tài)去影響它未來的發(fā)展；構(gòu)造動態(tài)規(guī)劃模型時，要充分注意是否滿足無后效性的要求；即構(gòu)造動態(tài)規(guī)劃模型時，要充分注意是否滿足無后效性的要求；即狀態(tài)變量要滿足無后效性的要求狀態(tài)變量要滿足無后效性的要求；第17頁/共78頁第十八頁，共78頁。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頁/共78頁第十九頁，共78頁。20(,)njjjj kv s u(,)njjjj kv s u第19頁/共78頁第二十頁，共78頁。21,1,()(,)knkkk nkknuufsopt Vs us第20頁/共78頁第

8、二十一頁，共78頁。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動態(tài)規(guī)劃本質(zhì)上是多階段決策過程動態(tài)規(guī)劃本質(zhì)上是多階段決策過程; ; 效益效益指標(biāo)函數(shù)指標(biāo)函數(shù)(hnsh)(hnsh)形式形式: : 和、和、積積無后效性無后效性),(111,nkkkknksususV可遞推可

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

10、2C1D3D2D1E3E2E1F1F2G531363876685225522333336634418第25頁/共78頁第二十六頁，共78頁。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頁/共78頁第二十七頁，共78頁。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頁/共78頁第二十八頁，共78頁。29C4AB2B1C3C2C1D3D2D1E3E2E1F1F2G5313638766852255223333366344180第28頁/共78頁第二十九頁，共78頁。30C4AB2B1C3C2C1D3D2D1E3E2E1F1F2G5313638766852255223333366344181813131216109768759403第29頁/共78頁第三十頁，共78頁。31C4AB2B1C3C2C1D3D2

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

14、六頁，共78頁。37ksku)(kkxD),(1kkkuxTx),(kkkuxv,kVk),(,),(11111nnkkkkkknnkkkkkuxuxVuxuxuxuxV),(1kkkkVux1,knV第36頁/共78頁第三十七頁，共78頁。38n8、設(shè)備更新問題第37頁/共78頁第三十八頁，共78頁。39第38頁/共78頁第三十九頁，共78頁。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頁/共78頁第四十頁，共78頁。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頁/共78頁第四十一頁，共78頁。42Max Z=x1.(x2)2.x3x1+x2+x3=c ( 0 )xi0 i=1,2,30 i=1,2,3第41頁/共78頁第四十二頁，共78頁。4333123122334s1 | 2 | 3 | 4 ss ss ss xcxxx 階段 223112ss xsxsc 按問題的變量個數(shù)劃分階段，把它看作按問題的變量個數(shù)劃分階段，把它看作(kn zu)一個一個三階段決策問題，三階段決策問題，k=1，

17、2，3第42頁/共78頁第四十三頁，共78頁。44v3（x3）=x3 ，各指標(biāo)函，各指標(biāo)函數(shù)數(shù)(hnsh)以乘積方式結(jié)合以乘積方式結(jié)合第43頁/共78頁第四十四頁，共78頁。45第44頁/共78頁第四十五頁，共78頁。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而 故 是 極 大 值 點d x第45頁/共78頁第四十六頁，共78頁。47*411111*3321122222*32233333*112111 x

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

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

21、2,3,4,5xf sP xss其中第54頁/共78頁第五十五頁，共78頁。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頁/共78頁第五十六頁，共78頁。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 =按計算表格的順序反推算(tu sun)，可得兩個最優(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頁/共78頁第五十七頁，共78頁。58第57頁/共78頁第五十八頁，共78頁。59第58頁/共78頁第五十九頁，共78頁。60kkk0 x0()3 1* x1,2,.,6 x

23、6()0.5()()kkkkkkkxxkvvvkxvkkkk當(dāng)?shù)趉期生產(chǎn)成本 c當(dāng)當(dāng)?shù)?期末庫存量為 時的存儲費用 h第 期總成本為ch狀態(tài)狀態(tài)(zhungti)轉(zhuǎn)移方程為：轉(zhuǎn)移方程為： vk-1+ xk- dk= vk第59頁/共78頁第六十頁，共78頁。61每期生產(chǎn)量每期生產(chǎn)量x k ：每期生產(chǎn)量不超過生產(chǎn)能力每期生產(chǎn)量不超過生產(chǎn)能力6（用（用m表示）；表示）；又因為又因為(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 每期期末庫存量每期期末

24、庫存量v k：不大于今后各期需求量之和不大于今后各期需求量之和不大于不大于m- d k 。410min(,6)kjkj kvdd 第60頁/共78頁第六十一頁，共78頁。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、頁/共78頁第六十二頁，共78頁。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時，1111131(1)min(30.5*1)6.5,3xvfxx時，1111142(2)min(30.5*2)8,4xvfxx時，1111153(3)min(30.5*3)9.5,5xvfxx時，1111164(4)min(30.5*6)11,6xvfxx時，第62頁/共78頁第六十三頁，共78頁。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頁/共78頁第六十四頁，共78頁。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頁/共78頁第六十五頁，共78頁。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頁/共78頁第六十六頁，共78頁。67k-1kkkv = v + d -x 階段需求量di庫存量vi生產(chǎn)量xi440032462300123