基于攝動法解決病態單純形法的一點改進

王麗芳

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

基于攝動法解決病態單純形法的一點改進

王麗芳

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

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

線性規劃；攝動法；退化；基可行解；最優解

考慮下列線性規劃問題：

mincx

s.t.Ax=bx≥0

(1)

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

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

現在使右端向量b攝動，令：

(2)

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

mincx

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

(3)

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

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

把式(4)按分量寫出：

(5)

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

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

(6)

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

(7)

根據定理1，利用單純形方法解攝動問題(3)時，不會出現循環現象。下面分析由求解問題(3)的結果能夠給出線性規劃問題(1)的最優解或給出關于線性規劃問題(1)的解的狀況的其他結論［3］。

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

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

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

例1

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

表1 初始單純形表

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

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

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

經2次迭代得到最優解和目標函數最優值：

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

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

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

［3］ 中國人民大學數學教研室.線性規劃［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年大學畢業,高級講師,現主要從事最優化方法方面的教學與研究工作。

［編輯］ 洪云飛