高培旺

（閩江學院數(shù)學系，福建福州 350108）

線性規(guī)劃問題規(guī)范型算法的改進及計算機實現(xiàn)

高培旺

（閩江學院數(shù)學系，福建福州 350108）

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

線性規(guī)劃；可行基；單純形算法；規(guī)范型；計算機實現(xiàn)

1 引言

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

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

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

2 線性規(guī)劃規(guī)范型算法的改進

考慮如下形式的線性規(guī)劃問題：

（LP）

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

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

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

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

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

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

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

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

算法A

步驟1）置i=1，轉(zhuǎn)下一步.

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

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

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

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

算法B

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

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

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

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

3 規(guī)范型算法改進的計算機實現(xiàn)

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

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

續(xù)表1

4 結(jié)束語

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

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

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

[2]黃紅選，韓繼業(yè).數(shù)學規(guī)劃[M].北京：清華大學出版社，2006.

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

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

[5]江樹彬，周傳世.解線性規(guī)劃問題的一種半單純形法[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]李煒.求線性規(guī)劃初始可行基的新方法[J].運籌與管理，2004，13（1）：7-10.

[8]高國成，王卓鵬，劉曉妍.線性規(guī)劃問題的規(guī)范型算法[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]高培旺.關(guān)于解線性規(guī)劃問題的一種半單純形法的注記[J].南通大學學報（自然科學版），2011，36（1）：19-21.

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

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

[13]高培旺.關(guān)于“單純形法選擇進出基變元的一個新準則”的計算效率[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

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

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