唐滄新，高培旺

（1.廣西財(cái)經(jīng)學(xué)院 信息與統(tǒng)計(jì)學(xué)院，廣西 南寧 530003；2.閩江學(xué)院 數(shù)學(xué)系，福建 福州 350121）

0 引言

單純形法因其在樞軸主元選擇中的靈活性而引起許多研究者的興趣，進(jìn)而產(chǎn)生了許多變式，如MBU單純形算法［1］、梯度單純形算法［2-3］、原始——對偶單純形算法［4］。文獻(xiàn)［5］也提出了一種單純形算法的變式，稱其為符號(hào)跟蹤算法，其思想受到一個(gè)約束條件的最簡單情形的啟發(fā)而產(chǎn)生，即對某個(gè)約束條件而言，正系數(shù)所對應(yīng)的變量中必有一個(gè)是最優(yōu)基變量，因而正系數(shù)是尋找最優(yōu)基變量的有效途徑之一。應(yīng)注意到的是含多個(gè)約束條件的線性規(guī)劃問題遠(yuǎn)比只含一個(gè)約束條件的簡單情形復(fù)雜得多。

針對文獻(xiàn)［5］中提出的問題，本文指出“線性規(guī)劃的符號(hào)跟蹤算法”所獲得的初始基并不一定是原問題的最優(yōu)基，實(shí)際上是第一階段單純形算法的一種變式，只不過輔助目標(biāo)函數(shù)沒有寫出來而加入了原問題的目標(biāo)函數(shù)。由于在入基變量的選擇中沒有遵循最小列檢驗(yàn)比準(zhǔn)則，右手邊有可能產(chǎn)生負(fù)數(shù)項(xiàng)，因而該初始基還有3種其他情況。文獻(xiàn)［6］給出的算法也存在這個(gè)問題，文獻(xiàn)［7-8］對此進(jìn)行了指正。盡管如此，本文擬探討由此初始基出發(fā)，對符號(hào)跟蹤算法的步驟進(jìn)行適當(dāng)修正和補(bǔ)充后，能否更快地到達(dá)原問題的最優(yōu)頂點(diǎn)（如果存在）。為此，我們從線性規(guī)劃標(biāo)準(zhǔn)測試庫NETLIB［9］和混合整數(shù)規(guī)劃標(biāo)準(zhǔn)測試庫MIPLIB［10］中選取了 26 個(gè)典型算例，通過 MAT?LAB編程在計(jì)算機(jī)上實(shí)現(xiàn)大規(guī)模數(shù)值試驗(yàn)，以此檢測該算法的計(jì)算效率。

1 符號(hào)跟蹤算法的描述及補(bǔ)正

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

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

不妨設(shè)B、N分別是（LP）系數(shù)矩陣的基與非基子矩陣，cB、cN分別是基與非基相應(yīng)的費(fèi)用系數(shù)向量。眾所周知，當(dāng)=B-1b≥0時(shí)，基B是原始可行的；當(dāng)判別檢驗(yàn)數(shù)σ=cBB-1A-c≥0時(shí)，基 B是對偶可行的；而當(dāng)≥0且σ≥0時(shí)，基 B既是原始可行又是對偶可行的，因而是最優(yōu)的。

符號(hào)跟蹤算法的原理可簡述為：基于“在正系數(shù)個(gè)數(shù)最少的約束條件中，正系數(shù)所對應(yīng)的變量中必有一個(gè)為最優(yōu)基變量”的推斷，在所有約束條件中找出正系數(shù)個(gè)數(shù)最少的約束（所在行）作為樞軸行，然后通過判別檢驗(yàn)數(shù)與該約束的正系數(shù)之比的最小值確定樞軸列，以搜尋可能的最優(yōu)基變量。然而，這個(gè)推斷是基于一個(gè)約束條件的簡單情形，由此推廣到含多個(gè)約束條件的復(fù)雜問題并沒有理論支持。實(shí)際上，符號(hào)跟蹤算法的樞軸準(zhǔn)則是使正系數(shù)對應(yīng)的判別檢驗(yàn)數(shù)在迭代之后轉(zhuǎn)化為非負(fù)值，僅此而已。因此，符號(hào)跟蹤算法不能保證右手邊向量非負(fù)，也不能保證在初始基產(chǎn)生后，所有判別檢驗(yàn)數(shù)全部轉(zhuǎn)化為非負(fù)值。具體來說，符號(hào)跟蹤算法獲得的初始基（用B表示）有下列4種可能情形：

由此可見，符號(hào)跟蹤算法僅僅求得原問題的一個(gè)初始基而非最優(yōu)基（當(dāng)然這個(gè)初始基有可能是最優(yōu)基），是第一階段單純形算法的變式。由于忽略了這個(gè)事實(shí)，導(dǎo)致符號(hào)跟蹤算法第一步的步驟（3）的結(jié)論是錯(cuò)誤的。當(dāng)原問題的初始基還未產(chǎn)生，亦即還存在人工基變量時(shí)，若存在某個(gè)σs＜0，且該列所有系數(shù)ais≤0，并不意味著“原問題有無界解”。如果把第一階段輔助目標(biāo)函數(shù)寫出來，該列所對應(yīng)的輔助目標(biāo)函數(shù)的判斷檢驗(yàn)數(shù)肯定大于或等于零，因?yàn)榈谝浑A段問題總是有界的。旋轉(zhuǎn)迭代過程按照第一階段單純形算法可以繼續(xù)進(jìn)行下去，直到獲得原問題的一個(gè)初始解或無可行解的結(jié)論。另外，為算法編程處理方便起見，在未產(chǎn)生基決策變量（即含人工基變量）但右端項(xiàng)為負(fù)的約束中，以負(fù)系數(shù)作為搜尋“最優(yōu)基變量”的基準(zhǔn)，這與“方程兩邊乘以-1，再以正系數(shù)為基準(zhǔn)選擇最優(yōu)基變量”是等價(jià)的。

根據(jù)上述對符號(hào)跟蹤算法的分析，我們對符號(hào)跟蹤算法步驟給出適當(dāng)修正和補(bǔ)充，詳細(xì)描述如下：

步驟1 記Arf代表還未產(chǎn)生基決策變量的行標(biāo)集合，一開始，Arf={1，2，…，m}，轉(zhuǎn)下一步。

步驟2 若Arf=?，原問題的初始基B產(chǎn)生，轉(zhuǎn)步驟3。否則，對任意 i∈Arf，如果≥0，計(jì)算第 i個(gè)約束中正系數(shù)的個(gè)數(shù) numi，轉(zhuǎn)步驟4；如果＜0，計(jì)算第i個(gè)約束中負(fù)系數(shù)的個(gè)數(shù)numi，轉(zhuǎn)步驟5。

步驟4 如果 numi=0，當(dāng)＞0時(shí)，原問題無可行解，算法結(jié)束；當(dāng)i=0，該約束為冗余約束，置Arf=Arf{i}，將其去掉。否則，有numi＞0，轉(zhuǎn)步驟6。

步驟5 如果numi=0，原問題無可行解，算法結(jié)束。否則，有numi＞0，轉(zhuǎn)下一步。

步驟6 求得所有numi后，取指標(biāo)r=arg min{numi}作為樞軸行，轉(zhuǎn)下一步。

通過執(zhí)行上述算法步驟，我們或者獲得（LP）的一個(gè)基本可行解，或者得到一個(gè)沒有可行解的事實(shí)。

2 符號(hào)跟蹤算法的數(shù)值試驗(yàn)

盡管符號(hào)跟蹤算法求得的初始基不一定是原問題的最優(yōu)基，但如果由此獲得的初始解位于最優(yōu)頂點(diǎn)的附近，就可以通過更少的迭代次數(shù)到達(dá)最優(yōu)頂點(diǎn)。然而，符號(hào)跟蹤算法的樞軸準(zhǔn)則增加了計(jì)算的復(fù)雜性，如果這種計(jì)算復(fù)雜性能通過減少迭代次數(shù)得到彌補(bǔ)，使耗費(fèi)的總的計(jì)算時(shí)間更少，那么符號(hào)跟蹤算法是有意義的。因此，有必要通過大規(guī)模數(shù)值試驗(yàn)對符號(hào)跟蹤算法的計(jì)算效率進(jìn)行檢驗(yàn)。

筆者從線性規(guī)劃標(biāo)準(zhǔn)測試庫NETLIB［9］和混合整數(shù)規(guī)劃標(biāo)準(zhǔn)測試庫MIPLIB［10］中選取了26個(gè)典型算例，其中，問題 air01、enigma、lp41、mod010屬于整數(shù)規(guī)劃問題，我們只求其相應(yīng)的線性規(guī)劃松弛問題的解。接下來，使用MATLAB V7.1語言對經(jīng)典單純形算法和符號(hào)跟蹤算法進(jìn)行編程，在Lenovo ThinkCenter M9201z計(jì)算機(jī)上執(zhí)行對所選取的26個(gè)算例的數(shù)值試驗(yàn)，以對兩種算法的計(jì)算效率進(jìn)行比較。數(shù)值試驗(yàn)的環(huán)境是完全相同的，計(jì)算結(jié)果如表1所示，其中，Iters表示求解線性規(guī)劃問題所需要的樞軸（迭代）數(shù)，Time表示所耗費(fèi)的總的計(jì)算時(shí)間（單位為s）。另外，用Type表示在符號(hào)跟蹤算法中所獲得的初始基的類型，看看出現(xiàn)第一種類型的問題有多少。

從表1看到，符號(hào)跟蹤算法求解26個(gè)算例產(chǎn)生的初始基沒有第一種類型的，這再一次印證了本文前面的分析。在迭代求解過程中，符號(hào)跟蹤算法在18個(gè)算例中所使用的迭代次數(shù)確實(shí)比經(jīng)典單純形算法少，甚至在問題air01、scsd1、lp41、mod010中所用迭代次數(shù)遠(yuǎn)遠(yuǎn)少于經(jīng)典單純形算法，這說明符號(hào)跟蹤算法獲得的初始解一般都比較靠近原問題的最優(yōu)頂點(diǎn)。然而，由于在樞軸行和樞軸列的選擇中耗費(fèi)了過多的計(jì)算時(shí)間，除問題israel、air01外，符號(hào)跟蹤算法在其他24個(gè)問題上所耗用的總的計(jì)算時(shí)間比經(jīng)典單純形算法還要多。特別是，符號(hào)跟蹤算法在問題scsd1、lp1、mod010上所使用的迭代次數(shù)不及經(jīng)典單純形算法的一半，卻耗用了比經(jīng)典單純形算法更多的計(jì)算時(shí)間?？梢?，符號(hào)跟蹤算法樞軸準(zhǔn)則的計(jì)算復(fù)雜性不能從迭代次數(shù)的減少中得到補(bǔ)償。一般地，符號(hào)跟蹤算法平均每次迭代要花費(fèi)更多的執(zhí)行時(shí)間，導(dǎo)致符號(hào)跟蹤算法的計(jì)算效率較低。

表1 經(jīng)典單純形算法與符號(hào)跟蹤算法的計(jì)算比較

3 結(jié)論

修正（對偶）單純形算法在樞軸列（行）的選擇計(jì)算中是最簡單的樞軸準(zhǔn)則之一，且在每次迭代之后，只需計(jì)算基逆矩陣和樞軸列（行）的系數(shù)，計(jì)算過程簡單而方便，旋轉(zhuǎn)迭代計(jì)算對所有單純形變式都是一樣的。因此，修正（對偶）單純形算法的運(yùn)算量相對而言是較小的。經(jīng)典單純形算法的缺陷之一是從一個(gè)頂點(diǎn)迭代到另一個(gè)與之相鄰的頂點(diǎn)，導(dǎo)致迭代進(jìn)程太慢，尤其是接近最優(yōu)頂點(diǎn)的時(shí)候。

Enge和Huhn［11］指出，逐列（行）搜尋樞軸主元的過程會(huì)帶來指數(shù)時(shí)間的計(jì)算工作量，從而造成總的計(jì)算效率下降。本文通過對中大規(guī)模問題的數(shù)值試驗(yàn)證實(shí)了這一點(diǎn)?？梢?，要找到一個(gè)好的單純形樞軸準(zhǔn)則和計(jì)算方法，以進(jìn)一步改進(jìn)經(jīng)典單純形算法的計(jì)算效率并不是一件容易的事情，需要我們不斷地思考和嘗試，進(jìn)行嚴(yán)謹(jǐn)?shù)睦碚摲治龊痛笠?guī)模數(shù)值試驗(yàn)。

［1］Anstreicher K M，Terlaky T.A monotonic build-up sim?plex algorithm for linear programming［J］.Operations Research，1994，42（3）：556-561.

［2］Forrest J，Goldfarb D.Steepest-edge simplex algorithm for linear programming［J］.Mathematical Program?ming，1992，57（1）：341-374.

［3］Vemuganti R R.On gradient simplex methods for linear programs［J］.Journal of Applied Mathematics and Deci?sion Sciences，2004，8（2）：107-129.

［4］Curet N D.A primal-dual simplex method for linear programs［J］.Operations Research Letters，1993，13（5）：233-237.

［5］唐建國.線性規(guī)劃的符號(hào)跟蹤算法［J］.運(yùn)籌與管理，2005，14（3）：55-59.

［6］唐建國.線性規(guī)劃的目標(biāo)函數(shù)最速遞減算法［J］.運(yùn)籌與管理，2005，14（4）：55-59.

［7］夏少剛，鄭直，費(fèi)威.與“求線性規(guī)劃問題可行基的一種方法”的再商榷［J］.運(yùn)籌與管理，2006，15（3）：16-24.

［8］夏少剛.線性規(guī)劃聯(lián)合算法的理論和應(yīng)用［J］.運(yùn)籌與管理，2004，13（1）：3-8.

［9］Browne S，Dongarra J，Grosse E，et al.The Netlib mathematical software repository［J］.D-Lib magazine，1995，1（9）：1-3.

［10］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.

［11］Enge A，Huhn P.A counterexample to H Arsham's“Ini?tialization of the simplex algorithm：an artificial-free approach”［J］.SIAM Review，1998，40（4）：1-6.