第1章 线性规划建模：从文字题到标准型

1. 优化模型由哪三部分组成

优化模型把“用最好的方式完成一件事”写成数学语言。不管是排产、配料还是运输，模型都只有三类要素：

如果目标函数和所有约束都是变量的一次式，这个模型就是线性规划（Linear Programming，LP）：

只要出现 $x_1^2$、$x_1x_2$、$\sqrt{x_1}$ 这样的项，模型就变成非线性规划，求解方法完全不同（见第5、6章）。

2. 建模三步

把文字题翻译成模型，按下面三步走，几乎不会漏条件：

1. 找目标，定变量。 先问“要让什么最大或最小”，再问“它由哪些可以决定的量决定”——这些量就是决策变量。
2. 逐条写出明示的限制。 文字里每一个“最多”“至少”“恰好”都对应一条约束。
3. 补上隐含条件。 题目没明说、但物理上必然成立的条件，最常见的是非负（产量不能是负数），有时还有整数要求。

例1：家具厂排产。 工厂生产桌子和椅子，资源和利润如下：

第一步，目标是总利润最大。设每天生产桌子 $x$ 张、椅子 $y$ 把，利润为 $z=60x+40y$。

第二步，每种资源都不能超用：

第三步，隐含条件 $x\ge0,\ y\ge0$。完整模型为

例2：饲料配方（最小化）。 两种原料 P、Q 每千克的营养含量和价格如下，混合饲料至少需要蛋白质 12、脂肪 8、纤维 12 个单位：

设用 P $x$ 千克、Q $y$ 千克，模型为

3. 图解法：最优解为什么在顶点

两个变量的问题可以画在平面上。每条约束 $a_1x+a_2y\le b$ 对应一个半平面，所有半平面的交集就是可行域。线性规划的可行域总是凸多边形（可能无界）。

目标函数 $z=60x+40y$ 的等值线是一族平行直线。$z$ 越大，直线越往右上方平移。把等值线一直往目标改进的方向推，最后离开可行域时碰到的那个点就是最优解。由于等值线是直线、可行域是凸多边形，这个“最后接触点”一定是顶点（或者是一整条边，此时边的两个端点也都最优）。

所以两变量问题只需比较顶点。例1的可行域有5个顶点：

最优方案：每天生产 12 张桌子、16 把椅子，利润 1360 元。检查资源使用：木工 $2\cdot12+16=40$（用满）、木材 $12+16=28$（用满）、油漆 $12+32=44<50$（剩 6 小时）。用满的约束叫紧约束，后面讲灵敏度时，非紧约束的资源少量增加不会改善最优值；紧约束是否有价值还要看影子价格，不能只凭“用满”判断。

例2是最小化，等值线往左下方推。可行域无界，但顶点只有4个：

最优是 P 用 2 千克、Q 用 6 千克，成本 26 元。$(2,6)$ 是 $3x+y=12$ 与 $x+y=8$ 的交点。

4. 标准型：单纯形法需要的形式

图解法只能处理两个变量。一般问题要用单纯形法（第2章），它要求模型先写成标准型：

即：所有约束都是等式、所有变量都非负，本章再把右端统一成非负。标准型不自动提供初始基本可行解；没有现成起点时，第5节用人工变量辅助寻找。转换规则如下：

松弛变量的含义是“没用完的资源”，剩余变量是“超出最低要求的部分”。它们在目标函数中的系数为 0，不改变原问题。

例3：完整转换一次。

第一步，处理负右端：第三条约束乘 $-1$，得 $x_1+3x_2-2x_3\ge3$。

第二步，处理下界和自由变量：令 $x_1'=x_1-1\ge0$（即 $x_1=x_1'+1$），令 $x_3=x_3'-x_3''$。代入：

• 目标：$z=4(x_1'+1)-2x_2+3x_3'-3x_3''=4x_1'-2x_2+3x_3'-3x_3''+4$，常数 4 先拿出，求 $z'=z-4$ 的最小值。
• 第一条：$x_1'+1+2x_2-x_3'+x_3''=6\Rightarrow x_1'+2x_2-x_3'+x_3''=5$。
• 第二条：$2x_1'+2-x_2+x_3'-x_3''\le8\Rightarrow 2x_1'-x_2+x_3'-x_3''\le6$。
• 第三条：$x_1'+1+3x_2-2x_3'+2x_3''\ge3\Rightarrow x_1'+3x_2-2x_3'+2x_3''\ge2$。
• 上界：$x_2\le5$。

第三步，加松弛、减剩余：

最后求出 $z'$ 的最小值后，原问题的最小值是 $z=z'+4$。

5. 人工变量：给单纯形法一个起点

单纯形法要从一个基本可行解出发。对 $\le$ 约束，松弛变量天然就是起点：令原变量为 0，松弛变量等于右端即可。但等式约束和 $\ge$ 约束没有这样的变量——$\ge$ 约束的剩余变量系数是 $-1$，令它等于右端会得到负值。

办法是给这些约束各加一个人工变量 $a\ge0$：

令 $x_1=x_2=e_1=0$，立刻得到 $s_1=3,\ a_1=6,\ a_2=15$，这是新方程组的一个可行解。规则可以概括为：每条约束恰好含一个“起步变量”——$\le$ 用松弛变量，$\ge$ 和 $=$ 用人工变量。

人工变量只是脚手架，它为正时原约束并不成立。所以必须让它们在最终解里都等于 0，做法是在目标中给它们很大的惩罚：最小化问题加 $+Ma$，最大化问题加 $-Ma$（$M$ 是一个足够大的正数），这就是第2章的大 M 法；另一种做法是两阶段法。

6. 基本解、基本可行解与极点

设标准型有 $m$ 条等式约束、$n$ 个变量（$n\ge m$，且系数矩阵 $A$ 的秩为 $m$）。

• 基本解： 任选 $n-m$ 个变量令其为 0（非基变量），用剩下 $m$ 个变量（基变量）解方程组；要求这 $m$ 个变量对应的列线性无关。最多有 $\binom{n}{m}$ 个基本解。
• 基本可行解： 所有分量都非负的基本解。
• 极点： 可行域中不在任何两点连线“内部”的点，也就是多边形的顶点。

关键结论：可行域的极点恰好就是基本可行解；如果最优解存在，一定能在某个基本可行解处取到。 所以求解线性规划，本质是在有限个基本可行解中找最好的一个。

例4：枚举全部基本解。

加松弛变量：$x_1+x_2+x_3=4$，$x_1+3x_2+x_4=6$。$n=4,\ m=2$，最多 $\binom42=6$ 个基本解：

4 个基本可行解正好对应可行域的 4 个顶点 $(0,0)$、$(0,2)$、$(3,1)$、$(4,0)$，最优解是 $x_1=4,\ x_2=0$，$z=12$。不可行的两个基本解是约束直线的交点，但落在可行域外面。

如果某个基本可行解中有基变量恰好等于 0，称为退化。它通常意味着有多余的约束经过同一个顶点。

枚举法在小问题上直观，但规模一大就不可行：20 个变量、10 条约束最多有 $\binom{20}{10}=184756$ 个基本解。单纯形法的作用，就是只沿着“让目标变好”的方向在顶点之间移动，不必全部枚举。

7. 三种特殊情况

注意“可行域无界”不等于“问题无界”：例2的可行域无界，但最小化成本仍有最优解。

8. 小结

• 线性规划 = 线性目标 + 线性约束 + 非负变量。
• 建模三步：目标和变量 → 明示约束 → 隐含条件。
• 可行域是凸的，最优解在顶点上取得；两变量问题比较顶点即可。
• 标准型要求等式约束、非负变量、非负右端；$\le$ 加松弛，$\ge$ 减剩余再加人工，$=$ 加人工。
• 基本可行解 = 极点；单纯形法就是在它们之间有方向地移动。

自测