單純形法

單純形法的基本想法是從線性規劃可行集的某一個頂點出發，沿着使目標函數值下降的方向尋求下一個頂點，面頂點個數是有限的，所以，只要這個線性規劃有最優解，那麼通過有限步迭代後，必可求出最優解 ^[2]  。

為了用迭代法 ^[2]  求出線性規劃的最優解，需要解決以下三個問題 ^[2]  ：

(1)最優解判別準則，即迭代終止的判別標準 ^[2]  ；

(2)換基運算，即從一個基可行解迭代出另一個基可行解的方法 ^[2]  ；

(3)進基列的選擇，即選擇合適的列以進行換基運算，可以使目標函數值有較大下降 ^[2]  。

原單純形法不是很經濟的算法。1953年美國數學家G.B.丹捷格為了改進單純形法每次迭代中積累起來的進位誤差，提出改進單純形法。其基本步驟和單純形法大致相同，主要區別是在逐次迭代中不再以高斯消去法為基礎，而是由舊基陣的逆去直接計算新基陣的逆，再由此確定檢驗數。這樣做可以減少迭代中的累積誤差，提高計算精度，同時也減少了在計算機上的存儲量 ^[3]  。

對偶單純形法是使用對偶理論求解線性規劃問題的一種方法，而不是求解對偶問題的一種方法。與對偶單純形法相對應，已有的單純形法稱為原始單純形法 ^[4]  。

原問題與對偶問題解之間的對應關係：即原問題單純形表的檢驗數行對應其對偶問題的一個基本解。單純形法求解的基本思想是：在整個迭代過程中，始終保持原問題的解是可行解，而對偶問題的解可以是非可行解，當對偶問題的解由非可行解變為可行解，也就是原問題的檢驗數行都滿足小於等於零時，原問題取得了最優解。而對偶單純形法的基本思想是：在整個迭代過程中，始終保持對偶問題的解是可行解，原問題的解可以是非可行解，當原問題的解由非可行解變為可行解時，對偶問題取得了最優解。所以，對偶單純形法的實質就是在保證對偶問題可行的條件下向原問題可行的方向迭代 ^[4]  。

數學優化中，由George Dantzig發明的單純形法是線性規劃問題的數值求解的流行技術。有一個算法與此無關，但名稱類似，它是Nelder-Mead法或稱下山單純形法，由Nelder和Mead發現（1965年），這是用於優化多維無約束問題的一種數值方法，屬於更一般的搜索算法的類別 ^[5]  。

這二者都使用了單純形的概念，它是N維中的N+1個頂點的凸包，是一個多胞體：直線上的一個線段，平面上的一個三角形，三維空間中的一個四面體，等等 ^[5]  。

如果線性規劃問題存在最優解，則一定有一個基可行解是最優解。因而線性規劃問題的求解，就是要從諸多的基可行解中找到最優解 ^[6]  。

利用單純形法求解線性規劃問題的解題思路是：確定初始基可行解，即從可行域的個頂點出發，判斷該頂點是否為最優解，若是最優解則問題求解結束；否則尋找新的基可行解，即轉換到另一個頂點(轉換的目的是優化目標函數值)，再判斷該頂點是否為最優解，如此循環往復，直到使目標函數值達到最大為止，而使目標函數值達到最大的基可行解即為問題的最優解。該過程如圖1所示 ^[6]  。

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

(1)把線性規劃問題的約束方程組表達成典範型方程組，找出基本可行解作為初始基本可行解 ^[7]  。

(2)若基本可行解不存在，即約束條件有矛盾，則問題無解 ^[7]  。

(3)若基本可行解存在，以初始基本可行解作為起點，根據最優性條件和可行性條件，引入非基變量取代某一基變量，找出目標函數值更優的另一基本可行解 ^[7]  。

(4)按步驟3進行迭代，直到對應檢驗數滿足最優性條件(這時目標函數值不能再改善)，即得到問題的最優解 ^[7]  。

(5)若迭代過程中發現問題的目標函數值無界，則終止迭代 ^[7]  。

用單純形法求解線性規劃問題所需的迭代次數主要取決於約束條件的個數。現在一般的線性規劃問題都是應用單純形法標準軟件在計算機上求解 ^[7]  。