動態規劃 Dynamic Programming 第十三章 動態規劃 Dynamic Programming 作業研究 二版 2009 © 廖慶榮

章節大綱 前言 驛馬車問題 最短路徑問題 由前往後式動態規劃 計算效率 資源分配問題 設備更新問題 連續狀態問題 機率性動態規劃 其他動態規劃應用 作業研究 二版 Ch.13 動態規劃

13.1 前言 動態規劃（dynamic programming；DP） 求解過程 13.1 前言 動態規劃（dynamic programming；DP） 隱含式列舉法（implicit enumeration method） 適用於一系列相關決策的問題 求解過程 將「原問題」分為一系列「子問題」 由最容易的子問題開始求解，直到最後求解的子問題就等於原問題為止 在求解子問題時，會用到已經解的子問題的解，因此計算會簡化許多 作業研究 二版 Ch.13 動態規劃

動態規劃模式 三個部分： 可加上第四個部分： 最佳值函數（optimal value function；OVF）：用以表達各子問題的函數 遞迴關係（recursive relation；RR）：將子問題以其他子問題表示的公式 邊界條件（boundary condition；BC）：根據OVF定義，不必計算即可明顯得知的值 可加上第四個部分： 答案（answer；ANS）：以OVF表示要求解答案 作業研究 二版 Ch.13 動態規劃

DP的求解過程 一律均由BC開始，反覆代入RR，以求解OVF所代表的各子問題，直到子問題即為ANS為止 作業研究 二版 Ch.13 動態規劃

13.2 驛馬車問題 驛馬車問題（stagecoach problem） 13.2 驛馬車問題 驛馬車問題（stagecoach problem） 淘金者要找出由城市1至城市n所有的路徑中，總保費最低的路徑（亦即，最安全的路徑） 驛馬車問題各城市間的路徑及保費： 作業研究 二版 Ch.13 動態規劃

驛馬車問題DP模式 作業研究 二版 Ch.13 動態規劃

驛馬車問題DP模式的圖示 階段變數（stage variable）：i 狀態變數（state variable）：s 作業研究 二版 Ch.13 動態規劃

範例13.1 /驛馬車問題 根據邊界條件： 根據遞迴關係： 作業研究 二版 Ch.13 動態規劃

範例13.1 /驛馬車問題 作業研究 二版 Ch.13 動態規劃

範例13.1 /驛馬車問題 最低的總保費為9 由最佳策略函數p（optimal policy function）可得最佳路徑為 (1-2-6-9-10) 作業研究 二版 Ch.13 動態規劃

範例13.2 /驛馬車問題的表格式計算 i =4 i =3 作業研究 二版 Ch.13 動態規劃

範例13.2 /驛馬車問題的表格式計算 i =2 i =1 作業研究 二版 Ch.13 動態規劃

13.3 最短路徑問題（無迴路網路） 迴路（circuit）： 有迴路的網路： 範例13.3 （無迴路網路的判斷） 13.3 最短路徑問題（無迴路網路） 迴路（circuit）： 有迴路的網路： 範例13.3 （無迴路網路的判斷） 作業研究 二版 Ch.13 動態規劃

13.3 最短路徑問題 DP模式： 圖示： 作業研究 二版 Ch.13 動態規劃

範例13.4 /無迴路最短路徑問題 找出由節點1至節點7的最短路徑 由p 值（見下頁）可追溯而得最短路徑為1-3-4-6-7 作業研究 二版 Ch.13 動態規劃

範例13.4 /無迴路最短路徑問題 作業研究 二版 Ch.13 動態規劃

13.4 由前往後式動態規劃 兩類DP： 由後往前式動態規劃（backward DP） N, N-1, …, 1 13.4 由前往後式動態規劃 兩類DP： 由後往前式動態規劃（backward DP） N, N-1, …, 1 由前往後式動態規劃（forward DP） 1, 2, …, N 作業研究 二版 Ch.13 動態規劃

Forward DP /無迴路最短路徑問題 模式： 圖示： 作業研究 二版 Ch.13 動態規劃

範例13.5 作業研究 二版 Ch.13 動態規劃

13.5 計算效率 考慮圖中的最短路徑問題，其兩類節點 第一類：9個節點，如： 需要兩個「加」及一個「比較」 第二類：6個節點，如： 13.5 計算效率 考慮圖中的最短路徑問題，其兩類節點 第一類：9個節點，如： 需要兩個「加」及一個「比較」 第二類：6個節點，如： 需要一個「加」 作業研究 二版 Ch.13 動態規劃

DP和完全列舉法TE的比較 作業研究 二版 Ch.13 動態規劃

最佳性原則 最佳性原則（principle of optimality） 目前階段狀態下的最佳決策僅和目前的狀態相關，而和如何到達此狀態的決策過程無關 以計算的觀點而言，當計算某階段狀態的OVF時，可直接使用之前已得到的OVF 以範例13.5為例。節點5的OVF計算如下： 作業研究 二版 Ch.13 動態規劃

13.6 資源分配問題 資源分配問題（resource allocation problem） 數學規劃（整數非線性規劃）模式： 13.6 資源分配問題 資源分配問題（resource allocation problem） 總共有單位的資源要分配給個活動，分配個資源給活動會產生的收益，應如何分配這些資源才能獲得最大的總收益？ 數學規劃（整數非線性規劃）模式： 作業研究 二版 Ch.13 動態規劃

13.6 資源分配問題 DP模式： 圖示： 作業研究 二版 Ch.13 動態規劃

範例13.6 /警車資源分配 決定如何將這6輛警車分配給4個不同的管轄區 各管轄區在不同警車數量時的每月犯罪案件數如下表所示： 作業研究 二版 Ch.13 動態規劃

範例13.6 /警車資源分配 根據邊界條件，可得 根據遞迴關係，可得 作業研究 二版 Ch.13 動態規劃

範例13.6 /警車資源分配 … 根據p值，可得表中所示的3組最佳警車分配方式 作業研究 二版 Ch.13 動態規劃

13.7 設備更新問題 設備更新問題（equipment replacement problem） 13.7 設備更新問題 設備更新問題（equipment replacement problem） 未來N年期間是否應購買新的設備？若要購買，應於第幾年購買，才能獲致最低的總成本 相關係數如下： 作業研究 二版 Ch.13 動態規劃

13.7 設備更新問題 DP模式 作業研究 二版 Ch.13 動態規劃

範例13.7 /設備更新問題 N=6 作業研究 二版 Ch.13 動態規劃

範例13.7 /設備更新問題 計算如下（簡略）： 最佳解： 作業研究 二版 Ch.13 動態規劃

13.8 連續狀態問題 可用最佳化技巧（如圖解法、微積分），來決定在 RR中的最大值或最小值 範例13.8：利用DP求解以下LP 解答： 13.8 連續狀態問題 可用最佳化技巧（如圖解法、微積分），來決定在 RR中的最大值或最小值 範例13.8：利用DP求解以下LP 解答： 作業研究 二版 Ch.13 動態規劃

範例13.8 解答(續)： 在 的可行區域內， 因此， 作業研究 二版 Ch.13 動態規劃

範例13.8 作業研究 二版 Ch.13 動態規劃

13.9 機率性動態規劃 機率性動態規劃（probabilistic DP） 投資問題 下一階段狀態無法完全由前一階段狀態與決策決定 13.9 機率性動態規劃 機率性動態規劃（probabilistic DP） 下一階段狀態無法完全由前一階段狀態與決策決定 投資問題 作業研究 二版 Ch.13 動態規劃

投資問題 作業研究 二版 Ch.13 動態規劃

範例13.9 C = $100萬；存入銀行年利率5％ 投資股票收益如下： 作業研究 二版 Ch.13 動態規劃

範例13.9 計算（簡略）： 因此，投資100萬元，第四年後可增為293.25萬元 根據p值：第1年全部存銀行，第2-4年均全部投資 作業研究 二版 Ch.13 動態規劃

13.10 其他動態規劃應用 貨物裝載問題（cargo-loading problem） 13.10 其他動態規劃應用 貨物裝載問題（cargo-loading problem） 每一類貨物分別要裝載多少數量（須為整數），才能使得貨物的總價值最高？ 貨物裝載問題的IP模式： 作業研究 二版 Ch.13 動態規劃

貨物裝載問題 DP模式： 作業研究 二版 Ch.13 動態規劃

旅行銷售員問題 旅行銷售員問題（traveling-salesman problem） DP模式 銷售員要如何安排旅行路線（每個城市拜訪一次），才能使得總距離最短？ DP模式 定義： 作業研究 二版 Ch.13 動態規劃

旅行銷售員問題 DP模式(續)： 作業研究 二版 Ch.13 動態規劃