线性规划与单纯形法¶
知识框架¶
线性规划（Linear Programming, LP）是整门运筹学的地基：对偶理论、运输问题、整数规划、目标规划都建立在它之上。本页要解决三个问题：
- 建模：把实际问题写成 LP 模型，并化为标准形
- 直观理解：两个变量时用图解法求解，建立"可行域是凸多面体、最优解在顶点"的几何直觉
- 通用算法：单纯形法的原理、表格操作模板，以及没有现成初始基时的大 M 法 / 两阶段法
考试中的典型考法：标准形转化（小题）、图解法 + 解的情况判断（小题）、单纯形表完整迭代（大题，几乎必考）、大 M 法或两阶段法（大题）、由单纯形表反读信息（如判断解的类型）。
线性规划模型与标准形¶
LP 模型的三要素¶
一个线性规划模型由三部分组成，且目标函数和约束都必须是线性的：
- 决策变量 \(x_1, x_2, \dots, x_n\)：要确定的未知量；
- 目标函数 \(\max\)（或 \(\min\)）\(z = c_1 x_1 + c_2 x_2 + \cdots + c_n x_n\)；
- 约束条件：一组线性等式或不等式，外加变量的符号约束（\(\ge 0\)、\(\le 0\) 或自由）。
一般形式：
标准形¶
定义（LP 标准形）
本整理采用最通行的约定，标准形要求同时满足：
- 目标函数为 极大化 \(\max z\)；
- 约束全部为 等式；
- 右端常数 \(b_i \ge 0\)；
- 所有变量 非负 \(x_j \ge 0\)。
矩阵形式：\(\max z = \boldsymbol{c}^{\mathsf T}\boldsymbol{x}\)，s.t. \(\boldsymbol{A}\boldsymbol{x} = \boldsymbol{b},\ \boldsymbol{x} \ge \boldsymbol{0}\)，其中 \(\boldsymbol{A}\) 为 \(m \times n\) 矩阵（\(m < n\)），\(\boldsymbol{b} \ge \boldsymbol{0}\)。
教材口径差异
有的教材以 \(\min\) 为标准形。两者只差一个符号转换，但检验数的最优性判别符号相反（见「单纯形法」一节），考试时务必按本校教材的口径答题，并在卷面上写清自己用的判别准则。
转化为标准形的方法（模板）¶
| 非标准情形 | 转化方法 |
|---|---|
| \(\min z\) | 令 \(z' = -z\)，改为 \(\max z' = -\sum c_j x_j\)，最后结果取反 |
| 约束为 \(\le\) | 左端 加松弛变量 \(x_s \ge 0\) 化为等式 |
| 约束为 \(\ge\) | 左端 减剩余变量 \(x_s \ge 0\) 化为等式 |
| 右端 \(b_i < 0\) | 该约束两边乘 \(-1\)（不等号方向反转） |
| 变量 \(x_j \le 0\) | 令 \(x_j' = -x_j \ge 0\) 代换 |
| 变量 \(x_j\) 自由（无符号约束） | 令 \(x_j = x_j' - x_j''\)，其中 \(x_j', x_j'' \ge 0\) |
松弛 / 剩余变量在目标函数中的系数均为 \(0\)。
图解法与解的几何特征¶
图解法步骤（仅适用于两个决策变量）¶
- 在 \(x_1 O x_2\) 平面上画出每条约束的边界直线，确定可行半平面，取交集得到可行域；
- 画一条目标函数等值线 \(c_1 x_1 + c_2 x_2 = z_0\)，其法向量（梯度方向）\((c_1, c_2)\) 是 \(z\) 增大的方向；
- 将等值线沿梯度方向（求 \(\max\)）平移，最后离开可行域的位置即最优解所在；
- 联立相应边界直线方程解出最优点坐标，代入目标函数得最优值。
解的四种情况¶
| 情况 | 几何特征 |
|---|---|
| 唯一最优解 | 等值线最后只触及可行域的一个顶点 |
| 无穷多最优解 | 等值线与可行域的某条边平行，整条边都最优 |
| 无界解（\(z \to +\infty\)） | 可行域无界，且目标函数可沿可行方向无限增大 |
| 无可行解 | 约束相互矛盾，可行域为空集 |
可行域无界 ≠ 无界解
可行域无界时，最优解仍可能存在（例如求 \(\max\) 而目标函数沿无界方向是减小的）。"无界解"要求目标函数值本身可以无限增大。
几何结论¶
- LP 的可行域是凸集（凸多面体）；
- 若最优解存在，则一定可以在可行域的某个顶点处取得；
- 顶点个数有限 —— 这就是单纯形法"只在顶点间搜索"的理论依据。
基本概念：基、基解、基可行解¶
设标准形中 \(\boldsymbol{A}\) 为 \(m \times n\) 矩阵，秩为 \(m\)。
定义
- 基（basis）：\(\boldsymbol{A}\) 中 \(m\) 个线性无关列构成的 \(m \times m\) 可逆子矩阵 \(\boldsymbol{B}\)。对应的变量称为基变量 \(\boldsymbol{x}_B\)，其余为非基变量 \(\boldsymbol{x}_N\)。
- 基解：令非基变量全为 \(0\)，由 \(\boldsymbol{B}\boldsymbol{x}_B = \boldsymbol{b}\) 解出 \(\boldsymbol{x}_B = \boldsymbol{B}^{-1}\boldsymbol{b}\)，得到的解称为对应于基 \(\boldsymbol{B}\) 的基解。
- 基可行解：满足非负条件 \(\boldsymbol{B}^{-1}\boldsymbol{b} \ge \boldsymbol{0}\) 的基解。对应的基称为可行基。
- 退化的基可行解：某个基变量取值为 \(0\) 的基可行解。
线性规划基本定理
- 可行域的顶点与基可行解一一对应（退化时多个基可能对应同一顶点）；
- 若 LP 有可行解，则必有基可行解；
- 若 LP 有最优解，则必有最优基可行解 —— 因此只需在有限个基可行解中搜索。
基解个数至多 \(\binom{n}{m}\) 个，基可行解是其中满足非负性的那部分。
单纯形法¶
基本思想¶
从一个基可行解（顶点）出发，每次迭代换到一个相邻且目标值不更差的基可行解，直到没有可改进方向为止。每次迭代做两件事：选一个非基变量入基、选一个基变量出基。
检验数与最优性判别¶
设当前基为 \(\boldsymbol{B}\)，记 \(z_j = \boldsymbol{c}_B^{\mathsf T} \boldsymbol{B}^{-1} \boldsymbol{p}_j\)（\(\boldsymbol{p}_j\) 为 \(\boldsymbol{A}\) 的第 \(j\) 列），定义检验数
\(\sigma_j\) 的含义：非基变量 \(x_j\) 每增加一个单位，目标函数 \(z\) 的净增量。基变量的检验数恒为 \(0\)。
最优性判别定理（max 问题）
对当前基可行解：
- 若所有检验数 \(\sigma_j \le 0\) —— 当前解最优；
- 若所有 \(\sigma_j \le 0\)，且某非基变量的 \(\sigma_k = 0\) —— 存在无穷多最优解；
- 若存在 \(\sigma_k > 0\)，且 \(x_k\) 所在列的系数 \(\boldsymbol{B}^{-1}\boldsymbol{p}_k \le \boldsymbol{0}\)（整列无正分量）—— 无界解；
- 否则继续迭代。
若求 \(\min\) 且不转化为 \(\max\)，判别符号整体反向（所有 \(\sigma_j \ge 0\) 时最优）。
单纯形表迭代步骤（模板）¶
设已有标准形和一个现成的初始可行基（典型情形：全部约束原为 \(\le\) 且 \(b \ge 0\)，松弛变量恰好构成单位阵初始基）。
- 建初始表：表头一行写各变量的价值系数 \(c_j\)；左侧三列依次为基变量、对应的 \(c_B\)、右端常数 \(b\)；中间填约束系数矩阵；
- 算检验数：对每列 \(j\)，\(\sigma_j = c_j - \sum_i (c_B)_i \, a_{ij}\)（即 \(c_j\) 减去"\(c_B\) 列与该列系数的内积"）；
- 判最优：所有 \(\sigma_j \le 0\) 则停止，按 1.4.2 的定理读出结论；
- 选入基变量：取 \(\sigma_k = \max\{\sigma_j : \sigma_j > 0\}\) 对应的 \(x_k\) 入基（最大检验数规则），\(x_k\) 所在列为主元列；
- 选出基变量（最小比值法）：对主元列中 \(a_{ik} > 0\) 的行计算 \(\theta_i = b_i / a_{ik}\)，取 \(\theta\) 最小的行，该行基变量出基；该行为主元行，交叉处 \(a_{lk}\) 为主元；
- 旋转运算（高斯消元）：主元行整行除以主元（主元变为 \(1\)）；其余各行减去"该行主元列系数 × 新主元行"，把主元列消成单位向量；同时更新左侧基变量与 \(c_B\) 列；
- 回到第 2 步。
完整数值例¶
加松弛变量 \(x_3, x_4, x_5\) 化为标准形，初始基为 \((x_3, x_4, x_5)\)。
初始表（\(c_j\)：\(2,\ 3,\ 0,\ 0,\ 0\)）：
| 基 | \(c_B\) | \(b\) | \(x_1\) | \(x_2\) | \(x_3\) | \(x_4\) | \(x_5\) | \(\theta\) |
|---|---|---|---|---|---|---|---|---|
| \(x_3\) | 0 | 8 | 1 | 2 | 1 | 0 | 0 | \(8/2=4\) |
| \(x_4\) | 0 | 16 | 4 | 0 | 0 | 1 | 0 | — |
| \(x_5\) | 0 | 12 | 0 | [4] | 0 | 0 | 1 | \(12/4=3\) ← |
| \(\sigma_j\) | 2 | 3 ↑ | 0 | 0 | 0 |
\(\sigma_2 = 3\) 最大，\(x_2\) 入基；\(\theta\) 最小在第 3 行，\(x_5\) 出基，主元为 \(4\)。
第二张表：
| 基 | \(c_B\) | \(b\) | \(x_1\) | \(x_2\) | \(x_3\) | \(x_4\) | \(x_5\) | \(\theta\) |
|---|---|---|---|---|---|---|---|---|
| \(x_3\) | 0 | 2 | [1] | 0 | 1 | 0 | \(-1/2\) | \(2/1=2\) ← |
| \(x_4\) | 0 | 16 | 4 | 0 | 0 | 1 | 0 | \(16/4=4\) |
| \(x_2\) | 3 | 3 | 0 | 1 | 0 | 0 | \(1/4\) | — |
| \(\sigma_j\) | 2 ↑ | 0 | 0 | 0 | \(-3/4\) |
\(x_1\) 入基，\(x_3\) 出基，主元为 \(1\)。
第三张表：
| 基 | \(c_B\) | \(b\) | \(x_1\) | \(x_2\) | \(x_3\) | \(x_4\) | \(x_5\) | \(\theta\) |
|---|---|---|---|---|---|---|---|---|
| \(x_1\) | 2 | 2 | 1 | 0 | 1 | 0 | \(-1/2\) | — |
| \(x_4\) | 0 | 8 | 0 | 0 | \(-4\) | 1 | [2] | \(8/2=4\) ← |
| \(x_2\) | 3 | 3 | 0 | 1 | 0 | 0 | \(1/4\) | \(3/(1/4)=12\) |
| \(\sigma_j\) | 0 | 0 | \(-2\) | 0 | \(1/4\) ↑ |
注意：\(\sigma_5 = 0 - \left[2 \times (-\tfrac12) + 0 \times 2 + 3 \times \tfrac14\right] = \tfrac14 > 0\)，还没到最优——迭代过程中检验数可能"由负转正"，每张表都要完整重算。\(x_5\) 入基，\(x_4\) 出基，主元为 \(2\)。
第四张表（最终表）：
| 基 | \(c_B\) | \(b\) | \(x_1\) | \(x_2\) | \(x_3\) | \(x_4\) | \(x_5\) | \(\theta\) |
|---|---|---|---|---|---|---|---|---|
| \(x_1\) | 2 | 4 | 1 | 0 | 0 | \(1/4\) | 0 | |
| \(x_5\) | 0 | 4 | 0 | 0 | \(-2\) | \(1/2\) | 1 | |
| \(x_2\) | 3 | 2 | 0 | 1 | \(1/2\) | \(-1/8\) | 0 | |
| \(\sigma_j\) | 0 | 0 | \(-3/2\) | \(-1/8\) | 0 |
所有 \(\sigma_j \le 0\)，达到最优：
（\(x_5 = 4\) 表示第三个约束有 4 个单位的松弛量：\(4x_2 = 8 < 12\)。）
人工变量法：大 M 法与两阶段法¶
当约束中含 "\(\ge\)" 或 "\(=\)" 时，化标准形后没有现成的单位阵初始基，需要给缺基的约束行加人工变量 \(x_a \ge 0\) 凑出单位阵。人工变量是"硬凑"出来的，最优解中必须把它们赶到 \(0\)，两种方法：
大 M 法¶
- 给每个人工变量在目标函数中赋系数 \(-M\)（求 \(\max\) 时；求 \(\min\) 则为 \(+M\)），\(M\) 是任意大的正数；
- 按普通单纯形法迭代，\(M\) 当作一个比任何具体数都大的符号参与检验数的比较（检验数形如 \(aM + b\)，先比 \(a\) 再比 \(b\)）；
- 最优表中若人工变量已全部出基（或取值为 0），去掉人工变量即得原问题最优解。
两阶段法¶
- 第一阶段：目标函数换成 \(\min w = \sum x_a\)（所有人工变量之和），用单纯形法求解；
- 若 \(w^* > 0\) —— 原问题无可行解，停止；
- 若 \(w^* = 0\) —— 得到原问题的一个基可行解；
- 第二阶段：删去人工变量列，换回原目标函数，从第一阶段的最终基出发继续单纯形迭代。
无可行解的判别
大 M 法迭代终止时，若仍有人工变量留在基中且取值大于 0，或两阶段法第一阶段最优值 \(w^* > 0\)，则原问题无可行解。
两种方法怎么选
手算考题大多用大 M 法（少建一张目标函数表）；当人工变量较多、或题目明确要求时用两阶段法。两阶段法数值上更稳定（计算机实现的首选），原理上完全等价。
解的判别汇总（由单纯形表读结论）¶
设求 \(\max\)，当前表已算出全部检验数：
| 表中特征 | 结论 |
|---|---|
| 所有 \(\sigma_j \le 0\)，且非基变量检验数全 \(< 0\) | 唯一最优解 |
| 所有 \(\sigma_j \le 0\)，且某非基变量 \(\sigma_k = 0\) | 无穷多最优解（让 \(x_k\) 入基可得另一最优顶点） |
| 某 \(\sigma_k > 0\)，且该列系数全 \(\le 0\)（无正分量，\(\theta\) 算不出） | 无界解 |
| 迭代结束但人工变量仍在基中且 \(> 0\) | 无可行解 |
退化与循环
最小比值出现并列时，下一张表必出现退化（某基变量为 0）；退化时目标值可能连续若干次迭代不增，极端情况会循环。手算考题几乎不考循环，了解结论即可：采用 Bland 规则（入基、出基都选下标最小者）可保证不循环。
典型例题¶
例 1（标准形转化）
将下列 LP 化为标准形：
解答
逐项处理：① \(\min \to \max\)：令 \(z' = -z\)；② 自由变量：令 \(x_3 = x_4 - x_5\)（\(x_4, x_5 \ge 0\)）；③ 第 1 个约束加松弛变量 \(x_6\)；④ 第 2 个约束减剩余变量 \(x_7\)。
最终答案换算回去：\(\min z = -z'^*\)，\(x_3^* = x_4^* - x_5^*\)。
例 2（图解法 + 解的情况）
用图解法求解，并说明解属于哪种情况：
解答
可行域是由 \(x_1 + 2x_2 = 8\)、\(x_1 = 4\)、\(x_2 = 3\) 和两坐标轴围成的凸多边形。目标函数等值线 \(2x_1 + 4x_2 = z_0\) 的法向量 \((2, 4)\) 与约束 \(x_1 + 2x_2 \le 8\) 的边界直线法向量 \((1, 2)\) 共线，因此等值线平移到最后与这条边界整段重合。
该边界上的可行段为顶点 \((2, 3)\) 到 \((4, 2)\) 之间的线段：
- 在 \((2, 3)\)：\(z = 4 + 12 = 16\)；
- 在 \((4, 2)\)：\(z = 8 + 8 = 16\)。
故本题为无穷多最优解，最优解集为线段 \(\{\lambda(2,3) + (1-\lambda)(4,2) : 0 \le \lambda \le 1\}\)，最优值 \(z^* = 16\)。
例 3（单纯形表完整迭代）
用单纯形法求解：
解答
加松弛变量 \(x_3, x_4\)，初始基 \((x_3, x_4)\)。
初始表（\(c_j\)：\(2,\ 3,\ 0,\ 0\)）：
| 基 | \(c_B\) | \(b\) | \(x_1\) | \(x_2\) | \(x_3\) | \(x_4\) | \(\theta\) |
|---|---|---|---|---|---|---|---|
| \(x_3\) | 0 | 4 | 1 | 1 | 1 | 0 | 4 |
| \(x_4\) | 0 | 6 | 1 | [2] | 0 | 1 | 3 ← |
| \(\sigma_j\) | 2 | 3 ↑ | 0 | 0 |
\(x_2\) 入基、\(x_4\) 出基：
| 基 | \(c_B\) | \(b\) | \(x_1\) | \(x_2\) | \(x_3\) | \(x_4\) | \(\theta\) |
|---|---|---|---|---|---|---|---|
| \(x_3\) | 0 | 1 | [1/2] | 0 | 1 | \(-1/2\) | 2 ← |
| \(x_2\) | 3 | 3 | \(1/2\) | 1 | 0 | \(1/2\) | 6 |
| \(\sigma_j\) | \(1/2\) ↑ | 0 | 0 | \(-3/2\) |
\(x_1\) 入基、\(x_3\) 出基：
| 基 | \(c_B\) | \(b\) | \(x_1\) | \(x_2\) | \(x_3\) | \(x_4\) | \(\theta\) |
|---|---|---|---|---|---|---|---|
| \(x_1\) | 2 | 2 | 1 | 0 | 2 | \(-1\) | |
| \(x_2\) | 3 | 2 | 0 | 1 | \(-1\) | 1 | |
| \(\sigma_j\) | 0 | 0 | \(-1\) | \(-1\) |
所有 \(\sigma_j \le 0\) 且非基变量检验数均严格小于 0，得唯一最优解：
例 4（大 M 法）
用大 M 法求解：
解答
第 2 个约束加松弛变量 \(x_3\)；第 1 个约束是等式、没有现成基变量，加人工变量 \(x_4\)，目标函数中其系数取 \(-M\)：
初始表（基 \((x_4, x_3)\)）：
| 基 | \(c_B\) | \(b\) | \(x_1\) | \(x_2\) | \(x_3\) | \(x_4\) | \(\theta\) |
|---|---|---|---|---|---|---|---|
| \(x_4\) | \(-M\) | 3 | [1] | 1 | 0 | 1 | 3 ← |
| \(x_3\) | 0 | 2 | 0 | 1 | 1 | 0 | — |
| \(\sigma_j\) | \(2+M\) ↑ | \(1+M\) | 0 | 0 |
\(\sigma_1 = 2 + M\) 最大，\(x_1\) 入基；只有第 1 行系数为正，\(x_4\) 出基：
| 基 | \(c_B\) | \(b\) | \(x_1\) | \(x_2\) | \(x_3\) | \(x_4\) | \(\theta\) |
|---|---|---|---|---|---|---|---|
| \(x_1\) | 2 | 3 | 1 | 1 | 0 | 1 | |
| \(x_3\) | 0 | 2 | 0 | 1 | 1 | 0 | |
| \(\sigma_j\) | 0 | \(-1\) | 0 | \(-M-2\) |
所有 \(\sigma_j \le 0\)，且人工变量 \(x_4\) 已出基，得最优解：
易错点与考点提醒¶
高频易错点
- min / max 口径：求 \(\min\) 不转化时，最优性判别是"所有 \(\sigma_j \ge 0\)"，与 \(\max\) 相反；最稳妥的做法是统一先化成 \(\max\) 标准形。
- \(\ge\) 约束的处理：减剩余变量后还没有基变量，通常还要再加人工变量——"减剩余"和"加人工"是两步，别合并成一步。
- 最小比值只对正分量算：主元列中 \(a_{ik} \le 0\) 的行不参与 \(\theta\) 比值（写 "—"）；若整列都 \(\le 0\)，结论是无界解而不是"无解"。
- 检验数每张表都要重算：迭代中非基变量的 \(\sigma_j\) 可能由负转正（见「完整数值例」第三张表），不能想当然认为"负过一次就一直负"。
- 无穷多最优解的判别对象是非基变量：基变量检验数本来就是 0，不能据此判"无穷多最优"。
- 人工变量 ≠ 松弛变量：松弛变量有实际意义（资源剩余量），可以留在最优基中；人工变量必须为 0，否则无可行解。
- 退化时 \(\theta\) 并列：任选其一即可（考试一般不深究），但下一张表会出现取值为 0 的基变量，属正常现象。
- 图解法答题要完整：画可行域、标顶点坐标、画等值线和梯度方向、写明最优点与最优值，缺一步都可能扣分。
速查表¶
| 主题 | 关键结论 |
|---|---|
| 标准形四要素 | \(\max\)、等式约束、\(b \ge 0\)、\(x \ge 0\) |
| 自由变量 | \(x_j = x_j' - x_j''\)（两个非负变量之差） |
| 检验数 | \(\sigma_j = c_j - \boldsymbol{c}_B^{\mathsf T} \boldsymbol{B}^{-1} \boldsymbol{p}_j\)；基变量恒为 0 |
| 最优判别（max） | 全部 \(\sigma_j \le 0\) |
| 入基 | 取 \(\sigma_j > 0\) 中最大者 |
| 出基 | 最小比值 \(\theta = \min\{b_i / a_{ik} : a_{ik} > 0\}\) |
| 无穷多最优 | 最优表中某非基变量 \(\sigma_k = 0\) |
| 无界解 | 某 \(\sigma_k > 0\) 且该列全 \(\le 0\) |
| 无可行解 | 人工变量留基且 \(> 0\)（或两阶段法 \(w^* > 0\)） |
| 大 M 法 | 人工变量目标系数 \(-M\)（max 口径） |
| 两阶段法 | 一阶段 \(\min \sum x_a\)；\(w^* > 0\) 即无可行解 |