民國115年 高考三級 工業工程 作業研究
第1題
以大M 法（Big M Method）求解以下線性規劃問題。（30 分） Maximize 2 +2 +3 Subject to , , Z x x x x x…
題目
以大M 法（Big M Method）求解以下線性規劃問題。（30 分） Maximize 2 +2 +3 Subject to , , Z x x x x x x x x x x x x x x x
參考解答（AI 生成，非官方）
- 一、題意與模式標準化。本題為求極大化之線性規劃，目標函數係數為 2、2、3，即 Max Z = 2x1 + 2x2 + 3x3；限制式之係數與右端值在題面排版中脫漏，無法完整辨識。就方法論而言，大 M 法（Big M Method）適用於含「大於等於」或「等於」限制式之問題：先將不等式化為等式，小於等於者加入寬鬆變數（slack variable），大於等於者減去剩餘變數（surplus variable），再對缺乏單位向量之限制式加入人工變數（artificial variable），並在目標函數中給予極大懲罰係數 M（求極大時為 −M）。
- 二、初始單純形表之建構。改寫後之目標函數可表示為 Max Z = 2x1 + 2x2 + 3x3 − M a1 − M a2，移項後以 Z − 2x1 − 2x2 − 3x3 + M a1 + M a2 = 0 表示。據此建立初始單純形表（simplex tableau）：各列對應一條限制式，各行對應各變數（含寬鬆、剩餘、人工變數）及右端常數欄；初期基變數（basic variable）由寬鬆變數與人工變數組成，其在表中之係數行恰構成單位矩陣。表格下方另列 Z_j 列與 C_j − Z_j（即 reduced cost，簡化成本）列，作為迭代判別依據。
- 三、迭代規則與比值檢定。求極大化問題時，選 C_j − Z_j 最大正值（或 Z_j − C_j 最負）之非基變數為進入變數（entering variable）；再以各列右端值除以該行正係數，取最小比值者所在列之基變數為離去變數（leaving variable），比值相同可任取，或依 Bland 法則以避免循環（cycling）；樞紐元素（pivot element）所在列先除以樞紐值使其為 1，再以列運算使該行其餘元素歸零，完成一次迭代。
- 四、最優性判定與可行性檢核。當所有 C_j − Z_j ≤ 0 時達最優；若此時人工變數仍為正值基變數，表示原問題無可行解（infeasible）；若某非基變數之 C_j − Z_j > 0 而其係數行全為非正，則問題為無界（unbounded）。因 M 為充分大之正數，最優解中人工變數必被逐出基底而為零，否則該解不具可行性。最後應將最優表之 x1、x2、x3 值代回原目標函數求 Z，並逐條驗證是否滿足原始限制式。
- 五、資料缺漏之處理與作答建議。由於題面限制式之係數與右端常數未能完整辨識，僅憑 Max Z = 2x1 + 2x2 + 3x3 無法建立唯一之初始表，亦無法算出唯一最優解與 Z 值，故本題資料缺漏，無法得出唯一數值。考生宜先依題意逐條抄錄限制式，明確標示所加之寬鬆、剩餘與人工變數，再逐表列出並註記樞紐行、樞紐列與比值，最後以「所有 C_j − Z_j ≤ 0 且人工變數均為零」作結，以取得方法分數。
AI 依官方試題文字產生的參考解答，非考選部公告答案，內容僅供備考參考。