北邮研究生课程《最优化理论与算法》知识总结 - Part 1

Important

考试划重点

线性规划 (LP) 部分 50%

标准型
单纯形方法（两阶段/大M）
对偶规划，对偶单纯形
灵敏度分析 (c,b,A，约束条件)
对偶理论
互补松弛条件
LP 的基本性质

基于教材最优化理论与算法(第2版)-陈宝林-清华大学出版社-2006。

Note

前置数学知识:

Ch 02. 线性规划的基本性质#

本章是单纯形法的理论基础，核心建立“几何极点 $\leftrightarrow$ 代数基本可行解”的等价关系。

本章逻辑主线

实际LP → 化为标准型（计算前提）；
几何顶点（极点）对应代数基本可行解；
理论保证：有可行解就有BFS，有最优解就有最优BFS；
由此引出下一章单纯形法：只需在有限个基本可行解中迭代寻优。

2.1 标准形式及图解法#

线性规划标准形式定义
$\begin{array}{ll} \min & \boldsymbol{c}\boldsymbol{x} \\ \text{s.t.} & \boldsymbol{A}\boldsymbol{x}=\boldsymbol{b} \\ & \boldsymbol{x} \ge \boldsymbol{0} \end{array}$
极小化目标、等式约束、右端常数 $b\ge0$ 、所有变量 $x_j\ge0$ 。
非标准型转化标准型全套规则
- 不等式约束： $\le$ 加松弛变量， $\ge$ 加剩余变量；
- 无符号自由变量： $x_j=x_j'-x_j'',x_j',x_j''\ge0$ ；
- 变量上下界平移： $x_j\ge l_j\Rightarrow x_j'=x_j-l_j\ge0$ ； $x_j\le u_j\Rightarrow x_j'=u_j-x_j\ge0$ ；
- 右端 $b_i<0$ ：方程两边乘 $-1$ ；最大化转最小化： $\max cx \Leftrightarrow \min -cx$ 。
图解法（二维变量专用）
- 可行域：线性不等式围成凸多边形；
- 目标函数等值线、梯度/法向量方向：极小化沿负梯度平移等值线；
- 结论：最优解出现在顶点（极点）；三种结果：唯一最优、无穷多最优、无界、无可行域。

2.2 线性规划基本性质#

1. 可行域几何性质#

定理2.2.1：线性规划可行域 $K=\{x|Ax=b,x\ge0\}$ 是凸集。

Note

凸集 (Convex Set): 如果在这个集合里任意挑两个点，连成一条线段，这条线段上的所有点也必须在这个集合内。

圆、正方形、球体都是凸集；而月牙形、五角星就不是凸集（因为凹进去的地方连线会跑到图形外面去）。

这个定理告诉我们：线性规划的可行域绝对不会有“凹陷”或“空洞”，它是一个规整的、实心的多面体。这为后续寻找最优解奠定了良好的几何基础。

2. 最优解极点定理（定理2.2.2）#

可行域非空时：

存在有限最优解 $\iff$ 可行域所有极方向满足 $cd^{(j)}\ge0$ ；若存在 $cd^{(j)}<0$ ，目标无界；
若有有限最优解，则最优值一定能在极点取到。

Note

极点（Extreme Point）：几何上的 “顶点” 或 “角点”。比如立方体的 8 个顶点。
极方向（Extreme Direction）：如果可行域是无限延伸的（无界），那么顺着某个方向可以一直走下去而不出界，这个方向就是极方向。
$c$ ：目标函数的系数向量（代表我们想优化、比如降低成本的方向）。
拆解理解:
- 第（1）条：如果可行域是无限大的，你顺着某个无限延伸的方向 $d^{(j)}$ 走，如果发现成本在降低（即 $cd^{(j)} < 0$ ），那你就可以无限走下去，成本变成 $- \infty$ ，这就是“目标无界”（说明题目设计不合理，现实中不存在）。只有往所有无限方向走都会使成本增加（即 $cd^{(j)} \ge 0$ ），才存在一个合理的、有限的最优解。
- 第（2）条（核心结论）：如果有最优解，它一定可以在某个顶点（极点）上达到。
- 为什么重要：可行域内部有无数个点，我们不可能每个都去试。但这定理告诉我们，只需要去检查那些有限的“角点”就可以了。这极大地缩小了搜索范围。

3. 基本解、基本可行解（BFS）定义#

问题背景: 约束条件是 $Ax = b$ ，其中 $A$ 是一个 $m \times n$ 的矩阵（ $m$ 个方程， $n$ 个变量，通常变量比方程多，即 $n > m$ ）。因为方程比变量少，所以这个方程组有无数个解。

基矩阵 $B$ 与非基矩阵 $N$ :

我们从 $A$ 的 $n$ 列中，挑出 $m$ 列，组成一个 $m \times m$ 的可逆矩阵，称为基（Basis），记为 $B$ 。
剩下的 $n-m$ 列组成非基（Non-basis），记为 $N$ 。
相应地，变量也分成两部分：基变量 $x_B$ （ $m$ 个）和非基变量 $x_N$ （ $n-m$ 个）。

基本解（Basic Solution）:

做法：把那 $n-m$ 个非基变量 $x_N$ 直接强制设为 0，然后求解剩下的 $m$ 个基变量 $x_B$ 。
公式： $Bx_B = b \implies x_B = B^{-1}b$ 。
整个解就是 $x = \begin{pmatrix} B^{-1}b \\ 0 \end{pmatrix}$ 。
注意：基本解只要求满足 $Ax=b$ ，不要求满足 $x \ge 0$ 。所以有些变量可能是负数。

基本可行解（Basic Feasible Solution, 简称 BFS）:

如果算出来的基本解里，所有分量都大于等于 0（即 $B^{-1}b \ge 0$ ），那么它既是“基本解”又是“可行解”，这就叫 BFS。

退化（Degenerate）：

如果算出来的基变量 $x_B$ 里，恰好有某些变量的值也是 0，就叫退化基本可行解；如果全都是正数（ $>0$ ），就叫非退化。

基本解总数上界 $C_n^m$ :

我们能挑出多少种不同的“基”？这就是从 $n$ 列里选 $m$ 列的组合数 $C_n^m = \frac{n!}{m!(n-m)!}$ 。
因为这个数字是有限的，所以基本可行解的数量也是有限的。

4. 极点与基本可行解等价定理（定理2.2.3，重中之重）#

几何上的“极点（角点）” $\iff$ 代数上的“基本可行解（BFS）”。

① 如果你用眼睛看，发现某个点是图形的顶点（极点），那么在代数上，它对应的变量中必定只有不超过 $m$ 个是非零的，且对应的矩阵列线性无关（可以作为基）。

② 反过来，如果你用矩阵算出了一个 BFS，那么它在多面体图像上一定对应着一个顶点（角点）。

推论：线性规划若有最优解，则一定存在最优基本可行解，是单纯形法理论根基。

Important

计算机不会看图，无法直接找“角点”；但计算机非常擅长做矩阵运算（算 BFS）。既然两者等价，计算机只需要在不同的 BFS（基）之间进行切换和比较，就等于在图形的各个顶点之间“跳跃”寻找最优解。这就是大名鼎鼎的“单纯形法”的运行逻辑。

5. 基本可行解存在定理（定理2.2.4）#

只要这个问题有解（即它的可行域不是空的，里面至少有一个点 $x$ ），那么这个可行域就一定存在至少一个顶点（基本可行解）。

证明:

假设你现在站在可行域的“内部”（一个普通的可行解，不是顶点）。
因为对应的列线性相关，你可以顺着某个方向移动，直到触碰到边界。
每次碰到边界，就会有多一个变量变成 0。
由于变量个数有限，你不断地往边界“推”，最终一定会推到某几个边界的交汇处——也就是退无可退的顶点（角点）。此时，正分量对应的列线性无关，你就得到了一个基本可行解。

意义：它保证了我们使用单纯形法时，**绝对能找到一个起点（顶点）**开始搜索。

Ch 03. 单纯形方法#

3.1 单纯形方法原理#

我们可以把单纯形方法（Simplex Method）想象成一个 “在多面体山谷中寻找最低点（或最高点）” 的探索游戏。

在线性规划中，可行区域就像一个由许多平面围成的多面体（比如一栋多面体建筑），而它的最优解（最低点或最高点）一定会出现在这个多面体的某个“顶点”（角）上。

单纯形方法的核心思想就是：从一个顶点出发，沿着棱线走到相邻的、更好的顶点，一步步直到找到最顶端或最低端。

例子#

\begin{aligned} \max \quad & 3x + 2y + z \\ \text{s.t.} \quad & x + 2y + z \le 400 \\ & 2x + y + z \le 500 \\ & x, y, z \ge 0 \end{aligned}

我们可以按照前面介绍的“下山/爬山”逻辑，一步步用单纯形方法来求解。因为这是一个求最大值(max)的问题，所以我们的目标是一路上坡，直到找不到更高的路为止。

第一步：准备工作（引入“松弛变量”和找起点）

为了把不等式变成等式，我们引入两个“松弛变量” $s_1$ 和 $s_2$ （它们代表资源没有用完的剩余量，且 $s_1, s_2 \ge 0$ ）：

$x + 2y + z + s_1 = 400$
$2x + y + z + s_2 = 500$

此时，我们的目标是最大化： $W = 3x + 2y + z$

寻找初始起点：

最容易找的起点是原点，即让所有决策变量都为 0：

$x = 0, \quad y = 0, \quad z = 0$

带入后，我们可以轻松得到：

$s_1 = 400, \quad s_2 = 500$

当前海拔高度（目标函数值）： $W = 0$

第二步：第一次迭代（寻找最陡的上坡路）

环顾四周（选择进基变量）

我们现在在 $(0,0,0)$ 这个顶点。看一眼目标函数：
$W = 3x + 2y + z$
- 如果增加 $x$ ，每增加 1 单位，海拔上升 3。
- 如果增加 $y$ ，每增加 1 单位，海拔上升 2。
- 如果增加 $z$ ，每增加 1 单位，海拔上升 1。
最陡的路显然是 $x$ 方向（因为系数 3 最大）。所以我们决定让 $x$ 进基（开始增加 $x$ 的值）。
计算能走多远（选择离基变量 - 最小比值测试）

沿着 $x$ 轴往前走，能走多远取决于等式约束中的“墙壁”：
- 墙壁 1（第一个约束）： $x + s_1 = 400 \implies x \le 400$
- 墙壁 2（第二个约束）： $2x + s_2 = 500 \implies x \le \frac{500}{2} = 250$
为了不撞破墙壁，我们只能走到最近的限制点： $x = 250$ 。

此时，墙壁 2 处的剩余资源用光了（ $s_2$ 变为了 0）。所以我们把 $s_2$ 选为离基变量。
移动到新顶点（坐标变换）

根据 $2x + y + z + s_2 = 500$ ，我们将 $x$ 表达出来：
$x = 250 - 0.5y - 0.5z - 0.5s_2$
把它代入到第一个约束和目标函数中，得到新的表达式：
- 新等式 1： $1.5y + 0.5z + s_1 - 0.5s_2 = 150$ （由原等式 1 代入 $x$ 得到）
- 新目标函数：
$W = 3(250 - 0.5y - 0.5z - 0.5s_2) + 2y + z = 750 + 0.5y - 0.5z - 1.5s_2$
我们成功来到了第二个顶点：

$x = 250, \quad s_1 = 150, \quad y = 0, \quad z = 0, \quad s_2 = 0$

当前海拔高度： $W = 750$ 。

第三步：第二次迭代（继续寻找上坡路）

环顾四周

在新的顶点，看一眼新的目标函数表达式：
$W = 750 + 0.5y - 0.5z - 1.5s_2$
- 增加 $y$ ，海拔还能上升（系数为 $+0.5$ ）。
- 增加 $z$ 或 $s_2$ 都会让海拔下降（系数为负）。
所以，我们决定让 $y$ 进基（开始增加 $y$ 的值）。
计算能走多远（最小比值测试）

看一看当前两个等式对 $y$ 的限制：
- 新等式 1： $1.5y + s_1 = 150 \implies y \le \frac{150}{1.5} = 100$
- 新等式 2（利用 $x$ 的表达式）： $x + 0.5y = 250 \implies y \le \frac{250}{0.5} = 500$
最严苛的限制是 $y \le 100$ 。当 $y = 100$ 时， $s_1$ 用光变为了 0。

因此， $s_1$ 被选为离基变量。
移动到新顶点

根据 $1.5y + 0.5z + s_1 - 0.5s_2 = 150$ ，我们可以将 $y$ 表达为：

$y = 100 - \frac{1}{3}z - \frac{2}{3}s_1 + \frac{1}{3}s_2$

把 $y$ 代入到 $x$ 的表达式以及目标函数中：
- $x$ 的新表达式：
$x = 200 - \frac{1}{3}z + \frac{1}{3}s_1 - \frac{2}{3}s_2$
- 最新目标函数：
$W = 750 + 0.5\left(100 - \frac{1}{3}z - \frac{2}{3}s_1 + \frac{1}{3}s_2\right) - 0.5z - 1.5s_2 = 800 - \frac{2}{3}z - \frac{1}{3}s_1 - \frac{4}{3}s_2$

我们成功来到了第三个顶点：

$x = 200, \quad y = 100, \quad z = 0, \quad s_1 = 0, \quad s_2 = 0$

当前海拔高度： $W = 800$ 。
检查是否到达终点

再次环顾四周，看看最新的目标函数：

$W = 800 - \frac{2}{3}z - \frac{1}{3}s_1 - \frac{4}{3}s_2$

此时，所有未使用的变量（ $z, s_1, s_2$ ）前面的系数全部为负数。这意味着：
- 无论你往哪个方向移动（增加 $z, s_1$ 或 $s_2$ ），海拔 $W$ 都只可能减小。
- 我们已经站在了最高峰！

最终结论

经过单纯形法的逐步迭代，我们找到了该线性规划问题的最优解：

最优决策变量：

$x = 200, \quad y = 100, \quad z = 0$
最大目标函数值（最高海拔）：

$W = 800$

单纯形表法#

原问题为极大化问题：

\max \quad Z = 3x + 2y + z

令 $W = -Z$ ，则原问题等价于求如下极小化问题：

\min \quad W = -3x - 2y - z

引入松弛变量 $s_1 \ge 0$ 和 $s_2 \ge 0$ ，将不等式约束转化为等式约束：

\begin{aligned} \min \quad & W = -3x - 2y - z + 0s_1 + 0s_2 \\ \text{s.t.} \quad & x + 2y + z + s_1 = 400 \\ & 2x + y + z + s_2 = 500 \\ & x, y, z, s_1, s_2 \ge 0 \end{aligned}

此时，目标函数的系数为：

c = [-3, -2, -1, 0, 0]

对于极小化问题，判别式（检验数）定义为 $\sigma_j = z_j - c_j$ 。当所有的 $z_j - c_j \le 0$ 时，当前解即为最优解。若存在 $z_j - c_j > 0$ ，则选择其中最大正值对应的变量作为入基变量。

1. 初始单纯形表（第 1 步迭代）

\begin{array}{cc|ccccc|c|c} \hline c_j & & -3 & -2 & -1 & 0 & 0 & & \\ C_B & \text{基变量} & x & y & z & s_1 & s_2 & \text{RHS} & \theta \text{ (RHS}/x_j) \\ \hline 0 & s_1 & 1 & 2 & 1 & 1 & 0 & 400 & 400 / 1 = 400 \\ 0 & s_2 & [2] & 1 & 1 & 0 & 1 & 500 & 500 / 2 = 250 \\ \hline z_j-c_j & & 3 & 2 & 1 & 0 & 0 & W = 0 & \\ \hline \end{array}

入基变量选择：检验数 $z_j - c_j$ 中最大正值为 $\sigma_1 = 3$ ，因此 $x$ 为入基变量。
出基变量选择：根据最小比值原则 $\theta$ ， $\min(400, 250) = 250$ ，故 $s_2$ 为出基变量。
主元（Pivot）：为交叉处的元素 $[2]$ 。

2. 第二次单纯形表（第 2 步迭代） 进行旋转变换（Pivot Row 2 除以 2，Row 1 减去新的 Row 2）：

\begin{array}{cc|ccccc|c|c} \hline c_j & & -3 & -2 & -1 & 0 & 0 & & \\ C_B & \text{基变量} & x & y & z & s_1 & s_2 & \text{RHS} & \theta (\text{ RHS}/x_j) \\ \hline 0 & s_1 & 0 & [3/2] & 1/2 & 1 & -1/2 & 150 & 150 / (3/2) = 100 \\ -3 & x & 1 & 1/2 & 1/2 & 0 & 1/2 & 250 & 250 / (1/2) = 500 \\ \hline z_j-c_j & & 0 & 1/2 & -1/2 & 0 & -3/2 & W = -750 & \\ \hline \end{array}

入基变量选择：检验数中仍有正数 $z_2 - c_2 = 1/2 > 0$ ，因此 $y$ 为入基变量。
出基变量选择：计算 $\theta$ ， $\min(100, 500) = 100$ ，故 $s_1$ 为出基变量。
主元（Pivot）：为交叉处的元素 $[3/2]$ 。

3. 第三次单纯形表（最终迭代） 进行旋转变换（Row 1 乘以 $2/3$ ，Row 2 减去 $1/2 \times$ 新 Row 1）：

\begin{array}{cc|ccccc|c|c} \hline c_j & & -3 & -2 & -1 & 0 & 0 & & \\ C_B & \text{基变量} & x & y & z & s_1 & s_2 & \text{RHS} & \theta \\ \hline -2 & y & 0 & 1 & 1/3 & 2/3 & -1/3 & 100 & - \\ -3 & x & 1 & 0 & 1/3 & -1/3 & 2/3 & 200 & - \\ \hline z_j-c_j & & 0 & 0 & -2/3 & -1/3 & -4/3 & W = -800 & \\ \hline \end{array}

最优性判断：此时所有的检验数 $z_j - c_j \le 0$ （具体值为 $0, 0, -2/3, -1/3, -4/3$ ），迭代结束，已找到最优解。

3.2 两阶段法 & 大 M 法#

在之前的例子中，我们所有的约束条件都是 $\le$ 。当我们把所有的决策变量（如 $x_1, x_2, x_3$ ）都设为 $0$ 时，松弛变量就可以很自然地作为初始起点（比如 $s_1 = 400, s_2 = 500$ ）。这个起点是在多面体可行域内的。

但在实际问题中，经常会出现 $\ge$ 或 $=$ 的约束。例如下面例题中的第三个约束： $2x_1 - x_2 + x_3 \ge 1$

\begin{array}{rrrrrcr} \min & 5x_1 &-&4x_2 &+&3 x_3 & & & \\ \text{s.t.} & 2x_1 &-&x_2 &+&4x_3 & \le & 4 \\ & x_1 &+ &x_2 &+&2x_3 & \le & 6 \\ & 2x_1 &- &x_2 &+&x_3 & \ge & 1 \end{array} \\ x_1,x_2,x_3 \ge 0

如果我们把 $x_1, x_2, x_3$ 都设为 $0$ ，就会得到 $0 \ge 1$ ，这显然是不成立的。也就是说，原点 $(0,0,0)$ 根本不在合法区域内。

如果我们强行减去一个“剩余变量” $s_3$ 将其化为等式：

$2x_1 - x_2 + x_3 - s_3 = 1$

当决策变量为 $0$ 时，会得到 $s_3 = -1$ ，这违反了非负约束（ $s_3 \ge 0$ ），因此 $s_3$ 也不能用来当做起点。

既然找不到起点，数学家们就想了一个“作弊”的办法：

我们在等式左边强行加入一个临时的虚拟变量（即人工变量 $a_1 \ge 0$ ），将等式强行写成：

$2x_1 - x_2 + x_3 - s_3 + a_1 = 1$

这样，当决策变量和剩余变量都为 $0$ 时，我们就有了一个数学上的初始起点： $a_1 = 1$ 。

但请注意：这个变量是虚构的。因此，我们在计算的过程中，必须用尽一切手段让这个人工变量变为 $0$ 。如果算到最后它还是大于 0，说明原问题根本没有可行解。

为了强行把人工变量逼到 $0$ ，有两种主流方法：

大 M 法 (Big M Method)：

我们在原目标函数里给人工变量加上一个极其沉重的惩罚。比如本题是求极小化，我们就把目标函数写成 $\min z + M \cdot a_1$ （其中 $M$ 是一个无穷大的正数）。因为我们要追求极小化，算法为了降低成本，会拼了命地优先把 $a_1$ 减小到 $0$ 。
两阶段法 (Two-Phase Method)：

因为大M法要在表格里一直带着一个字母 $M$ 进行加减乘除，手算很容易出错。因此人们发明了“分步走”的两阶段法：
- 第一阶段：不管原目标函数，我们只求人工变量的和最小（即 $\min g = a_1$ ）。如果第一阶段算完，发现最小只能做到 $g > 0$ ，说明无解；如果能做到 $g = 0$ ，说明我们已经摆脱了虚构变量，找到了一个真实的“合法顶点”。
- 第二阶段：丢弃人工变量，把原目标函数放回来，从第一阶段找到的那个真实顶点继续往下算。

下面使用大 M 法来解决这个问题。

对于约束 1（ $\le$ ），引入松弛变量 $s_1 \ge 0$ ；
对于约束 2（ $\le$ ），引入松弛变量 $s_2 \ge 0$ ；
对于约束 3（ $\ge$ ），引入剩余变量 $s_3 \ge 0$ 和人工变量 $a_1 \ge 0$ 。

由于是求极小化（ $\min$ ）问题，我们需要在目标函数中对人工变量 $a_1$ 加上一个极大的正惩罚项 $+M \cdot a_1$ （其中 $M$ 为一个极大的正实数）。

标准化后的模型为：

\begin{aligned} \min \quad & z = 5x_1 - 4x_2 + 3x_3 + 0s_1 + 0s_2 + 0s_3 + M a_1 \\ \text{s.t.} \quad & 2x_1 - x_2 + 4x_3 + s_1 = 4 \\ & x_1 + x_2 + 2x_3 + s_2 = 6 \\ & 2x_1 - x_2 + x_3 - s_3 + a_1 = 1 \\ & x_1, x_2, x_3, s_1, s_2, s_3, a_1 \ge 0 \end{aligned}

对于极小化问题，判别式（检验数）为 $\sigma_j = z_j - c_j$ ，其中 $z_j = \sum (c_B)_i a_{ij}$ 。

最优性条件：当所有的检验数 $z_j - c_j \le 0$ 时，当前解为最优解。
换入变量选择：若存在 $z_j - c_j > 0$ ，选择最大正数对应的变量作为入基变量。

1. 初始单纯形表（第 1 步迭代）

初始基变量选择为 $s_1, s_2, a_1$ ，其对应的目标函数系数为 $c_B = [0, 0, M]^T$ 。

\begin{array}{cc|ccccccc|c|c} \hline c_j & & 5 & -4 & 3 & 0 & 0 & 0 & M & & \\ C_B & \text{基变量} & x_1 & x_2 & x_3 & s_1 & s_2 & s_3 & a_1 & \text{RHS} & \theta \\ \hline 0 & s_1 & 2 & -1 & 4 & 1 & 0 & 0 & 0 & 4 & 4/2 = 2 \\ 0 & s_2 & 1 & 1 & 2 & 0 & 1 & 0 & 0 & 6 & 6/1 = 6 \\ M & a_1 & [2] & -1 & 1 & 0 & 0 & -1 & 1 & 1 & 1/2 = 0.5 \\ \hline z_j-c_j & & 2M-5 & -M+4 & M-3 & 0 & 0 & -M & 0 & z = M & \\ \hline \end{array}

入基变量：在 $z_j - c_j$ 中， $2M-5$ 是最大的正值（因为 $M$ 极大），因此选择 $x_1$ 入基。
出基变量：根据 $\theta$ 比值原则， $\min(2, 6, 0.5) = 0.5$ ，故选择 $a_1$ 出基。
主元：为 $[2]$ 。

2. 第二次单纯形表（第 2 步迭代）

主元变换：将第 3 行除以 2，然后通过行变换消去其他行在 $x_1$ 列上的系数。

\begin{array}{cc|ccccccc|c|c} \hline c_j & & 5 & -4 & 3 & 0 & 0 & 0 & M & & \\ C_B & \text{基变量} & x_1 & x_2 & x_3 & s_1 & s_2 & s_3 & a_1 & \text{RHS} & \theta \\ \hline 0 & s_1 & 0 & 0 & 3 & 1 & 0 & 1 & -1 & 3 & - \\ 0 & s_2 & 0 & [1.5] & 1.5 & 0 & 1 & 0.5 & -0.5 & 5.5 & 5.5 / 1.5 = 11/3 \\ 5 & x_1 & 1 & -0.5 & 0.5 & 0 & 0 & -0.5 & 0.5 & 0.5 & - \\ \hline z_j-c_j & & 0 & 1.5 & -0.5 & 0 & 0 & -2.5 & -M+2.5 & z = 2.5 & \\ \hline \end{array}

入基变量：检验数中只有 $z_2 - c_2 = 1.5 > 0$ ，因此选择 $x_2$ 入基。
出基变量：计算 $\theta$ 比值， $s_1$ 行和 $x_1$ 行对应的 $x_2$ 系数不大于 0（忽略），只有 $s_2$ 行满足条件，所以选择 $s_2$ 出基。
主元：为 $[1.5]$ （即 $\frac{3}{2}$ ）。

3. 第三次单纯形表（最终迭代）

主元变换：第 2 行乘以 $\frac{2}{3}$ ，并通过行变换消去其他行在 $x_2$ 列上的系数。为了结果精确，以下数据采用分数表示。

\begin{array}{cc|ccccccc|c|c} \hline c_j & & 5 & -4 & 3 & 0 & 0 & 0 & M & & \\ C_B & \text{基变量} & x_1 & x_2 & x_3 & s_1 & s_2 & s_3 & a_1 & \text{RHS} & \theta \\ \hline 0 & s_1 & 0 & 0 & 3 & 1 & 0 & 1 & -1 & 3 & - \\ -4 & x_2 & 0 & 1 & 1 & 0 & 2/3 & 1/3 & -1/3 & 11/3 & - \\ 5 & x_1 & 1 & 0 & 1 & 0 & 1/3 & -1/3 & 1/3 & 7/3 & - \\ \hline z_j-c_j & & 0 & 0 & -2 & 0 & -1 & -3 & -M+3 & z = -3 & \\ \hline \end{array}

最优性判断：所有的检验数 $z_j - c_j \le 0$ （具体为 $0, 0, -2, 0, -1, -3, -M+3 \le 0$ ）。因此，当前表格已达到最优。

结论

最优解已求得，其变量取值为：

$x_1 = \frac{7}{3}, x_2 = \frac{11}{3}, x_3 = 0$

松弛变量与剩余变量的取值为：

$s_1 = 3, s_2 = 0, s_3 = 0$

最优目标函数值（极小值）为：

z_{\min} = -3

3.3 退化与循环#

退化：在做最小比值筛选时，发现算出来的步长 $\theta = 0$ 。这意味着我们虽然换了基变量，但在空间中其实一步都没挪动。
循环（鬼打墙）：因为原地踏步，迭代了好几次，最后发现单纯形表居然和几步前一模一样。算法陷入了死循环，永远停不下来。
摄动法（解决办法）：
- 原理：既然是因为某些约束线刚好交在同一个点上（退化），那我们就把右端的常数项 $b$ 加上一个极小的扰动（比如 $\epsilon$ 的几次方）。
- 这样就把交在一起的线稍微“错开”了一点点，让死角变成一个小通道，从而打破死循环，保证算法能够继续走下去。

3.4 修正单纯形法#

痛点：标准的单纯形表要随着迭代不断更新整个大矩阵，如果变量有几万个，计算机会耗费大量内存来存那些根本不常用的数据。
核心改进：实际上，每次迭代我们只需要用到当前基矩阵的逆 $B^{-1}$ 、右端项和原始数据。
做法：我们不保存整张大表，只保留并更新 $B^{-1}$ 。每一次要算检验数或者主列时，临时用原始数据和 $B^{-1}$ 乘一下算出来。
逆的乘积形式：更新 $B^{-1}$ 时，用初等矩阵相乘，进一步节省存储空间。这非常适合计算机处理大型稀疏矩阵。

详见 wikipedia: Revised simplex method。

3.5 变量有界单纯形#

普通情况：变量只要 $\ge 0$ 就行。
有界情况：变量有区间限制（ $l_j \le x_j \le u_j$ ）。
聪明做法：不用把这些上下界当成新的约束条件塞进表格（否则表格会成倍变大）。
规则微调：
- 非基变量不仅可以等于 0（下界），还可以等于它的最大值（上界）。
- 在选进基和离基时，不仅要考虑变量不能跌破下界，还要考虑它们不能撑破上界。一旦某个变量在移动过程中碰到了上界，它就直接停在上界，不一定要替换基变量。

3.6 分解算法#

适用场景：一个超级大系统，里面有很多子系统（比如一个大集团有多个分厂，各自生产，但共享集团的部分总资源）。
角色分配：
- 主规划（总公司）：负责全局把控，协调分配集团总资源。
- 子规划（分公司）：各分公司根据总公司给出的内部资源价格（单纯形乘子），在自己的小范围内做优化，然后把方案报给总公司。
工作流程：分公司报方案 $\rightarrow$ 总公司评估并调整资源价格 $\rightarrow$ 分公司根据新价格重新优化报方案 $\rightarrow$ 循环往复，直到分公司无法报出更赚钱的方案，此时全局达到最优。

Ch 04. 对偶原理及灵敏度分析#

线性规划对偶理论#

1. 对偶形式构造规则#

【直观理解：什么是对偶？】

原始问题（Primal）：我有若干资源，如何安排生产，才能使利润最大？
对偶问题（Dual）：别人想买断我的所有资源，他该如何定价（对偶变量 $w$ 就是资源的估价），才能使收购总成本最小，同时我又愿意卖给他（不低于我自己生产的收益）？

（1）对称对偶

原问题（少花钱，满足基本需求）:
$\begin{array}{ll} \min & \boldsymbol{c}\boldsymbol{x} \\ \text{s.t.} & \boldsymbol{A}\boldsymbol{x}\ge\boldsymbol{b} \\ & \boldsymbol{x} \ge \boldsymbol{0} \end{array}$
对偶问题（多收钱，但报价不能高过市场价）
$\begin{array}{ll} \max & \boldsymbol{w}\boldsymbol{b} \\ \text{s.t.} & \boldsymbol{w}\boldsymbol{A}\le\boldsymbol{c} \\ & \boldsymbol{w} \ge \boldsymbol{0} \end{array}$

（2）非对称对偶与一般混合约束转换

原问题:
$\begin{array}{rrrrrcr} \min & cx & & & \\ \text{s.t.} & A_1x & \ge & b_1 \\ & A_2x & = & b_2 \\ & A_3x & \le & b_3 \\ \end{array} \\ x \ge 0$
对偶问题:
$\begin{array}{l} \max &w_1b_1+w_2b_2+w_3b_3 \\ \text{s.t.} &w_1A_1 + w_2A_2 + w_3A_3 \le c ，\\ \end{array} \\ w_1 \ge 0 ，\\ w_3 \le 0，\\ w_2无限制$

2. 三大对偶定理#

（1）弱对偶定理

数学表达： $\min$ 问题的任意可行解 $x^{(0)}$ 和 $\max$ 问题的任意可行解 $w^{(0)}$ ，有关系 $\boldsymbol{c}\boldsymbol{x^{(0)}} \ge \boldsymbol{w^{(0)}}\boldsymbol{b}$ 。
通俗翻译：“买家的最高出价，也绝不会超过卖家的最低底线。”
考试妙用：如果你找到一个原问题的解（比如收益是100）和一个对偶问题的解（比如成本也是100），不用怀疑，它们两个都已经达到最值了。

（2）强对偶定理

通俗翻译：在市场完全竞争（达到最优）时，买家的出价（资源总估值）和卖家的收益（生产总利润）一分钱都不差，完美相等。

（3）互补松弛定理

数学表达：成对乘积为0，即 $x_j (w A^T_j - c_j) = 0$ 且 $w_i (A_i x - b_i) = 0$ 。
通俗翻译（两句大白话）：
1. 若资源有剩，则该资源不值钱：如果某种资源 $i$ 在最优方案里没有用完（约束是严格不等式 $A_i x > b_i$ ），那它的影子价格（对偶变量）一定是 $w_i = 0$ 。
2. 若某产品赔钱，则绝不生产：如果生产产品 $j$ 的虚拟成本高于市场价（即 $w A^T_j > c_j$ ），那么最优方案中这种产品绝对不生产（ $x_j = 0$ ）。
3. 反过来：如果决定生产（ $x_j > 0$ ），说明刚好保本（ $w A^T_j = c_j$ ）。
考试怎么用：
- 题目通常会给你原问题的最优解 $x^* = (2, 0, 4)$ 。
- 第一步：因为 $x_1 > 0$ 和 $x_3 > 0$ ，所以对应的第1、3个对偶约束必须是等式（即等号成立）。
- 第二步：代入原问题的约束，看看哪些约束有剩余。如果有剩余，对应的对偶变量 $w_i = 0$ 。
- 第三步：列方程组，轻松解出对偶最优解 $w^*$ 。

例题

给定线性规划问题，原问题为

\begin{array}{ll} \min&\quad 2x_1 + 3x_2 + x_3 \\ \text{s.t.}&\quad 3x_1 - x_2 + x_3 \ge 1, \\ &\quad x_1 + 2x_2 - 3x_3 \ge 2, \\ &\quad x_1,x_2,x_3 \ge 0. \end{array}

它的对偶问题为

\begin{array}{ll} \max&\quad w_1 + 2w_2 \\ \text{s.t.}&\quad 3w_1 + w_2 \le 2, \\ &\quad -w_1 + 2w_2 \le 3, \\ &\quad w_1 - 3w_2 \le 1, \\ &\quad w_1,w_2 \ge 0. \end{array}

设用图解法求得对偶问题的最优解为 $\bar{\boldsymbol{w}} = (w_1,w_2) = \left( \frac{1}{7},\frac{11}{7} \right)$ ，试用互补松弛定理求原问题的最优解。

答案: 由于在最优解 $\bar{\boldsymbol{w}}$ 处，对偶问题的第三个约束 $w_1 - 3w_2 \le 1$ 成立严格不等式，根据 $x_j (w A^T_j - c_j) = 0$ 得 $x_3 = 0$ 。又由于 $\bar{\boldsymbol{w}}$ 的两个分量均大于 0，由 $w_i (A_i x - b_i) = 0$ 可知原问题中的前两个约束在最优解处成立等式，即

\left\{ \begin{array}{l} 3x_1 - x_2 + x_3 = 1, \\ x_1 + 2x_2 - 3x_3 = 2. \end{array} \right.

把 $x_3 = 0$ 代入上述方程组，得到

\left\{ \begin{array}{l} 3x_1 - x_2 = 1, \\ x_1 + 2x_2 = 2. \end{array} \right.

解此方程，得到 $x_1 = \frac{4}{7}, x_2 = \frac{5}{7}$ ，因此原问题的最优解是 $\bar{\boldsymbol{x}} = (x_1, x_2, x_3)^T = (\frac{4}{7}, \frac{5}{7}, 0)^T$ ，目标函数的最优值为 $f_{min} = \frac{23}{7}$ 。

对偶单纯形法#

在传统的原单纯形法（Primal Simplex Method）中，当我们遇到 $ge$ 或 $=$ 的约束条件时，加入常规的松弛变量后，由于右端常数（RHS）的要求，我们无法直接得到一个初始可行基（即单位矩阵）。

为了强行构造出一个初始基，原单纯形法必须引入人工变量，并使用大 M 法（Big-M Method）或两阶段法(Two-Phase Method)。这不仅增加了变量的维度，计算过程也非常繁琐，大 M 法还容易在计算机求解时引发数值不稳定的问题。

对偶单纯形法的巧妙之处在于：它允许“原问题不可行”，只要“对偶问题可行”即可开始迭代。

具体操作如下：

转化约束：将 $\ge b$ （其中 $b > 0$ ）的约束两边同乘 -1，变成 $\le -b$
加入常规松弛变量：直接加上大于等于 0 的松弛变量 $x_s$ 。此时的初始基就是这些松弛变量。
状态分析：
- 此时常数项变成了负数（-b），即变量取负值，原问题不可行（Primal Infeasible）。
- 但是，如果目标函数的检验数 $z_j - c_j$ 已经满足最优性条件（对于求极小值问题，所有 $z_j - c_j \le 0$ ），这就意味着对偶问题是可行的（Dual Feasible）。

例题#

用对偶单纯形法解问题:

\begin{array}{ll} \min & 12x_1 + 8x_2 + 16x_3 + 12x_4, \\ \text{s.t.} & 2x_1 + x_2 + 4x_3 \quad\quad \ge 2, \\ & 2x_1 + 2x_2 \quad\quad + 4x_4 \ge 3, \\ & x_j \ge 0,\quad j = 1,\dots,4. \end{array}

1. 问题标准化

原问题为极小化问题，且约束条件均为 $\ge$ 。为了使用对偶单纯形法，我们需要将约束条件两边同乘 $-1$ 转化为 $\le$ 形式，然后加入松弛变量 $x_5, x_6 \ge 0$ 。

转化后的目标函数和约束条件如下：

\begin{array}{ll} \min & z = 12x_1 + 8x_2 + 16x_3 + 12x_4 + 0x_5 + 0x_6 \\ \text{s.t.} & -2x_1 - x_2 - 4x_3 + x_5 = -2 \\ & -2x_1 - 2x_2 - 4x_4 + x_6 = -3 \\ & x_j \ge 0, \quad j = 1, \dots, 6 \end{array}

初始检验数分析：

对于求极小值问题，检验数的定义为 $\sigma_j = z_j - c_j$ 。当所有 $z_j - c_j \le 0$ 时，满足对偶可行性（即达到最优条件）。初始基变量为 $x_5, x_6$ ，对应常数项 $b$ 分别为 $-2, -3$ 。由于 $b_i < 0$ ，原问题不可行，但所有检验数 $z_j - c_j = 0 - c_j \le 0$ ，满足对偶可行性，因此可以直接使用对偶单纯形法。

2. 对偶单纯形法迭代过程

迭代规则：

换出变量 (Leaving Variable)： 选择 $b_i$ 中最小的负数所在的行，对应的基变量换出。
换入变量 (Entering Variable)： 对于换出变量所在行的系数 $a_{ij} < 0$ 的列，计算比值 $\theta = \frac{z_j - c_j}{a_{ij}}$ ，选择比值最小的列对应的非基变量换入。

初始单纯形表

$b_2 = -3$ 是最小的负数，因此 $x_6$ 换出（主元行 2）。计算比值 $\theta$ ：

$x_1: -12 / -2 = 6$
$x_2: -8 / -2 = 4$
$x_4: -12 / -4 = 3$ （最小）因此 $x_4$ 换入（主元列 4）。主元为 $a_{24} = -4$ 。

\begin{array}{|c|c|c|cccc|cc|} \hline C_B & X_B & b & x_1 & x_2 & x_3 & x_4 & x_5 & x_6 \\ \hline 0 & x_5 & -2 & -2 & -1 & -4 & 0 & 1 & 0 \\ 0 & x_6 & -3 & -2 & -2 & 0 & \mathbf{-4} & 0 & 1 \\ \hline z_j - c_j & & 0 & -12 & -8 & -16 & -12 & 0 & 0 \\ \hline \end{array}

第一次迭代

进行行变换，使主元变为 1，同列其他元素变为 0。

第 2 行 $\div (-4)$
检验数行 $- (-12) \times$ 新第 2 行

\begin{array}{|c|c|c|cccc|cc|} \hline C_B & X_B & b & x_1 & x_2 & x_3 & x_4 & x_5 & x_6 \\ \hline 0 & x_5 & -2 & \mathbf{-2} & -1 & -4 & 0 & 1 & 0 \\ 12 & x_4 & 3/4 & 1/2 & 1/2 & 0 & 1 & 0 & -1/4 \\ \hline z_j - c_j & & 9 & -6 & -2 & -16 & 0 & 0 & -3 \\ \hline \end{array}

此时 $b_1 = -2 < 0$ ，因此 $x_5$ 换出（主元行 1）。

计算比值 $\theta$ ( $a_{1j} < 0$ )：

$x_1: -6 / -2 = 3$
$x_2: -2 / -1 = 2$ （最小）
$x_3: -16 / -4 = 4$

因此 $x_2$ 换入（主元列 2）。主元为 $a_{12} = -1$ 。

第二次迭代

进行行变换：

第 1 行 $\div (-1)$
第 2 行 $- (1/2) \times$ 新第 1 行
检验数行 $- (-2) \times$ 新第 1 行

\begin{array}{|c|c|c|cccc|cc|} \hline C_B & X_B & b & x_1 & x_2 & x_3 & x_4 & x_5 & x_6 \\ \hline 8 & x_2 & 2 & 2 & 1 & 4 & 0 & -1 & 0 \\ 12 & x_4 & -1/4 & \mathbf{-1/2} & 0 & -2 & 1 & 1/2 & -1/4 \\ \hline z_j - c_j & & 13 & -2 & 0 & -8 & 0 & -2 & -3 \\ \hline \end{array}

此时 $b_2 = -1/4 < 0$ ，因此 $x_4$ 换出（主元行 2）。

计算比值 $\theta$ ( $a_{2j} < 0$ )：

$x_1: -2 / (-1/2) = 4$
$x_3: -8 / -2 = 4$
$x_6: -3 / (-1/4) = 12$

这里 $x_1$ 和 $x_3$ 的比值同为 4 发生退化（Tie），根据勃兰特法则（Bland’s Rule），选择下标较小的变量，因此 $x_1$ 换入（主元列 1）。主元为 $a_{21} = -1/2$ 。

第三次迭代

进行行变换：

第 2 行 $\div (-1/2)$
第 1 行 $- 2 \times$ 新第 2 行
检验数行 $- (-2) \times$ 新第 2 行

\begin{array}{|c|c|c|cccc|cc|} \hline C_B & X_B & b & x_1 & x_2 & x_3 & x_4 & x_5 & x_6 \\ \hline 8 & x_2 & 1 & 0 & 1 & -4 & 4 & 1 & -1 \\ 12 & x_1 & 1/2 & 1 & 0 & 4 & -2 & -1 & 1/2 \\ \hline z_j - c_j & & 14 & 0 & 0 & 0 & -4 & -4 & -2 \\ \hline \end{array}

3. 最终结论

在当前的单纯形表中，所有的常数项 $b_i \ge 0$ （原问题已具备可行性），且所有的检验数 $z_j - c_j \le 0$ （对偶问题保持最优性）。因此，当前解即为最优解。

最优解为： $x_1 = \frac{1}{2}, x_2 = 1, x_3 = 0, x_4 = 0$

目标函数的最小值为： $\min z = 14$

灵敏度分析#

工厂的生产计划做好了，突然经理说：“原材料涨价了（ $c$ 变了）”或者“仓库多送来一吨钢材（ $b$ 变了）”。我们千万不想重新列方程算一遍。灵敏度分析就是利用已经算好的最终单纯形表，做一点点矩阵乘法，快速算出新方案。

1. 核心概念：影子价格（Shadow Price）#

通俗翻译：“多给我一单位的某种资源，我的总利润能增加多少？”
经济意义：
- 如果某种资源在最优方案里没有用完，它的影子价格就是 $0$ （白送你一吨你也没用）。
- 如果某种资源紧缺，它的影子价格是 $5$ 。这意味着如果市场上这种资源的价格低于 $5$ ，你买进来就是划算的。

2. 常考扰动的应对策略#

（1）目标系数 $c_j$ 变了（产品价格波动）

如果它是“没生产”的产品（非基变量）：
- 只要它涨价没涨到“值得生产”的门槛（检验数依旧 $\le 0$ ），生产计划完全不变。
如果它是“正在生产”的产品（基变量）：
- 它变动会影响很多产品的检验数。我们需要列出不等式，算出它的“安全变动区间”。在这个区间内，生产计划不变。

（2）右端项 $b_i$ 变了（资源量变动）

用最终表的逆矩阵乘上新的资源向量，即 $B^{-1}b'$ 。
如果算出来的结果全 $\ge 0$ ：太棒了！原计划的结构不用变，只需要把新数字代入，算一下新产量和新利润（利用影子价格快速计算：新利润 = 旧利润 + 变动量 $\times$ 影子价格）。
如果算出来的结果出现了负数：说明现在的资源分配方案“不可行”了。不用重算，直接在这个表上用对偶单纯形法转几步即可。

（3）增加新约束（突然出台了环保新规）

第一步：把我们现有的最优解代入这个新约束。
第二步：如果新约束依然满足，皆大欢喜，新约束当不存在，最优解不变。
第三步：如果不满足，把新约束加到表格最下面，引入一个松弛变量。此时表格会出现负数，直接用对偶单纯形法把它纠正过来。

例子#

设生产桌子 $x_1$ 张，椅子 $x_2$ 把。

目标函数（利润最大化）：

max z = 50x_1 + 30x_2

约束条件：
- 木材限制： $4x_1 + 2x_2 \le 100$
- 工时限制： $2x_1 + 2x_2 \le 80$
- 非负约束： $x_1, x_2 \ge 0$

引入松弛变量：

$x_3$ ：未使用的木材量（木材松弛变量）
$x_4$ ：未使用的工时量（工时松弛变量）

\begin{array}{ll} \max & 50x_1 + 30x_2 \\ \text{s.t.} & 4x_1 + 2x_2 + x3 = 100\\ & 2x_1 + 2x_2 + x_4 = 80 \\ & x_j \ge 0, \quad j = 1, \dots, 4 \end{array}

初始单纯形表:

\begin{array}{cc|cccc|c|c} \hline c_j & & 50 & 30 & 0 & 0 & & \\ C_B & \text{基变量} & x_1 & x_2 & x_3 & x_4 & \text{RHS} & \theta (\text{ RHS}/x_j) \\ \hline 0 & x_3 & [4] & 2 & 1 & 0 & 100 & 100/4 = 25 \\ 0 & x_4 & 2 & 2 & 0 & 1 & 80 & 80/2 = 40 \\ \hline z_j - c_j & & -50 & -30 & 0 & 0 & 0 \\ \hline \end{array}

主元为 $[4]$ （第一行第一列）。对第一行进行行变换（除以4），然后消去第二行和判别数行中的 $x_1$ 。

迭代第二次表:

\begin{array}{cc|cccc|c|c} \hline c_j & & 50 & 30 & 0 & 0 & & \\ C_B & \text{基变量} & x_1 & x_2 & x_3 & x_4 & \text{RHS} & \theta (\text{ RHS}/x_j) \\ \hline 50 & x_1 & 1 & 1/2 & 1/4 & 0 & 25 & 25/(1/2) = 50 \\ 0 & x_4 & 0 & [1] & -1/2 & 1 & 30 & 30/1 = 30 \\ \hline z_j - c_j & & 0 & -5 & 25/2 & 0 & 1250 \\ \hline \end{array}

主元为 $[1]$ （第二行第二列）。消去第一行和 z 行中的 $x_2$ 。

\begin{array}{cc|cccc|c|c} \hline c_j & & 50 & 30 & 0 & 0 & & \\ C_B & \text{基变量} & x_1 & x_2 & x_3 & x_4 & \text{RHS} & \theta (\text{ RHS}/x_j) \\ \hline 50 & x_1 & 1 & 0 & 1/2 & -1/2 & 10 & \\ 30 & x_2 & 0 & [1] & -1/2 & 1 & 30 & \\ \hline z_j - c_j & & 0 & 0 & 10 & 5 & 1400 \\ \hline \end{array}

从最终表读取的关键信息：

最优解：生产桌子 $x_1^* = 10$ 张，椅子 $x_2^* = 30$ 把。
最大利润： $z^* = 1400$ 元。
最优基的逆矩阵 $B^{-1}$ ：直接对应初始松弛变量 $x_3$ ， $x_4$ 下方的矩阵
$B^{-1} = \begin{pmatrix} 0.5 & -0.5 \\ -0.5 & 1 \end{pmatrix}$
影子价格（对偶最优解）：看 $x_3$ ， $x_4$ 的检验数
- 木材的影子价格 $w_1 = 10$
- 工时的影子价格 $w_2 = 5$

场景 1. 椅子的利润 $c_2$ 从30元跌到25元，生产计划要变吗？

设椅子的利润 $c_2$ 的变动量为 $\Delta c_2$ （此处 $\Delta c_2 = -5$ ）。

当基变量的目标系数改变时，所有非基变量（ $x_3, x_4$ ）的检验数都会发生变化。

新检验数的计算公式为：

$\sigma_j' = \sigma_j - \Delta c_{\text{基}} \cdot (\text{最终表中该非基变量列})$

我们来检查非基变量 $x_3$ 和 $x_4$ 的新检验数（必须保持 $\ge 0$ 才能维持最优）：

对于 $x_3$ （木材）： $\sigma_3' = 10 - (\Delta c_2) \cdot (-0.5) = 10 + 0.5 \Delta c_2 \ge 0 \implies \Delta c_2 \ge -20$
对于 $x_4$ （工时）： $\sigma_4' = 5 - (\Delta c_2) \cdot (1) = 5 - \Delta c_2 \ge 0 \implies \Delta c_2 \le 5$

计算结果：只要 $-20 \le \Delta c_2 \le 5$ 最优生产方案（10张桌子，30把椅子）就不需要改变。

实际结论：跌到 25 元在安全区间内，所以生产方案完全不需调整。新利润变为 $10 \times 50 + 30 \times 25 = 1250$ 元。

场景 2. 供应商送来 10 公斤木材（资源 $b_1$ 从100变为110），开价 8 元/公斤，我们应该买吗？

这属于右端项 $b$ 的变动： $\Delta b = \begin{pmatrix} 10 \\ 0 \end{pmatrix}$ 。我们使用 $B^{-1}$ 来计算新的基变量取值，验证方案是否依然可行（即所有变量是否保持 $\ge 0$ ）：

x_B' = B^{-1} (b + \Delta b) = B^{-1} b + B^{-1} \Delta b

x_B' = \begin{pmatrix} 10 \\ 30 \end{pmatrix} + \begin{pmatrix} 0.5 & -0.5 \\ -0.5 & 1 \end{pmatrix} \begin{pmatrix} 10 \\ 0 \end{pmatrix} = \begin{pmatrix} 10 \\ 30 \end{pmatrix} + \begin{pmatrix} 5 \\ -5 \end{pmatrix} = \begin{pmatrix} 15 \\ 25 \end{pmatrix}

计算结果：

新的生产计划：桌子 $x_1 = 15$ 张，椅子 $x_2 = 25$ 把。
因为两个数都大等于 0，方案依然可行。
新利润： $15 \times 50 + 25 \times 30 = 1500$ 元（比原来增加了 100元）。
决策依据：利润增加了 100 元，平均每公斤木材增值 $100 / 10 = 10$ 元（这正是木材的影子价格）。既然供应商开价 8 元/公斤，低于 10 元，果断购买。

场景 3. 开发新产品（豪华木柜），利润 100 元，消耗 12 公斤木材 + 4 个工时，要生产吗？

这属于引入新变量 $x_{\text{new}}$ 。其在约束条件中的系数列为 $P_{\text{new}} = \begin{pmatrix} 12 \\ 4 \end{pmatrix}$ ，利润 $c_{\text{new}} = 100$ 。

我们需要计算新产品的检验数（在极大化问题中，若检验数 $z_{\text{new}} - c_{\text{new}} \ge 0$ ，则不值得生产）： $z_{\text{new}} - c_{\text{new}} = w \cdot P_{\text{new}} - c_{\text{new}}$

其中 $w = (10, 5)$ 是我们在最终表中得到的影子价格向量。 $z_{\text{new}} - c_{\text{new}} = (10, 5) \begin{pmatrix} 12 \\ 4 \end{pmatrix} - 100 = (120 + 20) - 100 = 140 - 100 = 40$

计算结果：

检验数为 +40。
因为检验数大于 0（在我们的标准中，由于生产它带来的消耗折合 140元，大于其自身的利润 100元），如果强行生产它，每生产一个木柜会导致总利润下降 40元。
实际结论：不生产木柜。

Ch 02. 线性规划的基本性质#

2.1 标准形式及图解法#

2.2 线性规划基本性质#

1. 可行域几何性质#

2. 最优解极点定理（定理2.2.2）#

3. 基本解、基本可行解（BFS）定义#

4. 极点与基本可行解等价定理（定理2.2.3，重中之重）#

5. 基本可行解存在定理（定理2.2.4）#

Ch 03. 单纯形方法#

3.1 单纯形方法原理#

例子#

单纯形表法#

3.2 两阶段法 & 大 M 法#

3.3 退化与循环#

3.4 修正单纯形法#

3.5 变量有界单纯形#

3.6 分解算法#

Ch 04. 对偶原理及灵敏度分析#

线性规划对偶理论#

1. 对偶形式构造规则#

2. 三大对偶定理#

对偶单纯形法#

例题#

灵敏度分析#

1. 核心概念：影子价格（Shadow Price）#

2. 常考扰动的应对策略#

例子#

支持与分享

目录