單純形法 （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（相同值的情況下取字典序 最小）之後，可以證明單純形法一定能夠在有限步之後終止，但是最壞情況 算法的時間複雜度 為指數函數 級別的，而且可以構造出讓單純形法的時間複雜度達到指數級別的具體實例 。不過實踐證明在絕大多數情況下單純形法的效率非常令人滿意。
單純形法的最壞時間複雜度為指數級別，並不意味着線性規劃 不存在多項式 級別的算法。橢球算法 和內點算法 均為解決線性規劃的多項式時間算法。
