線性規劃｜可行域及目標函數

學習目標

完成本文後，你應能夠：

• 繪畫 線性不等式組並找出 可行域。
• 定義 及 計算 目標函數 在可行域頂點的值。
• 運用 頂點法 求目標函數的 最大值或最小值。
• 處理變量須為整數時的 整數解 問題。
• 將現實問題（生產、資源、利潤）轉化為線性規劃模型。
• 將以上技巧應用於 DSE 風格的題目。

---

1. 引言：

線性規劃 每年 都在 DSE 卷一甲部（2）及乙部出現。題目可能要求你：

• 從一組不等式找出可行域
• 最大化或最小化線性目標函數
• 解涉及有限資源的現實問題
• 處理變量須為整數的情況

這些是高階技能，能幫助你在考試中奪取高分。

2. 繪畫線性不等式

二元線性不等式（例如 \( 2x + 3y \le 12 \)）代表一個半平面。 繪畫步驟如下：

1. 繪畫對應的 邊界線（\( 2x + 3y = 12 \)）。
2. \( \le \) 或 \( \ge \) 用 實線（包括邊界），\( < \) 或 \( > \) 用 虛線。
3. 選擇一個 測試點（例如 \( (0,0) \)）判斷哪一邊滿足不等式。
4. 塗陰影 同時滿足所有不等式的區域——這就是 可行域。

例題

題目：塗出由以下不等式定義的可行域：

\( x \ge 0 \)，\( y \ge 0 \)，\( x + y \le 6 \)，\( 2x + y \le 8 \)

3. 目標函數與頂點法

目標函數 是一個線性表達式，需要最大化或最小化，例如 \( P = 3x + 4y \)。 頂點法 指出：線性目標函數在凸多邊形上的最大值或最小值出現在可行域的頂點之一。

步驟：

1. 找出可行域的所有 頂點。
2. 在每個頂點 計算 目標函數的值。
3. 選取 最大值 或 最小值。

例題

題目：在以下約束下最大化 \( P = 3x + 2y \)：

\( x \ge 0, y \ge 0, x + y \le 5, x + 2y \le 8 \)。

4. 整數解

在現實問題中，變量通常必須是 整數（例如產品數量、人數）。 頂點法可能給出非整數解。要找出最佳整數解：

1. 找出最佳頂點（可能非整數）。
2. 找出可行域內靠近該頂點的所有 整數點。
3. 計算這些整數點的目標函數值。
4. 選擇最佳整數解。

例題

題目：在以下約束下最大化 \( P = 10x + 12y \)，其中 \( x, y \) 為整數：

\( x \ge 0, y \ge 0, 2x + 3y \le 30, 3x + 2y \le 30 \)。

5. 應用題

線性規劃常用於優化涉及有限資源的現實問題。常見應用包括：

• 生產計劃 – 在材料和勞動力限制下最大化利潤。
• 營養問題 – 在滿足營養要求下最小化成本。
• 資源分配 – 分配有限資源以最大化產出。
• 運輸問題 – 最小化運輸成本。

例題

題目：某工廠生產兩種產品 A 和 B。每單位 A 需要 2 小時勞動力和 1 單位材料；每單位 B 需要 1 小時勞動力和 2 單位材料。工廠每週有 100 小時勞動力和 80 單位材料。產品 A 的利潤為每單位 $30，B 為每單位 $20。應各生產多少以最大化利潤？

6. 例題

例題 1：基本線性規劃

題目：在以下約束下最小化 \( C = 4x + 5y \)：

\( x \ge 0, y \ge 0, x + 2y \ge 6, 3x + y \ge 6 \)。

例題 2：整數解

題目：在以下約束下最大化 \( P = 6x + 5y \)，其中 \( x, y \) 為整數：

\( x \ge 0, y \ge 0, 2x + y \le 10, x + 3y \le 12 \)。

例題 3：應用題

題目：某麵包師製作蛋糕和餅乾。每個蛋糕需要 3 杯麵粉和 2 杯糖；每個餅乾需要 2 杯麵粉和 1 杯糖。麵包師有 60 杯麵粉和 40 杯糖。蛋糕利潤為 $5，餅乾利潤為 $3。應各製作多少以最大化利潤？

7. DSE 風格練習題

8. 題解

基礎練習

點擊下列鏈接查閱：
 練習編 - 線性規劃｜可行域及目標函數

重點總結

---

複習清單

• 繪畫線性不等式
• 找出可行域（塗陰影區域）
• 求可行域的頂點
• 在頂點計算目標函數
• 選取最大／最小值
• 處理整數解：檢查附近的整數點
• 將文字題轉化為約束和目標函數