地特三等申論題
106年
[工業工程] 作業研究
第 一 題
📖 題組：
考慮下列線性規劃模式 極大化 Z = 3x1 + 2x2 + 3x3 受限於 3x1 + 2x2 ≤ 24 x1 + x2 + x3 ≤ 8 2x1 + x3 ≤ 10 x1, x2, x3 ≥ 0 假設此問題是一個資源分配問題，其中限制式 1、2、3 分別代表資源 1、2、3 的限制。此問題的最佳單形表如下表所示，其中 x4，x5，x6 分別代表限制式 1、2、3 的寬鬆變數（slack variable）。 BV | Z | x1 | x2 | x3 | x4 | x5 | x6 | RHS ---|---|---|---|---|---|---|---|--- Z | 1 | 0 | 1 | 0 | 0 | 3 | 0 | 24 x4 | 0 | 3 | 2 | 0 | 1 | 0 | 0 | 24 x3 | 0 | 1 | 1 | 1 | 0 | 1 | 0 | 8 x6 | 0 | 1 | -1 | 0 | 0 | -1 | 1 | 2
考慮下列線性規劃模式 極大化 Z = 3x1 + 2x2 + 3x3 受限於 3x1 + 2x2 ≤ 24 x1 + x2 + x3 ≤ 8 2x1 + x3 ≤ 10 x1, x2, x3 ≥ 0 假設此問題是一個資源分配問題，其中限制式 1、2、3 分別代表資源 1、2、3 的限制。此問題的最佳單形表如下表所示，其中 x4，x5，x6 分別代表限制式 1、2、3 的寬鬆變數（slack variable）。 BV | Z | x1 | x2 | x3 | x4 | x5 | x6 | RHS ---|---|---|---|---|---|---|---|--- Z | 1 | 0 | 1 | 0 | 0 | 3 | 0 | 24 x4 | 0 | 3 | 2 | 0 | 1 | 0 | 0 | 24 x3 | 0 | 1 | 1 | 1 | 0 | 1 | 0 | 8 x6 | 0 | 1 | -1 | 0 | 0 | -1 | 1 | 2
📝 此題為申論題，共 4 小題
小題 (一)
寫出此問題的對偶問題。（10 分）
思路引導 VIP
看到要求寫對偶問題，應立刻聯想「原始-對偶轉換規則（Primal-Dual Relationships）」。將極大化（Max）轉為極小化（Min），限制式右側常數（RHS）轉為對偶目標函數係數，變數係數矩陣轉置做為對偶限制式係數，並依據原問題的不等式方向判定對偶變數及限制式的符號。
小題 (二)
直接由最佳單形表中讀出對偶問題的最佳解（包括剩餘變數 surplus variable）。（8 分）
思路引導 VIP
解此題的關鍵在於掌握『原始問題最佳單形表』與『對偶問題最佳解』的對應關係。根據對偶理論，原始單形表中寬鬆變數（slack variables）在 Z 列的係數即為對偶變數的最佳解（影子價格），而原始決策變數在 Z 列的係數即為對偶剩餘變數（surplus variables）的最佳解。
小題 (三)
資源 1 與 2 的影子價格（shadow price）分別是多少？他們的意義為何？（6 分）
思路引導 VIP
看到題目要求影子價格，應立即聯想到在最佳單形表中，目標函數列（Z 列）下寬鬆變數（slack variable）的係數即為對應資源的影子價格。接著，結合資源分配問題的背景，解釋影子價格代表「每增加一單位該資源，能為最佳目標函數值帶來多少提升」，並可由寬鬆變數是否為基底變數來判斷資源是否用盡（binding/non-binding）。
小題 (四)
限制式 2、3 的寬鬆變數值為何？他們的意義為何？（6 分）
思路引導 VIP
看到此題，首先應確認各限制式對應的寬鬆變數代號（資源2為 x5、資源3為 x6），接著從最佳單形表的基礎變數（BV）與右側常數（RHS）欄位判讀數值（未在BV欄的非基礎變數值為0）。最後，利用作業研究中寬鬆變數代表「未用盡資源（unused resources）」的核心觀念來解釋其經濟與實體意義。