-
單純形方法
鎖定
單純形方法是用線性代數解聯立方程所用的迭代法求最優解的方法，是線性規劃問題的基本算法。它和代數學中解線性聯立方程組的高斯消去法極為相似。
- 中文名
- 單純形方法
- 外文名
- Simplex method
- 定 義
- 直接、快速的搜索最小值方法
- 特 點
- 收斂速度快，適用面較廣
- 領 域
- 目標函數的解析性
- 學 科
- 數學
單純形方法簡介
由George Dantzig發明的單純形法（simplex algorithm）在數學優化領域中常用於線性規劃問題的數值求解。
Nelder-Mead 法或稱下山單純形法，與單純形法名稱相似，但二者關聯不大。該方法由Nelder和Mead於1965年發明，是用於優化多維無約束問題的一種數值方法，屬於更普遍的搜索算法的類別。這兩種方法都使用了單純形的概念。單純形是N維中的N+1個頂點的凸包，是一個多胞體：直線上的一個線段，平面上的一個三角形，三維空間中的一個四面體等等，都是單純形。
單純形方法基本思想
它的基本思想是：採取逐步接近最優解的辦法，先求出一個可行解，但它未必是最優者，然後逐步改善可行解，使目標函數值逐步增大(或減小)，直到目標函數達到極值(最大值或最小值)時，該問題就得到了最優解，或判斷無最優解。
[1]
單純形方法解題步驟
單純形法的一般解題步驟可歸納如下：
1.把線性規劃問題的約束方程組表達成典範型方程組，找出基本可行解作為初始基可行解。
2.若基本可行解不存在，即約束條件有矛盾，則問題無解。
3.若基本可行解存在，從初始基可行解作為起點，根據最優性條件和可行性條件，引入非基變量取代某一基變量，找出目標函數值更優的另一基本可行解。
4.按步驟3進行迭代,直到對應檢驗數滿足最優性條件（這時目標函數值不能再改善），即得到問題的最優解。
5.若迭代過程中發現問題的目標函數值無界，則終止迭代
[2]
。
單純形方法最優化過程
如果b向量所有元素非負，則顯然我們只需要令所有的變量等於0，就可以得到一個可行解。在這種情況下，通過下述最優化過程，我們可以得到該線性規劃的最優解，或者指出該線性規劃的最優解為無窮大（不存在）
[3]
。
- 任取一個非基變量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，目標函數值為正無窮。
