ILP 基礎與 PuLP 入門
整數線性規劃 (Integer Linear Programming) 是數學最佳化中最重要的方法之一。它的核心是：用線性方程式描述問題，並要求部分或全部變數為整數。
目標: 最大化/最小化 c₁x₁ + c₂x₂ + ... + cₙxₙ
限制:
a₁₁x₁ + a₁₂x₂ + ... + a₁ₙxₙ ≤ b₁
a₂₁x₁ + a₂₂x₂ + ... + a₂ₙxₙ ≤ b₂
...
x₁, x₂, ..., xₙ ≥ 0
部分 xᵢ 為整數
安裝 PuLP
pip install pulp
第一個 ILP 模型：生產規劃
import pulp
# 建立問題（最大化利潤）
prob = pulp.LpProblem("生產規劃", pulp.LpMaximize)
# 決策變數：每個產品的生產數量
x1 = pulp.LpVariable("產品A", lowBound=0, cat="Integer")
x2 = pulp.LpVariable("產品B", lowBound=0, cat="Integer")
# 目標函數：最大化利潤
prob += 40 * x1 + 30 * x2, "總利潤"
# 限制條件
prob += 2 * x1 + 1 * x2 <= 100, "原料限制"
prob += 1 * x1 + 2 * x2 <= 80, "工時限制"
prob += x1 <= 40, "產品A市場需求"
# 求解
prob.solve()
print(f"求解狀態: {pulp.LpStatus[prob.status]}")
print(f"產品A 生產: {int(x1.value())} 單位")
print(f"產品B 生產: {int(x2.value())} 單位")
print(f"總利潤: {pulp.value(prob.objective)}")
更多章節內容持續建置中...
更多實作範例
使用 PuLP 求解
from pulp import *
# 定義問題
prob = LpProblem("Constrained Optimization", LpMaximize)
# 決策變數
x = LpVariable("x", 0, 10)
y = LpVariable("y", 0, 10)
# 目標函數
prob += 3*x + 4*y
# 限制條件
prob += 2*x + y <= 8
prob += x + 2*y <= 8
# 求解
prob.solve()
print(f'Status: {LpStatus[prob.status]}')
print(f'x = {value(x)}, y = {value(y)}')
print(f'Objective = {value(prob.objective)}')
應用場景
- 資源分配：在有限預算下最大化產出
- 排程問題：最小化工廠閒置時間
- 投資組合：在風險限制下最大化報酬
まとめ
- ILP は線形計画法に整数制約を加えたもの
- 分枝限定法 が ILP の主要な解法
- PuLP は Python で ILP を解くためのライブラリ
- 実際の問題では、問題の規模が大きくなると求解時間が急増する
線性規劃的力量
想像你要為一家工廠決定生產 A 產品和 B 產品各多少件，才能在資源限制下獲得最大利潤。
這就是線性規劃 (Linear Programming) 的典型場景——用數學模型描述商業問題，讓電腦幫你找出最佳解。
線性規劃的三個要素
| 要素 | 說明 | 工廠範例 | |:----:|:----:|:--------:| | 決策變數 | 你要決定的數量 | 生產 A 產品 x 件，B 產品 y 件 | | 目標函數 | 你要最大化或最小化的值 | 最大化利潤：$50x + $40y | | 限制條件 | 資源、時間、需求等限制 | 原料 ≤ 1000kg，工時 ≤ 500hr |
PuLP 是 Python 中最簡單易用的 LP 函式庫，讓你可以用直觀的語法描述這些要素。
下一章預告：從 ILP 到排班
ILP 是基礎工具，可以用來解決各種商業問題。下一章將把 ILP 應用到人員排班問題——這可能是 ILP 最常見也最實用的商業場景。