线性规划——单纯形法与图解法

线性规划是一种在满足线性约束条件的前提下，求线性目标函数最优值的方法，例如最大利润或最小成本。对于两个变量的问题，图解法通过找出可行域并检查其顶点来求解。对于更大规模的问题，单纯形法用代数方式实现同样的顶点思想。

只有当目标函数和约束条件都是线性的时，才能使用线性规划。如果关系是弯曲的、非线性的，或者包含像 $xy$ 这样的乘积项，那么这个模型就不是线性规划。

线性规划的定义

$$\text{maximize or minimize } z = c_1x_1 + c_2x_2 + \cdots + c_nx_n$$

满足如下约束，例如

$$a_{11}x_1 + a_{12}x_2 + \cdots + a_{1n}x_n \le b_1$$

以及其他类似的线性不等式，同时还可能有像 $x_i \ge 0$ 这样的条件，当变量取负值没有实际意义时尤其如此。

满足所有约束条件的点的集合称为可行域。线性规划要回答的问题是：在这些可行点中，哪一个能使目标函数取得最优值？

图解法是如何工作的

如果只有两个决策变量，你可以把每个约束条件画在 $xy$ 平面上。所有允许区域的重叠部分就是可行域。

该区域中的每一个点都是一个有效解。目标函数会给每个点对应一个数值。

对于线性规划，一个关键事实是：如果最优解存在，那么至少有一个最优解出现在可行域的顶点上。这就是为什么图解法关注顶点，而不是去检查阴影区域中的每一个点。

例题：用图解法求解线性规划问题

假设一家工厂生产两种产品，$A$ 和 $B$。

• 产品 $A$ 的单位利润：$3$
• 产品 $B$ 的单位利润：$5$
• 机器工时限制：每生产 1 单位 $A$ 需要 $1$ 小时，每生产 1 单位 $B$ 需要 $2$ 小时，总工时最多为 $8$ 小时
• 装配工时限制：每生产 1 单位 $A$ 需要 $1$ 小时，每生产 1 单位 $B$ 需要 $1$ 小时，总工时最多为 $5$ 小时

设 $x$ 为产品 $A$ 的产量，$y$ 为产品 $B$ 的产量。

最大化

$$P = 3x + 5y$$

满足

$$x + 2y \le 8$$ $$x + y \le 5$$ $$x \ge 0,\quad y \ge 0$$

求顶点

根据坐标轴和约束直线，可行域的顶点为

• $(0,0)$
• $(5,0)$
• $(0,4)$
• $(2,3)$

点 $(2,3)$ 来自求解边界方程组

$$x + 2y = 8,\quad x + y = 5$$

两式相减得 $y = 3$，再代入得到 $x = 2$。

在每个顶点处计算目标函数值

计算每个顶点处的利润：

• 在 $(0,0)$ 处，$P = 0$
• 在 $(5,0)$ 处，$P = 15$
• 在 $(0,4)$ 处，$P = 20$
• 在 $(2,3)$ 处，$P = 21$

所以最大利润为

$$P = 21$$

取得于

$$(x,y) = (2,3)$$

这就是图解法的一句话总结：画出可行域，找出顶点，并在这些点上计算目标函数值。

单纯形法的直观理解

图解法只在两个变量时比较实用；如果你愿意想象三维区域，有时三个变量也可以。现实中的优化问题往往有很多变量，因此再去画出可行域就不现实了。

单纯形法保留了同样的顶点思想，但它是用代数方式来完成的。粗略地说，它会从一个可行顶点移动到另一个能改进目标函数值的可行顶点，并在没有相邻移动能带来更优值时停止。

因此，一个很好的理解方式是：

• 图解法：直接看到顶点
• 单纯形法：不画图也能在顶点之间导航

这里讲的是直观思路，而不是完整算法。真正的单纯形法会使用单纯形表或等价的代数形式，来决定每一步哪个变量进入基、哪个变量离开基。

为什么顶点很重要

线性目标函数会形成一族等值线，例如

$$3x + 5y = k$$

其中 $k$ 取不同的值。随着这条直线向利润更大的方向平移，它最后仍与可行域接触的位置，就是最大值出现的位置。

在很多图形中，这个最后接触点是某一个单独的顶点。如果目标函数的等值线与某条边界边平行，那么这条边上的多个点都可能是最优解。在这种情况下，仍然至少存在一个最优顶点。

常见错误

把“可行”误认为“最优”

一个点可能满足所有约束条件，但仍然不能使目标函数达到最大或最小。可行只表示它是允许的。

忘记非负条件

如果 $x$ 和 $y$ 表示产量或运输量，负值通常没有实际意义。漏掉 $x \ge 0$ 或 $y \ge 0$ 会改变整个问题。

认为答案一定是整数

普通线性规划允许分数解。如果变量必须取整数，例如卡车数量或工人数，那么你需要整数规划模型，或者额外加入整数约束。

认为每个问题都有最优解

有些线性规划是不可行的，也就是说没有任何点能满足所有约束。还有一些问题是无界的，也就是说目标函数可以无限改进。只有当约束条件足够限制问题时，才会得到有限的最优值。

变量太多时仍使用图解法

一旦变量很多，画图就不再是合适的工具。这时就需要单纯形法或其他优化方法。

线性规划的应用场景

当决策需要在有限资源之间进行分配，并且目标与限制都可以用线性关系建模时，就会用到线性规划。典型例子包括生产计划、运输、人员安排、配料、排程和预算分配。

模型的效果取决于它的假设是否合理。如果真实关系并不接近线性，或者变量必须是整数，那么普通线性规划可能只能作为一个起点。

试着做一道类似的题

找一个包含两种产品、两个资源限制和一个利润函数的小型应用题。自己设变量、画约束图像，并测试各个顶点。一旦你真正理解了这个思路，单纯形法就会容易得多，因为它只是把同样的逻辑扩展到了更高维空间。