http://zh.wikipedia.org/wiki/单纯形法

数学最优化中，由George Dantzig发明的单纯形法（simplex algorithm）是线性规划问题的数值求解的流行技术。有一个算法与此无关，但名称类似，它是Nelder-Mead法或称下山单纯形法，由Nelder和Mead发现（1965年），这是用于优化多维无约束问题的一种数值方法，属于更一般的搜索算法的类别。

这二者都使用了单纯形的概念，它是N维中的N + 1个顶点的凸包，是一个多胞体：直线上的一个线段，平面上的一个三角形，三维空间中的一个四面体，等等。

[编辑] 标准形式

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

http://upload.wikimedia.org/math/3/f/3/3f3ae760b53f75e58640440c8e79a4bf.png

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

• 目标函数并非最大化：将所有http://upload.wikimedia.org/math/e/8/8/e88cbc51c97105e35e72240014e95188.png取负。
• 约束条件中存在大于或等于约束：将约束两边取负。
• 约束条件中存在等式：将其转化为两个不等式（一个大于等于，一个小于等于）
• 有的变量没有非负约束：加入新变量http://upload.wikimedia.org/math/9/d/d/9dd4e461268c8034f5c8564e155c67a6.png

[编辑] 松弛形式

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

http://upload.wikimedia.org/math/3/f/2/3f24f4fec6a85db135be6433667dbc4b.png

当然，此时http://upload.wikimedia.org/math/4/7/1/471b52f72a6793180bf0f0742bb38db6.png依然成立。

我们将http://upload.wikimedia.org/math/6/3/f/63fe1e0f90a9bb81ad0fd29780f92166.png这些变量称为非基变量，它们构成的集合记为N。将 http://upload.wikimedia.org/math/a/4/0/a40464b7d23d6b65a7c039b177dc6f3c.png 这些变量称为基变量，它们构成的集合记为B。简单地理解，非基变量能够由基变量唯一确定。

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

http://upload.wikimedia.org/math/c/c/8/cc89b7e16f7150948987a632e43cc34e.png

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

[编辑] 转轴操作

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

设变量http://upload.wikimedia.org/math/5/4/9/5498a9b7ad43d33983663fd095458416.png将变为基变量。

具体地说，一开始我们有

http://upload.wikimedia.org/math/6/9/5/69545a0f5aeef2cc0491e90cafd028d8.png

移项，得

http://upload.wikimedia.org/math/d/6/2/d62dc20ea9f2544d318c6785a978a298.png

如果http://upload.wikimedia.org/math/f/c/1/fc14d67b2b0871140906725bc9a0b194.png，我们有

http://upload.wikimedia.org/math/2/2/b/22b037470535d0d31eaba2d9e467b2b0.png

将此式代入其他的约束等式以及目标函数，我们就实现了http://upload.wikimedia.org/math/5/4/9/5498a9b7ad43d33983663fd095458416.png在基变量和非基变量上的互换。

[编辑] 最优化过程

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

1. 任取一个非基变量http://upload.wikimedia.org/math/2/0/8/208193642fa59890d401f0bbd80d70d9.png。
2. 选取一个基变量http://upload.wikimedia.org/math/e/0/1/e01832d42c401e4acfe293fb88908acd.png
3. 执行转轴操作pivot(d, e)，并转到第一步继续算法。

根据http://upload.wikimedia.org/math/e/0/1/e01832d42c401e4acfe293fb88908acd.png的最小性不难证明pivot(d, e)不会破坏b的非负性。因此将所有变量取0值仍然是可行解。同时，根据http://upload.wikimedia.org/math/c/0/1/c01f4372861fac5944b3a7b33b0cabe6.png，我们发现v一定是不降的。这就达到了更新解的目的。

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

1. 对于所有的非基变量，c均非正。
2. 对于某一个e，所有的http://upload.wikimedia.org/math/e/6/7/e671975e42f9cf339a46f0232cc02f3e.png均非正。

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

对于第二种情况来说，很容易证明此时线性规划的最优解是无穷大。只要让其他所有变量均为0，变量为正无穷。由于所有的http://upload.wikimedia.org/math/e/6/7/e671975e42f9cf339a46f0232cc02f3e.png都非正，因此非基变量的非负性得到保证。同时由于，目标函数值为正无穷。

[编辑] 实例

例：解最优化问题：

http://upload.wikimedia.org/math/d/7/c/d7c849cc946680e261b7a371fe89d84e.png

http://upload.wikimedia.org/math/5/e/2/5e209089951e9a24fcd3872dd12862fe.png

http://upload.wikimedia.org/math/2/a/2/2a2cce10ddcb5668943401da1a4c747f.png

http://upload.wikimedia.org/math/8/1/f/81f0e2f808da0361706cdbf9609d0e22.png

列单纯形表（即矩阵）：

然后从c所在行的正数中最大的一个所对应的变量作为基变量，因为这里两者一样，不妨选为http://upload.wikimedia.org/math/f/9/a/f9a3b8e9e501458e8face47cae8826de.png。

由于拿http://upload.wikimedia.org/math/f/9/a/f9a3b8e9e501458e8face47cae8826de.png所在列的正系数去除b所在列的数的结果为，故取http://upload.wikimedia.org/math/a/4/f/a4f66ba447cf765d4612169b07207e8d.png离开基变量。

然后对该矩阵进行行变换，使http://upload.wikimedia.org/math/f/9/a/f9a3b8e9e501458e8face47cae8826de.png所在列变成单位向量：

接下来令c所在行的其余的正数中最大的一个所在列的变量http://upload.wikimedia.org/math/8/f/4/8f43fce8dbdf3c4f8d0ac91f0de1d43d.png进入基变量，并且根据，令http://upload.wikimedia.org/math/a/a/5/aa51775bcd244abf06e709f0cd80e614.png离开基变量。

继续进行行变换，得到

由于c所在行的所有数都非正，问题结束。最优解为http://upload.wikimedia.org/math/9/4/3/94365d2e0ebeb058fd336e349b788f9a.png。

[编辑] 初始化过程

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

具体的方法是，加入一个新的非基变量http://upload.wikimedia.org/math/4/b/0/4b0ad26474f74a2748905375b67881e5.png，并在原线性规划的基础上构造一个新的辅助的线性规划。

http://upload.wikimedia.org/math/6/7/8/67869bcfe7a1ef69ed72c5b2c94123cb.png

注意这里N集合并不包含http://upload.wikimedia.org/math/4/b/0/4b0ad26474f74a2748905375b67881e5.png。

然后，选择一个基变量http://upload.wikimedia.org/math/6/3/9/639b2499f050c2caff4b0b9465e447a4.png最小，执行转轴操作pivot(d, 0)。不难证明该操作过后所有的b值全部非负。然后，使用前文中所述的最优化过程求解该辅助线性规划。

由于http://upload.wikimedia.org/math/4/b/0/4b0ad26474f74a2748905375b67881e5.png非负，因此该线性规划的答案非正。如果答案为负数，则说明原线性规划不可能让所有的基变量都非负，因此原线性规划无可行解。否则，只要令所有变量为0，并去掉http://upload.wikimedia.org/math/4/b/0/4b0ad26474f74a2748905375b67881e5.png变量，就可以得到可行解。

在从辅助线性规划转化到原来的线性规划的过程中，如果http://upload.wikimedia.org/math/4/b/0/4b0ad26474f74a2748905375b67881e5.png已经是非基变量，则可以将其从约束条件和目标函数中直接去掉。否则，需要任取一个非基变量执行pivot(0, e)，将http://upload.wikimedia.org/math/4/b/0/4b0ad26474f74a2748905375b67881e5.png变为非基变量。由于此时http://upload.wikimedia.org/math/4/b/0/4b0ad26474f74a2748905375b67881e5.png是基变量且，故一定成立，因此这个转轴操作不会破坏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国家集训队论文，《浅谈信息学竞赛中的线性规划——简洁高效的单纯形法实现与应用》，作者：李宇骞