運(yùn)籌學(xué)動態(tài)規(guī)劃ppt課件(2)(參考版)
2025-05-06 18:35本頁面
【正文】 （ K=4） s4 本階段費(fèi)用 s5 f5(s5) d+ f5(s5) f4(s4) x4 生產(chǎn)費(fèi)用 存儲費(fèi) d(s4,x4) 0 4 3+4 0 7 0 0 7 7 1 3 3+3 0 0 2 2 3+2 1 6 0 0 6 6 3 1 3+1 0 0 4 0 0 2 2 0 0 2 2 當(dāng) K=3時， S3的最小值 ={5 2+1－ 6， 6}=5 即 S3={0,1,2,3,4,5} (k=3) s3 本階段費(fèi)用 s4 f4(s4) d+ f4(s4) f3(s3) x3 生產(chǎn)費(fèi)用 存儲費(fèi) d(s3,x3) 0 2 3+2 0 5 0 12 12 3 3+3 0 6 1 4 3+4 0 7 2 6 13 5 3+5 0 8 3 1 1 3+1 0 7 2 3+2 1 12 3 3+3 2 6 4 3+4 3 13 5 3+5 4 2 s3 本階段費(fèi)用 s4 f4(s4) d+ f4(s4) f3(s3) x3 生產(chǎn)費(fèi)用 存儲費(fèi) d(s3,x3) 2 0 0 1 1 0 7 8 8 1 3+1 1 5 1 2 3+2 1 6 2 6 12 3 3+3 1 7 3 4 3+4 1 8 4 2 10 3 0 0 1 8 8 1 3+1 2 6 2 3+2 3 12 3 3+3 4 2 4 0 0 2 2 2 6 8 8 1 3+1 2 6 3 2 3+2 2 7 4 2 9 5 0 0 3 8 8 1 3+1 4 2 s2 本階段費(fèi)用 s3 f3(s3) d+ f3(s3) f2(s2) x2 生產(chǎn)費(fèi)用 存儲費(fèi) d(s2,x2) 0 3 3+3 0 6 0 12 18 16 4 3+4 7 1 5 3+5 8 2 8 16 1 2 3+2 0 12 3 3+3 1 17 4 3+4 2 8 5 3+5 3 8 2 1 3+1 1 5 0 12 17 15 2 3+2 6 1 3 3+3 7 2 8 15 4 3+4 8 3 8 16 5 3+5 9 4 8 17 (K=2) s2 本階段費(fèi)用 s3 f3(s3) d+ f3(s3) f2(s2) x2 生產(chǎn)費(fèi)用 存儲費(fèi) d(s2,x2) 3 0 0 0 12 1 3+1 1 2 3+2 2 8 3 3+3 3 8 4 3+4 4 8 5 3+5 5 8 s1 本階段費(fèi)用 s2 f2(s2) d+ f2(s2) f1(s1) x1 生產(chǎn)費(fèi)用 存儲費(fèi) d(s1,x1) 1 2 3+2 0 16 3 3+3 1 22 4 3+4 2 15 5 3+5 3 22 (K=1) 最優(yōu)生產(chǎn)決策為： x1=2, x2=5, x3=0, x4=4 最優(yōu)值為 1 2 3 4 。 解： K,則每月為一個階段 ,K=1,2,3,4 0 ≤ xk ≤ 5, 4. 狀態(tài)轉(zhuǎn)移方程由下式確定： 1 + k s ＝ k k k b x s + 其中 , k d 表示第 K 階段的產(chǎn)品總成本，即 ) , ( k k k x s d ＝ ? ? + ) 0 ( ) 5 0 ( 3 k k x x xk+ ，由已知條件顯然有 S1=1， S5=0 ，由已知條件知： 5. 建立基本方程 （即成本最小化） ) ( ) , ( [ min ) ( 1 1 + + + ? k k k k k U k k s f x s d s f k （ k=4,3,2,1） 0 ) ( 5 5 ? s f 當(dāng) K=4時， S4的最小可能值為 0，即 4月初沒有存貨。又知 1月初有庫存產(chǎn)品1件， 4月底不再留下產(chǎn)品。每件產(chǎn)品的可變成本為 1千元，每批產(chǎn)品的最大生產(chǎn)能力為 5件。一維背包問題的典型提法是：一 位旅行者能承受的背包最大重量是 b 千克，現(xiàn)有 n 種物品供他選擇裝入 背包，第 i 種物品單件重量為 i a 千克，其價值 ( 或重要性參數(shù) ) 為 c i ，總價 值是攜帶數(shù)量 i x 的函數(shù)即 i i x c ，問旅行者應(yīng)如何選擇所攜帶物品的件數(shù) 以使總價值最大 ? 模型可表述為： ? ? ? n i i i x c z 1 max . b x a n i i i ? ? ? 1 0 ? i x 且為整數(shù) （ i=1,2,…,n ） 段。 動態(tài)規(guī)劃求解時的幾種常用算法 １．離散變量的分段窮舉法 如最短路問題的解法 , 離散型資源分配問題等． ２．連續(xù)變量的解法 根據(jù)方程的具體情況靈活選取求解方法． 如連續(xù)型資源分配問題等． 例 用動態(tài)規(guī)劃方法求解下列問題 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時，有 333 3 3 3 4 40( ) m a x [ ( ) ( ) ]xsf s g x f s???+332 30m a x [ 2 ]xs x???可以看到 ,當(dāng) 時 , f3(s3)取得極大值 *33xs?33223 3 3 30( ) m a x [ 2 ] 2xsf s x s????當(dāng)Ｋ＝２時，有 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? + ? ??這是一個極小點(diǎn) , 為什么 ? 所以 ,極大值只可能在 [0,s2]的端點(diǎn)取得 , 則有 22 2 2 2 2 2(
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1