OR教學投影片(第10章)(OK).ppt.pptVIP

第十章動態規劃 林吉仁 著 高立圖書公司出版 10-1簡　介 動態規劃(DP)用來處理多階段決策問題，它將一個龐大的問題分解成一系列前後相關的小問題，再加以處理 動態規劃並無一定的數學模式 分類：確定性動態規劃、機率性動態規劃。前者又分離散型與連續型。 動態規劃的求解，可分順推的方式或逆推的方式 10-2動態規劃的特性 階段 (stage) ：第一階段是自家裡至國內機場 ，… 狀態 (state) ：第二階段開始時有3個狀態，即 B1, B2 或 B3 機場。 ? 狀態空間 、狀態變數 、狀態向量 決策變數：第一階段以家為起點，須決策要前往B1, B2 或 B3機場，換言之， x1= , 或 無記憶性(或馬可夫性質) ：當某階段開始時的狀態給定後，則之後的決策不受以前階段狀態的影響 遞迴關係式： 10-3離散型動態規劃 採取逆推計算方式 fn 是表示累計 n, n+1,?, N 階段的貢獻值 計算方式兩種： (1) 表列計算時，第 t 階段是列出 st 、xt，而求 xt* 時使得 ft 有最大值或最小值 ft* (2) 表列計算時，第 t 階段是列出 st、st+1，而求 st+1* 時使得 ft 有最大值或最小值 ft* 例題10-2 請利用動態規劃求解下列問題： 重點提示： 維度之災 ：動態規劃求解的計算工作隨狀態向量的維度增加，而極速增加 數學模式只要可明確、獨立劃分各階段變數，即可利用動態規劃加以求解。 動態規劃可求解的問題形態，幾乎不受限，可以是線性規劃、非線性規劃 10-4連續型動態規劃 連續型動態規劃因為狀態 St 元素有無限多個，求解時不能以表列方式，而須利用方程式。 逆推的求解過程有兩方式： 過程中將 ft 表示成 xt 及 st 的函數，利用 ( 偏 ) 微分 決定 xt* ( 以 st 表出 ) 時有最佳值 ft* ( 以 st 表出 )，待求得 f1* 即得最佳解 過程中將 ft 表示成 st 及 st+1 的函數，利用 ( 偏 ) 微分 決定 時有最佳值 ft*，待求得 f1* 即得最佳解 例10-5 網路圖 例題10-6利用動態規劃求解 解： 先將問題改成如下： 例10-6 網路圖 解： 例10-7 網路圖 (95) (70) 155 150 145 (80) (80) (80) 285 (95) (65) (70) 140 135 (60) 190 (65) 305 7 190 3 125 2 65 1 150 4 215 5 90 3 225 6 5 160 95 4 3 140 4 205 2 80 125 (70) (60) 195 205 (90) 295 300 (85) 305 205 (70) (65) 215 (70) (60) (70) (60) 155 (65) 225 (80) 220 第 1 階段 第 2 階段 第 3 階段 第 4 階段 國文 英文 數學 理化 190 205 125 125 125 125 65 65 65 65 80 80 80 90 90 (90) (80) 160 160 160 220 220 225 150 150 140 140 140 215 210 150 0 0 0 1 0 2 0 3 (65) 65 (80) 80 (90) (65) 65 65 65 (65) (65) (80) (80) 80 80 (90) 90 90 (95) 95 解： 例10-8 網路圖 例題10-9利用動態規劃求解 解： 作業研究 貢獻值 ： 最佳化原則 ：最佳策略的子策略也總是最佳的 (1)逆推計算時，fn 表累計第 n, n+1,?, N 階段的貢獻值，fn* 表其最佳值 (2)順推計算時，fn 表累計第 1, 2,?,n?1 階段的的貢獻值，fn* 表其最佳值 離散型動態規劃問題常可利用網路圖來思考、求解 解：(法一) 本題網路圖 解：(法二) 例題10-3 利用動態規劃求解 解： 本題網路圖 例題10-4利用動態規劃求解 解： 例10-4 網路圖 例題10-5利用動態規劃求解 解：