线性约束建模：从实际问题到数学语言

线性规划，说白了就是在一堆线性条件里找最优解。我刚开始接触这个领域时，总觉得它离实际工程很远。直到有一次做资源调度项目，才发现几乎所有约束都能用线性不等式表达——嗯，关键是怎么建这个模。

线性规划基础：三个核心要素

任何一个线性规划问题，都跑不出这三样东西：

• 决策变量——你要决定什么？比如生产多少产品、分配多少资源
• 目标函数——你要优化什么？利润最大化、成本最小化
• 约束条件——你受什么限制？产能、预算、时间窗口

举个我实际做过的例子。某条产线要安排两种产品A和B的生产。A每件利润40元，B每件利润30元。A耗时2小时，B耗时1小时，每天总工时不超过160小时。原材料A消耗3单位，B消耗2单位，每天原料供应不超过240单位。

这个问题的数学形式就是：

最大化：40x₁ + 30x₂
约束：
  2x₁ + x₂ ≤ 160    （工时约束）
  3x₁ + 2x₂ ≤ 240   （原料约束）
  x₁ ≥ 0, x₂ ≥ 0    （非负约束）

你看，就这么简单。但实际项目中，变量可能成百上千，约束条件更是密密麻麻。

约束矩阵构建：把问题装进表格

约束矩阵，就是把所有约束条件的系数整整齐齐排成一张表。每一行是一个约束，每一列是一个变量。

上面那个例子的约束矩阵长这样：

我习惯用矩阵形式 A·x ≤ b 来表示。A是系数矩阵，x是变量向量，b是右端项。这样做的好处是——所有算法都能用统一的数学语言处理。

松弛变量与剩余变量：把不等式变成等式

为什么要引入松弛变量和剩余变量？因为单纯形法只认等式约束。你想想看，一个不等式怎么放进矩阵运算里？

松弛变量用于"≤"约束。它表示"没用完的资源"：

2x₁ + x₂ ≤ 160
→ 2x₁ + x₂ + s₁ = 160, s₁ ≥ 0

s₁就是松弛变量。如果s₁=10，说明工时还剩10小时没用完。

剩余变量用于"≥"约束。它表示"超额完成的部分"：

x₁ + x₂ ≥ 50
→ x₁ + x₂ - s₂ = 50, s₂ ≥ 0

s₂就是剩余变量。如果s₂=5，说明实际产量比最低要求多了5件。

可行域与顶点搜索：解到底在哪

所有满足约束条件的点，构成了一个可行域。这个区域是个凸多边形——嗯，在高维空间里叫凸多面体。

为什么凸性这么重要？因为线性规划的最优解一定在可行域的顶点上。这个性质是单纯形法的理论基础。

我画了一张图，帮你理解这个概念：

单纯形法的思路很直接：从一个顶点出发，沿着边走到相邻的顶点，如果目标函数值变好了就继续走，直到没法再改善为止。这个过程就像爬山——不过是在一个多面体上爬。

顶点搜索的几何直觉

为什么最优解一定在顶点上？我给你一个直观解释。

目标函数是一条等值线（二维）或等值面（高维）。当这条线往最优方向移动时，它最后碰到的可行域边界点——就是顶点。如果等值线刚好和一条边重合，那整条边上的点都是最优解，但顶点仍然包含在其中。

这个性质让线性规划问题从"无限个候选解"变成了"有限个顶点候选"。单纯形法就是利用这个性质，只检查顶点，效率极高。

实际项目中的建模要点

做了这么多年优化项目，我总结了几条建模经验：

1. 变量定义要清晰——每个变量代表什么，单位是什么，必须写清楚。不然三个月后你自己都看不懂。
2. 约束不要冗余——多余的约束不会改变可行域，但会增加求解时间。我曾经见过一个模型里重复了5条一模一样的约束。
3. 注意数值尺度——如果x₁的量级是10⁶，x₂的量级是10⁻³，矩阵会病态。我习惯把所有变量归一化到相近的量级。
4. 先小规模测试——用10个变量、20个约束的小模型验证逻辑，再扩展到全量。这个习惯帮我省了无数调试时间。