歡迎來到線性規劃 (Linear Programming)!
在決策數學 1 (Decision Mathematics 1) 的這一章中，我們將探索現代數學中最有力的工具之一。線性規劃 (Linear Programming, LP) 的核心在於「最優化」——即在各種限制條件下，找出解決問題的最佳方案。無論是工廠如何在有限資源下實現利潤最大化，還是物流公司如何將燃料成本降至最低，線性規劃都是背後的關鍵技術。
如果剛開始覺得有些抽象，別擔心。我們基本上是在做這件事：將現實世界的問題轉化為代數表達式，然後使用固定的步驟（算法）來找出完美答案。讓我們開始吧！
1. 問題建模 (Formulation)
在解決問題之前，我們必須先將其從文字「翻譯」成數學語言。這個過程稱為建模 (Formulation)。
線性規劃問題的要素
1. 決策變量 (Decision Variables)：這是你可以控制的部分，通常用 \(x, y, z\) 等表示。例如，\(x = \) 生產蛋糕的數量。
2. 目標函數 (Objective Function)：這是你的目標。通常以「最大化 (Maximise)」（針對利潤/產量）或「最小化 (Minimise)」（針對成本/時間）開頭。例如：\(P = 5x + 3y\)。
3. 限制條件 (Constraints)：這是你的限制因素（如原材料、時間、資金）。通常以不等式表示，例如 \(2x + y \le 10\)。
4. 非負限制 (Non-negativity Constraint)：這是一個微小但至關重要的點！在現實中，你不可能生產 -5 個蛋糕。因此，我們必須加上 \(x, y \ge 0\)。
鬆弛變量、剩餘變量與人工變量
為了在後續使用高級算法，我們需要將不等式（如 \(\le\)）轉化為等式（如 \(=\)）。我們透過加入特殊的變量來達成：
鬆弛變量 (Slack Variables, \(s\))：用於 \(\le\) 的限制條件。可以將 "Slack" 想像成「剩餘」的資源。如果你有 10kg 麵粉但只用了 8kg，那麼鬆弛變量就是 2kg。
例子： \(3x + 2y \le 20\) 變為 \(3x + 2y + s_1 = 20\)。
剩餘變量 (Surplus Variables, \(s\))：用於 \(\ge\) 的限制條件。這是指超過最低要求的那部分「額外」數量。
例子： \(x + y \ge 5\) 變為 \(x + y - s_2 = 5\)。但等等！如果 \(x\) 和 \(y\) 為 0，那麼 \(-s_2 = 5\)，這意味著 \(s_2 = -5\)。在我們的算法中變量不能為負！這就引出了……
人工變量 (Artificial Variables, \(a\) 或 \(t\))：這些是「數學佔位符」，添加到 \(\ge\) 或 \(=$ 的限制條件中，為算法提供一個有效的起點。它們沒有現實意義，且必須在計算結束前被消除。
\n例子： \(x + y \ge 5\) 變為 \(x + y - s_2 + t_1 = 5\)。
快速回顧：
- 鬆弛 (Slack)：為 \(\le\) 加入「未使用的」資源（使用 \(+\) 號）。
- 剩餘 (Surplus)：為 \(\ge\) 減去「多餘的」資源（使用 \(-\) 號）。
- 人工 (Artificial)：為 \(\ge\) 或 \(=\) 引入一個「虛假」變量（使用 \(+\) 號）以幫助算法啟動。
2. 圖解法 (Graphical Method)
如果我們只有兩個變量（\(x\) 和 \(y\)），我們可以在圖表上繪製問題。這是可視化問題的好方法。
步驟詳解
1. 繪製限制條件：將不等式視為等式（直線）並畫出。
2. 找到可行域 (Feasible Region, FR)：這是圖上滿足所有限制條件的區域。為了保持清晰，建議塗掉那些不允許的區域（被排除的區域），剩下的就是可行域。
3. 確定最優點：最佳答案一定會出現在可行域的角點（頂點）上。
如何找到「最佳」角點？
有兩種方法：
- 頂點法 (Vertex Method)：計算可行域每個角點的坐標，並將其代入你的目標函數。數值最大（或最小）的那個點就是贏家！
- 目標直線法 (Objective Line Method / Ruler Method)：畫出一條代表目標函數的直線（例如假設 \(5x + 3y = 15\)）。將尺子放在這條線上，保持斜率不變並平移，直到它碰到可行域中最後一個接觸點。該點即為最優解。
常見錯誤：忘記有些問題要求整數解 (Integer Solutions)。如果最優點是 \(x = 2.7, y = 3.2\)，但你無法賣出 0.7 輛車，你必須檢查該點附近的整數坐標，找出可行域內最優的整數結果。
重點總結：最優解總是位於可行域的邊界上，通常是在角點！
3. 單純形法 (Simplex Algorithm)
圖解法對於 2D 問題很棒，但如果有 4 個變量呢？你總不能畫一個 4D 圖表！既然無法繪製，我們就使用單純形法 (Simplex Algorithm)——這是一種基於表格的逐步迭代方法 (tableau)。
初始表格 (Initial Tableau)
對於只有 \(\le\) 限制條件的最大化問題，我們建立一個表格。所有變量（\(x, y, s_1, s_2\)）放在頂部。最底行是目標行 (Objective Row)。
技巧：當把目標函數 \(P = 14x + 12y\) 寫入表格時，要將其改寫為 \(P - 14x - 12y = 0\)。這就是為什麼底部一行的數值通常以負數開始的原因！
迭代過程
1. 選擇主元列 (Pivot Column)：觀察目標行，選擇最負的數值。這代表該變量能最快增加你的利潤。
2. 比值檢驗 (Ratio Test，確定主元行)：對於每一行，將「數值 (Value)」列除以你所在主元列的數字。忽略零或負數結果。得到最小正比值的那一行就是你的主元行。
3. 主元運算 (Pivot)：使用行運算將主元（行列交點處的數字）變為 1，並將該列中其他所有數字變為 0。
4. 重複：持續此過程，直到目標行中沒有負數為止。如果沒有負數，你就找到了最大值！
你知道嗎？ 單純形算法是在二戰期間開發的，至今仍被航空公司用於安排航班和機組人員排班！
4. 高級方法：兩階段法與 Big-M 法
標準的單純形法只有在原點 (\(x=0, y=0\)) 是有效起點時才適用。如果我們有 \(\ge\) 限制條件，原點會位於可行域之外。我們需要一個「推動力」進入區域。這就是兩階段法 (Two-Stage) 和 Big-M 法 (Big-M Method) 的用武之地。
Big-M 法
我們在目標函數中為任何人工變量 (\(t\)) 添加一個極大的懲罰項 \(M\)。因為 \(M\) 極大，算法會為了避免這些懲罰而極力將 \(t\) 變為 0。一旦所有人工變量都為零，你就進入了可行域，剩下的部分按正常的單純形法運算即可。
兩階段法 (Two-Stage Method)
顧名思義，分兩個階段進行：
- 階段 1：建立一個臨時的目標函數：最小化所有人工變量的總和。我們的目標是讓這個總和變為 0。
- 階段 2：一旦總和為 0（意味著所有人工變量已消除），拋棄階段 1 的目標函數和人工變量列。然後使用得到的結果表格來求解原始的目標函數。
記憶法：
- Big-M：使用「懲罰項」(\(M\)) 來把人工變量「嚇跑」。
- 兩階段：使用「小遊戲」（階段 1）在玩「主遊戲」（階段 2）之前先把人工變量刪除。
總結檢核清單
- 建模：我有沒有加入非負限制 (\(x, y \ge 0\))？
- 鬆弛/剩餘：\(\le\) 是否用了 \(+s\)，\(\ge\) 是否用了 \(-s + t\)？
- 圖解法：我有沒有塗掉不想要的區域？是否檢查了是否需要整數解？
- 單純形法：主元列是否為目標行中最負的數？主元行是否為最小的正比值？
- 停止條件：對於最大化問題，當目標行中沒有負數時，我就停止。
如果單純形法的行運算讓你覺得乏味，別擔心！這只是 bookkeeping（簿記工作）。慢慢來，仔細檢查減法，你一定能找到最優路徑！