【正文】 3 4 S1 S2 S3 S4 + + ) ( ) , ( ) ( ) , ( 2 4 2 2 1 4 1 2 D f D C d D f D C d 3 f （ 2 C ）＝ min =min + + 3 2 4 6 =5 即從 C2 到 E 的最短距離為 5, 其路徑為 2 C → 2 D → E, 相應(yīng)的決策為 * 3 x （ 2 C ） = 2 D 1 2 3 4 S1 S2 S3 S4 即從 C3 到 E 的最短距離為 5, 其路徑為 C3 → D1 → E, 相應(yīng)的決策為 * 3 x （ 3 C ） = 1 D 。其次 , 動態(tài)規(guī)劃的計算結(jié)果 不僅得到了 A 到 E 的最短路線 , 而且得到了任意一點到 E 點的最優(yōu)路線 。 而正確地建立關(guān)于遞推關(guān)系基本方程的關(guān)鍵，又 在于 正確地選擇狀態(tài)變量 保證各階段的狀態(tài)變 量具有遞推的 狀態(tài)轉(zhuǎn)移關(guān)系 。 首先考 慮對項 目 1 的投資 , 然后考慮對項目 2 的投資 , 依次最后考慮第 n 項 投 資 . 這樣就 把原問題轉(zhuǎn)化為 n 階段的決策過程。一維背包問題的典型提法是：一 位旅行者能承受的背包最大重量是 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 ） 段。 （ K=4） s4 本階段費用 s5 f5(s5) d+ f5(s5) f4(s4) x4 生產(chǎn)費用 存儲費 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 本階段費用 s4 f4(s4) d+ f4(s4) f3(s3) x3 生產(chǎn)費用 存儲費 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 本階段費用 s4 f4(s4) d+ f4(s4) f3(s3) x3 生產(chǎn)費用 存儲費 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 本階段費用 s3 f3(s3) d+ f3(s3) f2(s2) x2 生產(chǎn)費用 存儲費 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 本階段費用 s3 f3(s3) d+ f3(s3) f2(s2) x2 生產(chǎn)費用 存儲費 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 本階段費用 s2 f2(s2) d+ f2(s2) f1(s1) x1 生產(chǎn)費用 存儲費 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 。每件產(chǎn)品的可變成本為 1千元，每批產(chǎn)品的最大生產(chǎn)能力為 5件。 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 個項目的資金數(shù) , 顯 然有 1 s =A, 1 + n s =0 。 這是建立動態(tài)規(guī)劃模型的兩個要點。他們針對多階段決策問題的特點 , 提出了解決這類問題的 ” 最優(yōu) 化原理 ” , 并成功地解決了生產(chǎn)管理、工程技術(shù)許多方面的實際問題。 即 B1 到終點 E 的最短距離為 9, 其路徑為 B1 → C2 → D2 → E , 本段的相應(yīng) 決策為 * 2 x （ 1 B ） = 2 C ) ( 1 2 B f = min + + + ) ( ) , ( ) ( ) , ( ) ( ) , ( 3 3 3 1 2 3 2 1 1 3 1 1 C f C B d C f C B d C f C B d =min + + + 5 5 5 4 7 6 =9 1 2 3 4 S1 S2 S3 S4 同理有 : ) ( 2 2 B f = min + + + ) ( ) , ( ) ( ) , ( ) ( ) , ( 3 3 3 2 2 3 2 2 1 3 1 2 C f C B d C f C B d C f C B d =min + + + 5 6 5 7