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

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

?

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

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

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

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

1 問題的提出

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

2 幾種算法的簡單介紹

2.1 單純形法

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

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

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

注：

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

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

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

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

2.2 橢球算法

如果能夠找到求解嚴(yán)格不等式組多項(xiàng)式時(shí)間算法，那么就有（LP）問題的多項(xiàng)式時(shí)間算法。橢球算法就是一種通過尋求嚴(yán)格不等式組的多項(xiàng)式時(shí)間算法，來證明線性規(guī)劃問題有多項(xiàng)式時(shí)間算法。可以理解為把線性規(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算法運(yùn)用了求解非線性規(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)型，形式如下：

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

Karmarkar算法的具體步驟：

下面對Karmarkar算法從一個(gè)迭代點(diǎn)尋求下一個(gè)迭代點(diǎn)的原理進(jìn)行解釋。

注:

2.4 原仿射尺度算法

原仿射問題與上面介紹的兩種內(nèi)點(diǎn)算法不同，它是可以求解標(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)型并不容易，所以原仿射尺度算法在實(shí)際應(yīng)用中是很受推崇的。但是原仿射尺度算法在理論上并未被證明是一個(gè)多項(xiàng)式時(shí)間算法。

3 幾種算法的比較

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