目標(biāo)超平面上的一種對(duì)偶單純形算法*

高 培 旺

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

0 引 言

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

(LP) maxcTx

s.t.Ax=b

x≥0

這里，A∈Rm×n(m

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

(ALP) maxeTAx

s.t.Ax+y=b

x≥0，y≥0

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

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

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

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

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

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

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

(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)無(wú)可行解或只有唯一零解，算法結(jié)束；否則，以cm+1，s為樞軸主元進(jìn)行旋轉(zhuǎn)變換，且一旦人工變量ym+1離基后就刪除其所在列，轉(zhuǎn)下一步.

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

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

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

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

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

3 結(jié) 論

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

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

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