高培旺

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

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

高培旺

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

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

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

1 引言

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

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

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

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

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

（LP）

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

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

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

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

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

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

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

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

算法A

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

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

步驟5）取列指標(biāo)l，滿足：ail=1m≤a

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

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

算法B

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

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

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

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

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

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

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

續(xù)表1

4 結(jié)束語(yǔ)

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

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

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

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

[3]白巖.線性規(guī)劃中兩階段法的簡(jiǎn)便計(jì)算法[J].長(zhǎng)春師范學(xué)院學(xué)報(bào)（自然科學(xué)版），2005，24（5）：1-3.

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

[5]江樹(shù)彬，周傳世.解線性規(guī)劃問(wèn)題的一種半單純形法[J].華南理工大學(xué)學(xué)報(bào)，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].運(yùn)籌與管理，2004，13（1）：7-10.

[8]高國(guó)成，王卓鵬，劉曉妍.線性規(guī)劃問(wèn)題的規(guī)范型算法[J].運(yùn)籌與管理，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ī)劃問(wèn)題的一種半單純形法的注記[J].南通大學(xué)學(xué)報(bào)（自然科學(xué)版），2011，36（1）：19-21.

[11]王全文，吳育華，吳振奎，等.單純形法選擇進(jìn)出基變?cè)囊粋€(gè)新準(zhǔn)則[J].數(shù)學(xué)的實(shí)踐與認(rèn)識(shí)，2009，39（14）：75-81.

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

[13]高培旺.關(guān)于“單純形法選擇進(jìn)出基變?cè)囊粋€(gè)新準(zhǔn)則”的計(jì)算效率[J].河南工程學(xué)院學(xué)報(bào)（自然科學(xué)版），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

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

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