地特三等申論題
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
利用主對偶轉換規則（SOB rules）建立對偶問題，注意原問題變數的非負限制與限制式符號之對應關係。建立後，可透過代數法將等式限制式代入其他不等式，以簡化並求解對偶問題。
小題 (二)
利用互補差額定理（complementary slackness theorem）求解原問題。
思路引導 VIP
運用互補差額定理前，必須先有對偶問題的最佳解。解題關鍵在於兩大原則：(1) 若對偶限制式代入最佳解後不為等式（有寬裕），則對應的原問題變數必等於其邊界值（此題為0）；(2) 若對偶變數大於0，則對應的原問題限制式必達等式。藉此找出足夠的方程式以解出原問題變數。