Linear programming

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

你有沒有想過，工廠是如何精確決定生產多少產品才能獲得最高利潤？又或是物流公司如何找到配送包裹最省錢的路徑？這正是線性規劃 (Linear Programming) 的核心所在！它是離散數學 (Discrete Mathematics) 的一個分支，專門用來在資源有限（例如時間、資金或材料）的情況下，找出「最佳」的結果（如最大化利潤或最小化成本）。

如果現在覺得這些概念有點抽象，不用擔心！我們會將它拆解成簡單的步驟，讓你成為解題高手！

1. 建立模型：制定問題

在我們解決問題之前，必須先將「現實世界的語言」轉化為「數學符號」。這個過程稱為制定 (Formulation)。你可以把它想像成把故事翻譯成數學語言。

線性規劃的三大要素

每個問題都需要這三個部分：

1. 決策變數 (Decision Variables)： 這些代表你想要決定的東西。通常我們將它們設為 \(x\) 和 \(y\)。例子：\(x\) = 要烘焙的杯子蛋糕數量，\(y\) = 要烘焙的布朗尼數量。

2. 目標函數 (Objective Function)： 這是你的目標。你是想最大化利潤還是最小化成本？我們通常用 \(P\) 代表利潤 (Profit) 或 \(C\) 代表成本 (Cost)。例子：如果每個杯子蛋糕賺 £2，每個布朗尼賺 £3，你的目標就是最大化 \(P = 2x + 3y\)。

3. 約束條件 (Constraints)： 這些是你的限制或「規則」。你的麵粉、時間或焗爐空間有限。我們將這些寫成不等式（使用 \(\le\) 或 \(\ge\) 等符號）。

逐步教學：如何制定問題

每次解題都請遵循這些步驟：

步驟 A： 清晰定義你的變數（例如：「設 \(x\) 為...」）。
步驟 B： 寫下目標函數。
步驟 C： 以不等式列出約束條件。
步驟 D： 別忘了非負約束 (Non-negativity Constraints)！在現實世界中，你不可能烘焙 -5 個杯子蛋糕。因此，我們幾乎總是會加上 \(x \ge 0\) 和 \(y \ge 0\)。

快速回顧： 若要制定問題，請找出你想決定的變數 (\(x, y\))、你的目標 (\(P\))，以及限制你的因素（不等式）。

2. 圖解法：繪出你的限制範圍

有了不等式後，我們需要在圖表上把它們畫出來。這能幫助我們找到滿足所有規則的「甜蜜點」。

繪畫直線

要畫出像 \(2x + 3y \le 12\) 這樣的不等式，首先要把它視為方程式：\(2x + 3y = 12\)。
小撇步：使用「遮蓋法 (Cover-up Method)」找出直線與軸的交點！
- 要找出 \(y\) 軸截距，遮住 \(x\)（令 \(x=0\)）：\(3y = 12\)，所以 \(y = 4\)。
- 要找出 \(x\) 軸截距，遮住 \(y\)（令 \(y=0\)）：\(2x = 12\)，所以 \(x = 6\)。
用直線連接 (0, 4) 和 (6, 0) 即可！

標示可行區域 (Feasible Region)

可行區域（通常標記為 R）是圖表上所有不等式同時成立的範圍。它就像地圖上唯一允許你行走的地帶。

重要提示： 請務必仔細閱讀題目關於塗色（標示區域）的要求。有些考官希望你標示出你「想要」的區域，而有些則希望你塗掉「不需要」的區域（留下可行區域留白）。AQA 考試通常建議你用 R 清晰標出可行區域。

你知道嗎？ 在線性規劃中，可行區域總是一個「凸集 (convex)」形狀，這意味著它沒有凹陷或缺口。

3. 尋找最佳答案

現在你有了區域 R，最佳答案（最佳解 optimal solution）幾乎總是位於該區域的其中一個頂點 (vertices)（角位）上。

方法一：頂點測試法 (Vertex Testing Method)

這是對初學者來說最「萬無一失」的方法！

1. 找出可行區域每個角落（頂點）的坐標。
2. 將每一組 \((x, y)\) 數值代入你的目標函數。
3. 觀察哪一組數值能給你最高（利潤）或最低（成本）的結果。

方法二：目標直線法 (Objective Line / Sliding Line Method)

想像你的目標函數是一把可以在圖表上滑動的尺。

1. 為目標函數的一個隨機值畫出一條線（例如，如果 \(P = 2x + 3y\)，畫出 \(2x + 3y = 6\)）。
2. 使用尺平行地滑動這條線（最大化時向遠離原點的方向滑動）。
3. 直線離開可行區域前觸碰到的最後一個點，就是你的最大值！
4. 若是最小化問題，直線進入區域後觸碰到的第一個點（從原點開始移動時）就是你的最小值。

常見錯誤： 學生往往一找到一個頂點就停下來了。請務必檢查所有角落，或使用滑動直線法，以確保這確實是絕對最佳解！

4. 處理「整數」問題 (Integer Programming)

有時數學計算可能會告訴你，最佳解是購買 \(3.7\) 輛巴士。很明顯，你不能這麼做！這就是所謂的離散 (Discrete) 約束。

如果答案必須是整數：
1. 先在圖上找出最佳解（即使它是小數）。
2. 查看可行區域內最靠近該點的整數坐標。
3. 將這些附近的整數點代入目標函數，看看哪一個最好。

重點總結： 當你需要取整數時，數學上的「最佳小數解」四捨五入後不一定是「最佳整數解」。請務必測試附近的點！

總結清單

- 我能定義 \(x\) 和 \(y\) 嗎？
- 我寫下目標函數 (\(P = ...\)) 了嗎？
- 我包含所有約束條件了嗎，包括 \(x, y \ge 0\)？
- 我的可行區域標記清晰嗎？
- 我測試過所有角位（頂點）來找到最大/最小值了嗎？

如果一開始覺得畫圖很混亂，不用擔心。只要有削尖的鉛筆和穩定的尺，你會發現線性規劃是 Further Maths 中最合乎邏輯且極具成就感的部分之一！