由George Dantzig發明的單純形法（simplex algorithm）在數學最佳化領域中常用於線性規劃問題的數值求解。原單純形法不是很經濟的算法。1953年美國數學家G.B.丹齊克為了改進單純形法每次疊代中積累起來的進位誤差，提出改進單純形法。其基本步驟和單純形法大致相同，主要區別是在逐次疊代中不再以高斯消去法為基礎，而是由舊基陣的逆去直接計算新基陣的逆，再由此確定檢驗數。這樣做可以減少疊代中的累積誤差，提高計算精度，同時也減少了在計算機上的存儲量。
基本介紹
- 中文名：改進單純形法
- 外文名：modified simplex method
- 提出時間：1965 年
- 提出者：J.A.Nelder 等
單純形法,簡介,單純形法的提出及依據,單純形法的基本思想,單純形法的特點,改進的單純形法,
單純形法
簡介
由GeorgeDantzig發明的單純形法（simplexalgorithm）在數學最佳化領域中常用於線性規劃問題的數值求解。
Nelder-Mead法或稱下山單純形法，與單純形法名稱相似，但二者關聯不大。該方法由Nelder和Mead於1965年發明，是用於最佳化多維無約束問題的一種數值方法，屬於更普遍的搜尋算法的類別。這兩種方法都使用了單純形的概念。單純形是
維中的
個頂點的凸包，是一個多胞體：直線上的一個線段，平面上的一個三角形，三維空間中的一個四面體等等，都是單純形。
單純形法的提出及依據
單純形法是美國數學家GeorgeDantzig於1947年首先提出的。其理論根據是：線性規劃問題的可行域是n維向量空間R中的多面凸集，其最優值如果存在必在該凸集的某頂點處達到，該頂點所對應的可行解稱為基本可行解。
單純形法的基本思想
單純形法是一種多變數函式的尋優方法，其主要思想是先找一個基本可行解，判斷是否為最優解，如果不是則找另外一個解，再進行判定，如此疊代運算，直至找到最優解或者判定其無界。
單純形法的特點
單純形法是一種直接、快速的搜尋最小值方法，其優點是對目標函式的解析性沒有要求，收斂速度快，適用面較廣。
單純形法的一般解題步驟可歸納如下：
- 把線性規劃問題的約束方程組表達成典範型方程組，找出基本可行解作為初始基本可行解。
- 若基本可行解不存在，即約束條件有矛盾，則問題無解。
- 若基本可行解存在，從初始基本可行解作為起點，根據最優性條件和可行性條件，引入非基變數取代某一基變數，找出目標函式值更優的另一基本可行解。
- 按步驟3進行疊代，直到對應檢驗數滿足最優性條件（這時目標函式值不能再改善），即得到問題的最優解。
- 若疊代過程中發現問題的目標函式值無界，則終止疊代。
改進的單純形法
原單純形法不是很經濟的算法。1953年美國數學家G.B.丹齊克為了改進單純形法每次疊代中積累起來的進位誤差，提出改進單純形法。其基本步驟和單純形法大致相同，主要區別是在逐次疊代中不再以高斯消去法為基礎，而是由舊基陣的逆去直接計算新基陣的逆，再由此確定檢驗數。這樣做可以減少疊代中的累積誤差，提高計算精度，同時也減少了在計算機上的存儲量。
改進的單純形法是在單純形操作中引入變異操作，以此來增強全局搜尋能力。具體做法是：
首先，進行基本單純形法操作，快速得到局部極小值，再對極小值點在取值範圍內進行變異操作，並重新進行基本單純形法操作，直到得到最優解為止。該算法的計算步驟如下：
1.選取初始單純形，初始步長L，最大變異次數mmax，計數器m=0；
2.進行基本單純形操作，找到一個極值點X1；
3.以極值點置作新的頂點，再選取初始單純形，並進行新一輪的單純形操作，得到新的極值點，兩極值點對應的目標函式為R1，R2；
4.若R1>R2，R1=R2，X1=X2，代入
其中(i=1,2,…,t)，Ximax、Ximin為參數X_i的上、下限；
為0到1之間的隨機數。
5.若
，對進行變異操作，計數器m=m+1：
6.若計數器m<mmax，轉(1)，否則輸出結果X1。
