關(guān)于“單純形法選擇進(jìn)出基變元的一個(gè)新準(zhǔn)則”的計(jì)算效率

高培旺

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

線性規(guī)劃廣泛應(yīng)用于經(jīng)濟(jì)與管理的各個(gè)領(lǐng)域[1-2]，研究大規(guī)模線性規(guī)劃問題的數(shù)值方法可以快速準(zhǔn)確地為管理者提供決策策略.單純形法是求解線性規(guī)劃實(shí)際問題非常有效的算法.從理論上看，經(jīng)典單純形法通過旋轉(zhuǎn)迭代從可行域的一個(gè)頂點(diǎn)到達(dá)另一個(gè)相鄰頂點(diǎn)，直到獲得最優(yōu)解(如果存在).顯然，在n(n>2)維空間中，從一個(gè)頂點(diǎn)出發(fā)，使目標(biāo)函數(shù)值增大(考慮最大化問題)的路徑不止一條.為了找到通往最優(yōu)頂點(diǎn)的最佳路線、減少迭代次數(shù)，人們提出了不同的單純形變式，如梯度單純形算法[3-4]、原有一對偶單純算法[5-6]及其他方法.其中，文獻(xiàn)[7]提出了單純形算法的一種改進(jìn)的樞軸準(zhǔn)則，并用一個(gè)很小的例子說明了其計(jì)算效率優(yōu)于經(jīng)典的單純形算法，既沒有給出嚴(yán)密的復(fù)雜性分析，也沒有進(jìn)行大規(guī)模的數(shù)值試驗(yàn)，因而是遠(yuǎn)遠(yuǎn)不夠的.

本研究對“單純形法選擇進(jìn)出基變元的一個(gè)新準(zhǔn)則”進(jìn)行了分析，詳細(xì)給出了算法步驟，并通過大規(guī)模的數(shù)值試驗(yàn)進(jìn)一步揭示了該算法的計(jì)算效率.結(jié)果表明，這種改進(jìn)的單純形算法雖然在大部分問題上的迭代次數(shù)比經(jīng)典的單純形算法有所減少，但所耗費(fèi)的計(jì)算時(shí)間卻大大增加，其計(jì)算效率隨著問題規(guī)模的增大而不斷下降.實(shí)際上，Arsham[8-9]也提出了與“單純形法選擇進(jìn)出基變元的一個(gè)新準(zhǔn)則”類似的算法思想，Enge和Huhn[10]從復(fù)雜性理論上指出了這種單純形樞軸準(zhǔn)則的缺陷，即迭代次數(shù)的減少一般不能彌補(bǔ)由逐列選擇樞軸主元的樞軸準(zhǔn)則所帶來的計(jì)算復(fù)雜性.

1 “單純形法選擇進(jìn)出基變元的一個(gè)新準(zhǔn)則”的算法思想

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

(LP)

maxf=cTx

s.t.Ax=b，x≥0.

這里，A∈Rm×n(m

f′=f0+θkσl,

(1)

(1)計(jì)算判別數(shù)σ=c-cBB-1A，如果σ≤0，則當(dāng)前原有可行解是最優(yōu)解，算法結(jié)束；否則轉(zhuǎn)下一步.

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

2 關(guān)于“單純形法選擇進(jìn)出基變元的一個(gè)新準(zhǔn)則”的計(jì)算效率

從理論上看，“單純形法選擇進(jìn)出基變元的一個(gè)新準(zhǔn)則”也許會減少單純形迭代次數(shù)，但由于樞軸準(zhǔn)則的設(shè)計(jì)計(jì)算更復(fù)雜，計(jì)算效率是否會提高必須要進(jìn)行大規(guī)模的計(jì)算試驗(yàn)和比較.為此，使用Matlab V7.1語言對經(jīng)典單純形算法和文獻(xiàn)[7]提出的改進(jìn)單純形算法進(jìn)行了編程.在計(jì)算機(jī)上求解計(jì)算了26個(gè)大規(guī)模典型算例，以比較經(jīng)典單純形算法和改進(jìn)的單純形算法的計(jì)算效率，其中問題adlittle，afiro，agg，agg2，beaconfd，blend，brandy，e226，israel，lotfi，sc105，sc205，sc50a，sc50b，scagr7，scagr25，scorpion，scsd1，sctap1，share1b，share2b和stocfor1來自線性規(guī)劃數(shù)據(jù)庫NETLIB[11]，問題air01，enigma，lp41，mod010來自混合整數(shù)規(guī)劃數(shù)據(jù)庫MIPLIB[12]，計(jì)算結(jié)果如表1所示.其中，Iters表示求解線性規(guī)劃問題所需要的樞軸(迭代)數(shù)，Time表示所耗費(fèi)的總的計(jì)算時(shí)間.

表1 經(jīng)典單純形算法和新的單純形算法的計(jì)算比較Tab.1 Computational comparison for the classical and new simplex algorithms

續(xù)表

注：*表示該問題在執(zhí)行了2 000次單純形迭代后，仍然沒有獲得問題的解.

從表1可以看到，除問題blend外，文獻(xiàn)[7]提出的新的單純形樞軸準(zhǔn)則一般比經(jīng)典的單純形算法所用的迭代次數(shù)少，但每一個(gè)問題所耗費(fèi)的計(jì)算時(shí)間都要比經(jīng)典的單純形算法多.尤其是隨著問題的決策變量數(shù)增多與規(guī)模增大，新的單純形樞軸準(zhǔn)則比經(jīng)典的單純形算法所用的計(jì)算時(shí)間更長、計(jì)算效率更低.

3 結(jié)束語

本研究對文獻(xiàn)[7]提出的“單純形法選擇進(jìn)出基變元的一個(gè)新準(zhǔn)則”進(jìn)行了大規(guī)模數(shù)值試驗(yàn)，以進(jìn)一步考察這種新的單純形樞軸準(zhǔn)則的計(jì)算效率.從理論上看，這種所謂“新”的單純形樞軸準(zhǔn)則能夠使目標(biāo)值在每次單純形迭代時(shí)得到最大增益，從而導(dǎo)致單純形迭代次數(shù)減少.但在實(shí)際中，樞軸準(zhǔn)則設(shè)計(jì)計(jì)算的復(fù)雜性卻大大降低了這種算法的計(jì)算效率.從問題e226的計(jì)算結(jié)果中可以看到，這種新的樞軸準(zhǔn)則使單純形迭代次數(shù)比經(jīng)典的單純形算法減少了接近一半，但計(jì)算時(shí)間卻是經(jīng)典算法的4倍左右，可謂得不償失.

另外，文獻(xiàn)[7]列舉了一個(gè)經(jīng)典單純形迭代循環(huán)的例子來試圖說明新的單純形樞軸準(zhǔn)則可以克服因退化產(chǎn)生的迭代循環(huán)問題，然而這僅僅是一個(gè)個(gè)例，在理論上并沒有證明.實(shí)際上，從表1可以看到，新的單純形樞軸準(zhǔn)則也會產(chǎn)生迭代循環(huán)的現(xiàn)象，如問題air01，scsd1和mod010.

通過對“單純形法選擇進(jìn)出基變元的一個(gè)新準(zhǔn)則”進(jìn)行的大規(guī)模數(shù)值試驗(yàn)可以發(fā)現(xiàn)，理論上“最佳”的樞軸準(zhǔn)則在實(shí)際中不一定是最好的，經(jīng)典單純形算法的簡單而方便實(shí)用的樞軸準(zhǔn)盡管“在最壞情況下”的迭代數(shù)是指數(shù)增長的，但實(shí)際使用效果非常好，這已經(jīng)為很多的實(shí)際問題所驗(yàn)證.類似文獻(xiàn)[7]的單純形算法還可找到一些[13].因此，提出一種新且“好”的單純形樞軸準(zhǔn)則并不是一件容易的事情，在進(jìn)行理論探討的同時(shí)還需要大規(guī)模數(shù)值試驗(yàn)來驗(yàn)證.

參考文獻(xiàn)：

[1] Adlakha V,Kowalski K,Vemuganti R,et al.More-for-less algorithm for fixed-charge transportation problems[J].Omega, 2007，35(1):116-127.

[2] Sonia，Puri M C.Two-stage time minimizing assignment problem[J].Omega，2008，36(5): 730-740.

[3] Forrest J，Goldfarb D.Steepest-edge simplex algorithm for linear programming[J].Mathematical Programming，1992，57(1): 341-374.

[4] Vemuganti R R.On gradient simplex methods for linear programs[J].Journal of Applied Mathematics and Decision Sciences，2004，8(2): 107-129.

[5] Curet N D.A primal-dual simplex method for linear programs[J].Operations Research Letters，1993，13(5): 233-237.

[6] Chen H D，Pardalos P M，Saunders M A.The simplex algorithm with a new primal and dual pivot rule[J].Operations Research Letters，1994，16(3): 121-127.

[7] 王全文，吳育華，吳振奎,等.單純形法選擇進(jìn)出基變元的一個(gè)新準(zhǔn)則[J] .數(shù)學(xué)的實(shí)踐與認(rèn)識，2009，39(14): 75-81.

[8] Arsham H.Initialization of the simplex algorithm:an artificial-free approach[J].SIAM Review，1997，39(8): 736-744.

[9] Arsham H.A computer implementation of the push-and-pull algorithm and its computational comparison with LP simplex method[J].Applied Mathematics and Computation，2005，170(1): 36-63.

[10] 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.

[11] 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.

[12] 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.

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