關于“線性規劃的符號跟蹤算法”的注記

唐滄新，高培旺

（1.廣西財經學院 信息與統計學院，廣西 南寧 530003；2.閩江學院 數學系，福建 福州 350121）

0 引言

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

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

1 符號跟蹤算法的描述及補正

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

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

不妨設B、N分別是（LP）系數矩陣的基與非基子矩陣，cB、cN分別是基與非基相應的費用系數向量。眾所周知，當=B-1b≥0時，基B是原始可行的；當判別檢驗數σ=cBB-1A-c≥0時，基 B是對偶可行的；而當≥0且σ≥0時，基 B既是原始可行又是對偶可行的，因而是最優的。

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

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

根據上述對符號跟蹤算法的分析，我們對符號跟蹤算法步驟給出適當修正和補充，詳細描述如下：

步驟1 記Arf代表還未產生基決策變量的行標集合，一開始，Arf={1，2，…，m}，轉下一步。

步驟2 若Arf=?，原問題的初始基B產生，轉步驟3。否則，對任意 i∈Arf，如果≥0，計算第 i個約束中正系數的個數 numi，轉步驟4；如果＜0，計算第i個約束中負系數的個數numi，轉步驟5。

步驟4 如果 numi=0，當＞0時，原問題無可行解，算法結束；當i=0，該約束為冗余約束，置Arf=Arf{i}，將其去掉。否則，有numi＞0，轉步驟6。

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

步驟6 求得所有numi后，取指標r=arg min{numi}作為樞軸行，轉下一步。

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

2 符號跟蹤算法的數值試驗

盡管符號跟蹤算法求得的初始基不一定是原問題的最優基，但如果由此獲得的初始解位于最優頂點的附近，就可以通過更少的迭代次數到達最優頂點。然而，符號跟蹤算法的樞軸準則增加了計算的復雜性，如果這種計算復雜性能通過減少迭代次數得到彌補，使耗費的總的計算時間更少，那么符號跟蹤算法是有意義的。因此，有必要通過大規模數值試驗對符號跟蹤算法的計算效率進行檢驗。

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

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

表1 經典單純形算法與符號跟蹤算法的計算比較

3 結論

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

Enge和Huhn［11］指出，逐列（行）搜尋樞軸主元的過程會帶來指數時間的計算工作量，從而造成總的計算效率下降。本文通過對中大規模問題的數值試驗證實了這一點。可見，要找到一個好的單純形樞軸準則和計算方法，以進一步改進經典單純形算法的計算效率并不是一件容易的事情，需要我們不斷地思考和嘗試，進行嚴謹的理論分析和大規模數值試驗。

［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］唐建國.線性規劃的符號跟蹤算法［J］.運籌與管理，2005，14（3）：55-59.

［6］唐建國.線性規劃的目標函數最速遞減算法［J］.運籌與管理，2005，14（4）：55-59.

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

［8］夏少剛.線性規劃聯合算法的理論和應用［J］.運籌與管理，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.