單純形法

用手机看条目

出自 MBA智库百科(https://wiki.mbalib.com/)

單純形法(Simplex Method)

目錄

單純形法的提出及依據[1]

  單純形法是美國數學家George Dantzig於1947年首先提出的。

  其理論根據是:線性規劃問題的可行域是n維向量空間Rn中的多面凸集,其最優值如果存在必在該凸集的某頂點處達到,該頂點所對應的可行解稱為基本可行解。

單純形法的基本思想

  單純形法是一種多變數函數的尋優方法,其主要思想是先找一個基本可行解,判斷是否為最優解,如果不是則找另外一個解,再進行判定,如此迭代運算,直至找到最優解或者判定其無界。

單純形法的特點

  單純形法是一種直接、快速的搜索最小值方法,其優點是對目標函數的解析性沒有要求,收斂速度快,適用面較廣。

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

  1.把線性規劃問題的約束方程組表達成典範型方程組,找出基本可行解作為初始基本可行解。

  2.若基本可行解不存在,即約束條件有矛盾,則問題無解。

  3.若基本可行解存在,從初始基本可行解作為起點,根據最優性條件和可行性條件,引入非基變數取代某一基變數,找出目標函數值更優的另一基本可行解。

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

  5.若迭代過程中發現問題的目標函數值無界,則終止迭代。

改進的單純形法[2]

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

  改進的單純形法是在單純形操作中引入變異操作,以此來增強全局搜索能力。具體做法是:

  首先,進行基本單純形法操作,快速得到局部極小值,再對極小值點在取值範圍內進行變異操作,並重新進行基本單純形法操作,直到得到最優解為止。該演算法的計算步驟如下:

  (1)選取初始單純形,初始步長L,最大變異次數mmax,計數器m=0;

  (2)進行基本單純形操作,找到一個極值點X1

  (3)以極值點置作新的頂點,再選取初始單純形,併進行新一輪的單純形操作,得到新的極值點,兩極值點對應的目標函數為R1,R2

  (4)若R1 > R2,R1 = R2,X1 = X2,

  代入:X_i=X_i+\S_i(X_i{\max}-X_i{\min})  (i=1,2,…,t)(1)

式中,XimaxXimin為參數X_i的上、下限;\S_i為0到1之間的隨機數。

  (5)若R_1\le R_2,對進行變異操作,計數器m=m+1:

  (6)若計數器m < mmax,轉(1),否則輸出結果X1

實例

Image:Ddd1.jpg

即求max:x1+x2,列單純形表(即矩陣):

Image:Ddd2.jpg

Image:Ddd3.jpg

單純形法原理

原理1,根據方程組消元法對矩陣進行行變換,變換後約束條件等價不變。如以上實例。

原理2,令非基變數為0,此時基變數的取值滿足約束條件。單純形法正是通過消元法交換基變數和非基變數,令非基變數為0,以求達到目標函數最優值的基變數組合。基變數即為繫數為1,0的變數。 圖解如下: 初始,將非基變數和基變數分為各自兩部分,

Image:Ddd9.jpg

對矩陣進行行變換,

Image:Ddd8.jpg

如圖所示,令非基變數為0,此時基變數的取值仍滿足約束條件。基變數的取值為Image:Latex.gif

原理3,對實例中c行的變換的解釋: 將基變數用非基變數表示如下圖,

Image:Ddd7.jpg

x1到xm即基變數。

Image:Ddd6.jpg

Image:Ddd5.jpg

c行所進行的變換就是求上圖中的Image:Latex22.gif

顯然當Image:Latex22.gif的累加值小於0時,令非基變數為0則Z(實例中x1+x2)達到最大。

參考文獻

  1. 劉勇,陳國東.基於單純形法的LINGO求解一般指派問題的探討[J].中國管理信息化.2008(6)
  2. 李春風,許承權,蒲文利.改進的單純形法及其在非線性參數估計中的應用[J].海洋測繪,2009,29(6)
本條目對我有幫助19
MBA智库APP

扫一扫,下载MBA智库APP

分享到:
  如果您認為本條目還有待完善,需要補充新內容或修改錯誤內容,請編輯條目

本条目由以下用户参与贡献

Yixi,卓奕涛.

評論(共1條)

提示:評論內容為網友針對條目"單純形法"展開的討論,與本站觀點立場無關。
Lvshaofei (討論 | 貢獻) 在 2011年3月2日 23:31 發表

很具體,很實用

回複評論

發表評論請文明上網,理性發言並遵守有關規定。

MBA智库
打开APP

以上内容根据网友推荐自动排序生成