高 培 旺

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

0 引 言

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

(LP) maxcTx

s.t.Ax=b

x≥0

這里，A∈Rm×n(m

為了應(yīng)用單純形算法求解上述問題(LP)，首先需要構(gòu)造輔助線性規(guī)劃問題(ALP)來獲得一個初始基本可行解.在等式約束中引入人工變量y=0產(chǎn)生第一階段問題：

(ALP) maxeTAx

s.t.Ax+y=b

x≥0，y≥0

這里，e=(1，…，1)T∈Rm，對問題(ALP)的求解幾乎占到整個單純形法計(jì)算工作量的一半[1]，因此，研究第一階段問題的求解方法和計(jì)算性能也是有價(jià)值的課題.相比第二階段單純形法，第一階段單純形算法能產(chǎn)生更多的信息，諸如目標(biāo)最優(yōu)值既定、人工變量都在初始基中，必須旋轉(zhuǎn)出去，如何充分利用這些已知信息，值得探討.

顯然，(ALP) 有一個基本可行解x=0，y=b，可以應(yīng)用Dantzig[2]的經(jīng)典單純形算法直接求解.另外，Arsham[3-4]提出了一種有趣的無人工單純形類型方法，其意圖是避免使用人工變量，且通過逐列搜尋入基的決策變量來盡快旋出人工變量.但Enge和Huhn[5]隨后指出這種方法其實(shí)包含人工變量，只不過字面上沒有寫出來，并通過一個反例說明逐列搜尋不能保證產(chǎn)生一個完全基，還可能帶來指數(shù)時間的計(jì)算工作量.為了使Arsham方法正常運(yùn)行，Gao[6]對其進(jìn)行了重要改進(jìn)，取得很好的計(jì)算效果.其實(shí)一些方法，如Terlaky[7-8]的有限criss-cross方法，雖然能防止退化產(chǎn)生的循環(huán)，但對實(shí)際問題的求解效率太低，沒有應(yīng)用價(jià)值.

注意到問題(ALP)的可行解(如果存在)位于目標(biāo)超平面eTAx=eTb上，其最優(yōu)值為eTb.根據(jù)這一特征，將人工變量ym+1從目標(biāo)超平面對應(yīng)的約束eTAx+ym+1=eTb中旋轉(zhuǎn)出去，然后將迭代運(yùn)動固定在目標(biāo)超平面上，則所有變量的簡約價(jià)值系數(shù)恒保持為零，即對偶可行.此時，(ALP)的求解過程僅在于獲得其原始可行性，應(yīng)用經(jīng)典對偶單純形算法求解[9]，不需要計(jì)算行系數(shù)與簡約價(jià)值系數(shù)的檢驗(yàn)比，節(jié)省計(jì)算工作量，但對偶退化易于產(chǎn)生迭代循環(huán).Samaras[10]等曾提出的一種原始-對偶外點(diǎn)算法，通過不斷縮小對偶縫隙來達(dá)到快速收斂的目標(biāo)，實(shí)際上，該方法是對偶單純形算法的一種變式，它利用變動的原始可行點(diǎn)來確定樞軸行，但它必須有一個原始可行點(diǎn)和一個對偶可行基來啟動，實(shí)現(xiàn)這個初始啟動要耗費(fèi)巨大的計(jì)算工作量[11]，得不償失.

討論第一階段輔助問題(ALP)的求解，提出一個單純形變式，將迭代過程固定在目標(biāo)超平面上，保持對偶可行性.為了盡可能避免對偶退化帶來的循環(huán)，Anstreicher和Terlaky[12]設(shè)計(jì)了一種MBU單純形算法準(zhǔn)則，它以右手項(xiàng)取負(fù)值的某個約束為目標(biāo)(約束)，通過對偶迭代使該目標(biāo)約束的右手項(xiàng)的值單調(diào)增加，直至變成非負(fù)，則右手項(xiàng)取負(fù)值的約束數(shù)量減少至少一個，依此下去，可達(dá)到問題的原始可行性，在保持問題對偶可行的前提下，該原始可行解就是問題的一個最優(yōu)解.這種方法具有明確的理論意義，但實(shí)際的計(jì)算效果不好[13]，主要是右手項(xiàng)取負(fù)值的約束數(shù)量較多時，需要求解多個只包含右手項(xiàng)為非負(fù)的約束子規(guī)劃，而且迭代數(shù)與選取目標(biāo)約束的順序有關(guān).為了克服MBU單純形算法的上述缺陷，本文以右手項(xiàng)取負(fù)值的所有約束之和為目標(biāo)(約束)，同時保持右手項(xiàng)為非負(fù)的約束仍然可行，一旦右手邊取負(fù)值的約束變?yōu)榭尚?，就將其從目?biāo)約束中刪除，直至獲得一個可行解或者得到原問題無可行解的結(jié)論.顯然，本文提出的算法只需求解一系列子規(guī)劃問題，在理論上與第一階段原始單純形算法求解整個(ALP)問題相比，每次迭代所耗費(fèi)的計(jì)算工作量要少.為了驗(yàn)證本算法的計(jì)算性能，從NETLIB[14]和MIPLIB[15]測試數(shù)據(jù)庫中選取一些標(biāo)準(zhǔn)的中大規(guī)模算例，通過MATLAB編程在計(jì)算機(jī)上實(shí)現(xiàn)數(shù)值試驗(yàn)，初步計(jì)算結(jié)果表明，與經(jīng)典單純形算法相比，本文提出的算法在大部分問題上使用更少的迭代次數(shù)和執(zhí)行時間，因而具有更高的計(jì)算效率.

孫慶雨,孫喆禹,邢文超,等.摻Ge氧化硅薄膜波導(dǎo)制備工藝與應(yīng)力研究[J].光子學(xué)報(bào)，2018，47(12)：1231003

1 目標(biāo)超平面上第一階段對偶單純形算法

如果原問題可行，輔助線性規(guī)劃問題(ALP)具有一個已知的目標(biāo)最優(yōu)值eTb，亦即(ALP)的最優(yōu)解位于目標(biāo)超平面eTAx=eTb上.于是，將eTAx+ym+1=eTb作為一個新約束加入(ALP)中，構(gòu)造一個與(ALP)等價(jià)的輔助問題如下：

(AALP) maxeTAx

s.t.Ax+y=b

eTAx+ym+1=eTb

x≥0，y≥0，ym+1≥0

其中，y=0，ym+1=0為人工變量.為了敘述方便，仍用A表示(AALP)的約束系數(shù)矩陣，用c表示(AALP)的價(jià)值系數(shù)向量，Ai為A的第i行，Aj為A的第j列.

命題1 如果(AALP)沒有原始可行解，則(LP)是不可行的.

s.t.Aix+yi=bi，i∈I+

x≥0，yi≥0，i∈I+

這里，I-={i|(B-1b)i<0}，I+={i|(B-1b)i≥0}.

根據(jù)上述原理，給出具體的算法步驟如下：

步驟1 選擇指標(biāo)s=argmax{eTA}，如果cm+1，s=(eTA)s≤0，則(LP)無可行解或只有唯一零解，算法結(jié)束；否則，以cm+1，s為樞軸主元進(jìn)行旋轉(zhuǎn)變換，且一旦人工變量ym+1離基后就刪除其所在列，轉(zhuǎn)下一步.

在上述算法步驟3中，如果沒有遇到退化產(chǎn)生的循環(huán)現(xiàn)象，本文提出的算法通過有限步迭代就可獲得(LP)的一個可行解，或者(LP)無可行解的結(jié)論.

2 數(shù)值計(jì)算研究

為了驗(yàn)證提出的算法的計(jì)算性能，從線性規(guī)劃標(biāo)準(zhǔn)測試庫NETLIB[14]和混合整數(shù)規(guī)劃標(biāo)準(zhǔn)測試庫MIPLIB[15]中選取了24個典型算例，其中，問題air01，enigma，lp41，mod010屬于整數(shù)規(guī)劃問題，只求解其相應(yīng)的線性規(guī)劃松弛問題的解，這些算例具有稀疏、退化的特征.接下來，使用MATLAB V7.1語言對經(jīng)典單純形算法和本文的目標(biāo)超平面上的對偶單純形算法進(jìn)行了編程，在Lenovo PentiumM計(jì)算機(jī)上執(zhí)行數(shù)值試驗(yàn)，求解這些算例的第一階段輔助問題，以對兩種算法的計(jì)算效率進(jìn)行比較.數(shù)值試驗(yàn)的環(huán)境是完全相同的，計(jì)算結(jié)果如表1所示，其中，Iters表示求解線性規(guī)劃問題所需要的樞軸(迭代)數(shù)，Time表示所耗費(fèi)的總的計(jì)算時間(s).這里需要說明的是，Anstreicher和Terlaky的對偶MBU單純形準(zhǔn)則必須要給定一個對偶可行基的前提下才能應(yīng)用，而這些算例的第一階段輔助問題一般不存在eTA≥0，bi<0的情形，因此，本文沒有對Anstreicher和Terlaky的對偶MBU單純形算法進(jìn)行編程計(jì)算.

表1 經(jīng)典單純形算法和目標(biāo)超平面上的對偶單純形算法的計(jì)算比較Table 1 Computation comparison of dual simplex algorithm on objective hyperplane and classic simplex algorithm

從表1看到，本文提出的算法在14個問題上比經(jīng)典的單純形算法所用的迭代次數(shù)少，在4個問題上與經(jīng)典的單純形算法所用的迭代次數(shù)持平，從24個問題所用的總的迭代次數(shù)來看，本文的目標(biāo)超平面上的對偶單純形算法與經(jīng)典單純形算法的迭代次數(shù)之比為4 153/4 547=0.913 3.尤其是從計(jì)算所耗費(fèi)的CPU時間來看，本文提出的算法只在1個問題(scsd1)上比經(jīng)典的單純形算法所用的時間多，驗(yàn)證了每次迭代比第一階段原始單純形算法所耗費(fèi)的計(jì)算工作量要少.可見，目標(biāo)超平面上的對偶單純形算法在大部分問題上所用的迭代次數(shù)更少，計(jì)算時間更短，因而計(jì)算效率更高.

3 結(jié) 論

提出的算法具有如下顯著特征：首先，它可以從既不是原始可行也不是對偶可行的初始點(diǎn)啟動，增加了啟動的方便性；其次，在目標(biāo)超平上的迭代產(chǎn)生對偶可行性，此時，樞軸準(zhǔn)則的設(shè)計(jì)只需考慮如何盡快獲得問題的原始可行解，當(dāng)所有變量的簡約價(jià)值系數(shù)保持為零時，樞軸列的選擇是非常靈活的.因此，本文提出的算法僅僅是目標(biāo)超平面上的一種單純形算法變式.

本方法把Anstreicher和Terlaky的MBU單純形算法思想用于目標(biāo)超平面上的迭代，在保持對偶可行性的前提下使原始可行約束的數(shù)量單調(diào)增加.為了克服驅(qū)動目標(biāo)行太多可能導(dǎo)致的計(jì)算效率較低的缺陷，本文引入右手項(xiàng)取負(fù)值的所有約束之和作為驅(qū)動目標(biāo)，以右手項(xiàng)為非負(fù)的所有約束為約束構(gòu)造子規(guī)劃問題，然后應(yīng)用Dantzig經(jīng)典單純形算法求解子問題，這樣每次迭代耗費(fèi)的計(jì)算工作量就比求解整個輔助問題要少.從上一節(jié)表1給出的計(jì)算結(jié)果來看，與經(jīng)典單純形算法相比，本方法對大部分算例求解所用的迭代數(shù)要少，即使有些問題用了較多的迭代數(shù)，但耗費(fèi)的執(zhí)行時間卻更短，這初步驗(yàn)證了本算法具有較高的計(jì)算效率.

在取得目標(biāo)超平面上的可行解之后，在約束行中也許能找到取零值的人工基變量，為了求解第二階段問題，需要將這些人工基變量旋轉(zhuǎn)出去.此時，應(yīng)用其他一些單純形算法變式，如cosine單純形方法選擇“好”的非基變量入基[16-17]，可以得到一個更接近(LP)最優(yōu)頂點(diǎn)的基本可行點(diǎn).