Linear programming

歡迎來到線性規劃：制定最佳決策！

你好！線性規劃 (Linear Programming, LP) 是決策數學中最實用且令人興奮的領域之一。它的核心在於：在給定一系列限制（約束條件）的情況下，找出最佳的結果——通常是實現利潤最大化或成本最小化。

在本章中，我們將學習如何將現實生活中的問題轉化為數學模型，並透過圖解法將其解決。如果「規劃」(Programming) 這個詞聽起來讓你感到畏懼，請別擔心；在這裡，它僅指規劃或排程。我們本質上是在使用幾何學來解決優化問題！

章節背景：本課題是 單元 D1：決策數學 1 (Decision Mathematics 1) 的核心部分。

---

1. 線性規劃的基礎

什麼是優化 (Optimization)？

在 D1 中，優化是指找出某事物的最大值或最小值。當所有相關關係均為線性（直線）時，線性規劃提供了一種系統化的方法來達成此目標。

線性規劃問題的三大基本要素

每一個線性規劃問題都必須包含以下三項：

1. 決策變數 (Decision Variables)： 這是我們試圖確定的數量。通常以 \(x\) 和 \(y\) 表示。
   例子：工廠應生產的 A 類椅子數量 (\(x\)) 和 B 類桌子數量 (\(y\))。
2. 目標函數 (Objective Function)： 這是我們想要最大化（如利潤、收入）或最小化（如成本、時間）的公式。它必須是一個關於決策變數的線性方程式。
3. 約束條件 (Constraints)： 這是對可用資源的限制。它們以線性不等式表示。
   例子：組裝的總可用時間不得超過 100 小時：\(2x + 5y \le 100\)。

---

2. 建立線性規劃模型

解決任何線性規劃問題的第一步，就是將文字敘述翻譯成數學語言。這通常是最具挑戰性的部分，請務必謹慎遵循以下步驟。

分步建立指南

1. 定義決策變數

清楚說明 \(x\) 和 \(y\) 代表什麼。請務必具體，必要時包含單位。

例子：設 \(x\) 為生產大袋裝的數量，\(y\) 為生產小袋裝的數量。

2. 列出目標函數

確定目標是最大化 (Max) 還是最小化 (Min)。寫下要優化的數量的公式，通常以 \(P\)（利潤，Profit）或 \(C\)（成本，Cost）表示。

例子：如果每袋大袋裝 (\(x\)) 利潤為 $5，每袋小袋裝 (\(y\)) 利潤為 $3，則目標函數為：

$$\text{Maximize } P = 5x + 3y$$

3. 建立約束條件（不等式）

找出問題強加的每一項限制（時間、材料、產能等）。

• 不等式方向檢查：
  • 「不得超過」、「最多」、「最大」、「限於」均表示 \(\le\)（小於或等於）。
  • 「至少」、「必須大於」、「最低」均表示 \(\ge\)（大於或等於）。
  • 若某項必須等於特定值，則使用 \(=\)（儘管這在 D1 圖解題中較罕見）。
• 非負約束 (Non-Negativity Constraints)： 由於你不可能生產負數的產品，務必加入： $$\mathbf{x \ge 0 \quad \text{且} \quad y \ge 0}$$

  （這些約束至關重要，它們定義了圖表的第一象限。）

建模重點總結

深呼吸並進行翻譯： 仔細閱讀問題，設定變數，寫下目標（目標函數），並列出限制（約束條件）。只要模型建立得正確，圖解部分就簡單多了！

---

3. 圖解法：尋找可行區域 (Feasible Region)

模型建立後，必須使用圖表來求解。由於我們處理的是兩個變數 (\(x\) 和 \(y\))，我們可以使用二維坐標平面。

步驟 1：繪製約束直線

要繪製不等式（例如 \(2x + y \le 10\)），我們首先將其視為方程式以畫出邊界線：

$$\mathbf{2x + y = 10}$$

• 找出截距：
  • 令 \(x=0\) 找出 y 截距。 （此處：\(y=10\)。點為 \((0, 10)\)）
  • 令 \(y=0\) 找出 x 截距。 （此處：\(2x=10\)，故 \(x=5\)。點為 \((5, 0)\)）
• 連接這些截距畫出一條直線。

步驟 2：識別可行區域 (R)

可行區域 (R) 是圖表中所有約束條件同時滿足的區域。我們需要判斷直線的哪一側代表該不等式。

測試點法 (Test Point Method)：

1. 選擇一個測試點，通常使用原點 \((0, 0)\)，除非直線經過原點。
2. 將 \((0, 0)\) 代入原不等式中。
3. 如果不等式成立（例如 \(0 \le 10\)），則可行區域位於包含 \((0, 0)\) 的那一側。
4. 如果不等式不成立（例如 \(0 \ge 10\) 為假），則可行區域位於另一側。

陰影慣例： 在決策數學中，標準做法是將「不需要的區域」（不可行區域）塗上陰影。這樣會使可行區域 (R) 保持清晰且無陰影，通常是一個由相交直線定義的多邊形。

記得包含約束條件 \(x \ge 0\)（遮蓋 y 軸左側）和 \(y \ge 0\)（遮蓋 x 軸下方）。

可行區域重點總結

可行區域 (R) 是圖表中唯一存在有效解的區域。R 的邊界即為約束直線。

---

4. 尋找最佳解

線性規劃的基本定理指出，最佳解（最大值或最小值）總是出現在可行區域 R 的其中一個頂點 (vertices)（角落點）上。

我們有兩種主要方法來找到這個最佳值：

方法 A：目標線法（搜尋線法）

此方法涉及繪製目標函數，並將其在可行區域內移動。

步驟 1：確定目標函數的斜率

設目標函數為 \(P = ax + by\)。為了將其畫成直線，我們將 \(P\) 設為一個方便的常數 \(k\)：

$$ax + by = k$$

將其重排為 \(y = mx + c\) 的形式以求出斜率 (\(m\))。

$$by = -ax + k \quad \implies \quad y = -\frac{a}{b}x + \frac{k}{b}$$

目標線的斜率為 \(m = -\frac{a}{b}\)。

步驟 2：繪製目標線

為 \(k\) 選擇一個能讓截距易於繪製的值（例如，如果 \(P = 3x + 2y\)，選擇 \(k=6\)，得出 \(3x + 2y = 6\)）。畫出這條線。這就是你的搜尋線 (Search Line)。

步驟 3：滑動直線

• 使用一把與搜尋線平行的尺。
• 如果你在進行最大化，滑動尺使其盡可能遠離原點，同時仍與可行區域 R 接觸。
• 如果你在進行最小化，滑動尺使其盡可能靠近原點，同時仍與可行區域 R 接觸。

步驟 4：識別最佳頂點

尺最後接觸到的點（單一個頂點或整條邊）即為最佳值。

💭 記憶小撇步： 當進行最大化時，你希望 \(P\) 的值盡可能大，因此你要最大化與原點（\(P=0\) 處）的距離。

方法 B：頂點測試法（角點法）

此方法簡單明瞭，但需要代數準確性來求出每個頂點的確切坐標。

步驟 1：列出所有頂點 (角點)

列出可行區域 R 的每一個角點坐標。使用聯立方程式求出由兩條約束直線交點所形成的確切頂點坐標。

例子：如果頂點 V 由 \(x + 2y = 10\) 和 \(x + y = 7\) 形成，則聯立解出 \((4, 3)\)。

步驟 2：代入目標函數

將每個頂點的坐標代入目標函數 (\(P\) 或 \(C\)) 進行測試。

例子：如果 \(P = 5x + 3y\)：

• 頂點 A \((0, 0)\)：\(P = 5(0) + 3(0) = 0\)
• 頂點 B \((5, 0)\)：\(P = 5(5) + 3(0) = 25\)
• 頂點 C \((4, 3)\)：\(P = 5(4) + 3(3) = 29\)

步驟 3：陳述最佳解

找出產生所需最大值或最小值的頂點。

例子：若要最大化，最佳值為 29，出現在 \((4, 3)\) 處。

---

5. 進階解釋與特殊情況

情況 1：非整數解與整數解

通常，變數 \(x\) 和 \(y\) 必須代表離散項目（如汽車、人數或包裝數量），因此必須為整數。

如果你的數學最佳解（透過方法 A 或 B 找到）是非整數——例如在 \((4.2, 3.8)\) 處取得最大利潤——你必須檢查可行區域 R 內或邊界上的相鄰整數點。

如何尋找整數最佳解：

1. 找出最佳的非整數頂點 \(V\)。
2. 觀察最接近 \(V\) 且仍在 R 內或邊界上的周圍整數坐標。
3. 將這些附近的整數點代入目標函數中進行測試。
4. 產生最佳結果的點即為整數最佳解。

重要提示： 當從非整數最佳解移動到整數點時，確保你移動的方向是使目標函數減少最少（如果最大化）或增加最少（如果最小化）的方向。

情況 2：多個最佳解

如果目標函數的斜率與其中一條約束邊界的斜率完全相同，那麼最佳解不會出現在單一點上，而是沿著整條邊緣線段分佈。

在這種情況下，連接頂點 A 和頂點 B 的邊界線段上的任何一點都會產生相同的最佳值。

在考試中回答此問題： 陳述最大/最小值，並說明它發生在連接頂點 A 到頂點 B 的線段上的所有點（包含端點）。

解釋與最終答案

最後一步永遠是將你的數學答案放回原始問題的情境中。

如果你的解是 \(x=10, y=5\) 且最大利潤為 $120：

最終答案： 該公司應生產 10 個單位 X 和 5 個單位 Y，以實現 $120 的最大利潤。