📐 线性规划基础

组合优化 · 从理论到实践

📌 核心模块

标准形式 · 单纯形几何 · 对偶理论 · 灵敏度分析 · 整数规划与线性松弛

📌 1. 线性规划标准形式

线性规划 (LP) 的标准形式为：

min  cᵀ x
s.t. A x = b
     x ≥ 0

其中 A 为 m×n 矩阵，b ≥ 0。任何线性规划均可通过引入松弛/剩余变量转化为标准形。

特征	标准形要求	转化技巧
目标	最小化	max cᵀx → min -cᵀx
约束	等式	不等式加松弛/剩余变量
变量	非负	自由变量拆分为 x⁺ - x⁻

📌 2. 单纯形法几何解释

可行域为多面体（凸集），最优解出现在顶点。单纯形法沿边从一个顶点移动到另一个更优的顶点。

▲ 多边形为可行域，红色顶点为最优，虚线为单纯形迭代路径

📌 3. 对偶理论

每个 LP 原问题对应一个对偶问题。弱对偶：cᵀx ≥ bᵀy；强对偶：若原问题有最优解，则对偶也有且最优值相等。

原问题 (Primal)	对偶问题 (Dual)
min cᵀx	max bᵀy
A x = b, x ≥ 0	Aᵀ y ≤ c, y 自由
第 i 个约束等式	变量 yᵢ 无限制
变量 xⱼ ≥ 0	第 j 个约束 ≤

互补松弛性：若 x*、y* 分别为原问题和对偶问题的最优解，则 x*ⱼ (cⱼ - Aᵀⱼ y*) = 0。

📌 4. 灵敏度分析

研究参数 (c, b, A) 变化对最优解的影响。核心工具：影子价格 (对偶变量) 和 允许变化范围。

目标系数 cⱼ：在保持最优基不变时，cⱼ 的允许增减范围。
右端项 bᵢ：影子价格给出 bᵢ 单位变化对目标值的影响。
约束矩阵 A：通常通过重新计算检验数分析。

📌 5. 整数线性规划 & 线性松弛

整数线性规划 (ILP)：变量取整数值。线性松弛 (LP relaxation) 去掉整数约束，提供下界 (最小化)。

🔹 ILP 标准形

min  cᵀx
s.t. A x ≤ b
     x ≥ 0,  x ∈ ℤⁿ

🔸 线性松弛

将 ℤⁿ 替换为 ℝⁿ，得到 LP。若松弛的最优解为整数，则也是 ILP 最优解；否则分支定界。

▲ 网格点为整数解，阴影为线性松弛多面体，橙色为 ILP 最优解

📌 代码示例 · Python 线性规划

使用 PuLP 库求解一个简单的 LP 与 ILP：

# 线性松弛 & 整数规划示例 (PuLP 伪代码风格)
from pulp import *

# 问题定义
prob = LpProblem("Example", LpMinimize)

# 变量
x = LpVariable("x", lowBound=0, cat='Continuous')  # 松弛连续
y = LpVariable("y", lowBound=0, cat='Integer')      # 整数变量

# 目标与约束
prob += 3*x + 2*y
prob += 2*x + y >= 8
prob += x + 3*y >= 6

# 求解
prob.solve()
print(f"松弛最优值: {value(prob.objective)}")   # 连续解

# 若要求整数，将 x 也改为 Integer 即 ILP

👉 线性松弛提供下界，分支定界利用该下界剪枝。