福州工業(yè)學(xué)校 林育山

?

線性規(guī)劃中幾種內(nèi)點算法的比較

福州工業(yè)學(xué)校 林育山

該文是關(guān)于內(nèi)點算法的一篇綜述，對幾種較為實用的求解線性規(guī)劃問題的算法進行總結(jié)，包括單純形法、橢球算法、Karmarkar算法、原仿射尺度算法等，并對這些算法進行比較。

線性規(guī)劃 內(nèi)點算法 比較

1 問題的提出

1947年，美國數(shù)學(xué)家G.B . Dantzig提出了求解線性規(guī)劃問題的通用方法——單純形法，大量的實際應(yīng)用表明，單純形法是一種行之有效的解線性規(guī)劃問題的算法。但是在理論上，單純形法并不是一個“好算法”，特別是在1972年美國學(xué)者V.Klee與G.L.Minty發(fā)表了一個例子，通過構(gòu)造一個病態(tài)的線性規(guī)劃，說明了單純形法在解決某些極端的例子中效果不好，很多研究線性規(guī)劃的數(shù)學(xué)家開始探討解線性規(guī)劃的NP問題。1979年，前蘇聯(lián)數(shù)學(xué)家哈奇揚發(fā)表了橢球算法，并證明了該算法是個多項式時間算法，說明線性規(guī)劃的多項式時間算法是存在的，但在實際應(yīng)用中，這一算法并沒有很強的實用性。1984年，在美國貝爾實驗室工作的印度籍?dāng)?shù)學(xué)家N.Karmarkar提出了解線性規(guī)劃的投影尺度法，這也是一個多項式時間算法，它比橢球法優(yōu)化了很多，這一工作一時引起了很多數(shù)學(xué)家對內(nèi)點算法的研究熱情，在不斷的改進中，一些新的、改進的或變形的內(nèi)點算法相繼出現(xiàn)。無論是內(nèi)點算法還是橢球算法，它們有一個共同點，就是采用了非線性規(guī)劃的一些思想來解決線性規(guī)劃問題。

2 幾種算法的簡單介紹

2.1 單純形法

將線性規(guī)劃問題（LP）寫成如下的矩陣形式：

設(shè)是的一個基，不失一般性的，設(shè)它由中的前列所組成，由高等代數(shù)的知識，必可將矩陣（1）通過初等變換變?yōu)槿缦滦问剑?/p>

（3）式可以寫成矩陣的形式如下：

注：

單純形法的具體步驟如下：

Step1 列出初始表，在表中找到一個初始基，化為標(biāo)準(zhǔn)形，得到對應(yīng)初始基的基本可行解。

Step2 檢查標(biāo)準(zhǔn)形表上的檢驗數(shù)(c=m+1, 是否均為正數(shù)，若是，則停止，當(dāng)前的基本可行解為最優(yōu)解，否則，進入Step 3。

在前面單純形法的介紹中，我們強調(diào)了一個非退化的前提，在退化的情況下，用上面的步驟去迭代時，可能出現(xiàn)死循環(huán)，對于這個問題，先后有Charnes提出了攝動法，Dantzig、Orden、Wolfe提出了字典序法以及Bland提出了Bland法則，本論文中我們僅介紹Bland法則。

2.2 橢球算法

如果能夠找到求解嚴(yán)格不等式組多項式時間算法，那么就有（LP）問題的多項式時間算法。橢球算法就是一種通過尋求嚴(yán)格不等式組的多項式時間算法，來證明線性規(guī)劃問題有多項式時間算法?？梢岳斫鉃榘丫€性規(guī)劃問題轉(zhuǎn)化為（8）的形式，即為弱不等式組，然后求出相應(yīng)的嚴(yán)格不等式組的解，從而導(dǎo)出弱不等式組的解，則可以求出原線性規(guī)劃問題的最優(yōu)解。所以橢球算法的本質(zhì)是求嚴(yán)格不等式組的解。下面簡單介紹一下橢球算法的原理。

2.2.1基本定義

2.2.2橢球算法

2.3 Karmarkar算法

Karmarkar算法運用了求解非線性規(guī)劃問題的思想來解決線性規(guī)劃問題。這種算法是在把一般線性規(guī)劃問題轉(zhuǎn)化為Karmarkar所特有的標(biāo)準(zhǔn)型，再利用一種求解這種標(biāo)準(zhǔn)型的算法最終求出最優(yōu)解。Karmarkar算法把線性規(guī)劃問題轉(zhuǎn)化成它所要求的那種標(biāo)準(zhǔn)型，我們稱之為Karmarkar標(biāo)準(zhǔn)型，形式如下：

其中這個標(biāo)準(zhǔn)型還要求滿足以下三個條件：

Karmarkar算法的具體步驟：

下面對Karmarkar算法從一個迭代點尋求下一個迭代點的原理進行解釋。

注:

2.4 原仿射尺度算法

原仿射問題與上面介紹的兩種內(nèi)點算法不同，它是可以求解標(biāo)準(zhǔn)形式的線性規(guī)劃問題LP：

不失一般性的，設(shè)秩()=，并設(shè)

原仿射尺度算法與Karmarkar算法在構(gòu)造原理上有很多的相似之處，它的好處是不用把一般的線性規(guī)劃問題轉(zhuǎn)化為Karmarkar標(biāo)準(zhǔn)型，由于把一般的問題轉(zhuǎn)化為Karmarkar標(biāo)準(zhǔn)型并不容易，所以原仿射尺度算法在實際應(yīng)用中是很受推崇的。但是原仿射尺度算法在理論上并未被證明是一個多項式時間算法。

3 幾種算法的比較

名稱解決的問題解決原理算法的時間應(yīng)用價值和優(yōu)缺點 單純形法直接解決線性規(guī)劃問題 s.t 在基本可行解中尋找最優(yōu)基本可行解指數(shù)形時間算法大量的實際應(yīng)用證明單純形法是一種行之有效的解線性規(guī)劃問題的算法，但對于一些極端的問題，單純形法效果不好 橢球算法把解決線性規(guī)劃問題轉(zhuǎn)化為求解嚴(yán)格不等式組通過不斷縮小嚴(yán)格不等式組的解所在的橢球的體積，最終確定是否有解多項式時間算法橢球算法證明了求解線性規(guī)劃問題的多項式時間算法的存在，但在實際應(yīng)用中，遠沒有單純形法好用 Karmarkar算法把解決線性規(guī)劃問題轉(zhuǎn)化求解Karmarkar標(biāo)準(zhǔn)型的問題從可行解的多面體內(nèi)部一個點出發(fā)，產(chǎn)生一個直接穿過多面體內(nèi)部的點列，從而得到所需的最優(yōu)解多項式時間算法是一種行之有效的多項式時間算法，但把一般的線性規(guī)劃問題轉(zhuǎn)化為Karmarkar標(biāo)準(zhǔn)型并不容易 原仿射尺度算法可以直接求解線性規(guī)劃問題在尋找迭代點的原理上與Karmarkar算法原理相似，但在確定何時停止迭代運用了線性規(guī)劃的對偶理論在理論上還未被證明是多項式時間算法實際效果優(yōu)于Karmarkar算法，在中大規(guī)模的線性規(guī)劃問題上，它們的求解效率優(yōu)于單純形法

[1] 張建中，許紹吉. 線性規(guī)劃[M]. 北京: 科學(xué)出版社，1990.

[2] 姚恩瑜，何 勇，陳仕平. 數(shù)學(xué)規(guī)劃和組合優(yōu)化[M]. 杭州: 浙江大學(xué)出版社，2001.

[3] Papadimitriou H C，Steiglizt K.，Combinatorial optimization algorithms and complexity[J]. Printice-Hall,1982.

[4] P.GaCs and L.Lovasz. Khachian’s algorithm for linear programming[J]. Math,Programming Study 14 (1981): 61-68.