高考申論題
110年
[工業工程] 作業研究
第 一 題
📖 題組：
考慮下列線性規劃問題： Maximize 2x1 – x2 + x3 subject to 3x1 + x2 + x3 ≤ 60 2x1 – 2x2 + 4x3 ≤ 20 x1 ≥ 0, x2 ≥ 0, x3 ≥ 0
考慮下列線性規劃問題： Maximize 2x1 – x2 + x3 subject to 3x1 + x2 + x3 ≤ 60 2x1 – 2x2 + 4x3 ≤ 20 x1 ≥ 0, x2 ≥ 0, x3 ≥ 0
📝 此題為申論題，共 3 小題
小題 (一)
試以單形法（simplex algorithm）求解其最佳解，或明確指出其最佳解不存在。必須使用表列式（tableau）求解，並完整列出每一回合求解之列表。請明確寫出最佳解之基底變數（basic variables）以及最佳之目標函數值。（15 分）
思路引導 VIP
本題為標準單形法運算。首先加入鬆弛變數 s1, s2 將不等式轉為等式。接著建立初始表（Initial Tableau），選擇 Z 列中係數最負者（或最大正值，視乎表法）進行入基，再用最小比值原則（Minimum Ratio Test）決定出基。重複此步驟直至 Z 列係數皆符合終止準則。
小題 (二)
試寫出其對偶問題（dual problem）。（不必求解）（10 分）
思路引導 VIP
線性規劃原問題（Primal）與對偶問題（Dual）的轉換規律：原問題 Max 轉對偶 Min；原問題約束係數矩陣轉置；原問題 RHS 變成對偶目標係數；原問題目標係數變成對偶 RHS。且約束方向與變數正負號有對應關係。
小題 (三)
假設需求量有所變化，目前之需求量如下表所示。建構參數表（Parameter Table）以將此問題轉換成運輸問題。(10 分)
倉庫1：最小需求量 210, 最大需求量 280
倉庫2：最小需求量 100, 最大需求量 130
倉庫3：最小需求量 190, 最大需求量 ∞
思路引導 VIP
面對需求量為區間（有最大/最小值）的運輸問題，核心解題技巧是「拆解需求」與「平衡供需」。將每個倉庫拆為「最小需求（必須滿足）」與「額外需求（彈性滿足）」，並加入「虛擬工廠」吸收無法被滿足的額外需求，同時以大M法（Big-M）懲罰虛擬工廠去滿足最小需求的情況。