高考申論題
107年
[工業工程] 作業研究
第 一 題
📖 題組：
考慮以下線性規劃問題： 極大化 $Z = 3x_1 + 4x_2 + 2x_3$ 受限於 $-x_1 + x_2 + x_3 = 4$ $-x_1 + x_2 - x_3 \le 6$ $x_1 \le 0, x_2 \ge 0$ （註：$x_3$ 未註明則視為 unrestricted） (一)建構並求解此問題之對偶問題。（10 分） (二)利用互補差額定理（complementary slackness theorem）求解原問題。（10 分）
考慮以下線性規劃問題： 極大化 $Z = 3x_1 + 4x_2 + 2x_3$ 受限於 $-x_1 + x_2 + x_3 = 4$ $-x_1 + x_2 - x_3 \le 6$ $x_1 \le 0, x_2 \ge 0$ （註：$x_3$ 未註明則視為 unrestricted） (一)建構並求解此問題之對偶問題。（10 分） (二)利用互補差額定理（complementary slackness theorem）求解原問題。（10 分）
📝 此題為申論題，共 2 小題
小題 (一)
建構並求解此問題之對偶問題。
思路引導 VIP
本題測驗核心為「對偶問題建構規則」與「基礎求解技巧」。首先需嚴謹對應原問題（Max）的變數符號（如 $x_1 \le 0, x_3$ urs）與限制式方向（$=, \le$）至對偶問題（Min）的限制式方向與變數符號。建構完成後，觀察到對偶問題僅有兩個變數且包含一條等式限制式，應直覺採用「代入法」降維求解，以最快速度求得對偶最佳解。
小題 (二)
利用互補差額定理（complementary slackness theorem）求解原問題。
思路引導 VIP
互補差額定理的核心在於建立原問題與對偶問題之間的『非零即緊繃』對應關係。解題時應先取得對偶問題之最佳解，透過檢視對偶限制式是否有差額來決定原問題變數是否為零；再利用大於零的對偶變數，將對應的原問題不等式轉為等式，最後解聯立方程式即可嚴謹求得原問題最佳解。