其他动态规划应用货物装载问题.PPT

作業研究 二版 Ch.13 動態規劃 p.*/43 13.7 設備更新問題 DP模式 作業研究 二版 Ch.13 動態規劃 p.*/43 範例13.7 /設備更新問題 N=6 作業研究 二版 Ch.13 動態規劃 p.*/43 範例13.7 /設備更新問題 計算如下（簡略）： 最佳解： 作業研究 二版 Ch.13 動態規劃 p.*/43 13.8 連續狀態問題 可用最佳化技巧（如圖解法、微積分），來決定在RR中的最大值或最小值 範例13.8：利用DP求解以下LP 解答： 作業研究 二版 Ch.13 動態規劃 p.*/43 範例13.8 解答(續)： 在 的可行區域內， 因此， 作業研究 二版 Ch.13 動態規劃 p.*/43 範例13.8 作業研究 二版 Ch.13 動態規劃 p.*/43 13.9 機率性動態規劃 機率性動態規劃（probabilistic DP） 下一階段狀態無法完全由前一階段狀態與決策決定 投資問題 作業研究 二版 Ch.13 動態規劃 p.*/43 投資問題 作業研究 二版 Ch.13 動態規劃 p.*/43 範例13.9 C = $100萬；存入銀行年利率5％ 投資股票收益如下： 作業研究 二版 Ch.13 動態規劃 p.*/43 範例13.9 計算（簡略）： 因此，投資100萬元，第四年後可增為293.25萬元 根據p值：第1年全部存銀行，第2-4年均全部投資 作業研究 二版 Ch.13 動態規劃 p.*/43 13.10 其他動態規劃應用 貨物裝載問題（cargo-loading problem） 每一類貨物分別要裝載多少數量（須為整數），才能使得貨物的總價值最高？ 貨物裝載問題的IP模式： 作業研究 二版 Ch.13 動態規劃 p.*/43 貨物裝載問題 DP模式： 作業研究 二版 Ch.13 動態規劃 p.*/43 旅行銷售員問題 旅行銷售員問題（traveling-salesman problem） 銷售員要如何安排旅行路線（每個城市拜訪一次），才能使得總距離最短？ DP模式 定義： 作業研究 二版 Ch.13 動態規劃 p.*/43 旅行銷售員問題 DP模式(續)： 作業研究 二版 Ch.13 動態規劃 作業研究 二版 Ch.13 動態規劃 第十三章 動態規劃 Dynamic Programming ? 廖慶榮 作業研究 二版 2009 p.*/43 章節大綱 前言 驛馬車問題 最短路徑問題 由前往後式動態規劃 計算效率 資源分配問題 設備更新問題 連續狀態問題 機率性動態規劃 其他動態規劃應用 作業研究 二版 Ch.13 動態規劃 作業研究 二版 Ch.13 動態規劃 p.*/43 13.1 前言 動態規劃（dynamic programming；DP） 隱含式列舉法（implicit enumeration method） 適用於一系列相關決策的問題 求解過程 將「原問題」分為一系列「子問題」 由最容易的子問題開始求解，直到最後求解的子問題就等於原問題為止 在求解子問題時，會用到已經解的子問題的解，因此計算會簡化許多 作業研究 二版 Ch.13 動態規劃 p.*/43 動態規劃模式 三個部分： 最佳值函數（optimal value function；OVF）：用以表達各子問題的函數 遞迴關係（recursive relation；RR）：將子問題以其他子問題表示的公式 邊界條件（boundary condition；BC）：根據OVF定義，不必計算即可明顯得知的值 可加上第四個部分： 答案（answer；ANS）：以OVF表示要求解答案 作業研究 二版 Ch.13 動態規劃 p.*/43 DP的求解過程 一律均由BC開始，反覆代入RR，以求解OVF所代表的各子問題，直到子問題即為ANS為止 作業研究 二版 Ch.13 動態規劃 p.*/43 13.2 驛馬車問題 驛馬車問題（stagecoach problem） 淘金者要找出由城市1至城市n所有的路徑中，總保費最低的路徑（亦即，最安全的路徑） 驛馬車問題各城市間的路徑及保費： 作業研究 二版 Ch.13 動態規劃 p.*/43 驛馬車問題DP模式 作業研究 二版 Ch.13 動態規劃 p.*/43 驛馬車問題DP模式的圖示 階段變數（stage variable）：i 狀態變數（state variable）：s 作業研究 二版 Ch.13 動態規劃 p.*/43 範例13.1 /驛馬車問題 根據邊界條件： 根據遞迴關係：