单纯形法是求解线性规划问题的一类算法,即在线性等式和不等式约束下优化线性目标函数。乔治·B. 丹齐格于1947年提出了这一方法,此后它成为运筹学和计算数学优化的基础工具。其核心操作是换基,也称为枢轴操作,即用一组因变量替换另一组因变量。从几何上看,非退化的枢轴操作通常对应于在可行多面体的相邻顶点之间移动。
该方法将候选解的有限代数描述与用于判断解能否改进、是否最优以及问题是否无界的检验相结合。尽管某些枢轴规则在专门构造的问题上需要指数级次数的迭代,但经过精心设计的实现对许多实际模型都非常有效。原始单纯形法、对偶单纯形法及各种专用变体,在生产计划、运输、调度和整数优化中仍然发挥着重要作用。它们的性能不仅取决于枢轴规则,还取决于稀疏线性代数运算、数值容差、预处理,以及复用先前计算得到的基的能力。
历史发展与适用范围
乔治·B·丹齐格于1947年在为美国空军研究规划问题时提出了单纯形法。这类问题需要在相互竞争的活动之间分配有限资源,而各项活动的资源需求和贡献都可以用线性关系表示。此前的研究,包括列昂尼德·康托罗维奇1939年关于生产计划的研究,已经识别出若干重要的线性资源分配问题。丹齐格给出了一套通用的计算程序,能够系统地处理大量约束和变量,使线性规划不再只是一种数学表述,而成为一种可实际运用的方法。
单纯形法的出现,恰逢电子计算机和经济资源配置数学理论的发展。它与博弈论的联系,尤其是与约翰·冯·诺依曼相关工作的联系,有助于确立线性规划对偶理论的重要地位。对偶理论表明,优化程序的输出不仅可以包括一项资源分配方案,还可以包括一套与之相匹配的界或价格体系,用以证明该方案的最优性。丹齐格于1963年出版的《线性规划及其扩展》成为系统阐述这一学科及其应用的重要著作。
早期的介绍通常借助单纯形表来讲解这种方法:这是一种矩形表格,其中包含经过变换的约束系数、右端项以及目标函数信息。随后便可通过初等行变换完成一次枢轴操作。随着问题规模增大,存储和更新整张单纯形表变得效率低下。修正单纯形法则改为维护基的表示,并计算每次迭代所需的量。后续的发展包括对偶单纯形法、改进的定价策略、稀疏基矩阵分解,以及对变量上下界的有效处理。这些改进没有改变换基这一基本原理,却大幅提升了可处理问题的规模。
“单纯形”一词指的是一种几何对象,即单纯形,但线性规划的可行域本身不一定是单纯形。它可以具有任意多个面和顶点,也可以是无界的。该算法也不同于1965年提出、用于无导数非线性优化的内尔德—米德单纯形法。内尔德—米德法通过移动一组构成单纯形的点并改变其形状来进行搜索;线性规划中的单纯形法则对约束矩阵的基进行操作。名称相同,并不意味着二者具有共同的最优性理论或计算机制。
标准形式与基本解的几何性质
原始单纯形法的一种便于处理的表述形式为
其中, 是一个 矩阵,,。上标 表示转置。目标函数是线性的,可行集是仿射空间与非负约束所定义区域的交集。因此,它是一个凸集,更具体地说,是一个多面体。不等式约束可以通过引入松弛变量或剩余变量转化为等式;无符号限制的变量则可以表示为两个非负变量之差。
假设去除冗余方程后, 的行秩为 ,即具有满行秩。从 中选取 个线性无关的列,构成非奇异方阵 。与这些列对应的变量称为基本变量,其余变量称为非基本变量。将非基本变量设为零后,由方程组可得
这就是一个基本解。若 ,它就是一个基本可行解。这里的基是在代数意义上使用的:选出的列构成约束矩阵列空间的一组基。同一个可行点可能对应多个基。
对于标准形式的可行集,基本可行解恰好就是其极点,也称顶点。若一个点不能表示为两个不同可行点的非平凡凸组合,则称其为极点。在基本解处,将足够多的坐标设为零后,等式约束便足以唯一确定其余坐标。如果全部 个基本变量都严格为正,该基本可行解就是非退化的。如果其中一个或多个为零,则称其为退化的,此时多个不同的基可能表示同一个顶点。
线性规划的一个核心定理指出:如果标准形式的问题可行,且其目标函数有下界,那么就存在最优基本可行解。因此,尽管可行集通常包含无穷多个点,搜索仍可限制在有限多个基之中。单纯形法并不按固定顺序枚举所有基,而是利用目标函数的信息来引导基之间的转换。对这一几何图景需要谨慎理解:退化可能使换基不伴随点的位置变化;而对于未施加标准形式非负约束的一般线性规划,在进行适当的重新表述之前,其可行集可能根本没有顶点。
约化成本与原始单纯形换基
对于当前基,将约束和目标函数按基变量与非基变量分块写为
消去基变量,得到
非基变量 的约化成本为
其中, 是 的第 列。约化成本衡量的是:在调整基变量以保持等式成立的情况下, 每增加一个单位所引起的目标值变化。对于最小化问题,约化成本为负的变量可以作为有望改进目标值的入基变量。
令 入基,并计算 。将 从零增大到 ,基变量就变为 。保持非负性的充要条件是:对每个满足 的分量,都有 。因此,最大可行步长为
达到这一最小比值的某个基变量出基。算法将 中该变量对应的列替换为 ,从而得到下一个基。目标值的变化量为 ;当 且 时,该变化量严格为负。这就是最小比值检验。
由此可以直接得到两个重要的终止判据。如果所有非基变量的约化成本都非负,则当前可行解就是最优解:上面给出的目标函数表达式表明,任何可行的非负 都只能使目标值增大或保持不变。如果某个约化成本为负的列对所有 都满足 ,那么就没有基变量会限制相应非基变量的增大。由此得到的可行射线使目标值无限下降,从而证明问题无界。得出这两种结论都不需要逐一检查所有可行解。
从能够改进目标值的列中选择入基列,称为定价。对于最小化问题,丹齐格最初提出的规则是选择约化成本最负的列。最陡边定价并不只依据约化成本,而是结合相应可行方向的长度来估计目标值的改进程度。Devex 定价以较低的计算代价近似计算相关权重。部分定价只考察部分列,而不是在每次迭代时重新计算所有约化成本。这些策略可以显著影响迭代次数和计算工作量。预测的改进幅度很大,并不意味着实际就能实现,因为比值检验可能只允许很短的步长,在退化顶点处甚至可能只允许零步长。
计算实例
考虑如下生产模型:
约束条件为
其中, 和 表示生产活动水平,第一个不等式限制共用资源的用量,另外两个不等式分别限制各自的产能。引入非负松弛变量 ,并将最大化问题改为最小化 。约束条件变为
松弛变量对应的列构成一个单位矩阵,因此可以直接得到一个可行的初始基:、、,且 。
和 的初始检验数分别为 和 。按照选择最负检验数的规则, 首先入基。它的变换列为 ,因此需要比较的比值为 和 。最小值为 ,所以 出基。新的点满足 、、、、。原最大化问题的目标值从 上升到 。第一次换基使 达到自身的产能上限,而不是耗尽共用资源。
新的方程组可写为
最小化问题的目标函数为
因此, 的检验数为 ,接下来由它入基。在 时,增大 会使 从 开始减小,使 从 开始减小,所以当 时, 首先降至零。得到的解为 、,原问题的目标值为 。从几何上看,算法沿着可行多边形的边,从 移动到 ,再移动到 。
在最终的基中,非基变量为 和 ,代入可得
两个检验数均为正,因此任何可行点处的最小化目标函数值都不可能低于 。等价地,任何可行生产方案的收益都不可能超过 。将原来的三个不等式分别乘以 、 和 ,即可得到相应的资源价格证书:将它们相加,得到 。这一证书说明,最终单纯形基的代数关系也能从对偶角度解释解的最优性。
寻找初始可行基
当所有约束均具有 的形式,且所有 、 时,很容易得到初始可行基。为每个不等式添加一个松弛变量,就能得到一个由单位矩阵构成的基,各基变量的值即为相应的右端项。等式约束、下界型不等式以及负的右端项通常会使这种简单构造不再适用。由于原始单纯形法以可行性为前提,因此不能随意选取一组构成非奇异矩阵的列就开始迭代。必须另行执行初始化过程,要么找出一个可行基,要么证明原约束系统不相容。
标准的两阶段法会引入人工变量。必要时将相应行乘以 后,可设 。辅助问题可写为
取人工变量 ,同时令 ,即可得到初始可行基。第一阶段使用单纯形法,使人工变量之和最小化。由于每个人工变量都非负,辅助问题的最优值为零就意味着它们可以全部取零,从而得到原问题的一个可行点。如果最优值严格大于零,则证明原约束系统无可行解。
第一阶段成功结束时,某些人工变量可能仍是基变量,但取值为零。在第二阶段中,不能直接保留这些变量,让它们不受限制地替代原变量。只要条件允许,就应通过转轴运算,将每个这样的人工变量替换为原变量或松弛变量。如果变换后的某一行中没有可用于替换的系数,则该行对应一个冗余等式,可以删除。随后恢复原目标函数,并根据保留下来的基重新计算其表达式。第二阶段继续执行常规的改进步骤和最优性检验。这样将两个阶段分开,使寻找可行解与优化各自承担明确而不同的作用。
另一种方法是大 法,即在原目标函数中对人工变量施加极大的惩罚。从符号运算的角度看,一个具有绝对优先级的无限大惩罚可以表达所需的优先顺序,但任意选取的有限数值 可能带来问题:取值过小可能无法保证可行性,取值过大则可能加剧尺度失衡和舍入误差问题。实际求解器还会采用快速初始基构造程序,寻找较有希望的起始基,并通过预处理检测简单的矛盾,例如相互冲突的变量界,或满足 的方程 。如果已经求解过一个相关问题,复用其基可能完全免去重新执行第一阶段的需要。
对偶性、最优性证书与对偶单纯形法
对于标准形式的最小化问题,其对偶问题为
其中 的符号不受限制。对于基 ,定义
于是有 ,且基列的约化成本为零。因此,约化成本非负意味着 是对偶可行解。由此可见,原始单纯形法的最优性检验,实际上是在检查当前基所生成的解是否对偶可行。对于原始可行的基本解,原始问题与对偶问题的目标值相等: 。 再由弱对偶性即可证明其最优性。
这一关系是拉格朗日对偶的一个具体实例。对于任意一对原始可行解和对偶可行解,都有
等号成立当且仅当每个乘积 都为零。这就是互补松弛条件:在最优解处,取正值的原始变量对应的约化成本必须为零,而严格为正的约化成本则要求对应变量为零。单纯形法通过基表示将这些关系明确地呈现出来。对偶乘子还可以在经济学上解释为资源的边际价值,但这种解释必须遵循相应的符号约定,并限于当前基保持有效的范围内。
卡尔顿·莱姆克于1954年提出的对偶单纯形法颠倒了两类可行性的处理优先次序:它在保持对偶可行性的同时,消除原始不可行性。在本文采用的最小化约定下,假设所有约化成本都非负,但某个基本变量值 为负。在字典表示 中,只有当 时,才能通过增大非基本变量来修复选定的不可行行。对偶比值检验从符合条件的变量中选择入基变量,使换基后的约化成本仍保持非负。在一种简单的标准形式版本中,该检验在符合条件的列中选择使 最小的列。
当问题的变动保持约化成本非负,却破坏了原始可行性时,对偶单纯形法尤其有效。改变右端项不会改变固定基所对应的约化成本,但基本变量值可能变为负数。加入一条当前解不满足的不等式,并为其引入松弛变量,同样可以得到一个有用的对偶可行初始基。这对于需要反复强化模型的优化过程十分重要。现代实现将这一基本方案推广到变量同时具有下界和上界的情形,采用上下界翻转、专门的比值检验以及数值保护措施。因此,原始单纯形法与对偶单纯形法是相互补充的方法,而不是对同一换基序列的两种不同描述。
退化、循环与枢轴选择
当一个基本可行解中至少有一个基变量等于零时,这个解就是退化的。在比值检验中,这样的变量可能迫使 。相应的枢轴操作会改变基,却不改变解所对应的点或目标值。这一现象解释了为什么负约化成本并不总能立即带来改善:它表明存在一个代数上有利的方向,但当前基可能不允许沿该方向迈出任何正步长。退化通常源于冗余约束或相互作用紧密的约束、网络结构,以及许多变量同时处于界限上的模型形式。
一连串零步长的枢轴操作可能导致停滞,其间算法遍历许多基,而目标值几乎没有改善,甚至毫无进展。更严重的是,某些枢轴规则可能使算法返回先前访问过的基,并无限重复。这就是循环。由于非退化的改善性枢轴操作会使目标值严格朝有利方向变化,因此在通常的原始单纯形法中,循环必然伴随着退化。所以,仅凭基的集合有限,并不能证明任意枢轴规则都会终止。一个完整的有限步算法需要采用能够防止基重复出现,或以其他方式保证算法取得进展的规则。
罗伯特·布兰德于1977年提出的 布兰德规则,是一种简单且能保证算法在有限步内终止的规则。为每个变量赋予一个固定编号。在符合条件的入基变量中选择编号最小者;若最小比值检验中有多个候选者并列,则选择其中编号最小的基变量出基。在精确算术下,这一规则可以防止循环。字典序枢轴法提供了另一种途径:按某种顺序打破并列,这种排序等价于对右端项施加一系列不同阶的无穷小扰动。扰动将原本重合的事件区分开来,而无须用普通浮点数表示真正的无穷小量。
防循环保证和计算效率是两个不同的问题。布兰德规则未必是实际计算中最快的定价策略,而更激进的定价策略可能需要配备保障措施,以防出现过长的退化枢轴序列。求解器往往结合使用扰动、不同的定价策略以及精心设计的比值检验。对零约化成本也必须谨慎解读。非基变量的约化成本为零,表明存在一个不会立即改变目标值的方向,但只有在能够沿该方向迈出适当的正可行步长时,才会得到一个不同的替代最优解。在退化最优解处,多个最优基可能表示同一个点。反过来,一整条边或一个更高维的面也可能由不同的最优解组成,这反映的是真正的解不唯一,而不仅仅是同一个解具有多种基表示。
修正单纯形法与数值实现
单纯形表法在每次枢轴操作后更新所有经过变换的系数,所用运算与高斯消元法密切相关。这种方法用于小型算例时直观清晰,但在变量数量较多时,计算代价可能很高。修正单纯形法无需维护整张单纯形表,其主要计算任务是求解
以及计算检验数 。这些方程组分别给出基变量的值、对偶乘子和入基方向。记号 在数学表达上很方便,但求解器通常不会显式构造逆矩阵。
实现时采用的是数值线性代数方法,通常使用稀疏形式的LU分解。换基只替换一列,因此更新已有分解往往比重新分解更省计算。乘积形式的逆矩阵更新方法及后来的稀疏更新方案都利用了这一结构。然而,随着更新次数增加,填充和数值误差都可能增大。定期重新分解可以重建更简洁的表示,并恢复计算的可靠性。因此,一次迭代的代价远不只取决于约束和变量的数量:稀疏结构以及不断变化的基都至关重要。
实际实现采用浮点运算,因此可行性和最优性检验需要使用容差,而不是与零进行精确比较。计算得到的基变量值若只是略小于零,可能源于舍入误差;若违反非负性条件的程度较大,则可能表明当前基确实不可行。较小的枢轴元素可能放大数值误差,尤其是在基矩阵的条件数很大时。生产级软件中的比值检验可能允许微小且受控的可行性偏差,以避免不稳定的枢轴选择。对行和列进行缩放、检查残差以及重新计算关键量,都有助于提高数值稳定性,但无法使病态数据下的计算变得精确。
现代求解器还会直接处理有界变量,而不是将每个界限都转换为一个额外的方程。非基变量可以处于下界或上界;检验数的符号判据取决于变量允许朝哪个方向移动。在迭代开始前,预求解可以消去固定变量、收紧界限、通过方程代入消元,并识别冗余约束。求解完成后,后处理会重构原始模型的解。需要数学上的严格认证时,可以通过有理数重构或精确算术检查,验证原始可行性、对偶可行性以及原始与对偶目标值相等。浮点求解器报告的状态是在指定容差下得出的数值结论,而精确的原始—对偶证书则能确立相应的代数结论。
复杂度与几何直觉的局限
可能的基的数量有一个基本上界 ,因为每个基都从 列中选取 列,尽管其中许多选择可能对应奇异矩阵,或不满足可行性条件。一种保证有限终止的枢轴规则,原则上仍可能遍历其中很大一部分。1972 年,维克托·克利和乔治·明蒂构造了一类畸变的立方体,使采用丹齐格枢轴规则某种标准形式的单纯形法沿着一条指数级长度的路径前进。在 维情形下,这一构造可以迫使算法遍历全部 个顶点。这表明,令人信服的几何直觉和良好的实际表现,并不意味着存在多项式的最坏情况界。
这一结果针对的是特定的枢轴规则和一族问题表述,并不是说单纯形法每次运行都会访问指数级数量的顶点。在同一个多面体上,不同规则的表现可能截然不同,而对抗性构造也取决于所分析的规则。不过,许多自然的单纯形法变体都已有已知的指数下界。复杂度还包含两个方面:枢轴操作的次数,以及每次枢轴操作所需的算术运算量。对于有理数输入,精确计算还必须计入表示中间值和输出值所需的位数。
线性规划本身可以在多项式时间内求解。列昂尼德·哈奇扬于 1979 年提出的椭球法结果,在有理数位复杂度模型下确立了这一点;纳伦德拉·卡马卡于 1984 年的工作则推动了高效内点法的发展。内点算法通常在适当的可行域或松弛问题的可行域内部移动,而不是沿着一系列顶点对应的基前进。因此,对内点算法的多项式时间分析,并不能为通常的单纯形枢轴规则提供多项式界。同样,单纯形路径很长,也不意味着对应的线性规划问题在计算上难以求解。
平均情况分析和平滑分析所研究的问题,与最坏情况界有所不同。平滑分析研究对任意输入数据施加微小随机扰动后的性能;丹尼尔·斯皮尔曼和尚华滕的工作,在特定扰动假设下,为一种特定的单纯形求解方法建立了多项式平滑复杂度界。这类结果有助于解释,为什么专门构造的困难实例未必能代表典型的计算表现,但它们并不保证在所有情况下都有同样良好的实际性能。一个相关的未决问题是:线性规划是否存在强多项式算法?粗略地说,这种算法的算术运算次数应当是变量数和约束数的多项式,不依赖于数值系数的大小,同时中间结果的编码长度也应受到控制。这比通常的多项式时间可解性要求更强,而单纯形法或内点法在实现上的成功都没有解决这一问题。
应用、再优化与专门变体
只要模型具有线性目标函数和线性约束,就可以应用单纯形法。在生产计划中,变量可以表示各项生产活动的水平,约束反映劳动力和原材料的可用量,目标函数系数则表示成本或收益。运输模型在满足供需平衡的条件下,为各条运输路线分配运输量。配料模型则对原料比例和质量指标施加约束。在零和博弈中,有限混合策略均衡问题可以表述为线性规划问题。各类应用是否成立,取决于可分性、资源消耗呈线性等建模假设,而不只是优化算法本身。
单纯形法在实践中的一大优势是再优化。基是对已求解模型局部代数结构的紧凑描述,在数据发生变化后仍可能有用。如果只有 发生变化,基矩阵和约化成本保持不变,但必须重新检查可行性。如果只有目标函数系数发生变化,当前的原始解仍然可行,但可能不再满足对偶可行性。此时,原始单纯形法或对偶单纯形法可以从现有基出发,重新达到最优。这些关系构成了敏感性分析的基础:在基保持最优的范围内,基本变量和目标值对数据变化的响应可以用显式的线性或仿射表达式描述。
在整数规划中,单纯形法经常用于求解分支定界法和割平面算法中的连续松弛问题。分支会改变变量的界;割则通过添加不等式来排除不需要的分数解。这两类修改通常都能保留一个适合用对偶单纯形法快速再优化的基。线性规划解为离散优化问题提供一个界,但单纯形法本身并不强制变量取整数值。某些具有特殊结构的模型由于约束矩阵的性质,其顶点均为整点,因此无需显式分支,就能通过求解线性规划来解决相应的离散问题。
当潜在变量数量极其庞大时,列生成可以利用约化成本来求解问题。受限主问题只包含选定的列;其对偶乘子定义了一个定价子问题,用于寻找尚未纳入、且约化成本能够改善目标值的变量。对于最小化模型,在通常的定价条件下,若能证明所有尚未纳入的列都不具有负的约化成本,就能确立完整线性规划松弛问题的最优性。网络单纯形法采用了另一种专门化方式:对于最小费用流问题,基可以用生成树结构表示,从而能够通过网络操作实现枢轴运算和可行性调整。通用求解器还可以将内点优化与交叉转换结合使用;后者将内点解转换为基本解,以便开展基于基的敏感性分析及后续再优化。