王麗芳

(廣州工程技術(shù)職業(yè)學院石化工程系，廣東 廣州 510726)

基于攝動法解決病態(tài)單純形法的一點改進

王麗芳

(廣州工程技術(shù)職業(yè)學院石化工程系，廣東 廣州 510726)

對一般的攝動法解決病態(tài)單純形法的方法進行了改進，給出了簡單的證明。

線性規(guī)劃；攝動法；退化；基可行解；最優(yōu)解

考慮下列線性規(guī)劃問題：

mincx

s.t.Ax=bx≥0

(1)

式中，A是m×n矩陣，秩為m；b≥0。

在線性規(guī)劃問題標準化以后，設系數(shù)矩陣的秩為m，變量個數(shù)為n，在基解或基可行解的概念中，n-m個非基變量都等于0，m個基變量由線性方程組惟一解出，一般為正分量，若有一個或一個以上基變量為0，則定義為退化情形，或稱退化解。

現(xiàn)在使右端向量b攝動，令：

(2)

式中，ε是充分小的正數(shù)；pj是矩陣A的第j列。得到線性規(guī)劃問題(1)的攝動問題：

mincx

s.t.Ax=b(ε)x≥0

(3)

下面證明，當ε取某些數(shù)值時，攝動問題(3)是非退化問題，并且可以通過求解攝動問題(3)來確定線性規(guī)劃問題(1)的最優(yōu)解或得出其他結(jié)論［1］。

定理1對于線性規(guī)劃問題(1)，存在實數(shù)ε1≥0使得當0<ε<ε1時，攝動問題(3)是非退化的。

把式(4)按分量寫出：

(5)

式中，J是非基變量下標集；xBi是基變量。

在B下，攝動問題(3)的基本解是:

(6)

把式(6)的右端可看作z的多項式：

(7)

根據(jù)定理1，利用單純形方法解攝動問題(3)時，不會出現(xiàn)循環(huán)現(xiàn)象。下面分析由求解問題(3)的結(jié)果能夠給出線性規(guī)劃問題(1)的最優(yōu)解或給出關(guān)于線性規(guī)劃問題(1)的解的狀況的其他結(jié)論［3］。

定理3若攝動問題(3)沒有可行解，則線性規(guī)劃問題(1)也沒有可行解。

定理4若對充分小的ε>0，攝動問題(3)是無界問題，則線性規(guī)劃問題(1)也是無界問題。

綜上所述，攝動問題(3)當ε充分小時一定是非退化的，因此能夠避免循環(huán)現(xiàn)象，并且通過求解攝動問題(3)一定能給出線性規(guī)劃問題(1)的解答。這樣，從根本上解決了可能發(fā)生的循環(huán)問題。

例1

初始單純形表如表1。取第4列為主列，先比較多項式的零次項的系數(shù)，再比較一次項的系數(shù)，即第1列中第1行及第2行的元素分別除以主列(第4行)中對應的正元素，取其最小比值(最小值為2),于是取表1第2行為主行，主元為12，經(jīng)主元消去得到如表2的單純形表。

表1 初始單純形表

再以表2中以第3行為主行，主元為1，經(jīng)主元消去得到如表3的單純形表。

表2 以第2行為主行消去主元后的單純形表

表3 以第3行為主行消去主元后的單純形表

經(jīng)2次迭代得到最優(yōu)解和目標函數(shù)最優(yōu)值：

例1是一個退化問題，即存在退化問題的基本可行解，用一般單純形方法求解時出現(xiàn)循環(huán)現(xiàn)象，而采用攝動法就成功地避免了循環(huán)的發(fā)生。

［1］徐成賢.近代優(yōu)化方法［M］.北京:科學出版社，2009.

［2］ 袁亞湘,孫文瑜.最優(yōu)化理論和算法［M］.北京:科學出版社,1997.

［3］ 中國人民大學數(shù)學教研室.線性規(guī)劃［M］.北京:中國人民大學出版社，1988.

10.3969/j.issn.1673-1409(N).2012.07.003

O224

A

1673-1409(2012)07-N005-03

2012-04-16

王麗芳(1966-),女，1987年大學畢業(yè),高級講師,現(xiàn)主要從事最優(yōu)化方法方面的教學與研究工作。

［編輯］ 洪云飛