Chapter 16 動態規劃

動態規劃階段的狀態與報酬函數 管理科學：作業研究與電腦應用 【Ch.16 動態規劃】

動態規劃後導式遞迴關係圖 管理科學：作業研究與電腦應用 【Ch.16 動態規劃】

Bottom-up 由下而上思考 (後退思考 Backward) 例題1-火柴問題 Bottom-up 由下而上思考 (後退思考 Backward) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 26 27 28 29 30 5 9 1 13 17 21 25 29 開始要先拿到第 (30-1) / (3+1) 的餘數 = 1 如果有 N 根火柴，兩個人輪流拿，每次每個人只能拿 1 根 , 2根 , … , 或 n 根。 也就是最少 1 根，最多 n 根。拿到最後一根的人為輸。 請問如何能保證必勝 ? 開始要先拿到第 (N-1) / (n+1) 的餘數 管理科學：作業研究與電腦應用 【Ch.16 動態規劃】

Top-down 由上而下思考 (前進思考 Forward) 64 32 16 8 4 2 例題2-64個硬幣問題 1 1 管理科學：作業研究與電腦應用 【Ch.16 動態規劃】

Bottom-up 由下而上思考 64 27 10 9 3 4 2 1 1 原則 : 244 -- 729 個 最多 6 次 244 -- 729 個 最多 6 次 82 -- 243 個 最多 5 次 28 -- 81 個 最多 4 次 10 -- 27 個 最多 3 次 4 -- 9 個 最多 2 次 1 三個只要量一次就可以 管理科學：作業研究與電腦應用 【Ch.16 動態規劃】

例題3-水杯問題 管理科學：作業研究與電腦應用 【Ch.16 動態規劃】

例題4-路徑問題 管理科學：作業研究與電腦應用 【Ch.16 動態規劃】

路徑問題-解1/3 管理科學：作業研究與電腦應用 【Ch.16 動態規劃】

路徑問題-解2/3 管理科學：作業研究與電腦應用 【Ch.16 動態規劃】

路徑問題-解3/3 管理科學：作業研究與電腦應用 【Ch.16 動態規劃】

路徑問題動態規劃計算效率 管理科學：作業研究與電腦應用 【Ch.16 動態規劃】

例題4 管理科學：作業研究與電腦應用 【Ch.16 動態規劃】

邊界條件是： f4(x)＝r4(x)，x＝0 , …… , 8 例題4-解1/4 邊界條件是： f4(x)＝r4(x)，x＝0 , …… , 8 f4(0)＝0，f4(1)＝1，f4(2)＝3，f4(3)＝6，f4(4)＝9， f4(5)＝12，f4(6)＝14，f4(7)＝16，f4(8)＝17 管理科學：作業研究與電腦應用 【Ch.16 動態規劃】

例題4-解2/4(第三階段) f3(0)＝0，p3(0)＝0； f3(1)＝max[0＋1 , 2＋0]＝2，p3(1)＝1； 管理科學：作業研究與電腦應用 【Ch.16 動態規劃】

例題4-解3/4(第二階段) f2(0)＝0，p2(0)＝0； f2(1)＝max[0＋2 , 1＋0]＝2，p2(1)＝0； 管理科學：作業研究與電腦應用 【Ch.16 動態規劃】

例題4-解4/4(第一階段) f1(8)＝max[0＋21 , 3＋19 , 7＋17 , 10＋13 ,12＋9 , 13＋6 , 14＋4 , 14＋2 , 14＋0]＝24，p1(8)＝2， 管理科學：作業研究與電腦應用 【Ch.16 動態規劃】

載貨問題 管理科學：作業研究與電腦應用 【Ch.16 動態規劃】

例題5 管理科學：作業研究與電腦應用 【Ch.16 動態規劃】

例題5-解1/3(第四&三階段) f4(x)＝2x，x＝0,1,2, …… , 11 p4(x)＝ x，x＝0,1,2, …… , 11 管理科學：作業研究與電腦應用 【Ch.16 動態規劃】

例題5-解2/3(第二階段) 管理科學：作業研究與電腦應用 【Ch.16 動態規劃】

例題5-解3/3(第一階段) f1(11)＝31，p1(11)＝2。所以A物品放2件。 剩下11－4×2＝3公斤， f2(3)=7，p2(3)＝0，即B物品不放入。 f3(3)=7，p3(3)=1，即C物品放1件。 剩下3－1×2＝1公斤，p4(1)=1，即D物品放1件。 最佳解：A物品2件，C物品1件，D物品1件，總效用31 管理科學：作業研究與電腦應用 【Ch.16 動態規劃】

更新問題 例題7 設備收入 管理科學：作業研究與電腦應用 【Ch.16 動態規劃】

設備維護成本 管理科學：作業研究與電腦應用 【Ch.16 動態規劃】

設備更新成本 管理科學：作業研究與電腦應用 【Ch.16 動態規劃】

例題7-解(更新問題各階段最佳決策) 管理科學：作業研究與電腦應用 【Ch.16 動態規劃】

更新問題的路徑圖 管理科學：作業研究與電腦應用 【Ch.16 動態規劃】

資源調配路徑圖 管理科學：作業研究與電腦應用 【Ch.16 動態規劃】

例題8-求最小成本路徑 管理科學：作業研究與電腦應用 【Ch.16 動態規劃】

最小成本路徑動態規劃解答 管理科學：作業研究與電腦應用 【Ch.16 動態規劃】