原始单纯形法

玻尔百科

核心要点

原始单纯形法通过在一个可行区域的相邻顶点之间系统性地移动，来寻找线性规划的最优解。
它使用一种名为单纯形表的代数工具来引导其搜索过程，利用检验数寻找改进方向，并通过最小比值检验来保持可行性。
诸如两阶段法之类的专门程序用于寻找初始可行解，而像 Bland 规则这样的反循环规则可防止算法陷入循环。
除了找到解之外，该算法还通过对偶变量（影子价格）提供了宝贵的经济学见解，并为更高级的整数规划求解器提供支持。

引言

线性规划是现代最优化的基石，它为在约束条件下做出最佳决策提供了一个数学框架。从工厂生产到投资组合，其应用极为广泛。但是，人们应如何在这片复杂的可能解的图景中导航，以找到唯一的最佳解呢？原始单纯形法，一种经典而强大的算法，给出了答案。它提供了一个保证找到最优解的系统性程序，但其内部工作原理通常看起来像一个黑箱。

本文旨在揭开单纯形法的神秘面纱，将抽象的代数转化为直观的概念。我们将探讨驱动该算法的基本逻辑，阐述它如何高效地搜索解并处理实践中出现的复杂情况。通过两个全面的章节，您将对这一重要的最优化工具有深入的理解。“原理与机制”一章将分解算法的几何与代数基础，从顶点跳跃到单纯形表的运作机制。随后，“应用与跨学科联系”一章将揭示该方法深远的影响，展示其在经济分析、计算机科学中的作用，以及作为解决更困难问题的引擎。

原理与机制

最优化的几何学：行走于顶点之间

想象你是一位登山者，但身处一个奇特的晶体世界。你的目标是在一颗巨大的、多面的宝石上找到最高点。这颗宝石，数学家称之为多胞体（polytope），代表了你优化问题的所有可能解——即可行域。它可能是一个简单的立方体、一个金字塔，或者一个在数百个维度中令人眼花缭乱的复杂物体，就像在一个思想实验中探索的八面体一样。

线性规划中一个优美而强大的真理是：最优解，也就是你正在寻找的那个顶峰，绝不会在一个平坦的面或一条边上。它总是在一个尖锐的角上，即一个顶点。这极大地简化了你的搜索。你不需要检查晶体内部的每一个点；你只需要检查那些角点。

原始单纯形法就是一种巧妙的搜索策略。它是一种系统地攀登这颗宝石的方法。你从一个顶点开始，观察与它相连的边。如果任何一条边指向上方，你就沿着它走到下一个顶点。你重复这个过程——从一个顶点移动到相邻的、更高的顶点——直到你到达一个所有路径都指向下方的角落。那时，你就知道你正站在顶峰。你已经找到了最优解。在八面体问题中，算法所描绘的旅程，仅用一步就从顶点 $(0,0,1)$ 移动到最优顶点 $(1,0,0)$ ，正是这一过程的完美而简洁的图景。

算法的仪表盘：用单纯形表导航

当宝石有成千上万个维度时，算法如何进行这种攀登呢？它无法直接“看到”几何形状。取而代之的是，它使用一个名为单纯形表（simplex tableau）或字典（dictionary）的代数仪表盘。这个表是我们当前位置的快照，提供了决定下一步行动所需的所有信息。它告诉我们我们正处于哪个顶点，该点是否是顶峰，如果不是，该走哪条边才能爬得更高。

指南针：检验数与改进的气息

在任何一个顶点，一些变量是“活跃的”（它们具有正值），这些被称为基变量。其余的变量则处于零值状态，被称为非基变量。非基变量代表了从我们当前顶点延伸出去的边。我们如何知道哪条边是向上的呢？

答案在于一组关键的数字，称为检验数（reduced costs）。对于一个最大化问题，一个非基变量的检验数精确地告诉你，沿着那条边每移动一个单位，目标函数将增加多少。一个正的检验数是指向“上坡”的路标。一个负的检验数则指向“下坡”。检验数为零意味着沿着那条边移动不会改变你的高度，至少一开始不会。

因此，最优性条件很简单：如果你在一个顶点，并且所有非基变量的检验数都为零或负数，那么你就到达了顶峰。没有上坡路可走。你已经找到了最优解。

考虑一个有趣的案例：两个不同的变量，比如 $x_1$ 和 $x_2$ ，对约束条件有完全相同的影响（它们在约束矩阵中的列向量相同）。然而，它们在目标函数中的值可能不同，或许 $x_1$ 提供 $c_1=5$ 的收益，而 $x_2$ 提供 $c_2=7$ 的收益。从算法的当前位置来看，使用任一变量的“成本”（就消耗的资源而言）是相同的。然而，检验数的计算公式 $\bar{c}_j = c_j - y^{\top} A_j$ 将揭示 $x_2$ 更可取。由于 $y^{\top} A_j$ 这一项对两者是相同的，更高的原始系数 $c_2$ 直接导致了更高的检验数。单纯形法通过检查检验数，智能地辨别出，尽管两个变量在多胞体的约束上“行走”的是同一条路径，但 $x_2$ 为目标函数提供了更陡峭的攀升。

选择路径：定价规则与一个警示故事

如果有多条边都指向上坡（即有多个正的检验数），我们应该选择哪一条呢？这就是定价规则（pricing rule）要回答的问题。

一种自然且常见的策略，被称为Dantzig 规则，是选择看起来最陡峭的边：即具有最大正检验数的那条边。这种贪心方法看起来很合理，而且通常效果很好。

然而，最优化的世界里隐藏着一个微妙的陷阱。局部最陡峭的路径并不总是全局旅程的最佳选择。臭名昭著的 Klee-Minty 立方体是一个专门构建用来欺骗 Dantzig 规则的多胞体。在攀登这个形状时，局部最陡峭的路径会引导算法在一系列指数级数量的顶点上曲折行进，最后才到达顶峰，而那个顶峰通常从另一个方向走只需一步之遥。更复杂的定价规则，如最陡边规则（steepest-edge rule），不仅考虑目标函数的变化率 ( $\bar{c}_j$ )，还通过在变量空间中行进的“距离”（ $\|p_j\|_2$ ）对其进行归一化。这可能使得每一步的计算成本更高，但正如在 Klee-Minty 立方体上的演示，它可以找到一条通往最优解的更直接的路径，从而大大减少枢轴变换的总次数。这给我们一个深刻的教训：最显而易见的策略并不总是最高效的。

道路的尽头：最小比值检验

一旦我们选择了一条要行进的边（即进基变量），我们不能永远走下去。我们必须保持在宝石上。随着我们增加进基变量的值，当前基变量的值将会改变。为了保持可行性，所有变量都必须保持非负。

单纯形表为我们提供了每个基变量如何变化的确切公式。对于进基变量 $x_E$ 和基变量 $x_{B_i}$ ，更新公式为 $x_{B_i}^{\text{new}} = x_{B_i}^{\text{old}} - \alpha \cdot d_i$ ，其中 $\alpha$ 是我们行进的距离，而 $d_i$ 是来自单纯形表的一个系数。如果 $d_i$ 是正的，增加 $\alpha$ 将会减少 $x_{B_i}$ 。我们必须在第一个基变量达到零时立即停止。否则就会“掉下”晶体，进入不可行区域。

这个计算过程被称为最小比值检验（minimum ratio test）。对于每个正在减少的基变量（ $d_i > 0$ ），我们计算使其变为零的比值： $\frac{x_{B_i}^{\text{old}}}{d_i}$ 。这些比值中的最小值 $\alpha^{\star}$ ，就是我们能行进的最大距离。

决定这个极限的基变量就是“阻挡”我们路径的那个变量。它离开基变量集合（在零值处变为非基变量），而进基变量则取代它在基中的位置。这次枢轴变换操作对应于到达下一个顶点。一个假设性的问题表明，当右端向量恰好是进基变量列向量的整数倍时，所有基变量会在同一时刻被驱动到零。这导致出基变量的选择出现平局，我们接下来会讨论这种情况。

当路径出现分岔：特殊情况

从一个顶点到另一个顶点的简单攀登可能会遇到奇特的地形。这些特殊情况不仅仅是理论上的奇闻；它们揭示了优化图景更深层次的属性。

无界的远方

如果我们选择了一个进基变量（一个上坡方向），但在检查其在单纯形表中的列时，发现所有系数都为零或负数，会发生什么？这意味着当我们增加这个变量时，当前没有一个基变量会减少。实际上，有些甚至可能会增加！这里没有边界，没有变量来阻挡我们的路径。我们找到了一个可以永远行进的方向，目标函数随之无限增加。问题是无界的。算法可以停止并报告没有有限的最优解。我们的“宝石”在至少一个方向上无限延伸。

陷入困境：退化与循环

有时，最小比值检验给出的步长为 $\alpha^{\star} = 0$ 。这发生在一个或多个基变量已经为零的情况下。这种情况被称为退化（degeneracy）。枢轴变换仍然可以发生——我们可以将一个值为0的基变量与一个值为0的非基变量交换——但我们并没有物理移动。我们停留在同一个顶点，只是改变了对它的代数描述。

退化不仅是一个不便之处；它为一种称为循环（cycling）的病态行为打开了大门。理论上，算法可能会执行一系列这样的零步长枢轴变换，一次又一次地改变其代数基，结果发现自己回到了一个之前见过的基，陷入了一个无限循环，而目标函数却从未得到改善。

虽然循环在实际问题中极为罕见，但其理论上的可能性是一个严重的缺陷。为了防止这种情况，数学家们开发了反循环规则（anti-cycling rules）。其中最著名的是 Bland 规则，它提供了一个简单、确定性的打破僵局的程序：在选择哪个变量进基或出基时，总是选择索引最小的那个。这个看似随意的规则在数学上被证明可以防止循环，确保单纯形算法在解存在的情况下总能找到一个。

寻找起点：两阶段法

我们整个旅程都假设我们能找到一个起始顶点。但是，如果最初那个显而易见的解（将决策变量设为零）并不可行呢？例如，一个约束可能是 $x_1 + x_2 \ge 4$ 的形式。设 $x_1=0, x_2=0$ 违反了这个约束。我们从哪里开始呢？

这就是两阶段法（two-phase method）来拯救我们的地方。这是一个用于寻找起始顶点的系统性程序。

在第一阶段（Phase I），我们暂时忘记我们真正的目标函数。我们为每个需要的约束引入“辅助”变量，称为人工变量（artificial variables），从而创建一个简单（但人为的）起始基。第一阶段的目标是一个新的、临时的优化问题：最小化这些人工变量的总和。

然后我们对这个新问题运行单纯形法。有两种可能的结果：

该总和的最小值为零。这意味着我们成功地将所有人工变量都赶出了基。它们不再被需要。现在的基由原始变量和松弛变量组成，我们已经找到了原始问题可行域的一个真实顶点。我们现在可以进入第二阶段（Phase II）：从这个有效的起点解决原始问题。
该总和的最小值大于零。这意味着不可能去掉所有的人工变量。这是一个深刻的结果：它证明了原始问题的可行域是空的。根本没有解，更不用说最优解了。问题是不可行的（infeasible）。

硬币的两面：对偶性与对偶单纯形法

最优中最优雅的概念之一是对偶性（duality）。每个线性规划问题，我们称之为原始（primal）问题，都有一个与之对应的影子问题，称为对偶（dual）问题。两者密不可分。对偶问题的变量对应于原始问题的约束，而其约束对应于原始问题的变量。

这种关系不仅仅是数学上的奇特性；它具有实际的力量。有时，一个问题的初始字典不是原始可行的（某些变量为负），但却是对偶可行的（对于最大化问题，所有检验数都为非正）。这种状态是对偶单纯形法（dual simplex method）的完美起点。

对偶单纯形法不是选择一个进基变量来改善目标函数，而是首先选择一个出基变量——即某个为负值的基变量，它违反了原始可行性。然后，它对目标函数行应用一个比值检验来选择一个进基变量，这个进基变量将把不可行的变量推回非负，同时保持解的对偶可行性（即最优性）。这就像从可行域外部导航，采取步骤以变得可行，同时始终保持最优性。

这个故事最美的部分在于它所揭示的对称性。在原始问题的单纯形表上执行一次对偶单纯形法的枢轴变换，与在对偶问题的单纯形表上执行一次标准的（原始）单纯形枢轴变换是完全等价的。原始问题的出基变量对应于对偶问题的进基变量，而原始问题的进基变量则对应于对偶问题的出基变量。它们是对同一次移动的两种不同视角。这种统一性展示了最优化的深层内在结构，将一系列算法和规则变成一个单一、连贯而优美的理论。

应用与跨学科联系

我们花了一些时间来拆解原始单纯形法的内部机制，观察它的齿轮和杠杆——基、枢轴变换、检验数——如何协同工作，系统地向最优解迈进。它是一台优美的数学机器。但一台机器的好坏取决于它能做什么。现在，我们将踏上一段旅程，去看看这个引擎如何工作。我们会在一些意料之中的地方发现它，但也会在一些非常令人惊讶的地方。你会看到，单纯形法的逻辑并非某种深奥、孤立的数学知识；它是一种基本的“选择演算”，自然界和人类的创造力已经一次又一次地发现了它。

分配的艺术：从食谱到数据包

线性规划的核心是关于稀缺资源的分配。经典的“食谱问题”或许是最直观的例子：你如何以尽可能低的成本满足所有日常营养需求（维生素、蛋白质等）？在这里，单纯形法的每一次枢轴变换都有一个非常具体的解释。当算法决定将“西兰花”引入基并将“菠菜”移出基时，它实际上是在决定，在边际上，往菜单里增加一些西兰花并减少一些菠菜是在保持健康的同时降低餐费的最有效方式。算法不仅仅是在处理数字；它在做出权衡，就像一个精明的购物者一样。

你可能会想：“这是一个不错的玩具问题，但现代世界呢？”好吧，让我们把杂货店换成电脑。中央处理器（CPU）有一种稀缺资源：时间。在任何给定时刻，它必须在许多具有不同优先级的竞争任务之间分配其处理时间。这是同一个问题！我们正在最小化的“成本”（或最大化的“利润”）是任务优先级的度量。而“营养物质”则是 CPU 时间片的份额。一次单纯形枢轴变换，它将一个变量与另一个变量在基中交换，与操作系统抢占一个低优先级任务以运行一个新到达的高优先级任务是直接对应的。优化你餐盘的同样基本逻辑，也优化了你电脑内部信息的流动。

价值的语言：影子价格与“如果-那么”情景分析

这里是单纯形法展现其魔力的地方。当它找到最优解时，它给你的不仅仅是答案。隐藏在其最终状态中，即对偶变量的值里，是一个全新的经济学洞察层面。

想象你正在经营一家工厂，你的产量受限于你拥有的钢材数量。你已经使用单纯形法找到了最赚钱的生产计划。现在你问：“如果我能多得到一吨钢材，我能多赚多少利润？”单纯形法已经计算出了答案。这个值被称为与钢材约束相关联的影子价格（shadow price），或对偶变量。它告诉你每种资源的边际价值。你现在确切地知道，你应该愿意为那额外的一吨钢材支付多少钱。这不是估计；这是问题结构直接导致的结果，由算法免费揭示。

这个由对偶变量构成的“影子世界”也赋予了算法惊人的灵活性。假设你已经找到了最优生产计划，但突然一项新的政府法规施加了额外的限制。你整个计划都毁了吗？你必须从头开始求解吗？不。通常，这个新约束会使你的旧解变得不可行，但影子价格（即对偶解）仍然完全有效。这是一个兄弟算法——对偶单纯形法——的完美起点，它可以用几次枢轴变换高效地修复解。它展示了如何智能地适应一个变化的世界，诊断新计划是否可能，或者新规则是否使你的目标变得不可行。

作为中坚力量的单纯形法：驱动更复杂的机器

在现代科学和工程中，单纯形法的真正力量通常是作为更大、更复杂的算法结构内部一个不知疲倦、可靠的引擎。世界上许多最棘手的问题——比如航空公司排班、配送卡车路线规划，或设计通信网络——都涉及整数约束（你不能飞0.7架飞机）。这些整数规划问题比我们一直在研究的线性规划问题要困难得多。

解决这些问题的一个常用策略叫做分支定界法（Branch-and-Bound）。它智能地将问题分解成一棵由更简单的线性规划问题组成的树。求解器可能会探索成千上万甚至数百万个这样的子问题。如果每个子问题都必须从头解决，这将是不可思议的缓慢。但诀窍在于：树中的每个子问题都只与其父问题略有不同，通常只是对一个变量增加了一个新的界限。父问题的最优基虽然不再完美，但对于子问题来说是一个极好的起点。这种技术称为热启动（warm start），它允许单纯形法仅用少数几次枢轴变换就能找到新的解，而不是数百次。这在计算上相当于有一个良好的开端，也正是它使得解决庞大的整数规划问题变得切实可行。

在另一个优美的例子，即切割下料问题（cutting-stock problem）中，我们想找出如何切割大卷的纸张或钢材以满足对较小尺寸零件的订单，同时最小化浪费。可能的切割模式数量是天文数字——大到甚至无法列出。解决方案是一种被称为列生成（column generation）的优雅舞蹈。我们从一个只使用少数几种基本模式的简化“主问题”开始求解。单纯形法解决这个主问题，并通过其对偶变量提供价格信号。这些信号随后被传递给一个“子问题”，其任务是找到一个主问题忽略了的、全新的、高价值的切割模式。这个新模式作为一个新列被添加到主问题中，然后重新求解。单纯形法扮演着总指挥的角色，利用其对偶变量在一个过于庞大而无法直接探索的问题空间中引导寻找创造性的新解。

意想不到的近亲：与数据科学及其他领域的联系

线性规划的结构出现在一些非常意想不到的地方，尤其是在现代数据科学和机器学习领域。

考虑将模型拟合到数据的任务，例如在图像重建中。我们希望找到一组像素强度 $x$ ，使得变换后的版本 $Ax$ 与我们的测量值 $b$ 相匹配。一种稳健的方法是最小化绝对误差之和，即 $||Ax - b||_1$ 。事实证明，这个问题可以完美地重构为一个线性规划问题，并用单纯形法求解。该算法不仅仅是运筹学的一个工具；它还是数据分析的一个基本工具。

此外，单纯形法不仅仅是一个吐出答案的黑箱。它是一个强大的诊断工具。如果你错误地构建了你的问题——例如，由于建模错误导致目标函数可以永远减少——单纯形法会检测到它。它有一个内置的标准，使其能够举手投降并说：“这个问题是无界的！目标可以被驱动到负无穷。”它不只是失败；它告诉你为什么失败，这在开发复杂模型时是一个非常宝贵的特性。

也许最深刻的联系在于，将单纯形枢轴规则视为贪心优化的一种普遍原则。在信号处理中，一种用于寻找方程组稀疏解的流行算法是正交匹配追踪（OMP）。在每一步，OMP 贪婪地选择与当前残差最相关的特征。这似乎与线性规划相去甚远。但如果你将底层问题表述为一个带非负约束的优化问题，一些非凡的事情发生了。OMP 的选择规则——选择具有最大绝对相关性 $|a_j^\top r|$ 的特征——在数学上等价于单纯形法选择具有最负检验数的变量的规则。线性规划中的“检验数”和信号处理中的“与残差的相关性”是同一种语言的两种方言：边际改进的语言。它们都衡量了激活一个新变量所能获得的“性价比”。这种统一性揭示了关于优化本质的一个深刻而美丽的真理。

一个适用于新时代的古老算法

从其在战后物流中的起源开始，单纯形法已经成长为一个通用工具。它决定了你吃什么，你的电脑如何运行，以及货物如何在全球范围内运输。它为解决远为更复杂的问题的求解器提供动力，并为拟合数据和理解资源价值提供了数学语言。而且，它并非陈旧之物。今天，研究人员正在重新设计单纯形算法，使其能够在如图形处理器（GPU）等大规模并行硬件上运行，利用复杂的数值技术以前所未有的速度解决具有数百万变量和约束的问题。

单纯形法的历程证明了一个优美思想的持久力量。它向我们展示，通过理解一个枢轴变换的简单、局部逻辑——即在每一步都做出最佳权衡——我们便可以解决极其复杂的全局性问题。