運(yùn)籌學(xué)動(dòng)態(tài)規(guī)劃ppt課件(2)(編輯修改稿)
2025-05-30 18:35 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 + ??7 . 動(dòng)態(tài)規(guī)劃求解的基本步驟 2. 狀態(tài)變量 k s ：表示第 K 段可用于剩余的 n k+1 個(gè)項(xiàng)目的資金數(shù) , 顯 然有 1 s =10, 4 s =0 。 3. 決策變量 k x ： 即應(yīng)分配第 K 個(gè)項(xiàng)目上的投資額。 ： K=1， 2，３ 4. 狀態(tài)轉(zhuǎn)移方程： k k k x s s ? + 1 5. 最優(yōu)目標(biāo)函數(shù) k f （ k s ）：表示當(dāng)可投資金數(shù)為 k s 時(shí) , 投資于剩余的 n k+1 個(gè)項(xiàng)目的最大收益。 6. 基本方程為： ? ? ? ? + ? + + + + 0 ) ( )] ( ) ( max[ ) ( 1 1 1 1 n n k k k k k k s f s f x g s f k=3,2,1 (逆序解法 ) 投資問(wèn)題 : 設(shè)總投資額為 A 萬(wàn)元 , 擬投資于 n個(gè)項(xiàng)目上，已知對(duì)第 i 個(gè) 項(xiàng)目投 資 i x 萬(wàn)元 , 收益函數(shù)為 ) ( i i x g , 問(wèn)應(yīng)如何分配資金才可以使總收益最大 ? 這是一個(gè)與時(shí)間無(wú)明顯關(guān)系的靜態(tài)最優(yōu)化問(wèn)題 , 可先列出其靜態(tài)模型為： 為了應(yīng)用動(dòng)態(tài)規(guī)劃方法求解 , 我們可以人為地賦予它 “ 時(shí)段 ” 的概 念。 方法是將投資項(xiàng)目排序 , 假想對(duì)各個(gè)投資項(xiàng)目有先后順序。 首先考 慮對(duì)項(xiàng) 目 1 的投資 , 然后考慮對(duì)項(xiàng)目 2 的投資 , 依次最后考慮第 n 項(xiàng) 投 資 . 這樣就 把原問(wèn)題轉(zhuǎn)化為 n 階段的決策過(guò)程。 接下來(lái)的問(wèn)題，便是如 何 選擇正確的 狀態(tài)變量 , 并使各后部子過(guò)程間具有遞推關(guān)系。 Max V ＝ ? ? n i i i x g 1 ) ( . A x n i i ? ? ? 1 0 ? i x (i=1,2,…,n) 2. 狀態(tài)變量 k s ：表示第 K 段可用于剩余的 n k+1 個(gè)項(xiàng)目的資金數(shù) , 顯 然有 1 s =A, 1 + n s =0 。 3. 決策變量 k x ： 即應(yīng)分配第 K 個(gè)項(xiàng)目上的投資額。 ： K=1， 2， … ， n 4. 狀態(tài)轉(zhuǎn)移方程： k k k x s s ? + 1 5. 最優(yōu)目標(biāo)函數(shù) k f （ k s ）：表示當(dāng)可投資金數(shù)為 k s 時(shí) , 投資于剩余的 n k+1 個(gè)項(xiàng)目的最大收益。 6. 基本方程為： ? ? ? ? + ? + + + + 0 ) ( )] ( ) ( max[ ) ( 1 1 1 1 n n k k k k k k s f s f x g s f k=n,n 1,…,2,1 如果運(yùn)用逆序遞推尋優(yōu) , 則 ) ( 1 s1 f 就是所求的最大收益。 動(dòng)態(tài)規(guī)劃求解時(shí)的幾種常用算法 １．離散變量的分段窮舉法 如最短路問(wèn)題的解法 , 離散型資源分配問(wèn)題等． ２．連續(xù)變量的解法 根據(jù)方程的具體情況靈活選取求解方法． 如連續(xù)型資源分配問(wèn)題等． 例 用動(dòng)態(tài)規(guī)劃方法求解下列問(wèn)題 21 2 31 2 31 2 3m a x z = 4x 9 2 x 10 x , , 0xxxxxx+++ + ??解：采用逆序解法 順序解法的基本方程為： ? ? ? ? + ? + 0 ) ( )] ( ) ( max[ ) ( 1 4 4 k+1 k k k k k s f s f x g s f k=3,2,1 當(dāng)Ｋ＝ 3時(shí)，有 333 3 3 3 4 40( ) m a x [ ( ) ( ) ]xsf s g x f s???+332 30m a x [ 2 ]xs x???可以看到 ,當(dāng) 時(shí) , f3(s3)取得極大值 *33xs?33223 3 3 30( ) m a x [ 2 ] 2xsf s x s????當(dāng)Ｋ＝２時(shí)，有 222 2 2 2 3 30( ) m a x [ ( ) ( ) ]xsf s g x f s???+22222 3 302230m a x [ 9 ( ) ]m a x [ 9 2 ) ]xsxsx f sxs?????+?+2222 2 20m a x [ 9 2 ( ) ]xs x s x??? + 22 2 2 2 2 2 ( , ) 9 2( )h s x x s x? + 記 求其極值點(diǎn) : 2 222229 4( ) ( 1 ) 09 4dh sxdxxs? + ? ??這是一個(gè)極小點(diǎn) , 為什么 ? 所以 ,極大值只可能在 [0,s2]的端點(diǎn)取得 , 則有 22 2 2 2 2 2( ) 2 ( ) 9f s s f s s??或當(dāng)Ｋ＝ 1時(shí)，有 111 1 1 1 2 20( ) m a x [ ( ) ( ) ]xsf s g x f s???+11 1 2 20m a x [ 4 ( ) ]xs x f s???+分兩種情況 : 討論 ! 當(dāng) x1=0時(shí) , f1(10)=200, 達(dá)到最大值 . 再由狀態(tài)轉(zhuǎn)移方程順推 ,可求出 : x2=0 x3=10 例 用動(dòng)態(tài)規(guī)劃方法求解下列問(wèn)題 21 2 31 2 31 2 3m a x z = 4x 9 2 x 10 x , , 0xxxxxx+++ + ??解：采用順序解法 順序解法的基本方程為： ? ? ? ? + ? － 0 ) ( )] ( ) ( max[ ) ( 1 １ ０ k k k k k＋１ k s f s f x g s f k=3,2,1 當(dāng)Ｋ＝１時(shí)，有 121 2 1 1 0 10( ) m a x [ ( ) ( ) ]xsf s g x f s???+12102m ax [ 4 ]4xsxs????12*xs?當(dāng)Ｋ＝２時(shí)，有 232 3 2 2 1 20( ) m a x [ ( ) ( ) ]xsf s g x f s???+23232 1 20220m a x [ 9 ( ) ]m a x [ 9 4 ) ]xsxsx f sxs?????+?+23232 3 20230m a x [ 9 4( ) ]m a x [ 5 4 ) ]xsxsx s xxs????? + ?+39s?*23xs?當(dāng)Ｋ＝ 3時(shí)，有 343 4 3 3 2 30( ) m a x [ ( ) ( ) ]xsf s g x f s???+343423 2 3023 4 30m a x [ 2 ( ) ]
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1