高考申論題
113年
[工業工程] 作業研究
第 二 題
📖 題組：
求解馬可夫決策過程之問題的其中一種方式是可以將此問題轉化成線性規劃的問題來看待。考慮以下由馬可夫決策過程之問題轉化後之原始（Primal）線性規劃問題： Minimize α(0)v(0) + α(1)v(1) + α(2)v(2) + α(3)v(3) + α(4)v(4) Subject to: v(0) − 0.9v(0) − 0.1v(1) − 0v(2) − 0v(3) − 0v(4) ≥ r(0,0) v(0) − 0.1v(0) − 0.9v(1) − 0v(2) − 0v(3) − 0v(4) ≥ r(0,1) v(1) − 0.9v(0) − 0v(1) − 0.1v(2) − 0v(3) − 0v(4) ≥ r(1,0) v(1) − 0.1v(0) − 0v(1) − 0.9v(2) − 0v(3) − 0v(4) ≥ r(1,1) v(2) − 0v(0) − 0v(1) − 0v(2) − 0v(3) − 0v(4) ≥ r(2,0) v(2) − 0v(0) − 0v(1) − 0v(2) − 0v(3) − 0v(4) ≥ r(2,1) v(3) − 0v(0) − 0v(1) − 0.9v(2) − 0v(3) − 0.1v(4) ≥ r(3,0) v(3) − 0v(0) − 0v(1) − 0.1v(2) − 0v(3) − 0.9v(4) ≥ r(3,1) v(4) − 0v(0) − 0v(1) − 0v(2) − 0.9v(3) − 0.1v(4) ≥ r(4,0) v(4) − 0v(0) − 0v(1) − 0v(2) − 0.1v(3) − 0.9v(4) ≥ r(4,1) v(s) ≥ 0 for s = 0,1,2,3,4。在此問題中，v(s)為決策變數而α(·)及r(·,·)為給定常數。 假設 x(s, a), s = 0,1,2,3,4; a = 0,1 為上述問題相對應之對偶（Dual）線性規劃問題之對偶決策變數（dual variable）。
求解馬可夫決策過程之問題的其中一種方式是可以將此問題轉化成線性規劃的問題來看待。考慮以下由馬可夫決策過程之問題轉化後之原始（Primal）線性規劃問題： Minimize α(0)v(0) + α(1)v(1) + α(2)v(2) + α(3)v(3) + α(4)v(4) Subject to: v(0) − 0.9v(0) − 0.1v(1) − 0v(2) − 0v(3) − 0v(4) ≥ r(0,0) v(0) − 0.1v(0) − 0.9v(1) − 0v(2) − 0v(3) − 0v(4) ≥ r(0,1) v(1) − 0.9v(0) − 0v(1) − 0.1v(2) − 0v(3) − 0v(4) ≥ r(1,0) v(1) − 0.1v(0) − 0v(1) − 0.9v(2) − 0v(3) − 0v(4) ≥ r(1,1) v(2) − 0v(0) − 0v(1) − 0v(2) − 0v(3) − 0v(4) ≥ r(2,0) v(2) − 0v(0) − 0v(1) − 0v(2) − 0v(3) − 0v(4) ≥ r(2,1) v(3) − 0v(0) − 0v(1) − 0.9v(2) − 0v(3) − 0.1v(4) ≥ r(3,0) v(3) − 0v(0) − 0v(1) − 0.1v(2) − 0v(3) − 0.9v(4) ≥ r(3,1) v(4) − 0v(0) − 0v(1) − 0v(2) − 0.9v(3) − 0.1v(4) ≥ r(4,0) v(4) − 0v(0) − 0v(1) − 0v(2) − 0.1v(3) − 0.9v(4) ≥ r(4,1) v(s) ≥ 0 for s = 0,1,2,3,4。在此問題中，v(s)為決策變數而α(·)及r(·,·)為給定常數。 假設 x(s, a), s = 0,1,2,3,4; a = 0,1 為上述問題相對應之對偶（Dual）線性規劃問題之對偶決策變數（dual variable）。
📝 此題為申論題，共 2 小題
小題 (二)
請寫出對偶問題之限制式。（20 分）
思路引導 VIP
- 矩陣轉置：Dual 的限制式個數等於 Primal 的變數個數。Primal 有 5 個變數 v(0)~v(4)，故 Dual 有 5 條限制式。
- 係數對應：Primal 中 v(s) 在各限制式前的係數，轉置後成為 Dual 中各對偶變數 x(s, a) 的係數。
小題 (一)
請寫出對偶問題之目標式。（5 分）
思路引導 VIP
- 辨識 Primal 與 Dual 的對應關係：Primal 是 Minimize，Dual 則是 Maximize。
- 目標函數轉換法則：Primal 的限制式右側常數項（RHS）會變為 Dual 的目標函數係數。