最優(yōu)化技術(shù)基礎(chǔ)PPT學(xué)習(xí)教案

1、會計(jì)學(xué)1 最優(yōu)化技術(shù)基礎(chǔ)最優(yōu)化技術(shù)基礎(chǔ) 第1頁/共23頁 第2頁/共23頁 通常多階段決策過程的發(fā)展是通過狀態(tài)的一系列變換來實(shí)通常多階段決策過程的發(fā)展是通過狀態(tài)的一系列變換來實(shí) 現(xiàn)的。一般情況下，系統(tǒng)在某個(gè)階段的狀態(tài)轉(zhuǎn)移除與本階段現(xiàn)的。一般情況下，系統(tǒng)在某個(gè)階段的狀態(tài)轉(zhuǎn)移除與本階段 的狀態(tài)和決策有關(guān)外，還可能與系統(tǒng)過去經(jīng)歷的狀態(tài)和決策的狀態(tài)和決策有關(guān)外，還可能與系統(tǒng)過去經(jīng)歷的狀態(tài)和決策 有關(guān)。因此，問題的求解就比較困難復(fù)雜。有關(guān)。因此，問題的求解就比較困難復(fù)雜。 適合于用動態(tài)規(guī)劃方法求解的只是一類特殊的多階段決策適合于用動態(tài)規(guī)劃方法求解的只是一類特殊的多階段決策 問題，即具有問題，即具有“無后

2、效性無后效性”( (馬爾柯夫性馬爾柯夫性) )的多階段決策過程。的多階段決策過程。 所謂無后效性，是指系統(tǒng)從某個(gè)階段往后的發(fā)展，僅由本階所謂無后效性，是指系統(tǒng)從某個(gè)階段往后的發(fā)展，僅由本階 段所處的狀態(tài)及其往后的決策所決定，與系統(tǒng)以前經(jīng)歷的狀段所處的狀態(tài)及其往后的決策所決定，與系統(tǒng)以前經(jīng)歷的狀 態(tài)和決策態(tài)和決策( (歷史歷史) )無關(guān)。無關(guān)。多階段決策過程特點(diǎn)多階段決策過程特點(diǎn): 狀態(tài)狀態(tài) x x1 1 階段階段1 1 T T1 1 決策決策u u1 1 狀態(tài)狀態(tài) x x2 2 決策決策u u2 2 階段階段2 2 T T2 2 狀態(tài)狀態(tài) x x3 3 .狀態(tài) 狀態(tài) x xk k 決策決策u

3、uk k 階段階段k k T Tk k 狀態(tài)狀態(tài) x xk k+1 +1 .狀態(tài) 狀態(tài) x xn n 決策決策u un n 階段階段n n TnTn 狀態(tài)狀態(tài) x xn n+1 +1 第3頁/共23頁 第4頁/共23頁 第5頁/共23頁 第6頁/共23頁 第7頁/共23頁 (1)(,( 1kkkkk susTs 第8頁/共23頁 )(,( kkkk spsR 第9頁/共23頁 nkspsRoptsf kkkk sPp kk kKk ,2, 1),(,()( )( nkuuup nkkk , 2 , 1, 1 )(,( kkkk spsR ,),()( 211111 n uusussp nkuu

4、up nkkk , 2 , 1, 1 第10頁/共23頁 （5） nk Uu Ss usTs ts usususRRoptf kk kk kkkk nn uu n ,2,1 ),( . ),( 1 2211 1 , 21 n uuu , 121 nn ssss 第11頁/共23頁 則對上述策略中所隱含的任一狀態(tài)而言， 第k子過程上對應(yīng)于該狀態(tài)的最優(yōu)策略必然 包含在上述全過程最優(yōu)策略p1*中，即為 )(,),(),()( 11nnkkkkkk susususp )(),(,),(),()( 221111nnkk sususususp 第12頁/共23頁 貝爾曼最優(yōu)化原理概念貝爾曼最優(yōu)化原理概念:

5、 如圖如圖, 如果已經(jīng)給出從點(diǎn)如果已經(jīng)給出從點(diǎn)A到到 點(diǎn)點(diǎn)C的最優(yōu)軌跡，那么從任一中間點(diǎn)的最優(yōu)軌跡，那么從任一中間點(diǎn)B到點(diǎn)到點(diǎn)C的部分軌跡必須的部分軌跡必須 是從是從B到到C的最優(yōu)軌跡。的最優(yōu)軌跡。 設(shè)給出路線設(shè)給出路線-是從是從A到到C的最優(yōu)路的最優(yōu)路 線，根據(jù)貝爾曼原理，則路線線，根據(jù)貝爾曼原理，則路線 是從是從B到到C的最優(yōu)路線。的最優(yōu)路線。 證證:用反證法用反證法, 假設(shè)某假設(shè)某 條其它路線，例如條其它路線，例如 是是 從從B到到C的最優(yōu)路線，那的最優(yōu)路線，那 么，路線么，路線I-比路線比路線I- 有更小的費(fèi)用。但這與有更小的費(fèi)用。但這與I- 是從是從A到到C最優(yōu)路線的最優(yōu)路線的 前提

6、相矛盾，因此前提相矛盾，因此必是必是 從從B到到C的最優(yōu)路線的最優(yōu)路線 貝爾曼闡述貝爾曼闡述: “一個(gè)最優(yōu)策略有這樣的特性，不論初始狀態(tài)和一個(gè)最優(yōu)策略有這樣的特性，不論初始狀態(tài)和 初始決策如何，相對于第一個(gè)決策所形成的狀態(tài)來說，余下初始決策如何，相對于第一個(gè)決策所形成的狀態(tài)來說，余下 的決策必定構(gòu)成一個(gè)最優(yōu)策略的決策必定構(gòu)成一個(gè)最優(yōu)策略”。 第13頁/共23頁 第14頁/共23頁 n ki iiikk usgsR),()( ),( iii usg ),(),( 111 nkkkkkk ssRusgR 第15頁/共23頁 求最短路徑 4.動態(tài)規(guī)劃方法應(yīng)用舉例 第16頁/共23頁 D D2 2(

7、(x x2 2)=)=D D2 2( (B B3 3)=)=B B3 3C C1 1, ,B B3 3C C2 2, ,B B3 3 C C3 3 f f 5 5 ( x( x 5 5 ) = f) = f 5 5 ( E ) = 0( E ) = 0 其含義是從其含義是從E E到到E E的最短路徑為的最短路徑為0 0。 第17頁/共23頁 x4 D4(x4) x5 v4(x4,d4) v4(x4,d4)+f5(x5) f4(x4) 最優(yōu)決策 d4* D1 D 1E E 5 5+0=5* 5 D1E D2 D 2E E 2 2+0=2* 2 D2E )(),(min)( 55444 )( 44

8、 444 xfdxvxf xDd 從從f f5 5(x(x5 5) )到到f f4 4(x(x4 4) )的遞推過程用下表表示的遞推過程用下表表示 ： 第四階段的遞推方程為：第四階段的遞推方程為： 在上表中，在上表中，*表示最優(yōu)值，由于決策允許集合表示最優(yōu)值，由于決策允許集合D4(x4) 中的決策是唯一的，因此這個(gè)值就是最優(yōu)值。中的決策是唯一的，因此這個(gè)值就是最優(yōu)值。 第18頁/共23頁 由此得到f4(x4)的表達(dá)式。由 于這是一個(gè)離散的函數(shù)，取值用 列表表示： f4(x4)的表達(dá)式的表達(dá)式 D15D1E x4f4(x4)最優(yōu)決策 d4* D22D2E 第19頁/共23頁 x3 D3(x3)

9、x4 v3(x3,d3) v3(x3,d3)+f4(x4) f3(x3) 最優(yōu)決策 d3* C1 C1D1 C1D2 D1 D2 3 9 3+5=8* 9+2=11 8 C1D1 C2 C2D1 C2D2 D1 D2 6 5 6+5=11 5+2=7* 7 C2D2 C3 C3D1 C3D2 D1 D2 8 10 8+5=13 10+2=12* 12 C3D2 從從f f4 4(x(x4 4) )到到f f3 3(x(x3 3) )的遞推過程用表格表示如下：的遞推過程用表格表示如下： )(),(min)( 44333 )( 33 333 xfdxvxf xDd 第三階段的遞推方程為：第三階段的

10、遞推方程為： 第20頁/共23頁 由此得到由此得到f f3 3( (x x3 3) )的表達(dá)式的表達(dá)式, ,取值用列表表示取值用列表表示： x3 f3(x3) 最優(yōu)決策d3* C1 8 C1D1 C2 7 C2D2 C3 12 C3D2 第21頁/共23頁 x2 D2(x2) x3 v2(x2,d2) v2(x2,d2)+f3(x3) f2(x2) 最優(yōu)決策 d2* B1 B1C1 B1C2 B1C3 C1 C2 C3 12 14 10 12+8=20* 14+7=21 10+12=22 20 B1C1 B2 B2C1 B2C2 B2C3 C1 C2 C3 6 10 4 6+8=14* 10+7=17 4+12=16 14 B2C1 B3 B3C1 B3C2 B3C3 C1 C2 C3 13 12 11 13+8=21 12+