單純形法simplex method求解線性規(guī)劃問題的通用方法.單純形是美國數學家G.B.丹齊克于1947年首先提出來的.它的理論根據是：線性規(guī)劃問題的可行域是 n維向量空間Rn中的多面凸集,其最優(yōu)值如果存在必在該凸集的某頂點處達到.頂點所對應的可行解稱為基本可行解.單純形法的基本思想是：先找出一個基本可行解,對它進行鑒別,看是否是最優(yōu)解；若不是,則按照一定法則轉換到另一改進的基本可行解,再鑒別；若仍不是,則再轉換,按此重復進行.因基本可行解的個數有限,故經有限次轉換必能得出問題的最優(yōu)解.如果問題無最優(yōu)解也可用此法判別.根據單純形法的原理,在線性規(guī)劃問題中,決策變量（控制變量）x1,x2,…x n的值稱為一個解,滿足所有的約束條件的解稱為可行解.使目標函數達到最大值（或最小值）的可行解稱為最優(yōu)解.這樣,一個最優(yōu)解能在整個由約束條件所確定的可行區(qū)域內使目標函數達到最大值（或最小值）.求解線性規(guī)劃問題的目的就是要找出最優(yōu)解.最優(yōu)解可能出現下列情況之一：

①存在著一個最優(yōu)解；

③不存在最優(yōu)解,這只在兩種情況下發(fā)生,即沒有可行解或各項約束條件不阻止目標函數的值無限增大（或向負的方向無限增大）.單純形法的一般解題步驟可歸納如下：

①把線性規(guī)劃問題的約束方程組表達成典范型方程組,找出基本可行解作為初始基本可行解.②若基本可行解不存在,即約束條件有矛盾,則問題無解.③若基本可行解存在,從初始基本可行解作為起點,根據最優(yōu)性條件和可行性條件,引入非基變量取代某一基變量,找出目標函數值更優(yōu)的另一基本可行解.④按步驟3進行迭代,直到對應檢驗數滿足最優(yōu)性條件（這時目標函數值不能再改善）,即得到問題的最優(yōu)解.⑤若迭代過程中發(fā)現問題的目標函數值無界,則終止迭代.用單純形法求解線性規(guī)劃問題所需的迭代次數主要取決于約束條件的個數.現在一般的線性規(guī)劃問題都是應用單純形法標準軟件在計算機上求解,對于具有106個決策變量和104個約束條件的線性規(guī)劃問題已能在計算機上解得.改進單純形法原單純形法不是很經濟的算法.1953年美國數學家G.B.丹齊克為了改進單純形法每次迭代中積累起來的進位誤差,提出改進單純形法.其基本步驟和單純形法大致相同,主要區(qū)別是在逐次迭代中不再以高斯消去法為基礎,而是由舊基陣的逆去直接計算新基陣的逆,再由此確定檢驗數.這樣做可以減少迭代中的累積誤差,提高計算精度,同時也減少了在計算機上的存儲量.對偶單純形法1954年美國數學家C.萊姆基提出對偶單純形法.單純形法是從原始問題的一個可行解通過迭代轉到另一個可行解,直到檢驗數滿足最優(yōu)性條件為止.對偶單純形法則是從滿足對偶可行性條件出發(fā)通過迭代逐步搜索原始問題的最優(yōu)解.在迭代過程中始終保持基解的對偶可行性,而使不可行性逐步消失.設原始問題為min{cx|Ax=b,x≥0},則其對偶問題為 max{yb|yA≤c}.當原始問題的一個基解滿足最優(yōu)性條件時,其檢驗數cBB-1A-c≤0.即知y＝cBB-1（稱為單純形算子）為對偶問題的可行解.所謂滿足對偶可行性,即指其檢驗數滿足最優(yōu)性條件.因此在保持對偶可行性的前提下,一當基解成為可行解時,便也就是最優(yōu)解.數學優(yōu)化中,由George Dantzig發(fā)明的單純形法是線性規(guī)劃問題的數值求解的流行技術.有一個算法與此無關,但名稱類似,它是Nelder-Mead法或稱下山單純形法,由Nelder和Mead發(fā)現（1965年）,這是用于優(yōu)化多維無約束問題的一種數值方法,屬于更一般的搜索算法的類別.這二者都使用了單純形的概念,它是N維中的N + 1個頂點的凸包,是一個多胞體：直線上的一個線段,平面上的一個三角形,三維空間中的一個四面體,等等.