線性規(guī)劃問(wèn)題

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

Maximize

例子

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

maximize

subjuct to

寫成矩陣形式：

Maximize Z in:

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

maximize

subject to

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

maximize

subject to

這里用

例子

上述線性規(guī)劃例子的對(duì)偶問(wèn)題：

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

問(wèn)題可以表述如下

假設(shè)

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

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

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

以下形式的問(wèn)題約束，例如：

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

線性規(guī)劃問(wèn)題通?？梢杂镁仃囆问奖磉_(dá)成：

maximize

subject to

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

例子

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

max

幾何上，線性約束條件的集合相當(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ī)劃問(wèn)題沒(méi)有最優(yōu)解。其中一種是在約束條件相互矛盾的情況下（例如

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

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

單純形算法利用多面體的頂點(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ī)劃問(wèn)題，單純形算法需要問(wèn)題大小的指數(shù)倍的運(yùn)行時(shí)間才能將之解出。事實(shí)上，有一段時(shí)期內(nèi)人們?cè)荒艽_定線性規(guī)劃問(wèn)題是NP完全問(wèn)題還是可以在多項(xiàng)式時(shí)間里解出的問(wèn)題。

第一個(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ì)算量要比“單形法”增長(zhǎng)的緩慢，有希望用之解決超大型線性規(guī)劃問(wèn)題。但在實(shí)際應(yīng)用上，Khachiyan的算法令人失望：一般來(lái)說(shuō)，單純形算法比它更有效率。它的重要性在于鼓勵(lì)了對(duì)內(nèi)點(diǎn)算法的研究。內(nèi)點(diǎn)算法是針對(duì)單形法的“邊界趨近”觀念而改采“內(nèi)部逼近”的路線，相對(duì)于只沿著可行域的邊沿進(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í)際問(wèn)題中它比單純形算法有顯著的效率提升。自此之后，很多內(nèi)點(diǎn)算法被提出來(lái)并進(jìn)行分析。一個(gè)常見(jiàn)的內(nèi)點(diǎn)算法為Mehrotra predictor-corrector method。盡管在理論上對(duì)它所知甚少，在實(shí)際應(yīng)用中它卻表現(xiàn)出色。

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

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

線性規(guī)劃理論中存在幾個(gè)尚未解決的問(wèn)題，這些開(kāi)放問(wèn)題的答案將會(huì)是數(shù)學(xué)運(yùn)算中的根本突破，并且很可能是我們解決大規(guī)模線性規(guī)劃問(wèn)題的主要進(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">

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

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

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

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

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

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

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

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

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

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

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

1.4線性規(guī)劃問(wèn)題的對(duì)偶理論

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

2.1枚舉法

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

2.3單純形法

2.4對(duì)偶單純形法

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

2.6其他方法

第3章定界對(duì)偶算法

3.1定界對(duì)偶算法的提出

3.2定界對(duì)偶算法的迭代方法描述

3.3定界對(duì)偶算法的正確性證明

3.4定界對(duì)偶算法求解示例

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

4.1運(yùn)輸問(wèn)題

4.2分派問(wèn)題

4.3有向圖的最短路問(wèn)題

4.4最大流問(wèn)題

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

4.6最小樹(shù)權(quán)下界問(wèn)題

4.7博弈問(wèn)題

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

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

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

4.11裝載問(wèn)題

第5章定界對(duì)偶算法的靈敏度分析

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

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

5.3增加新約束條件的分析

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

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

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

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

6.4二人零和博弈的局中人策略的對(duì)偶

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

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

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

7.3割平面法

7.4分枝定界法

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

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

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

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

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

參考文獻(xiàn)

后記2100433B

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

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