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