單純形法 simplex method 求解線性規劃問題的通用方法。單純形是美國數學家G.B.丹齊克於1947年首先提出來的。它的理論根據是：線性規劃問題的可行域是 n維向量空間Rn中的多面凸集，其最優值如果存在必在該凸集的某頂點處達到。頂點所對應的可行解稱為基本可行解。單純形法的基本思想是：先找出一個基本可行解，對它進行鑑別，看是否是最優解；若不是，則按照一定法則轉換到另一改進的基本可行解,再鑑別；若仍不是，則再轉換,按此重複進行。因基本可行解的個數有限，故經有限次轉換必能得出問題的最優解。如果問題無最優解也可用此法判別。 根據單純形法的原理，在線性規劃問題中，決策變數（控制變數）x1，x2，…x n的值稱為一個解,滿足所有的約束條件的解稱為可行解。使目標函式達到最大值（或最小值）的可行解稱為最優解。這樣，一個最優解能在整個由約束條件所確定的可行區域內使目標函式達到最大值（或最小值）。求解線性規劃問題的目的就是要找出最優解。 最優解可能出現下列情況之一：①存在著一個最優解；②存在著無窮多個最優解；③不存在最優解，這隻在兩種情況下發生，即沒有可行解或各項約束條件不阻止目標函式的值無限增大（或向負的方向無限增大）。 單純形法的一般解題步驟可歸納如下：①把線性規劃問題的約束方程組表達成典範型方程組，找出基本可行解作為初始基本可行解。②若基本可行解不存在，即約束條件有矛盾，則問題無解。③若基本可行解存在，從初始基本可行解作為起點，根據最優性條件和可行性條件，引入非基變數取代某一基變數，找出目標函式值更優的另一基本可行解。④按步驟3進行迭代,直到對應檢驗數滿足最優性條件（這時目標函式值不能再改善），即得到問題的最優解。⑤若迭代過程中發現問題的目標函式值無界，則終止迭代。 用單純形法求解線性規劃問題所需的迭代次數主要取決於約束條件的個數。現在一般的線性規劃問題都是應用單純形法標準軟體在計算機上求解，對於具有106個決策變數和104個約束條件的線性規劃問題已能在計算機上解得。 改進單純形法 原單純形法不是很經濟的演算法。1953年美國數學家G.B.丹齊克為了改進單純形法每次迭代中積累起來的進位誤差，提出改進單純形法。其基本步驟和單純形法大致相同，主要區別是在逐次迭代中不再以高斯消去法為基礎，而是由舊基陣的逆去直接計算新基陣的逆，再由此確定檢驗數。這樣做可以減少迭代中的累積誤差，提高計算精度，同時也減少了在計算機上的儲存量。 對偶單純形法 1954年美國數學家C.萊姆基提出對偶單純形法。單純形法是從原始問題的一個可行解透過迭代轉到另一個可行解，直到檢驗數滿足最優性條件為止。對偶單純形法則是從滿足對偶可行性條件出發透過迭代逐步搜尋原始問題的最優解。在迭代過程中始終保持基解的對偶可行性，而使不可行性逐步消失。設原始問題為min{cx|Ax=b，x≥0}，則其對偶問題為 max{yb|yA≤c}。當原始問題的一個基解滿足最優性條件時,其檢驗數cBB-1A-c≤0。即知y＝cBB-1（稱為單純形運算元）為對偶問題的可行解。所謂滿足對偶可行性，即指其檢驗數滿足最優性條件。因此在保持對偶可行性的前提下，一當基解成為可行解時，便也就是最優解。 數學最佳化中，由George Dantzig發明的單純形法是線性規劃問題的數值求解的流行技術。有一個演算法與此無關，但名稱類似，它是Nelder-Mead法或稱下山單純形法，由Nelder和Mead發現（1965年），這是用於最佳化多維無約束問題的一種數值方法，屬於更一般的搜尋演算法的類別。 這二者都使用了單純形的概念，它是N維中的N + 1個頂點的凸包，是一個多胞體：直線上的一個線段，平面上的一個三角形，三維空間中的一個四面體，等等。
單純形法 simplex method 求解線性規劃問題的通用方法。單純形是美國數學家G.B.丹齊克於1947年首先提出來的。它的理論根據是：線性規劃問題的可行域是 n維向量空間Rn中的多面凸集，其最優值如果存在必在該凸集的某頂點處達到。頂點所對應的可行解稱為基本可行解。單純形法的基本思想是：先找出一個基本可行解，對它進行鑑別，看是否是最優解；若不是，則按照一定法則轉換到另一改進的基本可行解,再鑑別；若仍不是，則再轉換,按此重複進行。因基本可行解的個數有限，故經有限次轉換必能得出問題的最優解。如果問題無最優解也可用此法判別。 根據單純形法的原理，在線性規劃問題中，決策變數（控制變數）x1，x2，…x n的值稱為一個解,滿足所有的約束條件的解稱為可行解。使目標函式達到最大值（或最小值）的可行解稱為最優解。這樣，一個最優解能在整個由約束條件所確定的可行區域內使目標函式達到最大值（或最小值）。求解線性規劃問題的目的就是要找出最優解。 最優解可能出現下列情況之一：①存在著一個最優解；②存在著無窮多個最優解；③不存在最優解，這隻在兩種情況下發生，即沒有可行解或各項約束條件不阻止目標函式的值無限增大（或向負的方向無限增大）。 單純形法的一般解題步驟可歸納如下：①把線性規劃問題的約束方程組表達成典範型方程組，找出基本可行解作為初始基本可行解。②若基本可行解不存在，即約束條件有矛盾，則問題無解。③若基本可行解存在，從初始基本可行解作為起點，根據最優性條件和可行性條件，引入非基變數取代某一基變數，找出目標函式值更優的另一基本可行解。④按步驟3進行迭代,直到對應檢驗數滿足最優性條件（這時目標函式值不能再改善），即得到問題的最優解。⑤若迭代過程中發現問題的目標函式值無界，則終止迭代。 用單純形法求解線性規劃問題所需的迭代次數主要取決於約束條件的個數。現在一般的線性規劃問題都是應用單純形法標準軟體在計算機上求解，對於具有106個決策變數和104個約束條件的線性規劃問題已能在計算機上解得。 改進單純形法 原單純形法不是很經濟的演算法。1953年美國數學家G.B.丹齊克為了改進單純形法每次迭代中積累起來的進位誤差，提出改進單純形法。其基本步驟和單純形法大致相同，主要區別是在逐次迭代中不再以高斯消去法為基礎，而是由舊基陣的逆去直接計算新基陣的逆，再由此確定檢驗數。這樣做可以減少迭代中的累積誤差，提高計算精度，同時也減少了在計算機上的儲存量。 對偶單純形法 1954年美國數學家C.萊姆基提出對偶單純形法。單純形法是從原始問題的一個可行解透過迭代轉到另一個可行解，直到檢驗數滿足最優性條件為止。對偶單純形法則是從滿足對偶可行性條件出發透過迭代逐步搜尋原始問題的最優解。在迭代過程中始終保持基解的對偶可行性，而使不可行性逐步消失。設原始問題為min{cx|Ax=b，x≥0}，則其對偶問題為 max{yb|yA≤c}。當原始問題的一個基解滿足最優性條件時,其檢驗數cBB-1A-c≤0。即知y＝cBB-1（稱為單純形運算元）為對偶問題的可行解。所謂滿足對偶可行性，即指其檢驗數滿足最優性條件。因此在保持對偶可行性的前提下，一當基解成為可行解時，便也就是最優解。 數學最佳化中，由George Dantzig發明的單純形法是線性規劃問題的數值求解的流行技術。有一個演算法與此無關，但名稱類似，它是Nelder-Mead法或稱下山單純形法，由Nelder和Mead發現（1965年），這是用於最佳化多維無約束問題的一種數值方法，屬於更一般的搜尋演算法的類別。 這二者都使用了單純形的概念，它是N維中的N + 1個頂點的凸包，是一個多胞體：直線上的一個線段，平面上的一個三角形，三維空間中的一個四面體，等等。