地特三等申論題
111年
[工業工程] 作業研究
第 一 題
📖 題組：
考慮下列線性規劃問題（linear programming problem）： Minimize $x$ Subject to $-x + 4y \leq 4$ $x + y \leq 6$ $x \geq 0, y \geq 0$
考慮下列線性規劃問題（linear programming problem）： Minimize $x$ Subject to $-x + 4y \leq 4$ $x + y \leq 6$ $x \geq 0, y \geq 0$
📝 此題為申論題，共 2 小題
小題 (一)
試寫出此問題單形法（simplex method）的表格型式（tableau form）。（5 分）
思路引導 VIP
遇到單形法表格題型，首先必須引入非負的鬆弛變數（slack variables），將所有的不等式限制條件轉換為『標準等式』。接著，將目標函數移項整理至等號左側，最後將各方程式的變數係數填入包含基變數（Basic Variables）與右側常數（RHS）的初始單形法表格中。
小題 (二)
試以表格型式進行演算，使得 x 與 y 二個決策變數均成為基底變數（basic variable）。請完整寫出以表格型式之演算過程，不必求解最佳解。（20 分）
思路引導 VIP
此題為標準的單純形法（Simplex Method）矩陣運算題。看到題目要求『使變數成為基底變數』，應立即聯想到加入差額變數標準化後，透過『最小比值測試（Ratio Test）』來決定退基變數，並利用列運算（Pivot operations）更新表格。重點在於確保每次轉換後的等式右邊（RHS）皆為非負值，以維持基本可行解（BFS）的特性，不必管目標函數是否最佳化。