Linear programming

歡迎來到線性規劃的世界！

在離散數學的這一章中，你將學習如何在資源有限的情況下做出最佳決策。想像你在經營一門生意：你希望最大化利潤，但你卻只有有限的員工、時間和原材料。這些限制就是所謂的約束條件 (constraints)。

線性規劃 (Linear Programming, LP) 是一套強大的數學工具，從航空公司排程到工廠管理，人們都利用它來找到效率最高的「甜蜜點」。別擔心，剛開始可能會覺得步驟繁多，我們會將其拆解成簡單且合乎邏輯的小單元。

1. 建立模型 (Formulating the Problem) (DD1)

在解題之前，我們必須將問題從文字「翻譯」成數學。這個過程稱為建模 (formulation)。

每個線性規劃問題都有三個主要元素：

1. 決策變數 (Decision Variables)： 這些是你能夠控制的事物。我們通常稱它們為 \(x\)、\(y\) 或 \(x_1\)、\(x_2\)。（例如：我應該烘焙多少個巧克力蛋糕？多少個雲呢拿蛋糕？）

2. 目標函數 (Objective Function)： 這是你的目標。你通常希望最大化某個數值（例如利潤）或最小化某個數值（例如成本或浪費）。它的形式如下：\( \text{Maximise } P = 5x + 3y \)。

3. 約束條件 (Constraints)： 這是你必須遵守的規則或限制，通常寫成不等式。（例如：你只有 10kg 的麵粉，而每個蛋糕都需要一定份量的麵粉。）

非負限制 (Non-negativity)： 在現實世界中，你不可能烘焙出 -5 個蛋糕！因此，我們幾乎總是會包含約束條件 \(x \ge 0, y \ge 0\)。

快速複習：建模的黃金法則

• 確認需要決策的項目 (變數)。
• 寫下你的目標 (目標函數)。
• 列出限制條件 (約束條件)。
• 別忘了 \(x, y \ge 0\)！

2. 圖解法 (Graphical Solutions) (DD2)

如果你只有兩個變數（\(x\) 和 \(y\)），你可以透過繪圖來解題！這是理解問題最直觀的方式。

圖解法的步驟：

1. 繪製約束條件： 將不等式視為方程式（直線）並繪製在圖表上。
2. 找出可行區域 (Feasible Region)： 這是圖表上滿足所有約束條件的區域。通常我們會將「不需要」的區域塗黑，以便留下清晰的「允許」區域。
3. 找出最佳點 (Optimal Point)： 最佳解總是位於可行區域的其中一個頂點 (vertices)（角點）。

如何找出最佳角點？

你可以使用目標線法 (Objective Line Method)（也稱為等利潤線）：
• 為你的目標函數隨意選一個數值，例如 \(5x + 3y = 15\)。
• 在圖表上畫出這條線。
• 使用直尺平移這條線，使其在可行區域內平行移動。
• 當這條線最後離開可行區域時所觸碰的最後一點，就是你的最大值點。

常見錯誤： 對於 \( \le \) 和 \( \ge \) 要非常小心。如果約束條件是 \(x + y \le 10\)，你需要的範圍是直線的下方。如果你塗錯了邊，你的可行區域就會出錯！

3. 單純形法：基礎概念 (The Simplex Algorithm) (DD3)

如果你有 10 個變數怎麼辦？你沒辦法畫出 10 維的圖表！這時候就需要單純形法 (Simplex Algorithm) 出場了。它是一套逐步執行的「食譜」，從可行區域的一個角點移向更好的角點，直到找到最佳解為止。

鬆弛變數 (Slack Variables)

單純形法不喜歡不等式 (\( \le \))，它更偏好方程式 (\( = \))。為了修正這點，我們在每個 \( \le \) 約束條件中加入一個鬆弛變數 (Slack Variable) (\(s\))。
類比： 如果你的預算有 10 英鎊，而你花了 7 英鎊，那麼你的「鬆弛額」就是 3 英鎊。
因此，\(x + y \le 10\) 會變為 \(x + y + s = 10\)，其中 \(s \ge 0\)。

初始單純形表 (Initial Tableau)

我們將所有方程式放入一個表格中，稱為單純形表 (tableau)。表格中的每一行代表一個約束條件。最底下一行通常是目標函數行（或稱為 \(P\) 行）。

重要： 當你將目標函數放入表格時，必須將其重新排列使其等於零。
例如：\(P = 5x + 3y\) 變為 \(P - 5x - 3y = 0\)。這就是為什麼最底行中的 \(x\) 和 \(y\) 值通常一開始是負數的原因。

4. 如何進行「樞軸運算」 (How to Pivot) (DD3 & DD4)

樞軸運算 (Pivoting) 是我們從尚可的解轉向更好解的方法。剛開始如果覺得複雜別擔心，這只是一組規則而已。

步驟 1：選擇樞軸欄 (Pivot Column)
觀察目標函數行（最底行），挑選負值最大（數值最小）的數字。這一欄告訴我們哪一個變數最能幫助我們增加利潤。

步驟 2：選擇樞軸列 (Pivot Row) (比例測試)
對於每一行（最底行除外），將「數值 (Value)」（等號右側的數）除以該樞軸欄中的數字。
• 規則： 選擇最小正比例的那一行。
• 為什麼？ 這能確保我們不會意外「打破」約束條件並離開可行區域。

步驟 3：列運算 (Row Operations)
現在，使用你在矩陣章節學過的「列消去法」技巧：
1. 將樞軸元素 (pivot element)（該欄與該列的交點）透過除法變為 1。
2. 透過加減樞軸列的倍數，將該欄中所有其他的數字變為 0。

你知道嗎？ 電腦每天使用單純形演算法數百萬次，解決龐大的問題，為企業節省了數十億英鎊！

5. 解讀最終單純形表 (Interpreting the Final Tableau) (DD4)

怎麼知道什麼時候結束？當目標函數行中沒有負數時，你就完成了。

如何解讀結果：

• 基本變數 (Basic Variables)： 這些是看起來像單位矩陣欄位（有很多 0 和一個 "1"）的欄。它們的值可以在「數值 (Value)」欄中找到。
• 非基本變數 (Non-basic Variables)： 這些是數值雜亂的欄位。我們將這些設為 0。
• 目標值 (Objective Value)： 右下角的數字就是你的最大利潤（或最小成本）。

重點小結： 如果在最終單純形表中，某個鬆弛變數 (\(s\)) 有數值，這代表你在該約束條件下有「剩餘」的資源。如果 \(s = 0\)，代表你剛好用完了所有資源！

總結清單

• 建模： 定義變數、目標和限制。
• 圖解法： 用於 2 個變數的情況；找出可行區域的頂點。
• 鬆弛變數： 加入它們以將 \( \le \) 轉變為 \( = \)。
• 樞軸欄： 最底行中負值最大的數。
• 樞軸列： 最小正比例 (數值 / 欄位值)。
• 結束： 最底行沒有負數，代表你已經找到最佳解！