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

在算法建模 (Modelling with Algorithms) 的這一章中，你將學會如何做出「最佳」決策。無論是工廠如何在有限資源下實現利潤最大化，還是物流公司如何在控制燃料成本的同時提升效率，線性規劃 (Linear Programming, LP) 都是他們所依賴的數學工具。別擔心一開始會看到很多術語——其實線性規劃的核心非常簡單，就是找到善用現有資源的最佳方法！

1. 問題建模 (Formulation)

在解決問題之前，我們必須先將它從「文字描述」轉譯成「數學語言」，這個過程稱為建模 (Formulation)。

線性規劃的組成要素

  • 決策變數 (Decision Variables)： 代表你可以控制的項目。例如：設 \(x\) 為生產標準款單車的數量，\(y\) 為生產專業款單車的數量。
  • 目標函數 (Objective Function)： 這是你的最終目標。通常是想要極大化 (maximize)（例如利潤）或極小化 (minimize)（例如浪費）。公式看起來像這樣：\(P = 5x + 8y\)。
  • 限制條件 (Constraints)： 這是你面臨的限制（如資金、時間、原料）。它們通常以不等式表示。例如：\(2x + 3y \le 60\)（表示可用的勞動工時）。
  • 非負限制 (Non-negativity)： 在現實世界中，你不可能生產負數量的單車！因此，我們必須加上 \(x \ge 0, y \ge 0\)。

標準型 (Standard Form)

當你的目標是極大化一個線性函數，所有的限制條件皆為小於或等於 (\(\le\)) 一個常數，且所有變數皆為非負數時，該線性規劃問題即處於標準型。

重點速覽：
變數： 我們要選擇什麼？
目標： 我們的目標是什麼？
限制： 有什麼規則必須遵守？

核心觀念： 建模就是將文字題目轉化為一組方程式與不等式的過程。

2. 鬆弛變數與增廣型 (Slack Variables and Augmented Form)

直接處理不等式比較困難，我們更偏好使用等式。為了將 \(\le\) 不等式轉換為 \(=\) 等式，我們需要引入一個鬆弛變數 (slack variable)。

類比：想像你有 50 英鎊的預算，你花了 \(x\) 英鎊。那剩下的「鬆弛量」就是你口袋裡的零錢。花費 + 餘額 = 50 英鎊。

運作方式：

如果你的限制條件是 \(2x + y \le 10\)，加上一個鬆弛變數 \(s_1\) 後會變成：
\(2x + y + s_1 = 10\)，其中 \(s_1 \ge 0\)。
這就是所謂的增廣型 (augmented form)（也稱為鬆弛型）。

常見錯誤： 忘記鬆弛變數也必須是非負的 (\(s \ge 0\))。

3. 圖解法 (2-D 問題)

如果問題只有兩個變數 (\(x\) 和 \(y\))，你可以直接在圖表上畫出來解決！

解題步驟：

  1. 畫出直線： 將不等式視為方程式（例如，畫出直線 \(x + y = 10\)）。
  2. 找出可行解區域 (Feasible Region)： 這是圖表上滿足所有限制條件的區域。可以將其視為「安全區」。
  3. 處理無解情況： 如果沒有任何區域同時滿足所有規則，則該問題為不可行 (infeasible)——即無解！
  4. 找到最佳點： 最佳解總是在可行解區域的頂點 (vertex)（角落）。你可以通過以下方式找到它：
    • 頂點測試 (Vertex Testing/Enumeration)： 計算每一個角落的目標函數值進行比較。
    • 目標線法 (Objective Line Method)： 畫出一條代表目標函數的直線，並將其平行移動，直到接觸到「安全區」最遠的邊界點。

整數線性規劃 (Integer Linear Programming, ILP)

有時變數必須是整數（你不可能賣出半台單車）。這就是整數線性規劃 (ILP)。
警告： 最好的整數解可能不是「數學計算結果」最接近的整數。你必須檢查可行解區域內附近的所有整數點。

你知道嗎？ 儘管我們生活在三維空間中，你依然可以想像三維的線性規劃，其可行解區域就像一個立體的晶體，而限制條件則是平面！

4. 單純形法 (The Simplex Method)

如果有 10 個變數怎麼辦？你沒法畫出 10 維的圖表！單純形法 (Simplex Method) 是一種代數算法，它會從可行解區域的一個角落移動到另一個「更好」的角落，直到找到最佳解為止。

關鍵術語：

  • 單純形表 (Tableau)： 用於組織方程式的表格。
  • 主元 (Pivot)： 表格中用來轉換到下一個角落的特定數值。
  • 基變數 (Basic Variables)： 當前頂點中「活躍」的變數。
  • 非基變數 (Non-basic Variables)： 當前頂點中值為零的變數。

運作邏輯：

算法會檢查單純形表的最後一行（目標函數行）。如果出現負數（在極大化問題中），代表我們還有提升利潤的空間！我們選擇一個主元列與行，執行「列運算」來建立新的表格，並不斷重複，直到最後一行所有的數值皆為正數或零。

別擔心這看起來很複雜！ 只要把它想成一種系統性的方法，讓你不用畫圖也能檢查形狀的所有角落。

重點速覽： 當目標函數值無法再提升時，單純形法就會停止。

5. 非標準型問題

有時候規則會改變，以下是處理方法：

  • 大於等於限制 (\(\ge\))： 這需要使用兩階段單純形法 (Two-Stage Simplex)。在第一階段，你需要先找到一個合法的起始頂點。
  • 等式限制 (\(=\))： 可以拆解為兩個不等式：\(x \le 4\) 與 \(x \ge 4\)。
  • 極小化問題： 大多數軟體與單純形法預設為極大化。若要極小化成本，你可以改為極大化成本的負值！

6. 作為線性規劃的網絡問題

線性規劃最酷的地方在於，它可以解決許多你已經學過的網絡問題！

  • 最短路徑 (Shortest Path)： 尋找最快路徑可以寫成一個極小化總距離的線性規劃問題。
  • 最大流 (Maximum Flow)： 計算管道流量可以寫成一個極大化流量變數的線性規劃問題。
  • 配對/分配問題 (Matching/Allocation)： 將工人和工作進行最佳化分配以最小化總成本，這也是經典的線性規劃問題。

核心觀念： 線性規劃是一個「通用」工具——幾乎任何涉及線性規則的問題都可以用它來處理。

7. 使用軟體

在現實世界中，我們使用電腦來解決複雜的線性規劃問題。你需要具備解讀輸出結果的能力：

  • 最佳值 (Optimal Value)： 最終的「最佳」結果（例如，最大利潤 = 500 英鎊）。
  • 變數值 (Variable Values)： 每一項應該生產多少數量（例如，\(x=10, y=5\)）。
  • 鬆弛量 (Slack)： 告訴你某個資源是否被完全使用（鬆弛量 = 0），還是有剩餘（鬆弛量 > 0）。

總結： 無論是手算、作圖還是用電腦求解，線性規劃的核心都是壓力（限制條件）下的最佳化。只要掌握建模，剩下的就只是遵循算法步驟而已！