2. 线性规划基础：标准形式、图解法与可行域

线性规划，说白了就是在一堆约束条件下，找个最优解。我刚开始接触这玩意儿的时候，觉得它就是个数学游戏。直到后来做供应链调度，才发现这东西真能帮公司省下几百万的物流成本。

今天咱们就聊聊线性规划最核心的三个东西：标准形式怎么写、二维问题怎么画图看、可行域和最优解到底是个啥。

2.1 线性规划的标准形式

你可能会问：为什么非要搞个标准形式？

嗯，原因很简单。所有求解算法，不管是单纯形法还是内点法，都认准了标准形式。你不按这个格式写，算法就不认账。

标准形式长这样：

minimize    c^T x
subject to  Ax = b
            x ≥ 0

拆开来看：

• 目标函数：必须是minimize。如果你遇到maximize，加个负号就行。我习惯在代码里直接写-c，省事。
• 约束条件：必须是等式Ax = b。不等式怎么办？加松弛变量或剩余变量。
• 变量非负：x ≥ 0。如果某个变量没这个限制，拆成两个非负变量的差。

举个例子。假设你有两个约束：

x₁ + x₂ ≤ 10
x₁ - x₂ ≥ 2
x₁, x₂ ≥ 0

转成标准形式：

第一个不等式：加松弛变量 s₁ ≥ 0，变成 x₁ + x₂ + s₁ = 10
第二个不等式：减剩余变量 s₂ ≥ 0，变成 x₁ - x₂ - s₂ = 2
目标函数：假设是 max 3x₁ + 2x₂，改成 min -3x₁ - 2x₂

我在项目中遇到过一个问题：有人把松弛变量和剩余变量搞混了。记住一个口诀——「≤ 加松弛，≥ 减剩余」。这样就不会错了。

2.2 图解法：二维问题的直观理解

二维线性规划，说白了就是画几条直线，然后找交点。我刚开始学的时候，觉得这方法太简单了。但后来发现，正是这种简单，帮我建立了对「可行域」和「最优解」的直觉。

来看一个具体例子：

maximize   z = 3x₁ + 2x₂
subject to x₁ + x₂ ≤ 4
           2x₁ + x₂ ≤ 6
           x₁, x₂ ≥ 0

图解法的步骤，我一般这么走：

1. 画约束直线：把每个不等式当成等式画出来。
2. 判断方向：看看约束是「≤」还是「≥」，确定哪一侧是可行区域。
3. 找可行域：所有约束的交集，就是你能选的方案范围。
4. 画目标函数等值线：比如 z=0, z=6, z=12 这些线。
5. 平移找最优：沿着梯度方向平移，最后一个接触可行域的点就是最优解。

上面这个例子的最优解，你猜在哪？

在两条约束直线的交点 (2, 2) 处。z = 3×2 + 2×2 = 10。

为什么会这样？因为线性规划的最优解，一定在可行域的顶点上。这不是巧合，这是线性规划的基本定理。

2.3 可行域与最优解的概念

可行域，就是所有满足约束条件的点组成的集合。说白了，就是你能选的方案范围。

可行域有三种情况：

• 非空有界：像个多边形，有顶点。这是最常见的情况。
• 非空无界：往某个方向无限延伸。这时候最优解可能不存在（如果目标函数也往那个方向走）。
• 空集：约束条件互相矛盾，没有可行解。我遇到过这种情况，当时检查了半天，发现是约束写反了。

最优解，就是在可行域里让目标函数取到极值的点。

这里有个重要性质：

这个性质有什么用？

你想想看，如果可行域有100万个点，你不可能一个个试。但顶点数量是有限的。单纯形法就是利用这个性质，从一个顶点跳到另一个顶点，直到找到最优解。

我曾经犯过一个错：以为所有优化问题的最优解都在顶点上。结果做非线性优化时，怎么都找不到最优解。后来才意识到，线性规划和非线性规划，本质上是两码事。

2.4 知识体系总览

下面这张图，把本章的核心逻辑串起来了：

2.5 避坑指南

我这些年踩过的坑，分享给你：

• 约束方向搞反：画图时，x₁ + x₂ ≤ 4 和 x₁ + x₂ ≥ 4 是完全相反的。我建议你每次画完，随便取个点验证一下。
• 忘记非负约束：很多人只画了题目给的约束，忘了 x₁ ≥ 0, x₂ ≥ 0。结果可行域画大了，最优解算错了。
• 目标函数方向搞错：最大化问题，等值线往梯度方向平移。最小化问题，往反方向平移。我刚开始也经常搞混。

好了，线性规划的基础就聊到这儿。记住标准形式的三件套、图解法的五步走、以及「最优解在顶点上」这个核心结论。后面咱们聊单纯形法的时候，你会发现这些基础有多重要。

---

公众号:蓝海资料掘金营，微信deep3321