Download presentation
Presentation is loading. Please wait.
1
Chapter 16 動態規劃
2
動態規劃階段的狀態與報酬函數 管理科學：作業研究與電腦應用 【Ch.16 動態規劃】
3
動態規劃後導式遞迴關係圖 管理科學：作業研究與電腦應用 【Ch.16 動態規劃】
4
Bottom-up 由下而上思考 (後退思考 Backward)
例題1-火柴問題 Bottom-up 由下而上思考 (後退思考 Backward) 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 動態規劃】
5
Top-down 由上而下思考 (前進思考 Forward)
64 32 16 8 4 2 例題2-64個硬幣問題 1 1 管理科學：作業研究與電腦應用 【Ch.16 動態規劃】
6
Bottom-up 由下而上思考 64 27 10 9 3 4 2 1 1 原則 : 244 -- 729 個 最多 6 次
個 最多 6 次 個 最多 5 次 個 最多 4 次 個 最多 3 次 個 最多 2 次 1 三個只要量一次就可以 管理科學：作業研究與電腦應用 【Ch.16 動態規劃】
7
例題3-水杯問題 管理科學：作業研究與電腦應用 【Ch.16 動態規劃】
8
例題4-路徑問題 管理科學：作業研究與電腦應用 【Ch.16 動態規劃】
9
路徑問題-解1/3 管理科學：作業研究與電腦應用 【Ch.16 動態規劃】
10
路徑問題-解2/3 管理科學：作業研究與電腦應用 【Ch.16 動態規劃】
11
路徑問題-解3/3 管理科學：作業研究與電腦應用 【Ch.16 動態規劃】
12
路徑問題動態規劃計算效率 管理科學：作業研究與電腦應用 【Ch.16 動態規劃】
13
例題4 管理科學：作業研究與電腦應用 【Ch.16 動態規劃】
14
邊界條件是： 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 動態規劃】
15
例題4-解2/4(第三階段) f3(0)＝0，p3(0)＝0； f3(1)＝max[0＋1 , 2＋0]＝2，p3(1)＝1；
管理科學：作業研究與電腦應用 【Ch.16 動態規劃】
![例題4-解2/4(第三階段) f3(0)＝0，p3(0)＝0； f3(1)＝max[0＋1 , 2＋0]＝2，p3(1)＝1；](http://slidesplayer.com/slide/17491100/102/images/15/%E4%BE%8B%E9%A1%8C4-%E8%A7%A32%2F4%28%E7%AC%AC%E4%B8%89%E9%9A%8E%E6%AE%B5%29+f3%280%29%EF%BC%9D0%EF%BC%8Cp3%280%29%EF%BC%9D0%EF%BC%9B+f3%281%29%EF%BC%9Dmax%5B0%EF%BC%8B1+%2C+2%EF%BC%8B0%5D%EF%BC%9D2%EF%BC%8Cp3%281%29%EF%BC%9D1%EF%BC%9B.jpg "管理科學：作業研究與電腦應用 【Ch.16 動態規劃】")
16
例題4-解3/4(第二階段) f2(0)＝0，p2(0)＝0； f2(1)＝max[0＋2 , 1＋0]＝2，p2(1)＝0；
管理科學：作業研究與電腦應用 【Ch.16 動態規劃】
![例題4-解3/4(第二階段) f2(0)＝0，p2(0)＝0； f2(1)＝max[0＋2 , 1＋0]＝2，p2(1)＝0；](http://slidesplayer.com/slide/17491100/102/images/16/%E4%BE%8B%E9%A1%8C4-%E8%A7%A33%2F4%28%E7%AC%AC%E4%BA%8C%E9%9A%8E%E6%AE%B5%29+f2%280%29%EF%BC%9D0%EF%BC%8Cp2%280%29%EF%BC%9D0%EF%BC%9B+f2%281%29%EF%BC%9Dmax%5B0%EF%BC%8B2+%2C+1%EF%BC%8B0%5D%EF%BC%9D2%EF%BC%8Cp2%281%29%EF%BC%9D0%EF%BC%9B.jpg "管理科學：作業研究與電腦應用 【Ch.16 動態規劃】")
17
例題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 動態規劃】
![例題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 動態規劃】](http://slidesplayer.com/slide/17491100/102/images/17/%E4%BE%8B%E9%A1%8C4-%E8%A7%A34%2F4%28%E7%AC%AC%E4%B8%80%E9%9A%8E%E6%AE%B5%29+f1%288%29%EF%BC%9Dmax%5B0%EF%BC%8B21+%2C+3%EF%BC%8B19+%2C+7%EF%BC%8B17+%2C+10%EF%BC%8B13+%2C12%EF%BC%8B9+%2C+13%EF%BC%8B6+%2C+14%EF%BC%8B4+%2C+14%EF%BC%8B2+%2C+14%EF%BC%8B0%5D%EF%BC%9D24%EF%BC%8Cp1%288%29%EF%BC%9D2%EF%BC%8C+%E7%AE%A1%E7%90%86%E7%A7%91%E5%AD%B8%EF%BC%9A%E4%BD%9C%E6%A5%AD%E7%A0%94%E7%A9%B6%E8%88%87%E9%9B%BB%E8%85%A6%E6%87%89%E7%94%A8+%E3%80%90Ch.16+%E5%8B%95%E6%85%8B%E8%A6%8F%E5%8A%83%E3%80%91.jpg "例題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 動態規劃】")
18
載貨問題 管理科學：作業研究與電腦應用 【Ch.16 動態規劃】
19
例題5 管理科學：作業研究與電腦應用 【Ch.16 動態規劃】
20
例題5-解1/3(第四&三階段) f4(x)＝2x，x＝0,1,2, …… , 11 p4(x)＝ x，x＝0,1,2, …… , 11
管理科學：作業研究與電腦應用 【Ch.16 動態規劃】
21
例題5-解2/3(第二階段) 管理科學：作業研究與電腦應用 【Ch.16 動態規劃】
22
例題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 動態規劃】
23
更新問題 例題7 設備收入 管理科學：作業研究與電腦應用 【Ch.16 動態規劃】
24
設備維護成本 管理科學：作業研究與電腦應用 【Ch.16 動態規劃】
25
設備更新成本 管理科學：作業研究與電腦應用 【Ch.16 動態規劃】
26
例題7-解(更新問題各階段最佳決策) 管理科學：作業研究與電腦應用 【Ch.16 動態規劃】
27
更新問題的路徑圖 管理科學：作業研究與電腦應用 【Ch.16 動態規劃】
28
資源調配路徑圖 管理科學：作業研究與電腦應用 【Ch.16 動態規劃】
29
例題8-求最小成本路徑 管理科學：作業研究與電腦應用 【Ch.16 動態規劃】
30
最小成本路徑動態規劃解答 管理科學：作業研究與電腦應用 【Ch.16 動態規劃】
Similar presentations
