圖解線性規劃簡介
歡迎來到離散數學中最實用的章節之一！線性規劃 (Linear Programming, LP) 的名稱聽起來很高級，但其實目標很簡單：在給定一系列限制條件下，找出最佳的結果（例如利潤最大化或成本最小化）。
想像你在經營一家小烘焙坊。你希望賺取最多的利潤，但你只有有限的麵粉、有限的烤箱使用時數，而且你不可能烤出負數個蛋糕！線性規劃能幫助我們平衡這些規則，找出成功的「甜蜜點」。
1. 建立問題模型：基本要素
在繪圖之前，我們需要將現實世界的情況轉化為數學模型。這稱為建立模型 (Formulation)。任何線性規劃問題都包含四個主要部分：
A. 決策變數 (Decision Variables)
這是你可以控制的項目。我們通常稱之為 \(x\) 和 \(y\)。務必定義它們所代表的含義並列出單位。
例子：設 \(x\) 為生產的標準杯子蛋糕數量，\(y\) 為生產的豪華杯子蛋糕數量。
B. 目標函數 (Objective Function)
這是你想要達成的目標。你是想最大化 (maximise) 利潤，還是最小化 (minimise) 浪費？它通常以方程式形式呈現，開頭通常是 \(P\)（利潤，Profit）或 \(C\)（成本，Cost）。
例子：如果一個標準杯子蛋糕能帶來 £2 利潤，而一個豪華款能帶來 £3 利潤，你的目標就是最大化 \(P = 2x + 3y\)。
C. 約束條件 (Constraints)
約束條件就是「規則」或限制。我們將這些寫成不等式（使用 \(\le\) 或 \(\ge\) 等符號）。
- 資源限制：「你只有 500g 糖。」如果每個 \(x\) 用 10g，每個 \(y\) 用 20g，那麼 \(10x + 20y \le 500\)。
- 比例約束：「你生產的標準蛋糕數量必須至少是豪華蛋糕的兩倍。」這代表 \(x \ge 2y\)。
D. 平凡約束 (Trivial Constraints)
在現實世界中，你不可能製作負數量的產品。我們必須總是包含 \(x \ge 0\) 和 \(y \ge 0\)。別忘了這些，它們能確保我們的圖形位於第一象限！
快速回顧：建立模型時，先找出變數，寫下你的「目標」（目標函數），並列出你的「規則」（約束條件）。
2. 可行區域：繪製規則
現在進入繪圖階段。我們需要找到可行區域 (Feasible Region)，即圖表上同時滿足所有規則的區域。
如何畫線
對於每個約束條件（例如 \(2x + 3y \le 12\)），首先將其視為方程式（\(2x + 3y = 12\)）來畫出一條直線。一個好用的技巧是截距法 (Cover-Up Method)：
- 令 \(x = 0\)，求出 \(y\)。(在我們的例子中：\(3y = 12\)，所以 \(y = 4\))。標記點 \((0, 4)\)。
- 令 \(y = 0\)，求出 \(x\)。(在我們的例子中：\(2x = 12\)，所以 \(x = 6\))。標記點 \((6, 0)\)。
- 將兩點用直線連接起來。
陰影規則（OCR 考試重點！）
在本課程中，我們遵循一個特定的慣例：塗黑不滿足條件的區域。
如果你的規則是 \(x + y \le 10\)，直線上方的任何點都是「錯誤的」（不符合規則）。請塗黑直線上方的區域。當你為所有約束條件都做完這個步驟後，你會剩下一個清晰、沒有陰影的區域。這個空白區域就是可行區域。
你知道嗎？ 使用這種「塗黑排除法」能讓可行區域脫穎而出，讓你更容易觀察解的位置！
3. 找出最佳解
一旦你有了清晰的可行區域，如何找到能帶來最大利潤的精確點呢？有兩種主要方法：
方法一：頂點測試法 (Vertex Testing)
「最佳」解永遠會出現在可行區域的其中一個頂點 (vertices)（角落）。
- 找出所有頂點的坐標。
- 將這些 \((x, y)\) 值代入你的目標函數。
- 得到最大值（求最大化時）或最小值（求最小化時）的那一個就是優勝者！
方法二：目標線法 (The Objective Line / "Sliding Line")
如果頂點很多，這個方法比較快：
- 為你的目標函數選擇一個隨機值（例如，如果 \(P = 2x + 3y\)，試著設 \(2x + 3y = 6\)）。
- 在圖上畫出這條線（通常畫成虛線）。
- 使用直尺，將該線平行移動穿過可行區域。
- 最大化時： 直線離開可行區域前觸碰到的最後一個點就是最大值。
- 最小化時： 直線進入可行區域內觸碰到的第一個點就是最小值。
重點摘要：「最佳」答案幾乎總是落在角落！利用直尺找出在目標方向上最遠的那個角落。
4. 處理整數解
如果剛開始覺得這部分很麻煩別擔心，因為有時候算出來的答案可能是「生產 4.7 輛車」。你不可能生產 0.7 輛車！如果題目要求整數解 (integer solutions)，你必須找出最合適的整數坐標。
常見錯誤：不要直接四捨五入！四捨五入後的點可能已經超出了你的可行區域（違反了規則）。
修正方法：觀察最接近你最佳頂點的整數點 \((x, y)\)，並確保它們仍然在未塗黑的可行區域內。將這些點代入目標函數中進行測試，看看哪一個最好。
總結清單
- 建模： 確定變數 (\(x, y\))，寫下目標函數 (\(P = ...\))，並列出約束條件。
- 作圖： 使用截距法畫線。
- 塗陰影： 將直線「錯誤」的一側塗黑。保持可行區域清晰。
- 求解： 測試頂點或使用滑動目標線法。
- 檢查： 答案是否需要為整數？在現實語境下是否合理？
秘訣： 請務必使用削尖的鉛筆和長直尺。精確的繪圖會讓你在使用滑動目標線法尋找「最後觸碰點」時輕鬆許多！