單純形方法是用線性代數解聯立方程所用的疊代法求最優解的方法，是線性規劃問題的基本算法。它和代數學中解線性聯立方程組的高斯消去法極為相似。
基本介紹
- 中文名：單純形方法
- 外文名：Simplex method
- 定義：直接、快速的搜尋最小值方法
- 特點：收斂速度快，適用面較廣
- 領域：目標函式的解析性
- 學科：數學
簡介,基本思想,解題步驟,最最佳化過程,
簡介
由George Dantzig發明的單純形法（simplex algorithm）在數學最佳化領域中常用於線性規劃問題的數值求解。
Nelder-Mead 法或稱下山單純形法，與單純形法名稱相似，但二者關聯不大。該方法由Nelder和Mead於1965年發明，是用於最佳化多維無約束問題的一種數值方法，屬於更普遍的搜尋算法的類別。這兩種方法都使用了單純形的概念。單純形是N維中的N+1個頂點的凸包，是一個多胞體：直線上的一個線段，平面上的一個三角形，三維空間中的一個四面體等等，都是單純形。
基本思想
它的基本思想是：採取逐步接近最優解的辦法，先求出一個可行解，但它未必是最優者，然後逐步改善可行解，使目標函式值逐步增大(或減小)，直到目標函式達到極值(最大值或最小值)時，該問題就得到了最優解，或判斷無最優解。
解題步驟
單純形法的一般解題步驟可歸納如下：
1.把線性規劃問題的約束方程組表達成典範型方程組，找出基本可行解作為初始基可行解。
2.若基本可行解不存在，即約束條件有矛盾，則問題無解。
3.若基本可行解存在，從初始基可行解作為起點，根據最優性條件和可行性條件，引入非基變數取代某一基變數，找出目標函式值更優的另一基本可行解。
4.按步驟3進行疊代,直到對應檢驗數滿足最優性條件（這時目標函式值不能再改善），即得到問題的最優解。
5.若疊代過程中發現問題的目標函式值無界，則終止疊代。
最最佳化過程
- 任取一個非基變數xe，使得ce>0。
- 選取一個基變數xd，使得Ad,e>0，且最小化bd/Ad。
- 執行轉軸操作pivot(d, e)，並轉到第一步繼續算法。
根據bd/Ad的最小性不難證明pivot(d, e)不會破壞b的非負性。因此將所有變數取0值仍然是可行解。同時，根據Δv=ce(bd/Ad),e≥0，我們發現v一定是不降的。這就達到了更新解的目的。
不難發現，算法終止有兩種情況：
- 對於所有的非基變數，c均非正。
- 對於某一個e，所有的Ad均非正。
可以證明，對於第一種情況，我們已經得到了該線性規劃的最優解。當前的v即為答案。嚴格證明比較複雜，但是直觀上是很容易理解的。因為所有的非基變數都是非負的，而所有的c都是非正的，因此只要某個非基變數不為0，就會使得目標函式更小。
對於第二種情況來說，很容易證明此時線性規劃的最優解是無窮大。只要讓其他所有變數均為0，變數xe為正無窮。由於所有的Ad都非正，因此非基變數的非負性得到保證。同時由於ce>0，目標函式值為正無窮。
