3. 线性规划与整数规划：从理论到实战
线性规划这东西，说白了就是在一堆约束条件下找最优解。我刚开始接触时也觉得挺玄乎，后来发现它无处不在——排班、物流、生产计划，甚至你点外卖时骑手的路线规划，背后都有它的影子。
这一章我们聊聊线性规划的标准形式、单纯形法的核心思想，然后进入整数规划的建模，最后用分支定界法收尾。嗯，内容不少，但都是硬核干货。
3.1 线性规划标准形式
先问个问题：为什么要有标准形式？
我个人习惯是，任何算法都需要一个统一的输入格式。线性规划的标准形式就像是一个约定——所有问题都先转换成这个格式，然后算法才能统一处理。
标准形式长这样：
minimize c^T x
subject to Ax = b
x ≥ 0其中：
- x 是决策变量向量
- c 是成本系数向量
- A 是约束矩阵
- b 是右端项向量
关键点：标准形式要求所有约束都是等式，所有变量非负。目标函数是求最小值。
你可能会问：实际中很多约束是不等式啊？没错，所以需要引入松弛变量和剩余变量来转换。比如：
原始约束：x₁ + 2x₂ ≤ 10
转换后： x₁ + 2x₂ + s₁ = 10, s₁ ≥ 0我在项目中遇到过一个问题：某工厂的生产计划，原本有20个不等式约束。我花了半小时把它们全部转成标准形式，结果发现漏了一个变量的非负约束——嗯，这种低级错误我犯过一次就记住了。
3.2 单纯形法思想
单纯形法，说白了就是沿着可行域的边边走，每次走到一个更好的顶点。为什么是顶点？因为线性规划的最优解一定在顶点上——这是理论保证。
算法核心步骤：
- 找到一个初始可行解（顶点）
- 检查当前解是否最优（检验数判断）
- 如果不是，沿着改善方向移动到相邻顶点
- 重复直到找到最优解
我的经验：单纯形法在实际中很少手算，但理解它的几何意义很重要。我曾经用Python手写过一次单纯形法实现，虽然效率不高，但对理解算法本质帮助极大。
这里有个避坑指南：我曾经以为单纯形法一定能快速收敛，直到遇到一个退化问题——迭代了上百次还在原地打转。后来加了Bland's规则才解决。所以，退化问题需要特殊处理。
3.3 整数规划建模
现实世界中，很多决策变量必须是整数——比如人数、机器台数、是否建厂。这就是整数规划的用武之地。
整数规划建模的常见技巧：
- 0-1变量：表示是否选择某个选项
- 整数变量：表示数量、次数等
- 逻辑约束：用大M法处理if-then条件
举个例子，选址问题：
变量：yᵢ = 1 如果在i地建厂，否则0
xᵢⱼ = 从i地运往j地的货物量
约束：
∑xᵢⱼ ≥ dⱼ （满足需求）
∑xᵢⱼ ≤ Cᵢ · yᵢ （容量限制，大M法）
yᵢ ∈ {0,1}, xᵢⱼ ≥ 0注意：整数规划比线性规划难求解得多。我曾经把一个整数规划问题直接扔给求解器，结果跑了两个小时没出结果——后来发现是模型规模太大，需要先做预处理。
3.4 分支定界法入门
分支定界法是求解整数规划最经典的方法。它的思想很简单：
- 先忽略整数约束，求解线性规划松弛问题
- 如果解已经是整数，结束
- 否则，选择一个非整数变量，分支成两个子问题
- 对每个子问题重复上述过程
举个例子：
原始问题：max 3x + 2y
s.t. 2x + 3y ≤ 12
x, y ≥ 0 且为整数
松弛解：x=3.5, y=1.67, 目标值=13.84
分支：
左分支：x ≤ 3 → 解为 x=3, y=2, 目标值=13
右分支：x ≥ 4 → 解为 x=4, y=1.33, 目标值=14.66（非整数，继续分支）核心技巧：分支定界法的效率取决于剪枝能力。如果某个分支的上界已经低于当前最优解，直接剪掉——这就是"定界"的作用。
我记得有一次做排班优化，问题有50个员工、7天、3个班次，整数变量多到爆炸。用分支定界法，配合好的剪枝策略，半小时就找到了最优解。如果不用剪枝，估计要算到天荒地老。
知识体系总览
下面这张图展示了本章的核心逻辑：
这张图把本章内容串起来了。左边是线性规划的两大核心：标准形式和单纯形法；右边是整数规划的两大核心：建模技巧和分支定界法。底部那条线，就是我们从理论到实战的路径。
实战建议：如果你刚开始学，我建议先手算一个小规模的单纯形法例子（比如2个变量、3个约束），感受一下迭代过程。然后再用Python的PuLP或Google OR-Tools跑一遍，对比结果。这样理论结合实践，学得最扎实。
好了，这一章的内容就到这里。线性规划和整数规划是组合优化的基石，理解透了后面学图论、网络流都会轻松很多。
公众号:蓝海资料掘金营，微信deep3321