高考申論題
114年
[工業工程] 作業研究
第 二 題
📖 題組：
三、考慮下列線性規劃問題： Max $z = x_1 - x_2 + 2x_3$ s.t. $x_1 + x_2 + 3x_3 \le 15$ （限制式 1） $2x_1 - x_2 + x_3 \le 3$ （限制式 2） $-x_1 + x_2 + x_3 \le 4$ （限制式 3） $x_1, x_2, x_3 \ge 0$ 令 $x_4, x_5, x_6$ 分別代表限制式 1, 2, 3 的寬裕變數（Slack Variable），考慮一個基本解（Basic Solution）$X_B = (x_1, x_3, x_2)$，此基本解所對應的反矩陣（Inverse）為 $B^{-1} = \begin{bmatrix} 1 & -1 & -2 \\ -1/2 & 1 & 3/2 \\ 3/2 & -2 & -5/2 \end{bmatrix}$
三、考慮下列線性規劃問題： Max $z = x_1 - x_2 + 2x_3$ s.t. $x_1 + x_2 + 3x_3 \le 15$ （限制式 1） $2x_1 - x_2 + x_3 \le 3$ （限制式 2） $-x_1 + x_2 + x_3 \le 4$ （限制式 3） $x_1, x_2, x_3 \ge 0$ 令 $x_4, x_5, x_6$ 分別代表限制式 1, 2, 3 的寬裕變數（Slack Variable），考慮一個基本解（Basic Solution）$X_B = (x_1, x_3, x_2)$，此基本解所對應的反矩陣（Inverse）為 $B^{-1} = \begin{bmatrix} 1 & -1 & -2 \\ -1/2 & 1 & 3/2 \\ 3/2 & -2 & -5/2 \end{bmatrix}$
📝 此題為申論題，共 3 小題
小題 (二)
請建構此基本解所對應的完整單形表（Simplex Tableau）。（10 分）
思路引導 VIP
本題測驗「修正單形法（Revised Simplex Method）」的矩陣運算觀念。看到已知基本解與其反矩陣 B^{-1}，應立即想到利用公式推導單形表：以 B^{-1}b 計算右端常數（RHS），以 c_B B^{-1} 推導單形乘子與目標函數列（Z-row），並以 B^{-1}A 找出新的技術係數。特別注意基本變數的順序 X_B = (x_1, x_3, x_2) 會嚴格對應到矩陣的各列與係數向量 c_B 的排列。
小題 (一)
請計算此基本解所對應的目標函數值。（5 分）
思路引導 VIP
在矩陣形式的單純形法（Revised Simplex Method）中，基本變數的值可透過 X_B = B^{-1}b 求得。計算出各變數數值後，注意排列順序，再代入目標函數公式 z = C_B X_B 即可得出目標函數值。
小題 (三)
請判斷此基本解是否為最佳解？若否，由此基本解開始，利用單形法（Simplex Method）求取最佳解。（10 分）
思路引導 VIP
遇到判斷基本解是否最佳的題型，首要任務是利用修正式單形法原理求出該基本解的對偶變數（Simplex Multipliers），進而計算非基底變數的約化成本（Reduced Cost）。若發現有可改進的方向，則重構目前的單形表，透過比例測試（Ratio Test）決定出入基變數，並完整執行樞紐運算直到達成最佳解。