動(dòng)態(tài)規(guī)劃的基本概念和基本方程.ppt

1,5.2 動(dòng)態(tài)規(guī)劃的基本概念和基本方程,(一)基本概念,(1)階段：k,(2)狀態(tài)變量：Sk,(3)決策變量： uk(Sk),(4)策略,(5)狀態(tài)轉(zhuǎn)移方程： Sk1 T (Sk ， uk),(6)指標(biāo)函數(shù)： Vk，n (Sk),(7)最優(yōu)指標(biāo)函數(shù)： fk (Sk),2,(二)前例1,(1)階段：k1，2，6 n=6,(2)狀態(tài)變量：Sk第k階段所處的位置 狀態(tài)集合 如S2 : (B1 , B2),(3)決策變量uk ：在第k段Sk狀態(tài)時(shí)決定選 取的下一段的某點(diǎn),(4)狀態(tài)轉(zhuǎn)移方程 ：Sk1 uk,3,(6)階段效益： d(Sk ，uk)為第k段，采取策略uk 到下一狀 態(tài)的距離,(5)最優(yōu)指標(biāo)函數(shù)： fk (Sk)：第k段，在Sk狀態(tài)時(shí)到終點(diǎn)G的最 短距離,4,例1 最短路徑問題,5,k6， f6(F1)4 f6(F2)3,6,同理 f5(E2)5 u5(E2) F2 f5(E3)9 u5(E3) F2,7,同理 f4(D2)6 u4(D2) E2 f4(D3)8 u4(D3) E2,K=3, ,8,9,(三)基本方程,或,10,例2,已知某種完好的機(jī)器1000臺(tái)， 高負(fù)荷時(shí) S1=8y1 a=0.7 低負(fù)荷時(shí) S2=5y2 b=0.9,問：每年初應(yīng)如何安排分配機(jī)器， 可使得5年總收益最大？,11,解,(1)階段：k=1,2,3,4,5 n=5,(2)狀態(tài)變量Sk ：第k年初始的完好設(shè)備數(shù),(3)決策變量uk：第k年初始分到高負(fù)荷下 的機(jī)器數(shù) Sk- uk：第k年初始分到低負(fù)荷下 的機(jī)器數(shù),12,(4)狀態(tài)轉(zhuǎn)移方程： Sk1 0.7 uk+0.9(Sk - uk)= 0.9Sk - 0.2 uk,(5)最優(yōu)指標(biāo)函數(shù)： fk (Sk)從第k-5年末采取最優(yōu)策略的最大收益,(6)一年收益： d(Sk , uk)=8uk+5(Sk - uk)= 3uk +5Sk,13,基本方程,14,K=5,15,K=4,16,K=3,17,K=2,K=1,f1(S1)23.7 S1 u1* =0 當(dāng)S11000時(shí) f1(1000)23700,18,結(jié)論,第一年1000臺(tái)投入低負(fù)荷 S2 0.9S1-0.2u1 0.9S1 900 第二年900臺(tái)投入低負(fù)荷 S3 0.9S2-0.2u2 0.9S2 810 第三年810臺(tái)投入高負(fù)荷 S4 0.9S3-0.2u3 0.7S3 567,19,第四年5