单纯形法

单纯形法（simplex algorithm）在数学优化领域中常用于线性规划问题的数值求解，由乔治·伯纳德·丹齐格发明。

下山单纯形法（Nelder-Mead method）与单纯形法名称相似，但二者关联不大。该方法由Nelder和Mead于1965年发明，是用于优化多维无约束问题的一种数值方法，属于更普遍的搜索算法的类别。这两种方法都使用了单纯形的概念。单纯形是 ${\displaystyle N}$ 维中的 ${\displaystyle N+1}$ 个顶点的凸包，是一个多胞体：直线上的一个线段，平面上的一个三角形，三维空间中的一个四面体等等，都是单纯形。

标准形式

假设有n个变量和m个约束。线性规划的标准形式如下：

${\displaystyle {\begin{aligned}&&\max \sum \limits _{1\leq k\leq n}{{{c}_{k}}{{x}_{k}}}\\&s.t.&\sum \limits _{1\leq k\leq n}{{{A}_{1,k}}{{x}_{k}}}\leq {{b}_{1}},\\&&\sum \limits _{1\leq k\leq n}{{{A}_{2,k}}{{x}_{k}}\leq {{b}_{2}},}\\&...\\&&\sum \limits _{1\leq k\leq n}{{{A}_{m,k}}{{x}_{k}}}\leq {{b}_{m}}\\&&{{x}_{1}},{{x}_{2,}}...,{{x}_{n}}\geq 0\end{aligned}}}$

所有其他形式的线性规划方程组都可以按照下列方式转化成标准形式：

• 目标函数并非最大化：将所有${\displaystyle {{c}_{k}}}$取负。
• 约束条件中存在大于或等于约束：将约束两边取负。
• 约束条件中存在等式：将其拆分为两个不等式（一个大于等于，一个小于等于）
• 有的变量没有非负约束：加入新变量${\displaystyle x',x''(x',x''>=0)}$并用${\displaystyle x'-x''}$替换原来的变量${\displaystyle x}$

松弛形式

可以将标准形式的线性规划转化为松弛形式，以方便运算。 在原来n个变量，m个约束的线性规划中，加入m个新的变量，将原来的不等式化为等式：

${\displaystyle {{x}_{n+j}}={{b}_{j}}-\sum \limits _{1\leq k\leq n}{{{A}_{j,k}}{{x}_{k}}}}$

当然，此时${\displaystyle {{x}_{n+j}}\geq 0}$依然成立。

我们将${\displaystyle {{x}_{1}},{{x}_{2}},...,{{x}_{n}}}$这些变量称为非基变量，它们构成的集合记为N。将 ${\displaystyle {{x}_{n+1}},{{x}_{n+2}},...,{{x}_{n+m}}}$这些变量称为基变量，它们构成的集合记为B。简单地理解，非基变量能够由基变量唯一确定。

在这样的定义下，线性规划的松弛形式可以写为如下形式：

${\displaystyle {\begin{aligned}&\max \sum \limits _{k\in N}{{{c}_{k}}{{x}_{k}}}\\&s.t.\\&\forall 1\leq i\leq n+m,{{x}_{i}}\geq 0\\&\forall j\in B,{{x}_{j}}={{b}_{j}}-\sum \limits _{k\in N}{{{A}_{j,k}}{{x}_{k}}}\\\end{aligned}}}$

因此，线性规划的松弛形式可以由${\displaystyle c,A,b,N,B}$唯一确定，${\displaystyle c}$是长度为n的向量，${\displaystyle b}$是长度为m的向量，${\displaystyle A}$是m*(n+m)的矩阵。${\displaystyle N,B}$是整数集合，分别表示非基变量集合以及基变量集合。

转轴操作

转轴操作是单纯形法中的核心操作，其作用是将一个基变量与一个非基变量进行互换。可以将转轴操作理解为从单纯形上的一个顶点走向另一个顶点。

设变量${\displaystyle {{x}_{n+d}}}$属于B（基变量），变量${\displaystyle {{x}_{e}}}$属于N（非基变量），执行转轴操作pivot(d,e)之后，${\displaystyle {{x}_{n+d}}}$将变为非基变量，相应地${\displaystyle {{x}_{e}}}$将变为基变量。

具体地说，一开始我们有

${\displaystyle {{x}_{n+d}}={{b}_{d}}-\sum \limits _{k\in N}{{{A}_{d,k}}{{x}_{k}}}}$

移项，得

${\displaystyle A_{d,e}x_{e}=b_{d}-\sum \limits _{k\in N,k\neq e}A_{d,k}x_{k}-{x}_{n+d}}$

如果${\displaystyle {{A}_{d,e}}\neq 0}$，我们有

${\displaystyle {{x}_{e}}={\frac {{b}_{d}}{{A}_{d,e}}}-(\sum \limits _{k\in N,k\neq e}{{\frac {{A}_{d,k}}{{A}_{d,e}}}{{x}_{k}})}-{\frac {1}{{A}_{d,e}}}{{x}_{n+d}}}$

将此式代入其他的约束等式以及目标函数，我们就实现了${\displaystyle {{x}_{n+d}}}$与${\displaystyle {{x}_{e}}}$在基变量和非基变量上的互换。

方法步骤

单纯形法的一般解题步骤可归纳如下：

1. 把线性规划问题的约束方程组表达成典范型方程组，找出基本可行解作为初始基本可行解。
2. 若基本可行解不存在，即约束条件有矛盾，则问题无解。
3. 若基本可行解存在，从初始基本可行解作为起点，根据最优性条件和可行性条件，引入非基变量取代某一基变量，找出目标函数值更优的另一基本可行解。
4. 按步骤3进行迭代，直到对应检验数满足最优性条件（这时目标函数值不能再改善），即得到问题的最优解。
5. 若迭代过程中发现问题的目标函数值无界，则终止迭代。

最优化过程

如果b向量所有元素非负，则显然我们只需要令所有的变量等于0，就可以得到一个可行解。在这种情况下，通过下述最优化过程，我们可以得到该线性规划的最优解，或者指出该线性规划的最优解为无穷大（不存在）。

1. 任取一个非基变量${\displaystyle {{x}_{e}}}$，使得${\displaystyle {{c}_{e}}>0}$。
2. 选取一个基变量${\displaystyle {{x}_{d}}}$，使得${\displaystyle {{A}_{d,e}}>0}$，且最小化${\displaystyle {{b}_{d}}/{{A}_{d,e}}\;}$
3. 执行转轴操作pivot(d, e)，并转到第一步继续算法。

根据${\displaystyle {{b}_{d}}/{{A}_{d,e}}\;}$的最小性不难证明pivot(d, e)不会破坏b的非负性。因此将所有变量取0值仍然是可行解。同时，根据${\displaystyle \Delta v={{c}_{e}}{\frac {{b}_{d}}{{A}_{d,e}}}\geq 0}$，我们发现v一定是不降的。这就达到了更新解的目的。

不难发现，算法终止有两种情况：

1. 对于所有的非基变量，c均非正。
2. 对于某一个e，所有的${\displaystyle {{A}_{d,e}}}$均非正。

可以证明，对于第一种情况，我们已经得到了该线性规划的最优解。当前的v即为答案。严格证明比较复杂，但是直观上是很容易理解的。因为所有的非基变量都是非负的，而所有的c都是非正的，因此只要某个非基变量不为0，就会使得目标函数更小。

对于第二种情况来说，很容易证明此时线性规划的最优解是无穷大。只要让其他所有变量均为0，变量${\displaystyle {{x}_{e}}}$为正无穷。由于所有的${\displaystyle {{A}_{d,e}}}$都非正，因此非基变量的非负性得到保证。同时由于${\displaystyle {{c}_{e}}>0}$，目标函数值为正无穷。

实例

例：解最优化问题：

${\displaystyle \min \quad Z=-x_{1}-x_{2}}$

${\displaystyle s.t.\quad 2x_{1}+x_{2}+x_{3}=12,}$

${\displaystyle \quad \quad \quad x_{1}+2x_{2}+x_{4}=9,}$

${\displaystyle \quad \quad \quad x_{i}\geq 0,i=1,2,3,4.}$

列单纯形表（即矩阵）：

	${\displaystyle x_{1}}$	${\displaystyle x_{2}}$	${\displaystyle x_{3}}$	${\displaystyle x_{4}}$	b
${\displaystyle x_{3}}$	2	1	1	0	12
${\displaystyle x_{4}}$	1	2	0	1	9
c	1	1	0	0	0

从c所在行的正数中最大的一个所对应的变量作为基变量，因为这里两者相等，不妨选为${\displaystyle x_{1}}$。

用${\displaystyle x_{1}}$所在列的正系数除b所在列的数并比较大小，有${\displaystyle {\frac {12}{2}}=6<{\frac {9}{1}}=9}$，故取${\displaystyle x_{3}}$离开基变量。

然后对该矩阵进行转轴操作，使${\displaystyle x_{1}}$所在列变为单位向量：

	${\displaystyle x_{1}}$	${\displaystyle x_{2}}$	${\displaystyle x_{3}}$	${\displaystyle x_{4}}$	b
${\displaystyle x_{1}}$	1	1/2	1/2	0	6
${\displaystyle x_{4}}$	0	3/2	-1/2	1	3
c	0	1/2	-1/2	0	-6

令c所在行其余最大的正数所在列的变量${\displaystyle x_{2}}$进入基变量，并且根据${\displaystyle {\frac {6}{1/2}}=12>{\frac {3}{3/2}}=2}$，令${\displaystyle x_{4}}$离开基变量。

继续进行行变换，得到

	${\displaystyle x_{1}}$	${\displaystyle x_{2}}$	${\displaystyle x_{3}}$	${\displaystyle x_{4}}$	b
${\displaystyle x_{1}}$	1	0	2/3	-1/3	5
${\displaystyle x_{2}}$	0	1	-1/3	2/3	2
c	0	0	-1/3	-1/3	-7

由于c所在行的所有数均非正，问题结束。最优解为${\displaystyle x_{1}=5,x_{2}=2}$，最优值为${\displaystyle Z=-x_{1}-x_{2}=-7}$。

初始化过程

如果b向量并不全为非负，则我们需要通过初始化过程来找到一个可行解，然后才可以使用最优化过程进行优化。当然，此时原线性规划不一定存在可行解。

具体的方法是，加入一个新的非基变量${\displaystyle {{x}_{0}}}$，并在原线性规划的基础上构造一个新的辅助的线性规划。

${\displaystyle {\begin{aligned}&\max -{{x}_{0}}\\&s.t.\\&\forall 0\leq i\leq n+m,{{x}_{i}}\geq 0\\&\forall j\in B,{{x}_{j}}={{b}_{j}}-(\sum \limits _{k\in N}{{{A}_{j,k}}{{x}_{k}}})+{{x}_{0}}\\\end{aligned}}}$

注意这里N集合并不包含${\displaystyle {{x}_{0}}}$。

然后，选择一个基变量${\displaystyle {{x}_{d}}}$使得${\displaystyle {{b}_{d}}}$最小，执行转轴操作pivot(d, 0)。不难证明该操作过后所有的b值全部非负。然后，使用前文中所述的最优化过程求解该辅助线性规划。

由于${\displaystyle {{x}_{0}}}$非负，因此该线性规划的答案非正。如果答案为负数，则说明原线性规划不可能让所有的基变量都非负，因此原线性规划无可行解。否则，只要令所有变量为0，并去掉${\displaystyle {{x}_{0}}}$变量，就可以得到可行解。

在从辅助线性规划转化到原来的线性规划的过程中，如果${\displaystyle {{x}_{0}}}$已经是非基变量，则可以将其从约束条件和目标函数中直接去掉。否则，需要任取一个非基变量${\displaystyle {{x}_{e}}}$执行pivot(0, e)，将${\displaystyle {{x}_{0}}}$变为非基变量。由于此时${\displaystyle {{x}_{0}}}$是基变量且${\displaystyle {{x}_{0}}=0}$，故${\displaystyle {{b}_{0}}=0}$一定成立，因此这个转轴操作不会破坏b向量的非负性。

效率分析

在采用Bland's法则选择用于转轴操作的d和e（相同值的情况下取字典序最小）之后，可以证明单纯形法一定能够在有限步之后终止，但是最坏情况算法的时间复杂度为指数函数级别的，而且可以构造出让单纯形法的时间复杂度达到指数级别的具体实例。不过实践证明在绝大多数情况下单纯形法的效率非常令人满意。

单纯形法的最坏时间复杂度为指数级别，并不意味着线性规划不存在多项式级别的算法。椭球算法和内点算法均为解决线性规划的多项式时间算法。

参考

• Greenberg, Harvey J., Klee-Minty Polytope Shows Exponential Time Complexity of Simplex Method University of Colorado at Denver (1997) PDF download （页面存档备份，存于互联网档案馆）
• Frederick S. Hillier and Gerald J. Lieberman: Introduction to Operations Research, 8th edition. McGraw-Hill. ISBN 0-07-123828-X
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 29.3: The simplex algorithm, pp.790–804.
• IOI2007国家集训队论文，《浅谈信息学竞赛中的线性规划——简洁高效的单纯形法实现与应用》，作者：李宇骞

参看

• Nelder-Mead方法

外部链接

• 线性规划和单纯形法简介 （页面存档备份，存于互联网档案馆） 作者Spyros Reveliotis（乔治亚理工）。
  • 分步单纯形法求解器 （页面存档备份，存于互联网档案馆） 可以求解线性规划问题。
• 基于Java的交互式单纯形工具 由Argonne国家实验室提供。
• 单纯形法 作者Elmer G. Wiens。演示算法细节，使用了“单纯形表”。
• 单纯形法教程 作者Stefan Waner，hofstra.edu。
• 单纯形法分解 Mazoo学习网志.