线性规划

线性规划（linear programming）是在一组线性约束下，使线性目标函数最大或最小的问题。它常用于分配有限资源、安排生产和运输。这里的变量可以连续取值；若产品件数等变量必须为整数，就需要进一步研究整数规划。

下面用同一个两产品模型，依次说明怎样建立约束、从图上找答案、用不等式证明最优，以及资源增加后答案怎样变化。

把资源和收益排成一张表

设两种产品的产量为 $x, y$ ，都允许连续分割。采用以下教学数据，各种资源分别使用自己的统一计量单位，收益使用同一货币单位。

项目	每单位产品 $x$	每单位产品 $y$	可用总量
第一种资源	1	1	4
第二种资源	2	1	5
单位收益	3	2	—

第一种资源的总消耗为 $x + y$ ，不能超过四；第二种资源为 $2 x + y$ ，不能超过五。产量不能为负，总收益是 $3 x + 2 y$ ，所以模型为 $max 3 x + 2 y, x + y \leq 4, 2 x + y \leq 5, x \geq 0, y \geq 0.$ “线性”表示变量只以常数倍相加的方式出现。这个模型假定单位资源消耗和收益不随产量改变；若有启用设备的固定成本或阶梯价格，就须修改模型。

先画出哪些方案可行

等式 $x + y = 4$ 是一条直线，不等式 $x + y \leq 4$ 取包含原点的一侧。第二条资源约束也给出一个半平面。再限制 $x, y \geq 0$ ，各区域共同部分就是可行域。

沿横轴，令 $y = 0$ ，两种资源分别要求 $x \leq 4$ 、 $x \leq 5 / 2$ ，所以横轴终点是 $(5 / 2, 0)$ 。沿纵轴，两个上限分别是四、五，所以纵轴终点是 $(0, 4)$ 。

两条资源边界的交点由 $x + y = 4, 2 x + y = 5$ 确定。第二式减第一式得 $x = 1$ ，代回得 $y = 3$ 。加上原点，可行域的四个顶点为 $(0, 0), (5 / 2, 0), (1, 3), (0, 4)$ 。

第一象限内两种资源约束形成四边形，目标直线三x加二y等于九在一三处接触可行域 — 阴影内每一点都是可行产量。平移收益相同的虚线，最后接触可行域的位置为 (1,3)。

收益相同的方案满足 $3 x + 2 y = c$ ，即 $y = - 3 x / 2 + c / 2$ 。改变 $c$ ，直线斜率不变，只是平行移动。向收益更高的方向移动，最后一次接触可行域时经过 $(1, 3)$ ，收益为九。

四个顶点收益分别为零、 $15 / 2$ 、九、八。为什么本例只检查顶点就够？这个凸四边形可以沿对角线分成两个三角形；三角形内每一点都可写成三个顶点的非负加权平均，权重和为一。线性目标在该点的值，也是顶点目标值的同一加权平均，不会超过其中最大值。因此至少有一个顶点达到最大收益。

这不保证最优点总唯一。若目标改为 $x + y$ ，从 $(0, 4)$ 到 $(1, 3)$ 的整条边都取得四，所有这些点都最优。

用两行不等式证明答案

图形有助于找到候选点，证明则可以更短。把两条资源约束相加： $(x + y) + (2 x + y) \leq 4 + 5, 3 x + 2 y \leq 9.$ 任何可行方案的收益都不会超过九。点 $(1, 3)$ 满足两条资源约束，且收益恰好为九，所以它一定全局最优。

这类证明包含两部分：一个可行方案给出已能达到的收益，一个对所有可行点成立的上界排除更好方案。两者相等，答案便得到核验，不依赖图上读数的精度。

如果简单相加不能恰好得到目标，还可以给资源约束加权。取非负数 $u, v$ ，得到 $(u + 2 v) x + (u + v) y \leq 4 u + 5 v .$ 只要 $u + 2 v \geq 3$ 、 $u + v \geq 2$ ，利用产量非负，就有 $3 x + 2 y \leq (u + 2 v) x + (u + v) y \leq 4 u + 5 v .$ 因此每组这样的 $u, v$ 都给出一个收益上界。寻找最小的上界，就是对偶问题： $min 4 u + 5 v, u + 2 v \geq 3, u + v \geq 2, u, v \geq 0.$ 本例取 $u = v = 1$ ，正好得到上界九。

对偶与剩余资源的关系

把原问题写成矩阵形式 $max {c^{𝖳} x : A x \leq b, x \geq 0}$ ，相应对偶为 $min {b^{𝖳} y : A^{𝖳} y \geq c, y \geq 0}$ 。这里 $x$ 是产量向量， $y$ 是资源权重向量。

任意一对可行解都满足 $c^{𝖳} x \leq y^{𝖳} A x \leq y^{𝖳} b .$ 第一步用产量非负和对偶约束，第二步用权重非负和资源约束。这称为弱对偶：原方案收益不超过对偶给出的上界。

把两端之差拆开，可得 $b^{𝖳} y - c^{𝖳} x = y^{𝖳} (b - A x) + (A^{𝖳} y - c)^{𝖳} x .$ 右边每项都非负。若差为零，每项必须为零：有剩余的资源必须对应零权重；正产量的产品必须对应恰好等于其单位收益的资源加权成本。这称为互补松弛。

本例两种资源在 $(1, 3)$ 处都用尽，两种产品产量也都为正，对应对偶两条约束都取等号。反过来，原、对偶均可行且满足互补松弛时，上下界相等，便能证明最优。

强对偶定理进一步保证：有限维线性规划可行且有有限最优值时，原问题和对偶都能取得最优解，两边最优值相等。前面的不等式证明了弱对偶，强对偶的一般证明还需更多几何工具，可参阅 MIT 线性规划对偶讲义。

增加资源，收益能增加多少

把第一种资源总量从四改为 $B$ ，第二种仍为五。问题成为 $max 3 x + 2 y, x + y \leq B, 2 x + y \leq 5, x, y \geq 0.$ 当资源很少时，第一种产品每份第一资源带来收益三，高于第二种产品的二。若 $0 \leq B \leq 5 / 2$ ，可以全部生产第一种： $x = B, y = 0$ 。第二资源消耗 $2 B \leq 5$ ，收益为 $3 B$ 。对任意可行点， $3 x + 2 y \leq 3 (x + y) \leq 3 B$ ，所以该方案最优。

当 $5 / 2 \leq B \leq 5$ ，两种资源同时用尽的交点满足 $x + y = B, 2 x + y = 5, x = 5 - B, y = 2 B - 5.$ 两个产量都非负，收益是 $B + 5$ 。把两条约束相加也给出上界 $B + 5$ ，所以这个方案最优。

当 $B \geq 5$ ，可以取 $x = 0, y = 5$ ，收益十。因为 $3 x + 2 y \leq 4 x + 2 y = 2 (2 x + y) \leq 10,$ 十也是全域上界。此后第一种资源再增加，第二种资源仍限制了收益。

最优收益因此是分段函数 $V (B) = {\begin{matrix} 3 B, & 0 \leq B \leq 5 / 2, \\ B + 5, & 5 / 2 \leq B \leq 5, \\ 10, & B \geq 5. \end{matrix}$

资源B增加时最优收益先以斜率三增长，在B等于二点五后斜率变一，到五后保持十 — 两个折点对应最优生产方案的变化：第二种资源开始限制产量，随后第一种资源不再稀缺。

图中每一段都由一个可行方案和一个匹配上界推导出来。折点是重新检查活跃约束的位置。

三个区间的斜率分别为三、一、零，表示增加一小单位第一资源所带来的边际收益。在原来的 $B = 4$ 附近，它等于一，与最优对偶权重 $u = 1$ 相同，因此对偶权重也常称影子价格。越过分段点后，最优生产结构改变，影子价格也随之改变。

不能只用一个“求解成功”概括的情况

若约束是 $x \geq 2$ 和 $x \leq 1$ ，不存在可行方案。把第一条改写为 $- x \leq - 2$ ，再与第二条相加，得到矛盾 $0 \leq - 1$ ，便证明了不可行。

若最大化 $x$ 而只有 $x \geq 0$ ，则可以让目标任意大，称为无界。但可行域无界不一定使目标无界：在同一可行域最小化 $x$ ，答案就是零。

变量若必须为整数，连续最优解也可能不适用。例如 $2 x + 2 y \leq 3$ 下，连续方案 $(0.75, 0.75)$ 可行，各自四舍五入成一后却违反约束。因此整数要求应在建模时写明，不能用事后四舍五入代替求解。

绝对值问题也能写成线性规划

用一个数 $z$ 接近观测一和四，若目标为 $| z - 1 | + | z - 4 |$ ，看起来出现了非线性符号。引入两个变量 $u, v$ ，要求 $u \geq z - 1, u \geq 1 - z, v \geq z - 4, v \geq 4 - z,$ 并最小化 $u + v$ ，就得到线性规划。前两条等价于 $u \geq | z - 1 |$ ，后两条等价于 $v \geq | z - 4 |$ ；取最小值时两者可以分别等于绝对值，所以转换保留了原目标的最优值与最优 $z$ 。

三角不等式给出目标至少为三。对任意 $1 \leq z \leq 4$ ，目标恰为 $(z - 1) + (4 - z) = 3$ ，因此整个区间最优。若把损失改为平方偏差，配方则给出唯一最优点 $z = 2.5$ ，参见最小二乘法。

算法与历史

二维问题可以画图，高维问题通常使用算法。单纯形法在基可行解之间改进目标，几何上常表现为沿顶点移动；退化时一次基变换可能仍停在同一点。内点法采用不同的路径逼近最优解。数值结果可以通过原约束残差、对偶约束和两边目标差复核。

在本例中，这些算法对象可以直接与资源联系起来。把剩余资源记为 $s_{1} = 4 - x - y$ 、 $s_{2} = 5 - 2 x - y$ ，两者都须非负。原点方案的剩余量为 $(4, 5)$ ；沿横轴增加第一产品时，第二资源先用尽，到达 $(x, y) = (5 / 2, 0)$ 。此时剩余量为 $(3 / 2, 0)$ 。

为了继续提高收益，沿第二资源用尽的边界增加第二产品。由 $2 x + y = 5$ 得 $x = (5 - y) / 2$ ，所以 $3 x + 2 y = \frac{15}{2} + \frac{y}{2}, s_{1} = 4 - x - y = \frac{3}{2} - \frac{y}{2} .$ 每增加一个单位 $y$ ，收益增加半单位，但第一资源剩余量也减少半单位。直到 $y = 3$ ，第一资源也用尽，算法到达 $(1, 3)$ 。这个过程没有在可行域外绕行；每一步都能用剩余量非负来核对。

三个方案的两种资源剩余量依次为四五、一点五零、零零；目标收益依次为零、七点五、九 — 同一条求解路径的资源视角：第二资源先成为限制，接着两种资源共同限制产量。

最终把 $x, y$ 用两项剩余量表示，有 $x = 1 + s_{1} - s_{2}$ 、 $y = 3 - 2 s_{1} + s_{2}$ ，目标随之变为 $3 x + 2 y = 9 - s_{1} - s_{2} \leq 9.$ 算法末尾的这个式子就是前文的最优性证据。详见单纯形法中的完整消元与最小比值检验。资源配置还可以与列昂惕夫投入产出模型衔接：后者先计算满足需求所需的总产出，若加入产能上限并选择哪些需求优先满足，便会形成新的线性规划，而不能只解一个无约束的投入产出方程组。

Kantorovich 在 1939 年发表与生产组织有关的数学方法，Dantzig 在 1947 年发展单纯形法。两人的工作背景分别见 MacTutor 传记和斯坦福大学记录。今天的线性规划把资源模型、多面体几何、对偶理论与算法联系在一起。

参考来源与延伸阅读

Boyd 与 Vandenberghe：Convex Optimization，第4章的线性规划、第5章的对偶与敏感性分析。
MIT 6.253 Lecture 10：线性规划对偶定理及Farkas引理。
MacTutor：Kantorovich；Stanford：Dantzig。
先修：矩阵、优化；相关：最短路径、数学建模。