線性規(guī)劃問題算法

單純形算法利用多面體的頂點(diǎn)構(gòu)造一個(gè)可能的解，然后沿著多面體的邊走到目標(biāo)函數(shù)值更高的另一個(gè)頂點(diǎn)，直至到達(dá)最優(yōu)解為止。雖然這個(gè)算法在實(shí)際上很有效率，在小心處理可能出現(xiàn)的“循環(huán)”的情況下，可以保證找到最優(yōu)解，但它的最壞情況可以很壞：可以構(gòu)筑一個(gè)線性規(guī)劃問題，單純形算法需要問題大小的指數(shù)倍的運(yùn)行時(shí)間才能將之解出。事實(shí)上，有一段時(shí)期內(nèi)人們曾不能確定線性規(guī)劃問題是NP完全問題還是可以在多項(xiàng)式時(shí)間里解出的問題。

第一個(gè)在最壞情況具有多項(xiàng)式時(shí)間復(fù)雜度的線性規(guī)劃算法在1979年由前蘇聯(lián)數(shù)學(xué)家Leonid Khachiyan提出。這個(gè)算法建基于非線性規(guī)劃中Naum Shor發(fā)明的橢球法 (ellip-soid method)，該法又是Arkadi Nemirovski（2003年馮?諾伊曼運(yùn)籌學(xué)理論獎(jiǎng)得主）和 D. Yudin的凸集最優(yōu)化橢球法的一般化。

理論上，“橢球法”在最惡劣的情況下所需要的計(jì)算量要比“單形法”增長的緩慢，有希望用之解決超大型線性規(guī)劃問題。但在實(shí)際應(yīng)用上，Khachiyan的算法令人失望：一般來說，單純形算法比它更有效率。它的重要性在于鼓勵(lì)了對內(nèi)點(diǎn)算法的研究。內(nèi)點(diǎn)算法是針對單形法的“邊界趨近”觀念而改采“內(nèi)部逼近”的路線，相對于只沿著可行域的邊沿進(jìn)行移動(dòng)的單純形算法，內(nèi)點(diǎn)算法能夠在可行域內(nèi)移動(dòng)。

1984年，貝爾實(shí)驗(yàn)室印度裔數(shù)學(xué)家卡馬卡（Narendra Karmarkar）提出了投影尺度法（又名Karmarkar's algorithm）。這是第一個(gè)在理論上和實(shí)際上都表現(xiàn)良好的算法：它的最壞情況僅為多項(xiàng)式時(shí)間，且在實(shí)際問題中它比單純形算法有顯著的效率提升。自此之后，很多內(nèi)點(diǎn)算法被提出來并進(jìn)行分析。一個(gè)常見的內(nèi)點(diǎn)算法為Mehrotra predictor-corrector method。盡管在理論上對它所知甚少，在實(shí)際應(yīng)用中它卻表現(xiàn)出色。

單形法沿著邊界由一個(gè)頂點(diǎn)移動(dòng)到“相鄰”的頂點(diǎn)，內(nèi)點(diǎn)算法每一步的移動(dòng)考量較周詳，“跨過可行解集合的內(nèi)部”去逼近最佳解。當(dāng)今的觀點(diǎn)是：對于線性規(guī)劃的日常應(yīng)用問題而言，如果算法的實(shí)現(xiàn)良好，基于單純形法和內(nèi)點(diǎn)法的算法之間的效率沒有太大差別，只有在超大型線性規(guī)劃中，頂點(diǎn)幾成天文數(shù)字，內(nèi)點(diǎn)法有機(jī)會(huì)領(lǐng)先單形法。

線性規(guī)劃的求解程式在各種各樣的工業(yè)最優(yōu)化問題里被廣泛使用，例如運(yùn)輸網(wǎng)絡(luò)的流量的最優(yōu)化問題，其中很多都可以不太困難地被轉(zhuǎn)換成線性規(guī)劃問題。

線性規(guī)劃理論中存在幾個(gè)尚未解決的問題，這些開放問題的答案將會(huì)是數(shù)學(xué)運(yùn)算中的根本突破，并且很可能是我們解決大規(guī)模線性規(guī)劃問題的主要進(jìn)展。

• LP存在強(qiáng)多項(xiàng)式時(shí)間算法嗎？

• LP存在多項(xiàng)式時(shí)間算法以得到一個(gè)嚴(yán)格互補(bǔ)解嗎"list-dot list-dot-paddingleft">

  LP在實(shí)數(shù)（單位成本）模型下存在多項(xiàng)式時(shí)間算法嗎"para" label-module="para">

  這些問題已經(jīng)由斯蒂芬·斯梅爾在二十一世紀(jì)十八個(gè)尚未解決的最偉大的問題中應(yīng)用。用斯梅爾的話來說，“第三個(gè)問題是線性規(guī)劃理論中最主要的尚未解決的問題”。然而，對于線性規(guī)劃問題存在弱多項(xiàng)式時(shí)間算法，比如橢球算法和內(nèi)點(diǎn)算法，尚未發(fā)現(xiàn)限制在約束條件個(gè)數(shù)和變量個(gè)數(shù)的強(qiáng)多項(xiàng)式時(shí)間算法，此算法的發(fā)展將會(huì)帶來理論上重大意義，或者是解決大規(guī)模線性規(guī)劃上的實(shí)際收益。

  線性規(guī)劃問題整數(shù)規(guī)劃

  要求所有的未知量都為整數(shù)的線性規(guī)劃問題叫做整數(shù)規(guī)劃（integer programming, IP）或整數(shù)線性規(guī)劃（integer linear programming, ILP）問題。相對于即使在最壞情況下也能有效率地解出的線性規(guī)劃問題，整數(shù)規(guī)劃問題的最壞情況是不確定的，在某些實(shí)際情況中（有約束變量的那些）為NP困難問題。

  0-1整數(shù)規(guī)劃是整數(shù)規(guī)劃的特殊情況，所有的變量都要是0或1（而非任意整數(shù)）。這類問題亦被分類為NP困難問題 。

  只要求當(dāng)中某幾個(gè)未知數(shù)為整數(shù)的線性規(guī)劃問題叫做混合整數(shù)規(guī)劃（mixed integer programming, MIP）問題。這類問題通常亦被分類為NP困難問題。

  存在著幾類IP和MIP的子問題，它們可以被有效率地解出，最值得注意的一類是具有完全單位模約束矩陣，和約束條件的右邊全為整數(shù)的一類。

  一個(gè)解決大型整數(shù)線性規(guī)劃問題的先進(jìn)算法為delayed column generation。2100433B

幾何上，線性約束條件的集合相當(dāng)于一個(gè)凸包或凸集，叫做可行域。因?yàn)槟繕?biāo)函數(shù)亦是線性的，所以其極值點(diǎn)會(huì)自動(dòng)成為最值點(diǎn)。線性目標(biāo)函數(shù)亦暗示其最優(yōu)解只會(huì)在其可行域的邊界點(diǎn)中出現(xiàn)。

在兩種情況下線性規(guī)劃問題沒有最優(yōu)解。其中一種是在約束條件相互矛盾的情況下（例如

另一種情況是，約束條件的多面體可以在目標(biāo)函數(shù)的方向無界（例如：

除了以上兩種病態(tài)的情況以外（問題通常都會(huì)受到資源的限制，如上面的例子），最優(yōu)解永遠(yuǎn)都能夠在多面體的頂點(diǎn)中取得。但最優(yōu)解未必只有一個(gè)：有可能出現(xiàn)一組最優(yōu)解，覆蓋多面體的一條邊、一個(gè)面、甚至是整個(gè)多面體（最后一種情況會(huì)在目標(biāo)函數(shù)只能等于0的情況下出現(xiàn)）。

每個(gè)線性規(guī)劃問題，稱為原問題，都可以變換為一個(gè)對偶問題。我們可將“原問題”表達(dá)成矩陣形式：

maximize

subject to

而相應(yīng)的對偶問題就可以表達(dá)成以下矩陣形式：

maximize

subject to

這里用

例子

上述線性規(guī)劃例子的對偶問題：

假如有一個(gè)種植園主缺少肥料和農(nóng)藥，他希望同這個(gè)農(nóng)夫談判付給農(nóng)夫肥料和農(nóng)藥的價(jià)格?？梢詷?gòu)造一個(gè)數(shù)學(xué)模型來研究如何既使得農(nóng)夫覺得有利可圖肯把肥料和農(nóng)藥的資源賣給他，又使得自己支付的金額最少？

問題可以表述如下

假設(shè)

在用單純型法求解線性規(guī)劃問題之前，必須先把線性規(guī)劃問題轉(zhuǎn)換成增廣矩陣形式。增廣矩陣形式引入非負(fù)松弛變量將不等式約束變成等式約束。問題就可以寫成以下形式：

Maximize

例子

以上例子的轉(zhuǎn)換成增廣矩陣：

maximize

subjuct to

寫成矩陣形式：

Maximize Z in:

描述線性規(guī)劃問題的常用和最直觀形式是標(biāo)準(zhǔn)型。標(biāo)準(zhǔn)型包括以下三個(gè)部分：

一個(gè)需要極大化的線性函數(shù)，例如：

以下形式的問題約束，例如：

和非負(fù)變量，例如：

線性規(guī)劃問題通常可以用矩陣形式表達(dá)成：

maximize

subject to

其他類型的問題，例如極小化問題，不同形式的約束問題，和有負(fù)變量的問題，都可以改寫成其等價(jià)問題的標(biāo)準(zhǔn)型。

例子

以下是一個(gè)線性規(guī)劃的例子。假設(shè)一個(gè)農(nóng)夫有一塊 A平方千米的農(nóng)地，打算種植小麥或大麥，或是兩者依某一比例混合種植。該農(nóng)夫只可以使用有限數(shù)量的肥料 F 和農(nóng)藥 P，而單位面積的小麥和大麥都需要不同數(shù)量的肥料和農(nóng)藥，小麥以

max

線性規(guī)劃是最優(yōu)化問題中的一個(gè)重要領(lǐng)域。在作業(yè)研究中所面臨的許多實(shí)際問題都可以用線性規(guī)劃來處理，特別是某些特殊情況，例如：網(wǎng)絡(luò)流、多商品流量等問題，都被認(rèn)為非常重要?，F(xiàn)階段已有大量針對線性規(guī)劃算法的研究。很多最優(yōu)化問題算法都可以分解為線性規(guī)劃子問題，然后逐一求解。在線性規(guī)劃的歷史發(fā)展過程中所衍伸出的諸多概念，建立了最優(yōu)化理論的核心思維，例如“對偶”、“分解”、“凸集”的重要性及其一般化等。在微觀經(jīng)濟(jì)學(xué)和商業(yè)管理領(lǐng)域中，線性規(guī)劃亦被大量應(yīng)用于例如降低生產(chǎn)過程的成本等手段，最終提升產(chǎn)值與營收。喬治·丹齊格被認(rèn)為是線性規(guī)劃之父。

第1章線性規(guī)劃問題的數(shù)學(xué)模型

1.1線性規(guī)劃問題的提出

1.2線性規(guī)劃問題的標(biāo)準(zhǔn)形式與典則形式

1.3線性規(guī)劃問題的解

1.4線性規(guī)劃問題的對偶理論

第2章求解線性規(guī)劃問題的一般方法

2.1枚舉法

2.2兩個(gè)變量線性規(guī)劃問題的圖解法

2.3單純形法

2.4對偶單純形法

2.5有界變量的線性規(guī)劃問題求解方法

2.6其他方法

第3章定界對偶算法

3.1定界對偶算法的提出

3.2定界對偶算法的迭代方法描述

3.3定界對偶算法的正確性證明

3.4定界對偶算法求解示例

第4章特殊線性規(guī)劃問題的定界對偶算法

4.1運(yùn)輸問題

4.2分派問題

4.3有向圖的最短路問題

4.4最大流問題

4.5最小費(fèi)用流問題

4.6最小樹權(quán)下界問題

4.7博弈問題

4.8最大權(quán)匹配問題

4.9最大基數(shù)匹配問題

4.10計(jì)劃網(wǎng)絡(luò)圖的關(guān)鍵路線問題

4.11裝載問題

第5章定界對偶算法的靈敏度分析

5.1目標(biāo)函數(shù)中常數(shù)c發(fā)生變化

5.2變量的上、下界u，v發(fā)生變化

5.3增加新約束條件的分析

第6章經(jīng)典的線性規(guī)劃對偶問題

6.1原材料與產(chǎn)品的對偶

6.2運(yùn)輸與販賣的對偶

6.3關(guān)鍵路徑與里程碑結(jié)點(diǎn)的對偶

6.4二人零和博弈的局中人策略的對偶

第7章整數(shù)規(guī)劃問題

7.1整數(shù)規(guī)劃問題的提出

7.2化為0—1型整數(shù)規(guī)劃求解

7.3割平面法

7.4分枝定界法

第8章多目標(biāo)規(guī)劃問題

8.1多目標(biāo)規(guī)劃問題的提出

8.2目標(biāo)規(guī)劃的圖解法

8.3目標(biāo)規(guī)劃的定界對偶算法求解示例

8.4多目標(biāo)規(guī)劃化為單目標(biāo)規(guī)劃求解

參考文獻(xiàn)

后記2100433B

《線性規(guī)劃問題的統(tǒng)一建模與快速算法》可作為運(yùn)籌學(xué)、管理學(xué)、系統(tǒng)工程等專業(yè)的線性規(guī)劃課程研究生教材，也可供有關(guān)專業(yè)的院校教師、研究生和大學(xué)高年級學(xué)生以及從事經(jīng)濟(jì)管理研究的相關(guān)人員作為參考用書。

線性規(guī)劃理論在工程設(shè)計(jì)、生產(chǎn)管理、交通運(yùn)輸、國防等領(lǐng)域以及自然科學(xué)的很多學(xué)科中都有著廣泛的應(yīng)用。線性規(guī)劃問題雖然是一個(gè)古老的問題，但求解線性規(guī)劃問題的方法在不斷發(fā)展：從單純形法、對偶單純形法、橢圓方法到內(nèi)點(diǎn)方法等等。雖然線性規(guī)劃有這么多解法，但是單純形方法在其中的統(tǒng)治地位始終沒變。對于退化線性規(guī)劃問題，用單純形方法求解時(shí)有可能產(chǎn)生循環(huán)，因此，研究退化線性規(guī)劃問題成為人們研究線性規(guī)劃問題的一個(gè)重要方面。1952年A. Charnes和W. W. Cooper給出了求解退化線性規(guī)劃問題的攝動(dòng)法，1954年G. B. Dantzig, A. Orden和P. Wolfe提出了求解退化線性規(guī)劃問題的字典序法，1976年G. G. Bland提出了求解退化線性規(guī)劃問題的Bland法則，這些方法都能避免循環(huán)發(fā)生。