線性規劃問題規范型算法的改進及計算機實現

高培旺

（閩江學院數學系，福建福州 350108）

線性規劃問題規范型算法的改進及計算機實現

高培旺

（閩江學院數學系，福建福州 350108）

線性規劃的規范性算法是從一個初始基出發，通過一種單純形變式求得可行基的方法.提出了求等式約束方程的初始基的方法，該方法不需要計算輔助目標函數的縮減費用，在約束無冗余的假定下經過至多m（等式個數）次迭代后一定得到一個初始基或者問題無可行基的結論，并對規范型算法進行了簡化.為了驗證改進的規范型算法的計算性能，通過MATLAB編程在計算機上實現大規模數值試驗，結果表明，與經典單純形算法相比，改進的算法平均每次迭代花費更少的執行時間，因而具有更高的計算效率，且隨著問題規模的擴大，其計算優越性更明顯.

線性規劃；可行基；單純形算法；規范型；計算機實現

1 引言

單純形法是求解線性規劃實際問題非常有效的算法，由于其在選擇初始頂點和迭代路徑上的靈活性，因而引起了許多研究者的興趣.對于含有等式約束的線性規劃問題，常采用經典的兩階段法[1-2]來求解.在第一階段單純形算法中，每個等式需要引入一個人工變量，然后使人工變量之和最小作為輔助的目標函數，以獲得問題的一個初始可行解.為了改進第一階段單純形算法，人們提出了一種設想：盡可能少地引入人工變量[3-4]或不引入人工變量[5-8].然而，Enge和Huhn[9]，文獻[10]都指出，一些無人工變量的初等變換方法實際上隱含著人工變量，只不過字面上沒有寫出來而已.在初等變換過程中每產生一個新的單位列向量，相當于主樞軸元所在行的人工變量從基中旋轉出去.

文獻[8]提出了一種線性規劃問題的規范性算法，有趣的是，該算法在獲得一個初始基（不可行）的前提下，通過簡單而巧妙的初等變換，將右手邊全部化成非負項，產生了規范型LP（2），繼而以變換前最負右手邊所對應的等式約束為“目標”，給出了一種單純形算法.該算法非常類似于“選擇進出基變元的新準則”[11-12]，其目的就是在每次迭代過程中使目標函數獲得最大的增益，雖然這種方法對某些問題可以減少迭代次數，但逐列搜尋樞軸主元的過程會帶來指數時間的計算工作量[9]，從而造成總的計算效率下降，文獻[13]通過對中大規模問題的計算試驗證實了這一點.注意到這種規范性算法是從一個初始基（不可行）出發求得可行基的過程，因而是一種后處理方法，但文獻[8]并沒有給出在等式約束條件下求一個初始基的方法.

本文提出了求等式約束方程的初始基的方法，該方法不需要計算輔助目標函數的縮減費用，在約束相容且無冗余的假定下經過與等式個數相同的迭代次數后一定得到一個初始基.如果這個初始基是不可行的，為了方便快捷地獲得一個可行基，對規范型算法進行了簡化，一是最負右手邊所對應的等式約束保持不變，即該等式約束的右手邊在變換后仍然為負；二是應用經典單純形算法的“最負判別數準則”選擇樞軸列.為了驗證改進的規范型算法的計算性能，我們從線性規劃標準測試庫NETLIB[14]和整數規劃標準測試庫MIPLIB[15]中選取了26個典型算例，通過MATLAB編程在計算機上實現大規模數值試驗，結果表明，與經典單純形算法相比，本文提出的改進算法對大部分問題具有更高的計算效率，且隨著問題規模的擴大，其計算優越性更加明顯.

2 線性規劃規范型算法的改進

考慮如下形式的線性規劃問題：

（LP）

這里，A∈Rm×n（m＜n），且假定rank(A)=m，c、b是相應維數的向量，且b≥0.

在（LP）的等式約束條件中引入非負人工變量向量xArt∈Rm，構造一個人工單位基I∈Rm×m如下：

通過基變量與非基變量的樞軸交換將產生新的基，用B表示，令B-1A=(aˉij)，B-1b=，顯然，當0時，相應的基是可行的；否則，不可行.下面的命題給出了判斷問題（LP）不可行性的一個準則.

證明對于x≥0，xArt=0，第i個含有人工基變量的等式約束可以表示為：

這意味著在x≥0，xArt=0中沒有滿足第i個約束的變量取值，因而問題（LP）無可行解.類似地，可以證明如果＞0時，有≤0，則問題（LP）亦無可行解.

在無冗余約束的假定下，下列命題明顯成立.

命題2假定rank(A)=m，對于含有人工基變量的任意第（i1≤i≤m）個約束，取=，如果=0，則必有＞0.

基于上述命題，我們可以將人工基變量逐一從基中旋轉出去，具體算法步驟描述如下：

算法A

步驟1）置i=1，轉下一步.

步驟2）如果i=m，算法以獲得一個初始基結束；否則，如果，轉步驟3）；如果，轉步驟4）；如果bi＞0，轉步驟5）.

步驟5）取列指標l，滿足：ail=1m≤a

j≤xn(aij)，如果ail≤0，算法結束，（LP）無可行解；否則，以ail為主樞軸元進行旋轉變換，置i=i+1，返回步驟2）.

在上述算法步驟3）～5）中，如果算法沒有以（LP）無可行解而結束，則主樞軸元ail≠0，樞軸交換可以逐行進行下去，這樣經過m次樞軸交換，我們就可以獲得（LP）的一個初始基，仍用B表示.進一步，若b≥0，這個初始基是可行的，第一階段算法結束；否則，基B是不可行的，由此出發，我們提出改進的規范型算法來獲取（LP）的一個可行基（如果存在），計算步驟可詳細敘述如下：

算法B

在第k行中再加入一個人工基變量，轉下一步.

步驟8）如果r=k，算法結束，（LP）的一個可行基已經取得；否則，返回步驟7）.

通過執行上述算法步驟，我們或者獲得原問題的一個基本可行解，或者得到問題無可行解的事實.

表1 第一階段問題經典單純形算法和新的單純形算法的計算比較

3 規范型算法改進的計算機實現

為了驗證改進的規范型算法的計算性能，本文從線性規劃標準測試庫NETLIB[14]和混合整數規劃標準測試庫MIPLIB[15]中選取了26個典型算例，其中，問題air01、enigma、lp41、mod010屬于整數規劃問題，我們只求解其相應的線性規劃松弛問題的解.接下來，我們使用MATLAB V7.1語言對經典單純形算法和改進的規范型算法進行了編程，在Lenovo PentiumM計算機上執行數值試驗，以對兩種算法的計算效率進行比較.數值試驗的環境是完全相同的，計算結果如表1所示，其中，Iters表示求解線性規劃問題所需要的樞軸（迭代）數，Time表示所耗費的總的計算時間（單位為秒）.

從表1我們可以看到，改進的規范型算法在每一個問題上平均迭代一次所耗費的計算時間都要比經典的單純形算法少，并且，改進的規范型算法在14個問題上比經典的單純形算法所用的迭代次數少，在5個問題上與經典的單純形算法所用的迭代次數持平，即使在7個問題上比經典的單純形算法所用的迭代次數多，除問題israel外，相差也不大.尤其是，隨著問題決策變量數的增多，規模的擴大，改進的規范型算法一般所用的計算時間更短、計算效率更高.

續表1

4 結束語

本文對文獻[8]的規范型算法作了適當的改進，提出了經過至多m步迭代獲得一個初始基的方法.如果這個基是不可行的，就用改進的規范型算法產生可行基.從數值試驗的結果來看，該算法在大部分問題上比經典單純形算法所用的迭代次數和所耗費的計算時間要少，尤其在一些較大規模的問題上，其計算優越性更加明顯，因而該算法在樞軸方法中是有競爭力的.另外，該算法可以對右手邊為負的不等式約束：A1x≤b1不作任何變換，直接添加松弛變量，因而計算處理更方便，也利于節省存儲空間.

美中不足的是，改進的規范型算法并不是在所有問題上都比經典單純形算法好，這也許與驅動行k的選擇有關.規范型算法的原理就是將驅動行的左邊作為目標函數，應用經典單純形的樞軸準則選擇樞軸行，以使驅動行的右邊取值單調遞增，直到變成零，則產生一個可行基.于是我們設想，如果選擇距離算法A產生的初始點最近的約束超平面作為驅動行，計算效果會否更好？也就是驅動行的右邊能更快地達到非負取值.這將留待以后作進一步研究.

[1]許萬蓉.線性規劃[M].北京：北京理工大學出版社，1990.

[2]黃紅選，韓繼業.數學規劃[M].北京：清華大學出版社，2006.

[3]白巖.線性規劃中兩階段法的簡便計算法[J].長春師范學院學報（自然科學版），2005，24（5）：1-3.

[4]孫可.線性規劃兩階段法的改進算法[J].運籌與管理，2000，9（1）：79-83.

[5]江樹彬，周傳世.解線性規劃問題的一種半單純形法[J].華南理工大學學報，1995，23（6）：93-99.

[6]Arsham H.Initialization of the simplex algorithm:An artificial-free approach[J].SIAM Review,1997,39(4):736-744.

[7]李煒.求線性規劃初始可行基的新方法[J].運籌與管理，2004，13（1）：7-10.

[8]高國成，王卓鵬，劉曉妍.線性規劃問題的規范型算法[J].運籌與管理，2004，13（3）：35-38.

[9]Enge A,Huhn P.A counterexample to H Arsham's"Initialization of the simplex algorithm:An artificial-free approach"[J].SIAM Review,1998,40(4):1-6.

[10]高培旺.關于解線性規劃問題的一種半單純形法的注記[J].南通大學學報（自然科學版），2011，36（1）：19-21.

[11]王全文，吳育華，吳振奎，等.單純形法選擇進出基變元的一個新準則[J].數學的實踐與認識，2009，39（14）：75-81.

[12]申卯興，葉微，劉毅，等.單純形法中樞軸元素選取準則的改進[J].計算機工程與應用，2003，25（1）：57-58.

[13]高培旺.關于“單純形法選擇進出基變元的一個新準則”的計算效率[J].河南工程學院學報（自然科學版），2012，24（2）：61-64.

[14]Dongarra J,Golub G,Grosse E,et al.Netlib and NA-Net:Building a scientific computing community[J].IEEE Annals of the history of computing,2008,30(2):30-41.

[15]Bixby R E,Ceria S,McZeal C M,et al.An updated mixed integer programming library:MIPLIB 3.0[J].Optima,1998,54(1):12-15.

Improvement and Its Computer Implementation of a New Algorithm for Linear Programming

GAO Pei-wang
(Department of Mathematics,Minjiang University,Fuzhou 350108,China)

A new algorithm for the normalized form of linear programming starts from an initial basis and then uses the simplex variant to achieve a feasible basis.This paper presents a method for finding an initial basis of the equality constraints,which does not need to compute the reduced costs of the auxiliary objective function, and under the assumption of no redundancy uses at most m iterations(equal to the number of equality constraints)to get an initial basis or the conclusion of no feasible basis.Furthermore,an improved algorithm of the normalized form is proposed to achieve a feasible basis conveniently and quickly.In the improvement,one is to keep the equality constraint with the most negative right-hand side unchanged,and the other is to apply the rule of the classical simplex method to choose the pivot column.Finally,a computer implementation is accomplished to test the computational performance of our improvement in comparison with the classical simplex algorithm.The computational results show that our improved algorithm averagely spends less executive time at each iteration than the classical simplex algorithm.

linear programming;feasible basis;simplex algorithm;normalized form;computer implementation

O221.1

A

1008-2794（2012）10-0018-05

2012-09-20

閩江學院人才引進基金資助課題“線性規劃樞軸算法的大規模計算比較分析及改進”（MJ2012001）

高培旺（1964—），男，湖南寧遠人，教授，博士，研究方向：最優化理論及其應用．