單體法

**單體法**（simplex algorithm）在數學最佳化領域中常用於線性規劃問題的數值求解，由喬治・伯納德・丹齊格發明。

下山單體法（Nelder-Mead method）與單體法名稱相似，但二者關聯不大。該方法由 Nelder 和 Mead 於 1965 年發明，是用於最佳化多維無約束問題的一種數值方法，屬於更普遍的搜索算法的類別。這兩種方法都使用了單體的概念。**單體**是 $N$ 維中的 $N+1$ 個頂點的凸包，是一個多胞體：直線上的一個線段，平面上的一個三角形，三維空間中的一個四面體等等，都是單體。

## 標準形式

假設有 n 個變數和 m 個約束。線性規劃的標準形式如下：

　
: ${\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}}$ 取負。
* 約束條件中存在大於或等於約束：將約束兩邊取負。
* 約束條件中存在等式：將其拆分為兩個不等式（一個大於等於，一個小於等於）
* 有的變數沒有非負約束：加入新變數 $x',x''(x',x''>=0)$ 並用 $x'-x''$ 替換原來的變數 $x$

## 鬆弛形式

可以將標準形式的線性規劃轉化為鬆弛形式，以方便運算。
在原來 n 個變數，m 個約束的線性規劃中，加入 m 個新的變數，將原來的不等式化為等式：

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

當然，此時 ${{x}_{n+j}}\geq 0$ 依然成立。

我們將 ${{x}_{1}},{{x}_{2}},...,{{x}_{n}}$ 這些變數稱為**非基變數**，它們構成的集合記為 N。將 ${{x}_{n+1}},{{x}_{n+2}},...,{{x}_{n+m}}$ 這些變數稱為**基變數**，它們構成的集合記為 B。簡單地理解，非基變數能夠由基變數唯一確定。

在這樣的定義下，線性規劃的鬆弛形式可以寫為如下形式：

$$
{\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$ 唯一確定， $c$ 是長度為 n 的向量， $b$ 是長度為 m 的向量， $A$ 是 m\*(n+m) 的矩陣。 $N,B$ 是整數集合，分別表示非基變數集合以及基變數集合。

## 轉軸操作

**轉軸操作**是單體法中的核心操作，其作用是將一個基變數與一個非基變數進行互換。可以將轉軸操作理解為從單體上的一個頂點走向另一個頂點。

設變數 ${{x}_{n+d}}$ 屬於 B（基變數），變數 ${{x}_{e}}$ 屬於 N（非基變數），執行轉軸操作 pivot (d,e) 之後， ${{x}_{n+d}}$ 將變為非基變數，相應地 ${{x}_{e}}$ 將變為基變數。

具體地說，一開始我們有

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

移項，得

$$
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}}\neq 0$ ，我們有

$$
{{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}}$ 與 ${{x}_{e}}$ 在基變數和非基變數上的互換。

## 方法步驟

單體法的一般解題步驟可歸納如下：

1. 把線性規劃問題的約束方程組表達成典範型方程組，找出基本可行解作為初始基本可行解。
2. 若基本可行解不存在，即約束條件有矛盾，則問題無解。
3. 若基本可行解存在，從初始基可行解作為起點，根據最優性條件和可行性條件，引入非基變數取代某一基變數，找出目標函數值更優的另一基本可行解。
4. 按步驟 3 進行疊代，直到對應檢定數滿足最優性條件（這時目標函數值不能再改善），即得到問題的最優解。
5. 若疊代過程中發現問題的目標函數值無界，則終止疊代。

## 最佳化過程

如果 b 向量所有元素非負，則顯然我們只需要令所有的變數等於 0，就可以得到一個可行解。在這種情況下，通過下述最佳化過程，我們可以得到該線性規劃的最優解，或者指出該線性規劃的最優解為無窮大（不存在）。

1. 任取一個非基變數 ${{x}_{e}}$ ，使得 ${{c}_{e}}>0$ 。
2. 選取一個基變數 ${{x}_{d}}$ ，使得 ${{A}_{d,e}}>0$ ，且最小化 ${{b}_{d}}/{{A}_{d,e}}\;$
3. 執行轉軸操作 pivot (d, e)，並轉到第一步繼續算法。

根據 ${{b}_{d}}/{{A}_{d,e}}\;$ 的最小性不難證明 pivot (d, e) 不會破壞 b 的非負性。因此將所有變數取 0 值仍然是可行解。同時，根據 $\Delta v={{c}_{e}}{\frac {{b}_{d}}{{A}_{d,e}}}\geq 0$ ，我們發現 v 一定是不降的。這就達到了更新解的目的。

不難發現，算法終止有兩種情況：

1. 對於所有的非基變數，c 均非正。
2. 對於某一個 e，所有的 ${{A}_{d,e}}$ 均非正。

可以證明，對於第一種情況，我們已經得到了該線性規劃的最優解。當前的 v 即為答案。嚴格證明比較複雜，但是直觀上是很容易理解的。因為所有的非基變數都是非負的，而所有的 c 都是非正的，因此只要某個非基變數不為 0，就會使得目標函數更小。

對於第二種情況來說，很容易證明此時線性規劃的最優解是無窮大。只要讓其他所有變數均為 0，變數 ${{x}_{e}}$ 為正無窮。由於所有的 ${{A}_{d,e}}$ 都非正，因此非基變數的非負性得到保證。同時由於 ${{c}_{e}}>0$ ，目標函數值為正無窮。

### 實例

例：解最佳化問題：

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

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

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

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

列單體表（即矩陣）：

從 c 所在行的正數中最大的一個所對應的變數作為基變數，因為這裡兩者相等，不妨選為 $x_{1}$ 。

用 $x_{1}$ 所在列的正係數除 b 所在列的數並比較大小，有 ${\frac {12}{2}}=6<{\frac {9}{1}}=9$ ，故取 $x_{3}$ 離開基變數。

然後對該矩陣進行轉軸操作，使 $x_{1}$ 所在列變為單位向量：

令 c 所在行其餘最大的正數所在列的變數 $x_{2}$ 進入基變數，並且根據 ${\frac {6}{1/2}}=12>{\frac {3}{3/2}}=2$ ，令 $x_{4}$ 離開基變數。

繼續進行行轉換，得到

由於 c 所在行的所有數均非正，問題結束。最優解為 $x_{1}=5,x_{2}=2$ ，最優值為 $Z=-x_{1}-x_{2}=-7$ 。

## 初始化過程

如果 b 向量並不全為非負，則我們需要通過初始化過程來找到一個可行解，然後才可以使用最佳化過程進行最佳化。當然，此時原線性規劃不一定存在可行解。

具體的方法是，加入一個新的非基變數 ${{x}_{0}}$ ，並在原線性規劃的基礎上構造一個新的輔助的線性規劃。

$$
{\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 集合併不包含 ${{x}_{0}}$ 。

然後，選擇一個基變數 ${{x}_{d}}$ 使得 ${{b}_{d}}$ 最小，執行轉軸操作 pivot (d, 0)。不難證明該操作過後所有的 b 值全部非負。然後，使用前文中所述的最佳化過程求解該輔助線性規劃。

由於 ${{x}_{0}}$ 非負，因此該線性規劃的答案非正。如果答案為負數，則說明原線性規劃不可能讓所有的基變數都非負，因此原線性規劃無可行解。否則，只要令所有變數為 0，並去掉 ${{x}_{0}}$ 變數，就可以得到可行解。

在從輔助線性規劃轉化到原來的線性規劃的過程中，如果 ${{x}_{0}}$ 已經是非基變數，則可以將其從約束條件和目標函數中直接去掉。否則，需要任取一個非基變數 ${{x}_{e}}$ 執行 pivot (0, e)，將 ${{x}_{0}}$ 變為非基變數。由於此時 ${{x}_{0}}$ 是基變數且 ${{x}_{0}}=0$ ，故 ${{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 學習網誌.