跳轉到

10.1 線性規劃入門#

概念說明#

線性規劃（Linear Programming, LP）是形式最簡單、應用最廣的優化問題：在線性等式與不等式限制下，最小化（或最大化）一個線性目標函數。標準形式：

minimize cᵀx，subject to Ax ≤ b, x ≥ 0

它的幾何圖像極其漂亮：每個線性限制是一個半空間，全部限制的交集是一個凸多面體；線性目標的等高線是一組平行超平面。當等高線往外推時，最後碰到的點一定是多面體的頂點——這個「最優解必在頂點」的事實，直接催生了單形法（Simplex Method）：從一個頂點出發，沿著稜線不斷走向目標值更小的相鄰頂點，直到無處可去。單形法實務上飛快（迭代次數約與維度同階），雖然理論最壞情況是指數時間；多項式時間的內點法則是理論與超大規模問題的另一選擇。

LP 的兩個看家概念是對偶性與鬆緊互補：每個 LP 都有個對偶問題，兩者的最優值相等（強對偶定理）；對偶變數（影子價格）告訴你「放寬某個限制一單位，目標能改善多少」——這在資源定價、敏感度分析上價值連城。

演算法步驟#

單形法的概念流程（以頂點跳躍為主軸）：

  1. 找一個可行頂點（引入輔助變數做兩階段法或大 M 法）。
  2. 計算各非基本變數的「改善率」（reduced cost）。
  3. 若所有改善率都非負，當前頂點即最優，停。
  4. 選一個能改善的變數進基（進基規則），決定離基變數（比例測試，維持可行性）。
  5. 做樞軸交換（本質是 5.1 節高斯消去的一步），回到第 2 步。

Python 程式碼範例#

import numpy as np
from scipy.optimize import linprog

# --- 生產排程範例 ---
# 產品 A、B：A 賺 3 元、B 賺 5 元
# 限制：機器時間 2A + B ≤ 8，人力 A + 3B ≤ 9，A,B ≥ 0
c = [-3, -5]                          # linprog 只做最小化 → 取負號
A = [[2, 1], [1, 3]]
b = [8, 9]
res = linprog(c, A_ub=A, b_ub=b, bounds=[(0, None), (0, None)],
              method="highs")
print(f"最優產量: A = {res.x[0]:.3f}, B = {res.x[1]:.3f}")
print(f"最大利潤 = {-res.fun:.3f}")

# --- 幾何驗證：頂點枚舉（二維可以直接列） ---
verts = [(0, 0), (4, 0), (0, 3)]
# 兩條限制的交點：2A+B=8 且 A+3B=9 → A=3, B=2
verts.append((3, 2))
for (a, bb) in verts:
    ok = 2*a + bb <= 8 + 1e-9 and a + 3*bb <= 9 + 1e-9 and a >= 0 and bb >= 0
    if ok:
        print(f"頂點 ({a}, {bb}) → 利潤 {3*a + 5*bb}")
# 應可見最大值出現在 (3, 2)，利潤 19

# --- 影子價格（對偶變數）與敏感度分析 ---
print("限制式影子價格 =", -res.ineqlin.marginals)
# 解讀：機器時間多 1 小時，利潤可增加多少

# --- 運輸問題：多倉多店最小運費 ---
# 2 個倉（供給 20, 30），3 個店（需求 10, 25, 15）
cost = np.array([[4, 6, 9], [5, 3, 8]])
supply, demand = [20, 30], [10, 25, 15]
n_ware, n_store = cost.shape
c2 = cost.flatten()
A_eq = np.zeros((n_ware + n_store, n_ware * n_store))
for i in range(n_ware):
    A_eq[i, i*n_store:(i+1)*n_store] = 1
for j in range(n_store):
    A_eq[n_ware + j, [i*n_store + j for i in range(n_ware)]] = 1
res2 = linprog(c2, A_eq=A_eq,
               b_eq=supply + demand, method="highs")
print(f"最小總運費 = {res2.fun}")
print("各倉→店運量矩陣:\n", res2.x.reshape(n_ware, n_store))

複雜度與誤差分析#

LP 的複雜度取決於演算法：單形法平均 O(mn) 次迭代（每次迭代是一次 O(m²) 的樞軸更新，m 為限制數），最壞 O(2ⁿ)（Klee-Minty 立方體反例）；內點法（HiGHS 的 IPM）O((mn)^{3.5}·log(1/ε)) 有理論保證。實務結論：十萬變數以下用 HiGHS 這類成熟求解器，別自己寫單形——數值細節（退化、循環、Bland 反循環規則）比演算法主體更難。誤差面：LP 是「精確結構 + 浮點實作」，答案可信度看對偶間隙（primal-dual gap），HiGHS 預設要求 gap < 10⁻⁸。建模層面的經驗法則：把問題化成 LP 的關鍵是確認目標與限制都是線性的；「整數解」需求會使問題變成 MILP（整數規劃），複雜度躍升為 NP-hard，常用技巧是 LP 鬆弛 + 分支定界。影子價格的解讀有一個常見誤區：它只在「該限制仍然綁定」的範圍內有效，外推前要查敏感度報告的範圍。

練習#

  1. 把本節生產排程改成三種產品、四條限制，用 linprog 求解，並用「枚舉所有頂點交點」的方式（itertools.combinations 取限制對，解 2×2 線性系統）驗證最優值確實在頂點上。
  2. 實作對偶問題：寫出生產排程的對偶形式（最大化 8y₁ + 9y₂，s.t. 2y₁+y₂ ≥ 3, y₁+3y₂ ≥ 5, y ≥ 0），用 linprog 求解，驗證對偶最優值等於 19（強對偶）。
  3. 運輸問題加上「倉 1 不能送店 3」的限制（令對應成本為極大值或刪除變數），觀察最優解與總運費的變化，並用影子價格解釋新增的配送需求為何特別貴。