歡迎來到線性規劃 (Linear Programming)！
你有沒有想過物流公司是如何找出最便宜的路線，或者工廠是如何精確決定產品產量以獲得最大利潤的？這正是線性規劃 (Linear Programming, LP) 的核心所在！這是一門在有限資源下作出最佳選擇的數學藝術。在「演算法建模 (Modelling with Algorithms)」這一部分，我們將利用線性規劃把現實生活中的「應用題」轉化為電腦（或聰明的學生）可以解決的數學問題。
1. 基本構建：問題建模 (Formulating the Problem)
在開始解決問題之前，我們需要掌握線性規劃的語言。每個問題都包含三個主要部分：
決策變量 (Decision Variables)
這是你可以控制的事項。例如，如果你經營一家烘焙坊，你的變量可能是：
設 \(x\) = 製作朱古力蛋糕的數量。
設 \(y\) = 製作雲呢拿蛋糕的數量。
重要提示： 在線性規劃中，變量必須代表數值，且通常是非負的（你不可能烘焙負 5 個蛋糕！）。
目標函數 (Objective Function)
這是你的目標。你是想獲得最多利潤（最大化 Maximisation）還是花費最少成本（最小化 Minimisation）？
例子： 如果每個朱古力蛋糕帶來 £5 利潤，每個雲呢拿蛋糕帶來 £3 利潤，你的目標就是最大化 \(P = 5x + 3y\)。
約束條件 (Constraints)
這是你的限制（即「規則」）。例如你可能只有 10kg 麵粉或 8 小時的焗爐使用時間。
例子： 如果一個朱古力蛋糕用 2kg 麵粉，雲呢拿蛋糕用 1kg，而你總共有 10kg 麵粉：
\(2x + 1y \le 10\)
標準型 (Standard Form)
當滿足以下條件時，線性規劃問題處於標準型：
1. 你正在最大化一個線性函數。
2. 所有約束條件都寫成「小於或等於」(\(\le\)) 一個常數。
3. 所有變量均為非負 (\(x, y \ge 0\)) 且為連續的（暫時來說，你可以製作 2.5 個蛋糕）。
快速回顧：
• 變量： 我在決定什麼？（必須是數字！）
• 目標： 我的目標是什麼？（最大化或最小化）
• 約束條件： 我的限制是什麼？
2. 鬆弛變量 (Slack Variables) 與增廣型 (Augmented Form)
演算法喜歡處理等式 (\(=\)) 而非不等式 (\(\le\))。為了修正這一點，我們使用鬆弛變量 (Slack Variables)。
你可以把「鬆弛變量」想像成「剩餘」的資源。如果你有 10kg 麵粉，用了一些來烘焙，那麼鬆弛變量 \(s\) 就是架子上閒置的麵粉。
因此，\(2x + y \le 10\) 會變成 \(2x + y + s = 10\)。
當我們將這些鬆弛變量加入所有約束條件時，我們稱之為增廣型 (Augmented Form)。這是使用單純形法 (Simplex Method) 的第一步！
3. 圖解法 (Solving Graphically)（二維問題）
如果你只有兩個變量 (\(x\) 和 \(y\))，你可以把問題畫在圖表上。別擔心你的繪圖技巧生疏，這一切都在於區域的劃分！
可行域 (Feasible Region)
當你在圖上標示出所有約束條件時，所有規則都能滿足的重疊區域就稱為可行域。在這個形狀內的任何一點都是可能的解。
無可行解 (Infeasibility)： 如果你的約束條件太嚴格，導致沒有任何區域能滿足所有規則，那麼該問題就是無可行解的（你實際上無法同時滿足所有規則）。
尋找最優點 (Optimal Point)
「最佳」點通常位於可行域的頂點 (Vertices)（角位）。你可以透過兩種方式找到它：
1. 目標線法 (Objective Line Method)： 畫一條代表你目標的線（例如 \(5x + 3y = 15\)）。使用尺子將這條線沿著圖表向改善的方向平行移動。當它離開可行域之前接觸到的最後一個角位，就是你的最優點！
2. 枚舉法 (Enumeration)： 將每一個角位的坐標代入你的目標函數，看看哪一個給出最大或最小值。
整數解怎麼辦？
有時你不能製作 2.5 個蛋糕；你需要整數。這就是整數線性規劃 (Integer Linear Programming, ILP)。
常見錯誤： 直接將小數答案四捨五入到最接近的整數可能會讓你得到一個位於可行域之外的點！相反，你應該檢查小數解附近的「晶格點」(Lattice points，即整數坐標)。
4. 單純形法 (The Simplex Method)
當你有三個或更多變量時，圖解法就不管用了（除非你能看到四維空間！）。單純形法是一種在可行域的各個角位之間進行代數「行走」，直到找到最佳點的方法。
單純形表 (The Tableau)
我們將數字整理成一個稱為單純形表的網格。
• 基變量 (Basic Variables)： 這些是目前「擁有」約束條件的變量（通常在開始時是鬆弛變量）。
• 非基變量 (Non-Basic Variables)： 這些被設定為零。
• 主元 (The Pivot)： 為了移動到更好的角位，我們選擇一個主元。我們選擇一列（通常是利潤行中負數值最大的那一列），然後使用「比值測試 (Ratio test)」來選擇行。
幾何基礎
單純形法的每一次行運算，實際上都是讓你從可行域的一個角位移動到相鄰且更好的角位。如果你在最大化問題的目標行中找不到負數，你就已經到達了山頂——你已經找到了最優解！
非標準問題（兩階段單純形法）
如果約束條件是「大於或等於」(\(\ge\)) 或「等於」(\(=\)) 怎麼辦？標準單純形法在這裡會遇到困難。
我們使用兩階段單純形法 (Two-Stage Simplex Method)。我們建立「人工變量 (Artificial Variables)」來找到起始點（第一階段），一旦我們進入可行域，再解決實際問題（第二階段）。
註：此課程大綱不需要知道「Big-M 法」——只需要兩階段法！
5. 現實世界中的線性規劃：網絡問題
線性規劃是一個「通用演算法」。你在本課程中學習的許多其他問題都可以寫成線性規劃形式：
• 最短路徑： 最小化路徑上的權重總和。
• 最大流： 最大化從源點到匯點移動的「貨物」總量。
• 關鍵路徑： 在項目網絡中找出最長路徑。
• 運輸問題： 最小化將貨物從多個工廠運送到多個商店的成本。
6. 使用軟體
在現實世界中，線性規劃問題擁有成千上萬個變量，我們使用試算表中的「規劃求解 (Solver)」。
你的任務： 你需要能夠觀察並解讀電腦輸出的數據。
• 哪些變量是「基變量」？
• 是否還有剩餘的鬆弛量 (Slack)（閒置資源）？
• 最終的目標函數值 (Objective value)是多少？
總結與重點
• 建模是關鍵： 如果你定義變量或約束條件錯誤，數學也救不了你！時刻檢查：「\(x\) 是否代表一個具體數字？」
• 可行域： 圖表上的「允許區域」。
• 鬆弛變量： 「剩餘的資源」。
• 單純形法： 一種透過代數方式從角位跳轉到角位，以尋找最高利潤或最低成本的方法。
• 整數問題： 小心四捨五入；檢查附近的整數點！
如果單純形表一開始看起來充滿了數字，別擔心。請記住：每一個步驟都只是一種華麗的說法，意指「讓我們嘗試形狀的另一個角位吧！」