高考申論題
105年
[工業工程] 作業研究
第 一 題
一、請以對偶單行法（Dual Simplex method）求解下述之線性規劃問題：（請詳列計算步驟，使用其他方法不計分）（25 分）
Zmin = x1 + 4x2 + 3x4
Subject to：
x1 + 2x2 − x3 + x4 ≥ 3
− 2x1 − x2 + 4x3 + x4 ≥ 2
x1, x2, x3, x4 ≥ 0
Zmin = x1 + 4x2 + 3x4
Subject to：
x1 + 2x2 − x3 + x4 ≥ 3
− 2x1 − x2 + 4x3 + x4 ≥ 2
x1, x2, x3, x4 ≥ 0
📝 此題為申論題
思路引導 VIP
面對對偶單行法考題，首先必須將所有大於等於的限制式乘上負一轉換為「小於等於 (≤)」型態，藉此產生非負的剩餘變數與負數的右邊界值（RHS），建構出滿足對偶可行性但不滿足原始可行性的初始表。解題核心邏輯為「先求離開、再求進入」：先挑選 RHS 最負的變數離開基底，再透過最小比例測試（目標式係數與樞紐列負數係數之比值）決定進入變數，直到所有 RHS 皆轉為大於等於零即達最佳解。
🤖
AI 詳解
AI 專屬家教
【解題關鍵】將限制式轉換為 ≤ 形式以產生負的右邊界值（RHS），建立滿足對偶可行性的初始單行表，並嚴格遵循對偶單行法規則（先找最負 RHS 決定離開變數，再以最小比例測試決定進入變數）。 【解答】 Step 1：模型標準化
▼ 還有更多解析內容
對偶單行法求解程序
💡 維持對偶可行性，透過迭代尋求原始可行性以達最佳解。
🔗 對偶單行法運算流程
- 1 標準化 — 限制式同乘-1轉為≦，RHS出現負值
- 2 選離開變數 — 從RHS選最負值列作為樞紐列
- 3 選進入變數 — 目標列除以樞紐列負係數，取比值最小者
- 4 列運算 — 執行高斯消去法更新單行表
- 5 最佳解判斷 — 當所有RHS皆≧0，即得最優解
↓
↓
↓
↓
🔄 延伸學習：延伸學習：當Ratio Test找不到分母為負的係數時，代表原問題無可行解。
