5.2動態(tài)規(guī)劃的基本概念和基本方程

1、15.2 5.2 動態(tài)規(guī)劃的基本概念和基本方程動態(tài)規(guī)劃的基本概念和基本方程(一一)基本概念基本概念(1)階段：階段：k(2)狀態(tài)變量：狀態(tài)變量：sk(3)決策變量：決策變量： uk(sk)(4)策略策略(5)狀態(tài)轉(zhuǎn)移方程：狀態(tài)轉(zhuǎn)移方程： sk1 t (sk ， uk)(6)指標(biāo)函數(shù)：指標(biāo)函數(shù)： vk，n (sk)(7)最優(yōu)指標(biāo)函數(shù)：最優(yōu)指標(biāo)函數(shù)： fk (sk)2(二二)前例前例1(1)階段：階段：k1，2，6 n=6(2)狀態(tài)變量：狀態(tài)變量：sk第第k階段所處的位置階段所處的位置 狀態(tài)集合狀態(tài)集合 如如s2 : (b1 , b2)(3)決策變量決策變量uk ：在第：在第k段段sk狀態(tài)時決定選

2、狀態(tài)時決定選 取的下一段的某點(diǎn)取的下一段的某點(diǎn)(4)狀態(tài)轉(zhuǎn)移方程狀態(tài)轉(zhuǎn)移方程 ：sk1 uk3(6)階段效益：階段效益： d(sk ，uk)為第為第k段，采取策略段，采取策略uk 到下一狀到下一狀 態(tài)的距離態(tài)的距離(5)最優(yōu)指標(biāo)函數(shù)：最優(yōu)指標(biāo)函數(shù)： fk (sk)：第：第k段，在段，在sk狀態(tài)時到終點(diǎn)狀態(tài)時到終點(diǎn)g的最的最 短距離短距離4例例1 最短路徑問題最短路徑問題ab1b2c1c2c3c4d1d2d3e1e2e3f1f2g53136876658333 84222133355266435k6， f6(f1)4 f6(f2)3k5 d(e1 ,f1) +f6(f1)f5(e1)min d(e

3、1 ,f2) +f6(f2) 3+4 min =7 u5(e1)= f1 5+36同理同理 f5(e2)5 u5(e2) f2 f5(e3)9 u5(e3) f2k4 d(d1 ,e1) +f5(e1)f4(d1)min d(d1 ,e2) +f5(e2) 2+7 min =7 u4(d1)= e2 2+57同理同理 f4(d2)6 u4(d2) e2 f4(d3)8 u4(d3) e2k=3 8k1 d(a ,b1) +f2(b1)f1(a)min d(a ,b2) +f2(b2) 5+13 min =18 u1(a)= b1 3+169(三三)基本方程基本方程fk(sk)mind(sk ,

4、 uk)+ fk+1(sk+1) k=6, 1f7(s7)0或或fk(sk)mind(sk , uk)+ fk+1(sk+1) k=5, 1f6(s6) mind(s6 , u6) 10例例2已知某種完好的機(jī)器已知某種完好的機(jī)器1000臺，臺， 高負(fù)荷時高負(fù)荷時 s1=8y1 a=0.7 低負(fù)荷時低負(fù)荷時 s2=5y2 b=0.9 問：每年初應(yīng)如何安排分配機(jī)器，問：每年初應(yīng)如何安排分配機(jī)器， 可使得可使得5年總收益最大？年總收益最大？11解解(1)階段：階段：k=1,2,3,4,5 n=5(2)狀態(tài)變量狀態(tài)變量sk ：第：第k年初始的完好設(shè)備數(shù)年初始的完好設(shè)備數(shù)(3)決策變量決策變量uk：第：

5、第k年初始分到高負(fù)荷下年初始分到高負(fù)荷下 的機(jī)器數(shù)的機(jī)器數(shù) sk- uk：第：第k年初始分到低負(fù)荷下年初始分到低負(fù)荷下 的機(jī)器數(shù)的機(jī)器數(shù)12(4)狀態(tài)轉(zhuǎn)移方程：狀態(tài)轉(zhuǎn)移方程： sk1 0.7 uk+0.9(sk - uk)= 0.9sk - 0.2 uk(5)最優(yōu)指標(biāo)函數(shù)：最優(yōu)指標(biāo)函數(shù)： fk (sk)從第從第k-5年末采取最優(yōu)策略的最大收益年末采取最優(yōu)策略的最大收益(6)一年收益：一年收益： d(sk , uk)=8uk+5(sk - uk)= 3uk +5sk 13基本方程基本方程fk(sk)maxd(sk uk)+ fk+1(sk+1) k=5, 1f6(s6)0uk即即fk(sk)ma

6、x(3uk+5sk)+ fk+1(0.9sk- 0.2uk) k=4, 1f5(s5) max3uk+5sk ukuk14k=5f5(s5) max3u5+5s58s5 u5 * =s50u5s515k=4f4(s4) max3u4+5s4 + f5(s5) max3u4+5s4 +8(0.9s4- 0.2u4) max1.4u4+12.2s4 13.6s4 u4 * =s40 u4 s40 u4 s40 u4 s416k=3f3(s3) max3u3+5s3 + f4(s4) max3u3+5s3 +13.6(0.9s3- 0.2u3) max0.28u3+17.24s3 17.5s3 u3 * =s30 u3 s30 u3 s30 u3 s317k=2f2(s2) max20.7s2-0.5u2 20.7s2 u2* =00 u2 s2k=1f1(s1)23.7 s1 u1* =0當(dāng)當(dāng)s11000時時 f1(1000)2370018結(jié)論結(jié)論第一年第一年1000臺投入低負(fù)荷臺投入低負(fù)荷 s2 0.9s1-0.2u1 0.9s1 900第二年第二年900臺投入低負(fù)荷臺投入低負(fù)荷 s3 0.9s2-0.2u2 0.9s2 810第三年第三年810臺投入高負(fù)荷臺投入高負(fù)荷 s4 0.9s3-0.2u3 0.7s3 56719第四年第四年567臺投入高負(fù)