第6讲 线性规划——用不等式组求最优解

从一个朴素的问题开始

某工厂生产甲、乙两种产品。已知：

• 生产 1 件甲产品需要原料 A 2 千克、原料 B 1 千克，利润 3 万元；
• 生产 1 件乙产品需要原料 A 1 千克、原料 B 2 千克，利润 2 万元；
• 原料 A 最多有 10 千克，原料 B 最多有 8 千克。

问：甲、乙各生产多少件时，总利润最大？

这个问题你直觉上就能猜：多生产利润高的甲产品。但甲产品耗的原料 A 更多，而原料 A 更紧缺——你必须在两种产品的产量之间做取舍。

线性规划就是解决这类「在约束条件下求最值」问题的数学工具。 它的核心思想是：把约束条件画成平面区域，把目标函数看成一组平行线，在这个区域里找使目标函数最大的点。

二元一次不等式表示的平面区域

在动手解决问题之前，先搞清楚一件事：一个二元一次不等式 $Ax + By + C > 0$ 在平面直角坐标系中表示什么？

答案：它表示一条直线 $Ax + By + C = 0$ 某一侧的所有点组成的半平面。

判断哪一侧：在直线一侧任取一个不在直线上的点（通常取原点 $(0,0)$ 最方便），代入不等式，如果满足，那这一侧就是解区域；如果不满足，那另一侧才是。

例：画出不等式 $x + y \le 4$ 表示的区域。

先画直线 $x + y = 4$（过点 $(4,0)$ 和 $(0,4)$），取原点测试：$0 + 0 = 0 \le 4$，满足，所以原点在解区域内——即直线的左下方。又因为不等号是 $\le$，直线本身也在区域内（画实线）。

多个不等式的公共区域

实际问题中，约束条件往往不止一个，而是一组不等式。这时需要画出每个不等式的区域，然后取它们的交集——这个交集叫做可行域。

例：不等式组 $\begin{cases} x + y \le 4 \ x \ge 0 \ y \ge 0 \end{cases}$ 的可行域是什么？

• $x + y \le 4$：直线 $x+y=4$ 左下方
• $x \ge 0$：y 轴右侧（含 y 轴）
• $y \ge 0$：x 轴上方（含 x 轴）

三个区域的交集是一个直角三角形，顶点为 $(0,0), (4,0), (0,4)$。

示意图

线性规划的基本概念

把刚才的例子完整地翻译成线性规划的术语：

约束条件：限制决策变量的不等式组，如 $x + y \le 4, x \ge 0, y \ge 0$。

可行域：所有满足约束条件的点 $(x,y)$ 组成的区域。

目标函数：我们要优化的量，如总利润 $z = 3x + 2y$（这里 $x$ 是甲产品件数，$y$ 是乙产品件数）。

最优解：使目标函数取得最大值（或最小值）的可行域内的点。

图解法的本质：目标函数 $z = ax + by$ 可以写成 $y = -\dfrac{a}{b}x + \dfrac{z}{b}$，这是一组斜率为 $-\dfrac{a}{b}$ 的平行线。$z$ 越大（或越小），这组平行线在 y 轴上的截距就越大（或越小）。我们只需要把这组平行线在可行域内平移，找到截距最大（或最小）时的位置，对应的点就是最优解。

图解法求最值

回到开头的问题，用图解法完整求解。

第一步：设变量，列约束。

设生产甲产品 $x$ 件，乙产品 $y$ 件。由题意： $\begin{cases} 2x + y \le 10 & \text{(原料A约束)} \\ x + 2y \le 8 & \text{(原料B约束)} \\ x \ge 0, y \ge 0 & \text{(非负约束)} \end{cases}$

第二步：画可行域。

在平面直角坐标系中画出四个不等式表示的区域，取交集。

直线 $2x + y = 10$ 过点 $(5,0)$ 和 $(0,10)$。 直线 $x + 2y = 8$ 过点 $(8,0)$ 和 $(0,4)$。

两条直线的交点：解方程组 $\begin{cases} 2x + y = 10 \\ x + 2y = 8 \end{cases}$ 得 $x = 4, y = 2$，交点为 $(4, 2)$。

可行域是一个四边形，顶点为 $O(0,0), A(5,0), B(4,2), C(0,4)$。

第三步：平移目标函数，找最优解。

目标函数 $z = 3x + 2y$，写成 $y = -\dfrac{3}{2}x + \dfrac{z}{2}$。

这组平行线的斜率是 $-\dfrac{3}{2}$。我们从下往上平移（增大 $z$），最后离开可行域的点是哪个？

可行域的四个顶点依次代入目标函数：

• $O(0,0)$：$z = 0$
• $A(5,0)$：$z = 15$
• $B(4,2)$：$z = 12 + 4 = 16$
• $C(0,4)$：$z = 8$

所以最优解在点 $B(4,2)$，最大利润为 16 万元。

关键结论：线性规划的最优解一定在可行域的顶点（或边上）取得。 这是因为目标函数是线性的，其等值线是一组平行直线，在凸多边形（可行域）上平移时，极值必然在边界顶点处达到。

深入理解

为什么最优解在顶点？

你可能会问：为什么不用检查可行域内部的点？为什么只要比较顶点就够了？

几何解释：目标函数 $z = ax + by$ 的等值线是一组平行线。当你从很远的地方（$z$ 很小或很大）往可行域平移这组平行线时，第一次碰到可行域的点是「最小值点」，最后离开可行域的点是「最大值点」。因为可行域是凸多边形，这两次「接触」都发生在顶点（或一条边上，此时边上所有点都是最优解）。

代数解释：可行域是若干个半平面的交集，是一个凸多边形。线性函数在凸集上的极值必然在边界上取得，而边界又由线段组成，线性函数在线段上的极值在端点取得。所以极值在顶点。

整点问题

有些实际问题中，变量必须是整数（比如产品件数不能是小数）。这时候「最优解在顶点」的结论可能不够用——顶点坐标不一定是整数。

处理整点问题的方法：

1. 先求出连续情况下的最优解（顶点）
2. 在最优解附近找出所有整点
3. 逐一比较这些整点对应的目标函数值

例：还是上面的问题，但要求 $x, y$ 为整数。顶点 $B(4,2)$ 恰好是整点，所以最优解不变——甲 4 件、乙 2 件，利润 16 万元。

如果顶点不是整点（比如交点是 $(3.5, 2.3)$），就需要在附近枚举整点：$(3,2), (3,3), (4,2), (4,3)$ 等，分别代入目标函数比较。

实际问题中的注意事项

1. 定义域：实际问题中的变量往往有隐含约束（如 $x, y \ge 0$，且通常要求为整数）
2. 不等号方向：「最多」「不超过」对应 $\le$，「至少」「不低于」对应 $\ge$
3. 检验：求出的最优解要代回所有约束条件验证是否满足
4. 多解情况：如果目标函数的斜率和某条边界线的斜率相同，那么这条边上的所有点都是最优解（无穷多解）

在高中数学体系里的位置

线性规划是高中数学中「不等式应用」板块的核心内容，也是连接代数和几何的重要桥梁。

和函数的联系：线性规划的目标函数本质上是一次函数，最优解问题等价于在一次函数约束下求最值。这为后续学习「凸优化」奠定了基础。

和向量的联系：线性规划的可行域是若干半平面的交集，这些半平面由法向量确定。理解法向量和目标函数梯度之间的关系，有助于从更高视角理解为什么最优解在顶点。

高考地位：线性规划在高考中通常以选择题或填空题的形式出现，也可能作为解答题的一部分（尤其是在应用题中）。难度中等，但要注意实际问题的约束条件和整数要求。

思考与拓展

1. 解不等式组 $\begin{cases} x - y \ge 1 \ x + y \le 5 \ y \ge 0 \end{cases}$，画出可行域并求 $z = 2x + 3y$ 的最大值和最小值。
2. 某工厂生产甲、乙两种产品，每件甲获利 4 万元、乙获利 3 万元。生产一件甲需原料 A 3kg、原料 B 1kg；生产一件乙需原料 A 2kg、原料 B 2kg。现有原料 A 18kg、原料 B 10kg。问如何安排生产使总利润最大？
3. 为什么线性规划的最优解一定在可行域的顶点？你能从代数的角度严格证明吗？
4. 如果目标函数是 $z = x^2 + y^2$（非线性），最优解还在顶点吗？为什么？

一句话总结

线性规划就是把约束条件画成可行域，把目标函数看成一组平行线，在可行域的顶点里找最优解——多边形凸区域的极值，必然在角落上。