高考申論題
110年
[工業工程] 作業研究
第 二 題
📖 題組：
考慮下列線性規劃問題： Maximize 2x1 – x2 + x3 subject to 3x1 + x2 + x3 ≤ 60 2x1 – 2x2 + 4x3 ≤ 20 x1 ≥ 0, x2 ≥ 0, x3 ≥ 0
考慮下列線性規劃問題： Maximize 2x1 – x2 + x3 subject to 3x1 + x2 + x3 ≤ 60 2x1 – 2x2 + 4x3 ≤ 20 x1 ≥ 0, x2 ≥ 0, x3 ≥ 0
📝 此題為申論題，共 2 小題
小題 (二)
試寫出其對偶問題（dual problem）。（不必求解）（10 分）
思路引導 VIP
線性規劃原問題（Primal）與對偶問題（Dual）的轉換規律：原問題 Max 轉對偶 Min；原問題約束係數矩陣轉置；原問題 RHS 變成對偶目標係數；原問題目標係數變成對偶 RHS。且約束方向與變數正負號有對應關係。
小題 (一)
試以單形法（simplex algorithm）求解其最佳解，或明確指出其最佳解不存在。必須使用表列式（tableau）求解，並完整列出每一回合求解之列表。請明確寫出最佳解之基底變數（basic variables）以及最佳之目標函數值。（15 分）
思路引導 VIP
本題為標準單形法運算。首先加入鬆弛變數 s1, s2 將不等式轉為等式。接著建立初始表（Initial Tableau），選擇 Z 列中係數最負者（或最大正值，視乎表法）進行入基，再用最小比值原則（Minimum Ratio Test）決定出基。重複此步驟直至 Z 列係數皆符合終止準則。