動態(tài)規(guī)劃理論部分ppt課件-在線瀏覽
2025-06-23 12:08本頁面
【正文】 4 13 11 12 3 9 6 5 8 10 5 2 C1 C3 D1 A B1 B3 B2 D2 E C2 f4(D2)=2 f5(E)=0 f3(C3)=12 f4(D1)=5 f2(B3)=19 f3(C2)=7 f3(C1)=8 f1(A)=19 f2(B2)=14 f2(B1)=21 狀態(tài) 最優(yōu)決策 狀態(tài) 最優(yōu)決策 狀態(tài) 最優(yōu)決策 狀態(tài) 最優(yōu)決策 狀態(tài) A （ A， B2） B2 （ B2， C1） C1 （ C1， D1） D1 （ D1， E） E 從 A到 E的最短路徑為 19，路線為 A→B 2→C 1 →D 1 →E 三、動態(tài)規(guī)劃的基本概念 (1) 階段 （ stage） 把所研究的決策問題，按先后順序劃分為若 （ 2） 狀態(tài) （ state） 狀態(tài)表示每個階段開始時所處的自然狀況或 (3) 決策 （ decision） 決策表示在某一階段處于某種狀態(tài)時，決策者在若干種方案中作出的選擇決定。決策變量的取值會受到狀態(tài)變量的制約，被限制在某一范圍之內。描述階段的變量稱階段變量，常用 k表示。描述狀態(tài)的變量稱為狀態(tài)變量，第 k階段的狀態(tài)變量常用 sk表示。 T1 S1 S2 V1 u1 T2 S3 V2 u2 Tk Sk Sk+1 Vk uk Tn Sn Sn+1 Vn un … … 多階段決策過程如下： n個決策子問題 k稱為階段變量 Sk描述 k階段初的狀態(tài) ， 即狀態(tài)變量 一般把輸入狀態(tài)稱為該階段的階段狀態(tài) 。在全過程上，各階段的決策按順序排列組成的決策序列 p1,n＝ { u1,u2,…… ,un } 稱為全過程策略，簡稱策略；而在 k子過程上的決策序列 pk,n＝ { uk,uk+1,…… ,un } 稱為 k子過程策略，也簡稱子策略。 階段指標函數(shù) 是對某一階段的狀態(tài)和決策產生的效益值的度量 用 Vk(sk,uk)表示 。 若第 k階段的狀態(tài)變量值為 sk， 當決策變量 uk 的取值決定后 ，下一階段狀態(tài)變量 Sk+1的值也就完全確定 。 這種對應關系記為 : sk+1＝ Tk(sk,uk)， 稱為狀態(tài)轉移方程 。 過程指標函數(shù) 是指 從 第 k階段至第 n階段 所包含的各階段的狀態(tài)和決策所產生的總的效益值，記為 : Vk,n＝ Vk,n(Sk,uk,Sk+1,uk+1,…… ,Sn,un) Tk Sk Sk+! Vk (Sk,uk) uk (Sk) Tn Sn Sn+1 …… Vn (Sn,un) un (Sn) K－ 子過程 定義在全過程上的準則函數(shù)相當于目標函數(shù)，一般記為 : V1,n＝ V1,n(S1,u1, … Sk,uk ,… ,Sn,un)， 或簡記為 V1,n , 1 1,( ) ( , , , , , )knk k k n k k k k n nuuf S opt V S u S u S u???()kkfS 把過程指標函數(shù) Vk,n對 k子過程策略 pk,n求最優(yōu)，得到一個關于狀態(tài) Sk的函數(shù)，稱為 最優(yōu)值函數(shù) 或 貝爾曼函數(shù) ，記為 : 。常見的兩種過程指標函數(shù)形式是： 也就是說在階段 k從初始狀態(tài) Sk出發(fā) ， 執(zhí)行最優(yōu)決策序列或策略 ，到達過程終點時 ， 整個 k子過程中的最優(yōu)目標函數(shù)取值 。 ,( ) ( , )knnk k j j juu jkf S op t V S u?? ?,( ) ( , )knnk k j j juu jkf S o p t V S u?? ?或 ,1,1 , 1 1 ,1 , 1 1 ,11( ) ( 。 ) ][ ( , ) ( 。 1111( ) [ ( , ) ( ) ]( ) 0kkk k k k k k kuUnnf s o p t v s u f sfs?????????????逆序遞歸方程： 1 ( , )k k k ks T s u? ?狀態(tài)轉移方程： 正序遞歸方程： 1100( ) [ ( , ) ( ) ]( ) 0kkk k k k k k kuUf s o p t v s u f sfs???????????1 1 1( , )k k k ks T s u? ? ??狀態(tài)轉移方程： 其中 ： fk(sk)表示第 k階段初始狀態(tài)為 sk 時， k前部子過程的最優(yōu)準則函數(shù) 。 ③ 確定決策變量和決策允許集合 。 ⑤ 明確階段效應和目標 。 k = n－ 1時 ， 動態(tài)規(guī)劃的基本方程是 11 1 1 1 1( ) { ( , ) ( ) }nn n n n n n nuf s o p t V s u f s?? ? ? ? ??? 因所有的 都已經求出，因此可以根據(jù) 就階段 n1每個可能狀態(tài) ， 求出條件最優(yōu)決策及相應的條件最優(yōu)目標函數(shù)值。 1 2 2 2( , )n n n ns T s u? ? ? ??11()nnfs??2ns ? k = n－ 2時 ， 動態(tài)規(guī)劃的基本方程是 22 2 2 2 2 1 1( ) { ( , ) ( ) }nn n n n n n nuf s opt V s u f s?? ? ? ? ? ? ???k=1時 ， 動態(tài)規(guī)劃的基本方程是 11 1 1 1 1 2 2( ) { ( , ) ( ) }uf s o p t v s u f s?? 由于所有的 f2(s2) 都已經求出，因此可以根據(jù) s2=T1(s1,u1) 就階段 1每個可能狀態(tài) s1 ,求條件最優(yōu)決策及相應的條件最優(yōu)目標函數(shù)值 f1(s1) . 依次下去 …………. 最后，順序地求出最優(yōu)目標值、最優(yōu)策略和最優(yōu)路線 解 該問題可以作為三段決策過程 。 sk表示給部門 k分配資金時擁有的資金數(shù) 。 狀態(tài)轉移方程是 sk+1=sk uk。 例 2：某公司擬將 5百萬元資金投放下屬 A、 B、 C三個部門 ， 其中A與 C的投資額不超過 4百萬元 ， B的投資額不超過 3百萬元 ， C投資額至少是 1百萬元 。 15 11 8 4 C 12 10 5 0 B 12 10 6 3 0 A 收 益 （萬元） 4 3 2 1 投放資金 (萬元 ) 0 44( ) 0fs ?遞歸方程為： （ 1） K=3時（第 3階段） 注意到 C的投資額不超過 4百萬元， 至少是 1百萬元 . 允許狀態(tài)集合 S3＝ { 1, 2, 3, 4 }, 即用剩余額 S3＝ 1， 2， 3， 4 投資部門 C，得到的收益為： 3 3 3 3( 1 ) 4 ,
教學課件相關推薦
鄂ICP備17016276號-1