单纯形法 （simplex algorithm）在数学优化领域中常用于线性规划 问题的数值求解 ，由喬治·伯納德·丹齊格 发明。
图中展示了一个线性规划多面体，以及使用单纯形法求解相应线性规划问题的可能路径（红色）。 下山单纯形法 （Nelder-Mead method）与单纯形法名称相似，但二者关联不大。该方法由Nelder和Mead于1965年发明，是用于优化多维无约束问题的一种数值方法，属于更普遍的搜索算法 的类别。这两种方法都使用了单纯形 的概念。单纯形 是
N
{\displaystyle N}
N
+
1
{\displaystyle N+1}
顶点 的凸包 ，是一个多胞体 ：直线上的一个线段，平面上的一个三角形，三维空间中的一个四面体 等等，都是单纯形。
编辑
假设有n个变量 和m个约束 。线性规划的标准形式如下：
max
∑
1
≤
k
≤
n
c
k
x
k
s
.
t
.
∑
1
≤
k
≤
n
A
1
,
k
x
k
≤
b
1
,
∑
1
≤
k
≤
n
A
2
,
k
x
k
≤
b
2
,
.
.
.
∑
1
≤
k
≤
n
A
m
,
k
x
k
≤
b
m
x
1
,
x
2
,
.
.
.
,
x
n
≥
0
{\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}}}
所有其他形式的线性规划方程组都可以按照下列方式转化成标准形式：
目标函数 并非最大化：将所有
c
k
{\displaystyle {{c}_{k}}}
约束条件中存在大于或等于约束：将约束两边取负。
约束条件中存在等式 ：将其拆分为两个不等式 （一个大于等于，一个小于等于）
有的变量没有非负约束：加入新变量
x
′
,
x
″
(
x
′
,
x
″
>=
0
)
{\displaystyle x',x''(x',x''>=0)}
x
′
−
x
″
{\displaystyle x'-x''}
x
{\displaystyle x}
编辑
可以将标准形式的线性规划转化为松弛形式，以方便运算。
在原来n个变量，m个约束的线性规划中，加入m个新的变量，将原来的不等式化为等式：
x
n
+
j
=
b
j
−
∑
1
≤
k
≤
n
A
j
,
k
x
k
{\displaystyle {{x}_{n+j}}={{b}_{j}}-\sum \limits _{1\leq k\leq n}{{{A}_{j,k}}{{x}_{k}}}}
当然，此时
x
n
+
j
≥
0
{\displaystyle {{x}_{n+j}}\geq 0}
我们将
x
1
,
x
2
,
.
.
.
,
x
n
{\displaystyle {{x}_{1}},{{x}_{2}},...,{{x}_{n}}}
非基变量 ，它们构成的集合 记为N。将
x
n
+
1
,
x
n
+
2
,
.
.
.
,
x
n
+
m
{\displaystyle {{x}_{n+1}},{{x}_{n+2}},...,{{x}_{n+m}}}
基变量 ，它们构成的集合记为B。简单地理解，非基变量能够由基变量唯一确定。
在这样的定义下，线性规划的松弛形式可以写为如下形式：
max
∑
k
∈
N
c
k
x
k
s
.
t
.
∀
1
≤
i
≤
n
+
m
,
x
i
≥
0
∀
j
∈
B
,
x
j
=
b
j
−
∑
k
∈
N
A
j
,
k
x
k
{\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}}}
因此，线性规划的松弛形式可以由
c
,
A
,
b
,
N
,
B
{\displaystyle c,A,b,N,B}
c
{\displaystyle c}
向量 ，
b
{\displaystyle b}
向量 ，
A
{\displaystyle A}
矩阵 。
N
,
B
{\displaystyle N,B}
整数 集合，分别表示非基变量集合以及基变量集合。
编辑
转轴操作 是单纯形法中的核心操作，其作用是将一个基变量与一个非基变量进行互换。可以将转轴操作理解为从单纯形 上的一个顶点 走向另一个顶点。
设变量
x
n
+
d
{\displaystyle {{x}_{n+d}}}
x
e
{\displaystyle {{x}_{e}}}
x
n
+
d
{\displaystyle {{x}_{n+d}}}
x
e
{\displaystyle {{x}_{e}}}
具体地说，一开始我们有
x
n
+
d
=
b
d
−
∑
k
∈
N
A
d
,
k
x
k
{\displaystyle {{x}_{n+d}}={{b}_{d}}-\sum \limits _{k\in N}{{{A}_{d,k}}{{x}_{k}}}}
移项，得
A
d
,
e
x
e
=
b
d
−
∑
k
∈
N
,
k
≠
e
A
d
,
k
x
k
−
x
n
+
d
{\displaystyle A_{d,e}x_{e}=b_{d}-\sum \limits _{k\in N,k\neq e}A_{d,k}x_{k}-{x}_{n+d}}
如果
A
d
,
e
≠
0
{\displaystyle {{A}_{d,e}}\neq 0}
x
e
=
b
d
A
d
,
e
−
(
∑
k
∈
N
,
k
≠
e
A
d
,
k
A
d
,
e
x
k
)
−
1
A
d
,
e
x
n
+
d
{\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}}}
将此式代入其他的约束等式以及目标函数，我们就实现了
x
n
+
d
{\displaystyle {{x}_{n+d}}}
x
e
{\displaystyle {{x}_{e}}}
编辑
单纯形法的一般解题步骤可归纳如下：
把线性规划问题的约束方程组表达成典范型方程组，找出基本可行解作为初始基本可行解。
若基本可行解不存在，即约束条件有矛盾，则问题无解。
若基本可行解存在，从初始基本可行解作为起点，根据最优性条件和可行性条件，引入非基变量取代某一基变量，找出目标函数值更优的另一基本可行解。
按步骤3进行迭代，直到对应检验数满足最优性条件（这时目标函数值不能再改善），即得到问题的最优解。
若迭代过程中发现问题的目标函数值无界，则终止迭代。
编辑
如果b向量所有元素非负，则显然我们只需要令所有的变量等于0，就可以得到一个可行解 。在这种情况下，通过下述最优化 过程，我们可以得到该线性规划的最优解 ，或者指出该线性规划的最优解为无穷大 （不存在）。
任取一个非基变量
x
e
{\displaystyle {{x}_{e}}}
c
e
>
0
{\displaystyle {{c}_{e}}>0}
选取一个基变量
x
d
{\displaystyle {{x}_{d}}}
A
d
,
e
>
0
{\displaystyle {{A}_{d,e}}>0}
最小化
b
d
/
A
d
,
e
{\displaystyle {{b}_{d}}/{{A}_{d,e}}\;}
执行转轴操作pivot(d, e)，并转到第一步继续算法。 根据
b
d
/
A
d
,
e
{\displaystyle {{b}_{d}}/{{A}_{d,e}}\;}
Δ
v
=
c
e
b
d
A
d
,
e
≥
0
{\displaystyle \Delta v={{c}_{e}}{\frac {{b}_{d}}{{A}_{d,e}}}\geq 0}
不难发现，算法终止有两种情况：
对于所有的非基变量，c均非正。
对于某一个e，所有的
A
d
,
e
{\displaystyle {{A}_{d,e}}}
可以证明，对于第一种情况，我们已经得到了该线性规划的最优解。当前的v即为答案。严格证明比较复杂，但是直观上是很容易理解的。因为所有的非基变量都是非负的，而所有的c都是非正的，因此只要某个非基变量不为0，就会使得目标函数更小。
对于第二种情况来说，很容易证明此时线性规划的最优解是无穷大。只要让其他所有变量均为0，变量
x
e
{\displaystyle {{x}_{e}}}
A
d
,
e
{\displaystyle {{A}_{d,e}}}
c
e
>
0
{\displaystyle {{c}_{e}}>0}
编辑
例：解最优化问题：
min
Z
=
−
x
1
−
x
2
{\displaystyle \min \quad Z=-x_{1}-x_{2}}
s
.
t
.
2
x
1
+
x
2
+
x
3
=
12
,
{\displaystyle s.t.\quad 2x_{1}+x_{2}+x_{3}=12,}
x
1
+
2
x
2
+
x
4
=
9
,
{\displaystyle \quad \quad \quad x_{1}+2x_{2}+x_{4}=9,}
x
i
≥
0
,
i
=
1
,
2
,
3
,
4.
{\displaystyle \quad \quad \quad x_{i}\geq 0,i=1,2,3,4.}
列单纯形表（即矩阵）：
x
1
{\displaystyle x_{1}}
x
2
{\displaystyle x_{2}}
x
3
{\displaystyle x_{3}}
x
4
{\displaystyle x_{4}}
b
x
3
{\displaystyle x_{3}}
2
1
1
0
12
x
4
{\displaystyle x_{4}}
1
2
0
1
9
c
1
1
0
0
0
从c所在行的正数中最大的一个所对应的变量作为基变量，因为这里两者相等，不妨选为
x
1
{\displaystyle x_{1}}
用
x
1
{\displaystyle x_{1}}
12
2
=
6
<
9
1
=
9
{\displaystyle {\frac {12}{2}}=6<{\frac {9}{1}}=9}
x
3
{\displaystyle x_{3}}
然后对该矩阵进行转轴操作，使
x
1
{\displaystyle x_{1}}
x
1
{\displaystyle x_{1}}
x
2
{\displaystyle x_{2}}
x
3
{\displaystyle x_{3}}
x
4
{\displaystyle x_{4}}
b
x
1
{\displaystyle x_{1}}
1
1/2
1/2
0
6
x
4
{\displaystyle x_{4}}
0
3/2
-1/2
1
3
c
0
1/2
-1/2
0
-6
令c所在行其余最大的正数所在列的变量
x
2
{\displaystyle x_{2}}
6
1
/
2
=
12
>
3
3
/
2
=
2
{\displaystyle {\frac {6}{1/2}}=12>{\frac {3}{3/2}}=2}
x
4
{\displaystyle x_{4}}
继续进行行变换，得到
x
1
{\displaystyle x_{1}}
x
2
{\displaystyle x_{2}}
x
3
{\displaystyle x_{3}}
x
4
{\displaystyle x_{4}}
b
x
1
{\displaystyle x_{1}}
1
0
2/3
-1/3
5
x
2
{\displaystyle x_{2}}
0
1
-1/3
2/3
2
c
0
0
-1/3
-1/3
-7
由于c所在行的所有数均非正，问题结束。最优解为
x
1
=
5
,
x
2
=
2
{\displaystyle x_{1}=5,x_{2}=2}
Z
=
−
x
1
−
x
2
=
−
7
{\displaystyle Z=-x_{1}-x_{2}=-7}
编辑
编辑
在采用Bland's法则选择用于转轴操作的d和e（相同值的情况下取字典序 最小）之后，可以证明单纯形法一定能够在有限步之后终止，但是最坏情况 算法的时间复杂度 为指數函數 级别的，而且可以构造出让单纯形法的时间复杂度达到指数级别的具体实例。不过实践证明在绝大多数情况下单纯形法的效率非常令人满意。
单纯形法的最坏时间复杂度为指数级别，并不意味着线性规划 不存在多项式 级别的算法。椭球算法 和内点算法 均为解决线性规划的多项式时间算法。
编辑
编辑
编辑
