U45 線性規劃 (LP) 必考公式

問題結構

一個典型的線性規劃問題包含以下部分：

• 決策變數：通常用 $x$ 和 $y$ 表示。
• 目標函數：需要最大化或最小化的線性函數，記為 $P = ax + by$ 或 $C = ax + by$。
• 約束條件：一組線性不等式（或等式），例如 $x \ge 0$, $y \ge 0$, $ax + by \le c$ 等。
• 可行解區域：所有滿足約束條件的點 $(x, y)$ 所構成的區域。

解題目標是在可行解區域中，找出使目標函數取得最大值或最小值的點，稱為最優解。

頂點檢驗法

對於一個有界可行解區域，若目標函數 $P = ax + by$ 存在最大值或最小值，則最優解必定出現在可行解區域的其中一個頂點上。

解題步驟：

1. 繪出所有約束條件對應的直線，並標示出可行解區域。
2. 找出可行解區域的所有頂點坐標。
3. 將每個頂點的坐標代入目標函數 $P$ 中計算其值。
4. 比較這些值，找出最大值或最小值。

上圖中，陰影區域為可行解區域，紅色點 A, B, C, D 為頂點。最優解必在其中一點取得。

平行線族與最優解

目標函數 $P = ax + by$ 可以寫成 $y = -\frac{a}{b}x + \frac{P}{b}$（假設 $b \ne 0$）。這表示對於不同的 $P$ 值，我們得到一系列斜率為 $-\frac{a}{b}$ 的平行線。$P$ 值越大（或越小），直線在 $y$ 軸上的截距 $\frac{P}{b}$ 也越大（或越小）。

尋找最優解時，我們沿著平行線的法線方向（即 $(a, b)$ 方向）平移這組平行線。對於最大化問題，我們向使 $P$ 值增加的方向平移，直到直線即將離開可行解區域。最後接觸到的點即為最優解。對於最小化問題，則向相反方向平移。

無界解與無可行解

並非所有線性規劃問題都有唯一的最優解。

• 無界解：若可行解區域無界，且目標函數在該區域內可以無限地增大（最大化問題）或減小（最小化問題），則問題有無界解。例如，約束條件只有 $x \ge 0, y \ge 0$，目標為最大化 $P = x + y$。
• 無可行解：若約束條件互相矛盾，導致沒有任何點能同時滿足所有條件，則可行解區域為空集，問題無解。例如，同時要求 $x + y \le 5$ 和 $x + y \ge 10$，且 $x, y \ge 0$。

多重最優解

若目標函數的等值線與可行解區域的一條邊界線平行，則當這條邊界線上的所有點都使目標函數取得相同的最優值時，問題存在多重最優解。

假設目標函數為 $P = 2x + 4y$，而其中一條約束條件是 $x + 2y = k$。由於兩條直線的斜率相同（均為 $-\frac{1}{2}$），若這條邊界線是可行解區域的一部分，則該線段上的所有點都是最優解。

四步解題法

1. 定義變數：清晰定義決策變數 $x$ 和 $y$ 代表什麼。
2. 列出約束：根據題意，將所有限制（如資源上限、最低要求等）翻譯成關於 $x$ 和 $y$ 的線性不等式。別忘記非負約束 $x \ge 0$ 和 $y \ge 0$。
3. 建立目標函數：寫出需要最大化（如利潤、產量）或最小化（如成本、時間）的線性函數 $P$ 或 $C$。
4. 圖解與求解：繪製可行解區域，找出頂點，代入目標函數計算並比較，得出最優解及對應的最優值。

切記在最後的答案中，必須用完整的句子說明最優解是什麼（例如：應生產產品 A 10 件和產品 B 15 件），以及對應的最優值是多少（例如：最大利潤為 $800$）。