1.单纯形算法 (Simplex Algorithm)

1.1 引言：朴素解法的局限性

在线形规划问题中，我们有如下推论：

可行域 (Feasible Region, Ω): 在几何上，满足约束条件 Ax = b 和 x ≥ 0 的所有解 x 构成的空间是一个凸多面体 (Convex Polyhedron)。你可以把它想象成一个高维度的、由平坦表面围成的几何体。
顶点 (Vertex): 就是这个凸多面体的“角点”。
为何最优解在顶点上?
- 目标函数 c^T x 是线性的。在一个凸多面体内，如果你从一个顶点沿着一条边移动到另一个顶点，目标函数的值要么是线性增加，要么是线性减少，要么保持不变。
- 因此，目标函数的最大值或最小值（最优值）不可能出现在多面体的“内部”或“边”的中间，它必然会出现在空间的“尽头”，也就是顶点上。（也可能出现在一条边或一个面上，但这种情况下，该边或面上的所有顶点也都是最优解）。

我们可以用朴素的算法：

基 (Basis, B): 从 n 个变量中选取 m 个变量，这 m 个变量组成的集合 B 称为一组基。对应的变量称为基变量 (basic variables)，剩下的 n-m 个变量称为非基变量 (non-basic variables)。
步骤 1: set x_j = 0 for j ∉ B: 将所有非基变量的值设为0 。在几何上，n 维空间中的一个 x_j = 0 方程定义了一个 n-1 维的超平面。当我们将 n-m 个非基变量设为0时，相当于用 n-m 个超平面去切割，它们的交点就是我们要求的潜在“角点”。
步骤 2: Compute x_B = A_B^(-1)b: 剩下的 m 个基变量的值由 m 个线性方程 A_B * x_B = b 唯一确定。A_B 是由矩阵 A 中对应基变量的列向量组成的 m x m 矩阵。
步骤 3: If x ≥ 0: 这一步是可行性检验 。我们通过代数方法算出的这个解，必须满足x ≥ 0 的约束，才能算是可行域内的一个点，也就是一个真正的顶点。这个满足条件的解被称为基可行解 (Basic Feasible Solution, BFS)。在代数上，一个基可行解就对应几何上的一个顶点。
步骤 4: 比较并返回最低值: 对所有找到的基可行解（顶点），计算其目标函数值，然后选出最好的那个。

1.2 单纯形算法的核心思想

单纯形算法 (Simplex Algorithm) 核心是一种沿着可行域多面体的顶点进行迭代搜索的策略。
算法必须从可行域的一个角点启动。如何找到这第一个顶点本身就是一个问题，后文会讲到的“两阶段法”就是为了解决这个启动问题。
Pivot (枢轴/主元变换): 这是单纯形算法的核心操作。它在代数上指将一个非基变量与一个基变量进行互换；在几何上，这个操作就对应着从当前顶点沿着一条边移动到另一个相邻的顶点。
对于我们寻求最小值的LP问题，算法在选择移动方向（即选择哪条边）时，总会选择一个能让目标函数值减小或保持不变的方向。这保证了算法总是在向着“更好”的解前进，不会走回头路。
"local optimum is also a global optimum" (局部最优即是全局最优)。因为可行域是一个凸集（凸多面体），且目标函数是线性的（也是一种凸函数）。在一个凸优化问题中，任何一个局部最优解都必然是全局最优解。

1.3 算法的数学步骤

1.3.1 关键前提 (Key Prerequisites)

标准型 (Standard Form): 线性规划的标准形式是 min c^T x，约束为 Ax = b, x ≥ 0 。这是单纯形算法操作的对象。
A has full row rank (A矩阵行满秩): 这是一个重要的技术假设。
- 补充知识: “行满秩”意味着矩阵 A 的 m 个行向量是线性无关的。通俗地说，就是约束方程 Ax = b 中没有冗余的方程（比如某个方程可以由其他方程线性组合而成），也没有相互矛盾的方程。这个假设保证了方程组“不多不少”，是我们能从中选出 m 个线性无关的列向量组成可逆矩阵 A_B 的基础。
BFS (基可行解): PPT假设我们已经处在一个BFS上。这就是我们之前讨论的顶点。

1.3.2 变量与矩阵的划分：核心代数操作

单纯形法的精髓在于，它在 n 个变量中，总是有 m 个“主角”和 n-m 个“配角”。

基 B (Basis) 和 非基 N (Non-basis):
- B: 一个包含 m 个变量索引的集合，这些变量被称为基变量 (basic variables, x_B) 。你可以理解为，它们是当前用来“支撑”起解的核心变量。
- N: 剩下 n-m 个变量的索引集合，被称为非基变量 (non-basic variables, x_N) 。它们在当前这个解中被“固定”住了。
矩阵划分:
- 根据变量的划分，约束矩阵A 和变量向量 x 也相应地被拆分为两部分。
- A_B: 由矩阵 A 中，与基变量 x_B 对应的列向量组成的一个 m x m 的方阵。
- A_N: 由与非基变量 x_N 对应的列向量组成的 m x (n-m) 矩阵。
- 这样，约束方程 Ax = b 就可以被重写为 A_B * x_B + A_N * x_N = b。这个改写是后续所有推导的基础。

1.3.3 基可行解 (BFS) 的严格定义

PPT的最后部分给出了一个BFS必须满足的代数条件，这非常关键：

x_N = 0
- 解释: 在任何一个BFS（顶点）上，所有的非基变量的值必须为0。这是“基解”的定义。从几何上看，这相当于我们处于 n-m 个约束边界超平面的交点上。
x_B = A_B^(-1)b
- 解释: 当 x_N = 0 时，上面的方程 A_B * x_B + A_N * x_N = b 就简化为了 A_B * x_B = b。要解出 x_B，就需要 A_B 是一个可逆矩阵 (这也是选择基B的要求)，两边左乘 A_B 的逆矩阵 A_B^(-1)，就得到了 x_B 的唯一解。
x_B ≥ 0
- 解释: 这是“可行” (Feasible) 的体现。我们算出的基变量 x_B 必须全部大于等于0，才能满足 x ≥ 0 的约束。如果算出的 x_B 中有负数，那么这个解虽然是一个“基解”，但不是“基可行解”，它位于可行域之外。

我们现在知道了如何描述一个顶点 (BFS)。
单纯形算法的“移动”，即“Pivot (枢轴)”操作，在代数上就体现为：
1. 从非基变量 x_N 中选择一个变量，让它的值从0开始增加（这个变量将要“入基”）。
2. 为了保持 Ax=b 约束仍然成立，基变量 x_B 的值必然会相应地发生改变。
3. 当这个入基变量增加到某个临界点时，某一个原来的基变量的值会恰好减小到0。
4. 这个值变为0的基变量就“出基”，成为新的非基变量。
这样一次“一进一出”的操作，就完成了一次从当前BFS到相邻BFS的移动。

1.4 推导出方向向量 $v_j$ 的计算公式。

$v_j$ 这个向量描述了：当我们选择将一个值为0的非基变量 $x_j$ 提升一个微小量 $α$ 时，为了继续满足等式约束 $Ax=b$，原来的那组基变量 $x_B$ 必须做出怎样的线性调整。最终结论是，这个调整方向向量 $v_j$ 可以通过公式 $v_j = A_B^{-1}A_j$ 计算得出。

1.4.1 目标：移动到相邻顶点

几何上，从一个顶点移动到相邻顶点。
代数上，这意味着一个非基变量（值=0）要“入基”（值>0），同时必然有一个基变量要“出基”（值变为0）。这一页主要关注“入基”的瞬间会发生什么。

具体操作:

选择一个非基变量 $x_j$ (其中$ j ∈ N$)，让它的值从 0 增加到 $α$ ($α > 0$) 。
保持其他非基变量不动，它们的值仍然是 0 。这保证了我们是沿着多面体的一条“边”在移动，而不是斜穿一个“面”。
保持可行性：移动后的新解 $x_{new}$ 必须仍然满足等式约束 $Ax_{new} = b$ 。这就迫使基变量 $x_B$ 必须进行相应的调整。

1.4.2 推导：如何计算这种调整

假设调整形式: 假设基变量 $x_B$ 的调整是与 $α$ 成正比的，所以把新的基变量写成 ${x_B}^{new} = x_B - αv_j$ 。这里的 $v_j$ 就是我们要求的未知“方向向量”或“比率向量”。

数学推导如下：

我们将新的解

$x_{new}$ 代入约束 $Ax_{new} = b$ 。利用上一页PPT的矩阵分块形式，这个等式可以写作： $$A_Bx_B^\mathrm{new}+A_jx_j^\mathrm{new}=b$$ 代入 ${x_B}^{new}$ 和 $x_j^\mathrm{new}$ 的表达式： $$A_B(x_B-\alpha v_j)+A_j(\alpha)=b$$ 展开并整理： $$A_Bx_B-\alpha A_Bv_j+\alpha A_j=b$$ 关键简化: 因为我们出发的点是一个基可行解 (BFS)，所以它本身就满足 $A_B x_B = b$。所以上式中的 $A_B x_B$ 和 $b$ 可以相互抵消。 $$b-\alpha A_Bv_j+\alpha A_j=b$$ $$-\alpha A_Bv_j+\alpha A_j=0$$ 求解 $v_j$: $$\alpha A_Bv_j=\alpha A_j$$ 两边消去 $α$ (因为 $α > 0$)，再同时左乘 $A_B$ 的逆矩阵 $A_B^{-1}$ ，我们就得到了最终的公式： $$v_j=A_B^{-1}A_j$$

$v_j$ 的含义是什么？

$v_j$ 可以被理解为替换率 (Substitution Rate) 或 权衡向量 (Trade-off Vector)。
它的每一个分量 $v_{ij}$ (其中 $i ∈ B$) 表示：当非基变量 $x_j$ 增加1个单位时，基变量 $x_i$ 必须减少 $v_{ij}$ 个单位，才能维持等式 $Ax=b$ 的平衡。
举例: 假设 $x_B = (x_1, x_2)$，我们想让非基变量 x_3 入基。如果我们算出来 v_3 = (2, -0.5)^T，这就意味着：
- x_3 每增加 α，x_1 就必须减少 2α。
- x_3 每增加 α，x_2 就必须减少 -0.5α，也就是增加 0.5α。

1.5 判别数 (Reduced Costs, $\bar{c}_j$)

1.5.1 判断数定义

当我们把一个非基变量 $x_j$ 的值从0增加到 $α$ 时，目标函数值会如何变化。这个变化率就是判别数 $\bar{c}_j$。因此，$\bar{c}_j$成为了我们选择哪个变量入基（即决定移动方向）的判断标准：

如果决定增加非基变量 $x_j$，那么基变量 $x_B$ 应该如何变化 ($x_B \rightarrow x_B - \alpha v_j$) 才能保持 $Ax=b$ 约束。现在，我们要回答一个更重要的问题：我们应该选择增加哪个 $x_j$ 呢？ 答案是，选择那个能让目标函数 $c^T x$ 减小得最快的。

核心推导过程如下：

写出新目标函数值: 新的解是 $x_{new}$，新的目标函数值就是 $c^T x_{new}$。
展开计算: $$c^Tx^{\mathrm{new}}=c_B^Tx_B^{\mathrm{new}}+c_jx_j^{\mathrm{new}}$$
代入 ${x_B}^{new} = x_B - \alpha v_j$ 和 ${x_j}^{new} = \alpha$： $$c^Tx^{\mathrm{new}}=c_B^T(x_B-\alpha v_j)+c_j\alpha$$
分离出变化量: $$c^Tx^{\mathrm{new}}=c_B^Tx_B-\alpha c_B^Tv_j+\alpha c_j$$ 整理后得到： $$c^Tx^{\mathrm{new}}=\underbrace{c_B^Tx_B}{=\text{旧的目标函数值}}+\alpha(\underbrace{c_j-c_B^Tv_j}{\text{变化率}})$$
定义判别数 (Reduced Cost): 我们将这个“变化率”$c_j - c_B^T v_j$ 定义为一个新符号 $\bar{c}_j$。代入上一页的结论 $v_j = A_B^{-1}A_j$，就得到了判别数的完整计算公式： $$\overline{c}_j=c_j-c_B^TA_B^{-1}A_j$$ 这个公式告诉我们，新目标函数值 = 旧目标函数值 + $\alpha\cdot\overline{c}_j$。

另外，由数学推导可知，任何基变量的判别数恒为零。

1.5.2 单纯形法的两个核心判断

根据判别数的含义，我们得到了算法的两个核心规则：

最优性检验 (Optimality Condition) - Case 1: 如果对于所有非基变量，其判别数 $\bar{c}_j$ 都大于等于0，意味着无论引入哪个非基变量，都无法再降低总成本了。因此，当前解就是最优解，算法停止。
入基变量选择 (Entering Variable Selection) - Case 2: 如果存在一个或多个 $\bar{c}_j$<0，说明当前解还有优化的空间。我们需要从中选择一个变量入基。
- 选择规则: 理论上，任何一个 $\bar{c}_j$<0 的变量都可以入基。常见的选择策略有：
  - 一般规则: “选择第一个判别数为负的 j” (这在实现上最简单)。
  - Dantzig原始规则: 选择值最小的 $\bar{c}_j$ (即最负的)，这被称为“最贪心”的策略，因为它使得目标函数在单位步内的下降率最大。

我们已经解决了往哪个方向走的问题（选择 $j$）。
但还没解决能走多远的问题（确定 $α$）。$α$ 不能无限增大，因为增大的过程中，某个基变量 $x_i$ 可能会减小到0。一旦有基变量小于0，解就变得不可行了。因此，下一步就是要计算 $α$ 的最大允许值。这就是“最小比率测试”要解决的问题。

1.6 最小比率测试

在已经确定了入基变量 $x_j$ (因为其判别数 $\bar{c}_j$<0) 的前提下，有两种可能性。

我们从上一节知道，当非基变量 $x_j$ 增加 $α$ 时：

基变量会更新为： $$x_B^\mathrm{new}=x_B-\alpha v_j$$ 目标函数会更新为： $$c^\top x^{\mathrm{new}}=c^\top x+\alpha\overline{c}_j$$ 其中$\overline{c}_j<0$。

1.6.1 情况一：问题无界 (Unbounded Solution)

条件: $v_j≤0$ 。这意味着向量$v_j$ 的所有分量 $v_{ij}$ 都是非正数。
分析:
- 观察基变量的更新公式 $x_i^\mathrm{new}=x_i-\alpha v_{ij}$。
- 因为 $α > 0$，$x_i ≥ 0$ (当前解是可行的)，而 $v_{ij} ≤ 0$，所以 -$αv_{ij}$ 必然大于等于0。
- 这意味着，无论 $α$ 增加到多大，新的基变量 $x_i^{new}$ 的值只可能增加或保持不变，永远不会变成负数。
- 同时，非基变量 $x_j$ 也在增加。所以，新的解 $x_{new}$ 永远满足非负约束。
结论: 我们可以让 $α$ 无限制地趋向于无穷大 $α → ∞$ 。由于$\bar{c}_j<0$，目标函数 $c^\top x+\alpha\overline{c}_j$ 将趋向于负无穷 $-∞$ 。
补充知识 (几何与现实意义):
- 几何上: 这对应于可行域多面体有一条“边”是无限延伸的，并且沿着这条边移动，目标函数值会持续下降。
- 现实中: 这通常意味着你的数学模型有误，缺少了某些关键的限制条件。例如，一个生产模型如果只考虑利润而没考虑原材料、工时或市场需求的上限，就可能得出可以无限生产、赚取无限利润的荒谬结论。

1.6.2 情况二：执行最小比率测试 (Minimum Ratio Test)

条件: $v_j$ 中至少存在一个正分量 $v_{ij}>0$ 。
分析:
- 对于那些 $v_{ij}>0$ 的基变量 $i$，更新公式 $x_i^\mathrm{new}=x_i-\alpha v_{ij}$ 表明，$x_i^{new}$ 的值会随着 $α$ 的增大而减小。
- 为了保证新解的可行性，我们必须满足 $x_i^{new}≥0$，即 $x_i−αv_{ij}≥0$。
- 移项可得，对每一个i (其中 $v_ij>0$)，$α$ 都有一个上限：$α≤x_i/v_{ij}$ 。
确定最终步长 $α$:
- 我们希望 $α$ 尽可能大，因为这样目标函数的下降量才最大。
- 但是，我们必须同时遵守所有这些上限约束。因此，我们只能选择那个最严格的、最小的上限作为最终的步长 $α$。
- 这就是最小比率测试的由来： $$i^*=\arg\min_{i\in B:v_{ij}>0}{x_i/v_{ij}}$$ 这个公式就是在寻找哪个基变量 $i$ 会“最先”被 $α$ 减到0 。

确定出基变量:

找到的这个$i^∗$ 所对应的基变量 $x_i^∗$，就是即将要离开基的变量。当$α$ 取到最大值时，它的新值 $x_{i^∗}^{new}$ 将恰好为0，成为新的非基变量。

至此，一次完整的迭代（枢轴变换）就完成了：

通过判别数 $c_j$ 找到了入基变量 $j$。
通过最小比率测试找到了出基变量 $i^*$。

接下来，我们就可以更新基 $B$ 为 $B_{new} = (B - {i^*}) ∪ {j}$ ，然后进入下一轮迭代。

1.7 总结

我们可以把这个算法流程想象成一个“寻宝机器人”在一个多面体上的寻路过程。

算法循环 (Repeat)

第1步：给定一个基可行解 (BFS)

机器人状态：机器人正站在多面体的一个顶点上。
解释: 这是每一次循环的起点。我们手上必须有一个合法的基 $B$，它对应一个所有变量值都非负的解。

第2步：计算判别数 $\bar{c}_j$，寻找第一个为负的 $j$

机器人动作：机器人扫描所有与当前顶点相连的、且通往“更低处”的路径。
- 最优性检验: 如果所有的判别数 $\bar{c}_j$ 都大于等于 0，说明没有通往更低处的路径了，机器人已经到达“谷底”，当前位置就是最优解。算法结束并返回结果。
- 选择入基变量: 如果存在为负的判别数，就选择一个。我们可以选择的规则是“Find the first j” 。
- 补充知识 (选择规则): 这个“选择第一个”的规则，是布兰德规则 (Bland's Rule) 的一部分，它的优点是实现简单且能有效避免算法“循环”（后续会讲到）。更常见的“贪心”规则是选择值最小（最负）的那个 $\bar{c}_j$，这通常能让目标函数下降得更快。

第3步：计算方向 $v_j$ 并确定出基变量 $i^*$

机器人动作：在选定路径后，计算出沿着这条路走，会撞上哪一个“边界”，从而确定下一个要停留的顶点。
解释:
- 首先检查这条路径是否无限长。如果$v_j≤0$，说明路径无限延伸且一直向下，宝藏在无穷远处。算法停止，报告问题无界 (unbounded)。
- 如果路径有限，就通过最小比率测试 $i^*=\arg\min{x_i/v_{ij}}$ 找到那个“最先到达的边界” 。这个边界对应的基变量$x_i^∗$ 就是要离开基的变量。
- 补充知识 (平局打破规则): “if there are multiple choices of i*, choose the smallest one” 。如果有多个基变量同时到达边界（即最小比率相同），就选择变量下标最小的那个。这是布兰德规则 (Bland's Rule) 的另一半，同样是为了防止算法“循环”。

第4步：更新基集合 $B$

机器人动作：机器人移动到新的顶点。
解释: 这是执行“枢轴变换 (Pivot)”的最后一步。将旧的出基变量 $i^*$ 从基集合 $B$ 中移除，并把新的入基变量 $j$ 加入，形成新的基 $B_{new}$ 。然后带着这个新的基，返回第1步，开始新一轮的迭代。

1.7.1 算法性质 (Property)

保持BFS身份不变: 这是单纯形法能够成功的基石。
为什么能保持？ 最小比率测试保证了：
1. 出基变量$x_i^∗$ 的新值恰好为0，符合非基变量的定义。
2. 所有其他的基变量的新值仍然大于等于0。
因此，每一步操作都保证了我们是从一个合法的顶点，不多不少，正好移动到了另一个合法的顶点上，整个过程都在可行域的边界上进行，绝不会“跑偏”。

2.单纯形表 (Simplex Tableau)

2.1 动机 (Motivation)

我们已经学过的单纯形枢轴变换 (Pivot) 的步骤：

增加 (Add): 将一个非基变量 $j$ 加入基 $B$ 。
移除 (Remove): 将一个基变量 $i^*$ 从基 $B$ 中移除。
更新 (Update): 形成新的基 $A_{B^{new}}$ 。
求解 (Solve): 计算新的基解 $x_B^{new} = A_{B^{new}}^{-1} \mathbf{b}$ 。

我们需要在每一次迭代中求解一个线性方程组，这是个问题

求解 $x_B^{new} = A_{B^{new}}^{-1} \mathbf{b}$，在计算上等同于两步：
1. 求 m x m 矩阵 $A_{B^{new}}$ 的逆矩阵。
2. 用这个逆矩阵乘以向量 $b$。
补充知识 (计算复杂度): 对于一个 m x m 的矩阵，求逆是一个计算量相当大的操作，其时间复杂度通常在 $O(m^3)$级别。单纯形法可能需要进行很多次迭代，如果每次迭代都“从零开始”去求一次矩阵的逆，总的计算成本会非常高，尤其是在 $m$（约束数量）很大的现实问题中。

实际上，我们可以利用相邻两次迭代之间的内在联系。

1: 新的基 $B^{new}$ 和旧的基 $B$ 非常相似。它们之间仅仅相差一个入基变量和一个出基变量。
2: 这意味着新的矩阵 $A_{B^{new}}$ 和旧的矩阵 $A_B$ 也非常相似——它们仅仅相差一个列向量。
补充知识 (矩阵的秩一更新): 在线性代数中，替换矩阵的一列，可以被看作是一种“秩一更新 (Rank-one update)”。对于这类更新，存在着比完全重新求逆快得多的方法来计算新的逆矩阵。例如，Sherman-Morrison公式就描述了如何基于 $A^{-1}$ 快速计算 $(A + uv^\top)^{-1}$ 的逆。单纯形表中的“主元消去法” (Pivoting) 正是这种高效更新思想的一个程序化实现。
结论: 我们不必在每次迭代时都丢弃所有信息然后重算。我们可以利用上一步已经计算出的信息（比如与 $A_B^{-1}$ 相关的信息），通过一次高效的“增量更新”，廉价地得到下一步所需的信息（与 $A_{B^{\text{new}}}^{-1}$ 相关的信息）。

2.2 单纯形表的构建

2.2.1 形式变换

![[Pasted image 20250909200403.png]]

以把这个推导过程看作是“解构与重组”一个线性规划问题

第1步：从标准型到分块形式 (左上 → 右上)

操作: 这个变换只是把变量和矩阵进行了“分组”。它将所有 $n$ 个变量 $x$ 分为 $m$ 个基变量 $x_B$ 和 $n-m$ 个非基变量 $x_N$ 。相应地，成本向量 $c$ 和约束矩阵 $A$ 也被分成了对应的两块。
目的: 这一步在数学上没有做任何改变，只是为了在公式中明确区分基变量和非基变量的角色，为后续操作做准备。
- 原始约束 $Ax = b$ 被重写为 $A_Bx_B+A_Nx_N=\mathbf{b}$

第2步：用非基变量表示基变量 (右上 → 左下)

操作: 这一步是关键的代数变换。它从约束方程 $A_Bx_B+A_Nx_N=\mathbf{b}$ 出发，解出了基变量 $x_B$：
1. 移项: $A_Bx_B=\mathbf{b}-A_Nx_N$
2. 两边左乘 $A_B$ 的逆矩阵 $A_B^{−1}$ (我们知道 $A_B$ 是可逆的): $x_B=A_B^{-1}\mathbf{b}-A_B^{-1}A_Nx_N$

目的与补充:

这个新的约束形式$x_B=A_B^{-1}\mathbf{b}-A_B^{-1}A_Nx_N$ 非常有用。
它直接告诉我们当前基可行解 (BFS) 的值：因为在 BFS 中，所有非基变量 $x_N=0$，所以代入上式，立刻得到 $x_B=A_B^{−1}b$。
它也告诉我们移动的方向：如果我们让某个非基变量 $x_j$ 从0开始增加，基变量 $x_B$ 将会如何变化。这个变化的比率就藏在矩阵 $A_B^{-1}A_N$ 中，所以实际上 $A_B^{-1}A_N$ 就代表了方向向量 $v_j$。

第3步：用非基变量表示目标函数 (左下 → 右下)

操作: 这是最核心的一步。我们希望把目标函数也改写成只用非基变量 $x_N$ 来表达。最下方的紫色框展示了这个代换过程。
1. 原始目标函数为 $c_B^\top x_B+c_N^\top x_N$。
2. 将第2步中得到的 $x_B$ 的表达式 $x_B=A_B^{-1}\mathbf{b}-A_B^{-1}A_Nx_N$ 代入。
3. 整理后，目标函数变为$$\min(\mathbf{c}_N^\top-\mathbf{c}_B^\top A_B^{-1}A_N)\mathbf{x}_N+\mathbf{c}_B^\top A_B^{-1}\mathbf{b}$$

目的与补充 (这是最重要的部分): 这个最终形式的目标函数由两部分组成：

第一部分: $(\mathbf{c}_N^\top-\mathbf{c}_B^\top A_B^{-1}A_N)\mathbf{x}_N$ 。
- 括号里的行向量 $(\mathbf{c}_N^\top-\mathbf{c}_B^\top A_B^{-1}A_N)$ 正是所有非基变量的判别数（Reduced Costs）组成的向量
- 这意味着，在这个新的表达式中，每个非基变量 $x_j$ 前面的系数，直接就是它的判别数 $c̄_j$。
第二部分: $\mathbf{c}_B^\top A_B^{-1}\mathbf{b}$ 。
- 这是一个常数项，它不随 $x_N$ 的变化而变化。
- 这个常数的值，正是当前基可行解 (BFS) 所对应的目标函数值（因为此时 $x_N=0$）。

经过这一系列变换，我们得到一个与原始问题完全等价的新问题。在这个新问题中：

当前状态一目了然: 常数项是当前的目标函数值，约束方程给出了当前的基变量值。
下一步决策极其简单: 只需查看目标函数中非基变量 $x_N$ 的系数（即判别数），如果有负数，就说明还有优化空间，可以直接拿来用。

2.3 使用单纯形表进行迭代

2.3.1 原理

我们将上述成果组织成一个表格

	$x_B$ (基变量)	$x_N$ (非基变量)	$SOL$ (解)
$Basis$ (约束行)	$I$ (单位矩阵)	$A_B^{-1} A_N$	$A_B^{-1} b$
0 (目标行)	0	$c_N^T - c_B^T A_B^{-1} A_N$	$-c_B^T A_B^{-1} b$

约束行 (Top Part):

这一部分代表了变换后的约束方程：$I\mathbf{x}_B+(A_B^{-1}A_N)\mathbf{x}_N=A_B^{-1}\mathbf{b}$
$I$ (单位矩阵): 表明基变量 $x_B$ 已经被解出，是“干净”的。
$A_B^{-1} A_N$: 补充: 这个矩阵块至关重要，它的每一列就是我们之前讨论过的方向向量 $v_j$
$A_B^{-1} b$: 补充: 这一列是当前解的值，即 $x_B$ 的值。
目标行 (Bottom Part):
- 这一部分代表了变换后的目标函数。
- 0: 对应基变量 $x_B$ 的系数，基变量的判别数为0。
- $c_N^T - c_B^T A_B^{-1} A_N$: 补充: 这部分就是所有非基变量的判别数 $c̄_j$ 组成的行向量。
- $-c_B^T A_B^{-1} b$: 这是当前目标函数值的负数。

为什么目标函数值是负的？

推导:

我们知道变换后的目标函数是：$z=(\mathbf{c}_N^\top-\mathbf{c}_B^\top A_B^{-1}A_N)\mathbf{x}_N+\mathbf{c}_B^\top A_B^{-1}\mathbf{b}$
在当前基可行解 (BFS) 中，$x_N = 0$ ，所以当前目标函数值是 $z_{\mathrm{current}}=\mathbf{c}{B}^{\top}A{B}^{-1}\mathbf{b}$。
为了把目标函数也写成一个形如 $... = 0$ 的等式，方便用矩阵处理，我们可以把它改写成：$(\mathbf{c}_N^\top-\mathbf{c}_B^\top A_B^{-1}A_N)\mathbf{x}N-(z-z{\mathrm{current}})=0$。
单纯形表约定 $z$ 的系数为1（通常省略不写），并且把常数项（即当前的目标函数值）移到等式右边。这样目标行就代表了方程：$(\mathbf{c}_N^\top-\mathbf{c}_B^\top A_B^{-1}A_N)\mathbf{x}N+z=z\mathrm{current}$如果我们把所有变量（包括 $z$）都放在左边，常数放在右边，就得到了表格最后一行的形式。表格中的 $-c_B^T A_B^{-1} b$ 就是把当前目标函数值移项到方程另一侧的结果（根据不同教科书的约定，符号可能变化，但原理相同）。

结论: 整个单纯形表，可以看作是下面这个方程组的系数矩阵： $$\begin{cases}\mathbf{x}_B+(A_B^{-1}A_N)\mathbf{x}_N=A_B^{-1}\mathbf{b}\(\mathbf{c}_N^\top-\mathbf{c}_B^\top A_B^{-1}A_N)\mathbf{x}_N=-\mathbf{c}_B^\top A_B^{-1}\mathbf{b}&\end{cases}$$

将问题表格化后，之前复杂的操作就变得非常直观和机械化：

判断最优？ 只需检查目标行的非基变量部分，看是否有负数。
选入基变量？ 选择目标行中负数对应的列。
选出基变量？ 用“解”列 ($SOL$) 除以“入基列”的正数，找最小的比率，比率最小的那一行对应的基变量出局。
更新迭代？ 以入基列和出基行的交叉点为主元，进行一次高斯-若尔当消元（行变换），就能得到下一张全新的、信息完备的单纯形表。

这个过程完全避免了矩阵求逆，将 $O(m^3)$ 的复杂操作，降级为一系列 $O(m⋅n)$ 的行变换，计算效率大大提高。

2.3.2 使用单纯形表

这张PPT通过三个“Recall”清晰地建立了这种对应关系：

目标行 = 判别数 $c̄_j$
- 作用: 这是算法的“决策中心”或“仪表盘”。我们通过检查这一行中非基变量对应的数值，来判断当前解是否最优。如果存在负数，我们就根据它来选择哪个变量入基 (enter the basis) 。
约束行主体 = 方向向量 $v_j$
- 作用: 当我们从目标行确定了入基变量 $j$ 后，我们就在表格的主体部分找到对应的第 $j$ 列。这一列就是方向向量 $v_j$ 。它告诉我们，当 $x_j$ 增加1个单位时，各个基变量会如何变化。
解列 (SOL) = 当前基解 $x_B$
- 作用: 这一列显示了当前各个基变量的值。它和我们选定的方向向量 $v_j$ 列一起，用于执行最小比率测试，以确定哪个变量出基 (leave the basis) 。

我们可以把所有知识串起来，形成一个清晰的操作流程：

读取表格，做出决策 (Steps ①, ②, ③)

当你拿到一个单纯形表时，首先要检查目标行（最后一行）中非基变量所对应的数值（即判别数 $c̄_j$）。

IF (情况一): 所有 $c̄_j$ 都 ≥ 0
- 决策: 算法停止，已经找到了最优解。
- 如何读取答案:
  - 最优解: 基变量的值就是 $SOL$ 列对应的数值，所有非基变量的值为0 。
  - 最优目标函数值: $-c_B^T A_B^{-1} b$ 单元格中的值的相反数 。
ELSE IF (情况二): 存在某个 $c̄_j < 0$，且该 $j$ 列中所有元素都 ≤ 0
- 决策: 算法停止，问题是无界的，最优目标值为负无穷。
- 解释: $c̄_j < 0$ 告诉我们增加 $x_j$ 是有利的。而 $j$ 列（即 $v_j$ 向量）所有元素非正，意味着增加 $x_j$ 不会导致任何一个基变量减少。因此，我们可以无限增加 $x_j$ ，目标函数值也会无限减小。
ELSE (情况三): 存在 $c̄_j < 0$ ，且该 $j$ 列中至少有一个正数
- 决策: 需要继续迭代。
- 操作:
  1. 确定主元列 (Pivot Column): 选择一个 $c̄_j < 0$ 的列 $j$ 作为主元列（该列变量为入基变量）。
  2. 确定主元行 (Pivot Row): 对主元列中的每一个正数 $v_{i,j}$ ，计算比率 $x_i / v_{i,j}$（其中 $x_i$ 是该行 SOL 列的值）。比率最小的那一行 $i^*$ 就是主元行（该行变量为出基变量）。
  3. 确定主元 (Pivot Element): 主元列 $j$ 和主元行 $i^$ 的交叉点 $v_{i,j}$ 就是主元。

核心操作：高斯-若尔当交换 (Pivoting) (Step ④)

这是更新表格的机械化操作，目的是让新的入基变量 $x_j$ 成为一个的“基变量”。

目标: 将主元列变换成一个单位向量（主元位置为1，其他位置为0）。
具体步骤 (补充):
1. 主元行归一化: 将主元行的所有元素，都除以主元 $v_{i^*,j}$。这样操作后，主元位置的值就变成了1。
2. 主元列清零: 对于表格中的所有其他行（包括目标行），用该行减去某个倍数的“新主元行”（上一步操作后的主元行）。这个“倍数”就是该行主元列上原来的数值。这样操作后，主元列上除了主元位置为1外，其他所有元素都会变成0。
操作的意义:
- 这个看似简单的行变换，其背后是在进行所有必要的代数运算。它等价于完成了基的替换，并自动计算出了新基下的解、新的判别数、以及新的方向向量。
- 操作完成后，你会得到一个全新的单纯形表。新的基变量$x_j$ 对应的列变成了单位向量，而旧的出基变量 $x_{i*}$ 对应的列不再是单位向量。整个表格的结构（基变量列构成单位矩阵，基变量的判别数为0）被保持了下来，可以直接用于下一轮的决策。

2.3.3 技巧

当我们的基矩阵 $A_B$ 恰好是单位矩阵 $I$ 时，构建单纯形表的过程将得到极大的简化。在这种特殊但非常常见的情况下，我们无需进行任何矩阵求逆运算，可以直接将原始问题矩阵 $A$ 的非基部分 $A_N$ 和向量 $b$ 直接复制到表格中。同时，计算初始判别数 $c̄_j$ 的公式也变得更简单，只需一次点积和一次减法。

考虑一个典型的不等式约束问题，例如 $Ax ≤ b$ (且 $b ≥ 0$)。
当我们为了将其转换为标准型 $Ax = b$ 而引入松弛变量 (slack variables) 时，每个松弛变量在 $A$ 矩阵中增加的一列都恰好是一个单位向量（只有一个1，其余是0）。
如果我们选择所有这些松弛变量作为我们的初始基 (initial basis)，那么它们所对应的基矩阵 $A_B$ 就自然而然地构成了一个完美的单位矩阵 $I$。

因此，这个“特殊情况”实际上是单纯形法最常用、最自然的“冷启动”方式。

当 $A_B = I$ 时，它的逆矩阵 $A_B^{-1}$ 也等于 $I$。这个性质让之前复杂的单纯形表公式瞬间变得简单：

通用公式: $A_B^{-1} A_N$ 变为 $I * A_N = A_N$，$A_B^{-1} b$ 变为 $I * b = b$
判别数公式: $$\overline{c}_j=c_j-c_B^\top A_B^{-1}A_j\text{ 变为 }\overline{c}_j=c_j-c_B^\top A_j$$

基于以上简化，构建初始单纯形表的步骤如下：

填写约束行:
- 在基变量 $x_B$ 列下方，填入单位矩阵 $I$。
- 在非基变量$x_N$ 列下方，直接抄写原始矩阵 $A$ 中对应的非基部分 $A_N$ 。
- 在 SOL 列，直接抄写原始的 $b$ 向量。
填写目标行:

在基变量 $x_B$ 列下方，填入 0。
在非基变量 $x_N$ 列下方，逐个计算判别数 $\overline{c}_j=c_j-c_B^\top A_j$ 。
- 最简情况 (补充): 在很多问题中，初始基变量是成本为0的松弛变量，所以 $c_B$ 是一个全零向量。此时，$c_B^T A_j$ 恒为0，初始的判别数就直接等于原始成本 $c̄_j = c_j$ 。
在 SOL 列，填入 $-c_B^Tb$ 。

3.特殊情况处理

3.1 两阶段法 (Two-Phase Method)

解决单纯形算法的一个关键前提是：如何找到一个初始的基可行解 (BFS)？

两阶段法的核心思想是：

第一阶段 (Phase 1): 先忽略原始的目标函数，构造一个辅助问题 (auxiliary problem)。这个辅助问题的唯一目标就是“想尽一切办法找到一个原始问题的可行解”。
如果第一阶段成功找到了一个可行解，我们再进入第二阶段 (Phase 2)，从这个找到的解出发，回头去优化我们真正关心的原始目标函数。

我们之前遇到的“简单”问题，通常是所有约束都是 ≤ 类型，且右端项 $b$ 都非负。在这种情况下，我们引入的松弛变量自然地构成了一个初始基，对应的基矩阵是单位矩阵 $I$，初始解 $x=0$ ，松弛变量 $=b$ 就是一个完美的BFS。

补充知识: 但在以下“困难”情况中，初始BFS并不明显：

含有 ≥ 约束: 例如 $x_1 + x_2 ≥ 5$ 。标准化后变为 $x_1 + x_2 - s_1 = 5$ ( $s_1$ 是剩余变量)。如果我们令 $x_1=x_2=0$ ，会得到 $s_1=-5$ ，这不满足非负约束，不是一个可行的初始解。
含有 = 约束: 例如 $x_1 + x_2 = 5$。这里根本没有松弛或剩余变量可以作为初始的基变量。

在这些情况下，我们就无法像之前一样轻松地“启动”单纯形算法。

第一阶段详解：只寻找可行解

第一阶段的目标：不计成本，只为找到一个满足 $Ax=b, x≥0$ 的解。

核心技巧：引入人工变量 (Artificial Variables)
- 我们在原约束中引入一组全新的、临时的变量$y$，构建新的约束：$Ax + y = b$ 。
- 这些 $y$ 变量就像是“脚手架”或“辅助轮”。它们的作用是让我们可以构造一个极其简单的初始BFS。
构造辅助问题
- 新的目标: 我们的目标是尽快拆掉这些“脚手架”，所以新的目标函数是最小化所有人工变量的和，即 $min 1^Ty$ (也就是 $min Σy_i$ ) 。
- 新的约束: $Ax + y = b$ , 且 $x, y ≥ 0$ 。
绝妙的起点
- 对于这个全新的、更大的辅助问题，我们有了一个显而易见的初始BFS：令原始变量 $x=0$ ，人工变量 $y=b$ 。
- 此时，基变量就是所有 $y$ 变量，它们对应的基矩阵 $A_B$ 就是一个单位矩阵 $I$
- 注意: 为了保证 $y=b$ 是一个可行的解 ( $y≥0$ )，我们需要确保 $b$ 的所有分量都是非负的。如果原始问题中某个约束的 $b_i$ < 0 ，我们需要先将该约束方程两边同乘以-1 。
执行与结果解读
- 现在我们有了一个完美的起点，可以直接对这个辅助问题运行我们已经学过的单纯形算法。
- 算法结束后，检查最优目标值（也就是 $Σy_i$ 的最小值）：
  - 如果最小值为 0: 这意味着所有人工变量 $y$ 都成功地被降为了0 。此时，剩下的 $x$ 变量的值就构成了一个满足 $Ax=b, x≥0$ 的解。第一阶段成功 我们找到了原始问题的一个可行解。
  - 如果最小值大于 0: 这说明我们无论如何努力，都无法将作为“脚手架”的人工变量完全拆除。这意味着原始约束 $Ax=b$ 本身就是矛盾的（在 $x≥0$ 的前提下）。第一阶段失败！ 这证明了原始问题无解 (infeasible) 。

所以，第一阶段不仅能帮我们找到初始BFS，还能顺便检验原始问题是否有解。

3.2 退化情况 (Degenerate Case)

当一个基可行解(BFS)中，至少有一个基变量的值为0时，就称这个解是退化的。

退化通常源于在进行最小比率测试时，有多行同时获得了最小值，出现了“平局”。

后果:

良性退化: 算法可能会经过一个退化解，但依然能正常前进并找到最优解。
零步长迭代: 算法可能在同一个顶点上进行一次或多次“原地踏步”的迭代。虽然基变了，但解向量 $x$ 和目标函数值都没有任何改善。
循环 (Cycling): 这是最坏的情况。算法陷入一个无限循环，不断地重复一系列的基变换，但永远停留在同一个点上，导致算法无法终止。

尽管在实际应用中，由于浮点数计算误差等原因，真正的“循环”现象极其罕见，但这个案例的存在说明了为一个算法设计终止性保障机制的重要性。为了让单纯形法成为一个在任何情况下都可靠的算法，必须引入一套反循环规则 (Anti-Cycling Rules)

3.2.1 布兰德规则 (Bland's rule)

布兰德规则 (Bland's rule)，这是一套简单而强大的枢轴选择规则，其唯一目的是防止单纯形法在退化问题中发生循环 (cycling)。

该规则包含两个部分，都遵循“最小下标优先”的原则：

入基规则: 当有多个判别数为负的变量时，选择下标 j 最小的那个变量入基。
出基规则: 当最小比率测试出现平局时，选择下标 i 最小的那个变量出基。

只要严格遵守布兰德规则，单纯形法就从数学上保证了总能在有限步内终止，从而完美地解决了循环问题。

Class 2 - Simplex Method

beautifulremi

1.单纯形算法 (Simplex Algorithm)

1.1 引言：朴素解法的局限性

1.2 单纯形算法的核心思想

1.3 算法的数学步骤

1.3.1 关键前提 (Key Prerequisites)

1.3.2 变量与矩阵的划分：核心代数操作

1.3.3 基可行解 (BFS) 的严格定义

1.4 推导出方向向量 $v_j$ 的计算公式。

1.4.1 目标：移动到相邻顶点

1.4.2 推导：如何计算这种调整

1.5 判别数 (Reduced Costs, $\bar{c}_j$)

1.5.1 判断数定义

1.5.2 单纯形法的两个核心判断

1.6 最小比率测试

1.6.1 情况一：问题无界 (Unbounded Solution)

1.6.2 情况二：执行最小比率测试 (Minimum Ratio Test)

1.7 总结

1.7.1 算法性质 (Property)

2.单纯形表 (Simplex Tableau)

2.1 动机 (Motivation)

2.2 单纯形表的构建

2.2.1 形式变换

第1步：从标准型到分块形式 (左上 → 右上)

第2步：用非基变量表示基变量 (右上 → 左下)

第3步：用非基变量表示目标函数 (左下 → 右下)

2.3 使用单纯形表进行迭代

2.3.1 原理

2.3.2 使用单纯形表

2.3.3 技巧

3.特殊情况处理

3.1 两阶段法 (Two-Phase Method)

第一阶段详解：只寻找可行解

3.2 退化情况 (Degenerate Case)

3.2.1 布兰德规则 (Bland's rule)

1.单纯形算法 (Simplex Algorithm)

1.1 引言：朴素解法的局限性

1.2 单纯形算法的核心思想

1.3 算法的数学步骤

1.3.1 关键前提 (Key Prerequisites)

1.3.2 变量与矩阵的划分：核心代数操作

1.3.3 基可行解 (BFS) 的严格定义

1.4 推导出方向向量 $v_j$ 的计算公式。

1.4.1 目标：移动到相邻顶点

1.4.2 推导：如何计算这种调整

1.5 判别数 (Reduced Costs, $\bar{c}_j$​)

1.5.1 判断数定义

1.5.2 单纯形法的两个核心判断

1.6 最小比率测试

1.6.1 情况一：问题无界 (Unbounded Solution)

1.6.2 情况二：执行最小比率测试 (Minimum Ratio Test)

1.7 总结

1.7.1 算法性质 (Property)

2.单纯形表 (Simplex Tableau)

2.1 动机 (Motivation)

2.2 单纯形表的构建

2.2.1 形式变换

第1步：从标准型到分块形式 (左上 → 右上)

第2步：用非基变量表示基变量 (右上 → 左下)

第3步：用非基变量表示目标函数 (左下 → 右下)

2.3 使用单纯形表进行迭代

2.3.1 原理

2.3.2 使用单纯形表

2.3.3 技巧

3.特殊情况处理

3.1 两阶段法 (Two-Phase Method)

第一阶段详解：只寻找可行解

3.2 退化情况 (Degenerate Case)

3.2.1 布兰德规则 (Bland's rule)

1.5 判别数 (Reduced Costs, $\bar{c}_j$)