查看“单纯形法”的源代码

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

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

== 标准形式 ==
假设有n个[[变量]]和m个[[約束 (數學)|约束]]。线性规划的标准形式如下：
:<math>\begin{align}
  & & \max \sum\limits_{1\le k\le n}{{{c}_{k}}{{x}_{k}}} \\ 
 & s.t. & \sum\limits_{1\le k\le n}{{{A}_{1,k}}{{x}_{k}}}\le {{b}_{1}}, \\ 
 & & \sum\limits_{1\le k\le n}{{{A}_{2,k}}{{x}_{k}}\le {{b}_{2}},} \\ 
 & ... \\ 
 & & \sum\limits_{1\le k\le n}{{{A}_{m,k}}{{x}_{k}}}\le {{b}_{m}} \\ 
 & & {{x}_{1}},{{x}_{2,}}...,{{x}_{n}}\ge 0  
\end{align}</math>

所有其他形式的线性规划方程组都可以按照下列方式转化成标准形式：
* [[目标函数]]并非最大化：将所有<math>{{c}_{k}}</math>取负。
* 约束条件中存在大于或等于约束：将约束两边取负。
* 约束条件中存在[[等式]]：将其转化为两个[[不等式]]（一个大于等于，一个小于等于）
* 有的变量没有非负约束：加入新变量<math>x'</math>，并用<math>x-x'</math>替换原来的变量<math>x</math>

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

<math>{{x}_{n+j}}={{b}_{j}}-\sum\limits_{1\le k\le n}{{{A}_{j,k}}{{x}_{k}}}</math>

当然，此时<math>{{x}_{n+j}}\ge 0</math>依然成立。

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

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

<math>\begin{align}
  & \max \sum\limits_{k\in N}{{{c}_{k}}{{x}_{k}}} \\ 
 & s.t. \\ 
 & \forall 1\le i\le n+m,{{x}_{i}}\ge 0 \\ 
 & \forall j\in B,{{x}_{j}}={{b}_{j}}-\sum\limits_{k\in N}{{{A}_{j,k}}{{x}_{k}}} \\ 
\end{align}</math>

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

== 转轴操作 ==
'''转轴操作'''是单纯形法中的核心操作，其作用是将一个基变量与一个非基变量进行互换。可以将转轴操作理解为从[[单纯形]]上的一个[[頂點 (幾何)|顶点]]走向另一个顶点。

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

具体地说，一开始我们有

<math>{{x}_{n+d}}={{b}_{d}}-\sum\limits_{k\in N}{{{A}_{d,k}}{{x}_{k}}}</math>

[[移项]]，得

<math>A_{d,e}x_e = b_d-\sum\limits_{k\in N,k\ne e}A_{d,k}x_k-{x}_{n+d}</math>

如果<math>{{A}_{d,e}}\ne 0</math>，我们有

<math>{{x}_{e}}=\frac{{{b}_{d}}}{{{A}_{d,e}}}-(\sum\limits_{k\in N,k\ne e}{\frac{{{A}_{d,k}}}{{{A}_{d,e}}}{{x}_{k}})}-\frac{1}{{{A}_{d,e}}}{{x}_{n+d}}</math>

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

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

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

== 最优化过程 ==
如果b向量所有元素非负，则显然我们只需要令所有的变量等于0，就可以得到一个[[可行解]]。在这种情况下，通过下述[[最优化]]过程，我们可以得到该线性规划的[[最优解]]，或者指出该线性规划的最优解为[[无穷大]]（不存在）。
# 任取一个非基变量<math>{{x}_{e}}</math>，使得<math>{{c}_{e}}>0</math>。
# 选取一个基变量<math>{{x}_{d}}</math>，使得<math>{{A}_{d,e}}>0</math>，且[[最小化]]<math>{{{b}_{d}}}/{{{A}_{d,e}}}\;</math>
# 执行转轴操作pivot(d, e)，并转到第一步继续算法。

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

不难发现，算法终止有两种情况：
# 对于所有的非基变量，c均非正。
# 对于某一个e，所有的<math>{{A}_{d,e}}</math>均非正。
可以证明，对于第一种情况，我们已经得到了该线性规划的最优解。当前的v即为答案。严格证明比较复杂，但是直观上是很容易理解的。因为所有的非基变量都是非负的，而所有的c都是非正的，因此只要某个非基变量不为0，就会使得目标函数更小。

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

=== 实例 ===
例：解最优化问题：

<math>\min \quad - x_1 - x_2</math>

<math>s.t. \quad 2x_1 + x_2 + x_3 = 12,</math>

<math>\quad x_1 + 2x_2+ x_4 = 9,</math>

<math>x_i \geq 0, i = 1, 2, 3, 4.</math>

列单纯形表（即矩阵）：
{| class="wikitable"
|-
|  || <math>x_1</math> || <math>x_2</math> || <math>x_3</math> || <math>x_4</math> || b 
|-
| <math>x_3</math> || 2 || 1 || 1 || 0 || 12
|-
| <math>x_4</math> || 1 || 2 || 0 || 1 || 9
|-
| c || 1 || 1 || 0 || 0 || 0
|}

然后从c所在行的正数中最大的一个所对应的变量作为基变量，因为这里两者一样，不妨选为<math>x_1</math>。

由于拿<math>x_1</math>所在列的正系数去除b所在列的数的结果为<math>\frac {12}2 = 6 < \frac 91 = 9</math>，故取<math>x_3</math>离开基变量。

然后对该矩阵进行行变换，使<math>x_1</math>所在列变成单位向量：

{| class="wikitable"
|-
|  || <math>x_1</math> || <math>x_2</math> || <math>x_3</math> || <math>x_4</math> || b 
|-
| <math>x_1</math> || 1 || 1/2 || 1/2 || 0 || 6
|-
| <math>x_4</math> || 0 || 3/2 || -1/2 || 1 || 3
|-
| c || 0 || 1/2 || -1/2 || 0 || -6
|}

接下来令c所在行的其余的正数中最大的一个所在列的变量<math>x_2</math>进入基变量，并且根据<math>\frac 6{1/2} = 12 > \frac 3{3/2} = 2</math>，令<math>x_4</math>离开基变量。

继续进行行变换，得到

{| class="wikitable"
|-
|  || <math>x_1</math> || <math>x_2</math> || <math>x_3</math> || <math>x_4</math> || b 
|-
| <math>x_1</math> || 1 || 0 || 2/3 || -1/3 || 5
|-
| <math>x_2</math> || 0 || 1 || -1/3 || 2/3 || 2
|-
| c || 0 || 0 || -1/3 || -1/3 || -7
|}

由于c所在行的所有数都非正，问题结束。最优解为<math>x_1 = 5, x_2 = 2</math>，最优值为<math>\min - x_1 - x_2 = -7</math>。

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

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

<math>\begin{align}
  & \max -{{x}_{0}} \\ 
 & s.t. \\ 
 & \forall 0\le i\le n+m,{{x}_{i}}\ge 0 \\ 
 & \forall j\in B,{{x}_{j}}={{b}_{j}}-(\sum\limits_{k\in N}{{{A}_{j,k}}{{x}_{k}}})+{{x}_{0}} \\ 
\end{align}</math>

注意这里N集合并不包含<math>{{x}_{0}}</math>。

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

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

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

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

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

== 参考 ==
* Greenberg, Harvey J., ''Klee-Minty Polytope Shows Exponential Time Complexity of Simplex Method'' University of Colorado at Denver (1997) [http://glossary.computing.society.informs.org/notes/Klee-Minty.pdf 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方法]]

== 外部链接 ==
* [http://www.isye.gatech.edu/~spyros/LP/LP.html 线性规划和单纯形法简介] 作者Spyros Reveliotis（乔治亚理工）。
** [http://www2.isye.gatech.edu/~spyros/Panagiotis/JAVAstuff/HTML/Sim.html 分步单纯形法求解器] 可以求解线性规划问题。
* 基于Java的[https://web.archive.org/web/20060423065925/http://www-fp.mcs.anl.gov/otc/Guide/CaseStudies/simplex/ 交互式单纯形工具] 由Argonne国家实验室提供。
* [https://web.archive.org/web/20060518080331/http://www.egwald.com/operationsresearch/lpsimplex.php 单纯形法] 作者Elmer G. Wiens。演示算法细节，使用了''单纯形表''。
* [https://web.archive.org/web/20060409024948/http://people.hofstra.edu/faculty/Stefan_Waner/RealWorld/tutorialsf4/frames4_3.html 单纯形法教程] 作者Stefan Waner，hofstra.edu。
* [https://web.archive.org/web/20060624003125/http://learning.mazoo.net/archives/001240.html 单纯形法分解] Mazoo学习网志.

{{算法}}
[[Category:组合优化]]
[[Category:運籌學]]