第1 章導(dǎo)論

人類的智慧之一在于其進(jìn)行活動(dòng)有預(yù)定目標(biāo). 早期人們單憑經(jīng)驗(yàn)判斷和行事以達(dá)目標(biāo)，而現(xiàn)代人則借助先進(jìn)的軟硬件科學(xué)手段進(jìn)行決策，所獲效益與之前自是不可同日而語(yǔ).

所謂“最優(yōu)化”，簡(jiǎn)言之即以盡可能小的代價(jià)達(dá)成盡可能好的結(jié)果. 如怎樣分配有限的資源(人力、金錢(qián)、物資等) 使獲益最大化，或以最小的代價(jià)達(dá)成一定目標(biāo)等. 人們根據(jù)所占有的信息和數(shù)據(jù)，將實(shí)際問(wèn)題用數(shù)學(xué)語(yǔ)言，如數(shù)字、方程或函數(shù)等恰當(dāng)表述，即建立數(shù)學(xué)模型；然后用最優(yōu)化數(shù)學(xué)方法求解模型，從而為決策提供科學(xué)可靠的定量依據(jù). 這種將問(wèn)題數(shù)學(xué)化并用數(shù)學(xué)手段加以解決的方法因電子計(jì)算機(jī)的使用而具有無(wú)可估量的革命性意義.

線性規(guī)劃模型具有非常簡(jiǎn)單的數(shù)學(xué)結(jié)構(gòu)，其中所涉及的函數(shù)或方程均為線性.不過(guò)其規(guī)模卻可以很大，涉及成千上萬(wàn)個(gè)變量或方程已習(xí)以為常，而其求解也并非易事. 借助計(jì)算機(jī)，目前線性規(guī)劃計(jì)算技術(shù)已有能力求解很大規(guī)模的問(wèn)題. 包含數(shù)十個(gè)甚至數(shù)百個(gè)約束條件和變量的只算是小問(wèn)題，有成千上萬(wàn)約束條件和變量的可算中等規(guī)模問(wèn)題，而有數(shù)十萬(wàn)或數(shù)百萬(wàn)以上也許才算是大規(guī)模問(wèn)題. 20 世紀(jì)90年代初，美國(guó)運(yùn)籌學(xué)家成功地求解了一個(gè)有一千多萬(wàn)個(gè)變量的線性規(guī)劃問(wèn)題，為一家航空公司乘務(wù)人員的工作安排提供了最佳方案(Bixby，1992). 然而隨著全球化趨勢(shì)日益明顯，為追求大系統(tǒng)整體效益而建立的線性規(guī)劃模型越來(lái)越大，對(duì)算法和軟件的效率及穩(wěn)定性等提出了更高的極具挑戰(zhàn)性的要求.

本書(shū)旨在從實(shí)用的角度介紹線性規(guī)劃的理論、方法和實(shí)現(xiàn)技術(shù)，既包括這一領(lǐng)域的基礎(chǔ)和傳統(tǒng)內(nèi)容，也著力反映最新研究成果和進(jìn)展.

1.1 線性規(guī)劃源起

對(duì)線性規(guī)劃的源起和發(fā)展作一個(gè)簡(jiǎn)要回顧是有益、富有情趣和給人啟迪的.

線性規(guī)劃的萌芽可以追溯到19 世紀(jì)20 年代. 法國(guó)數(shù)學(xué)家J. B. J. Fourier(因其冠名的級(jí)數(shù)而著名) 于1823 年、比利時(shí)數(shù)學(xué)家V. Poussin 于1911 年分別寫(xiě)過(guò)一篇涉及線性規(guī)劃的論文，然而這些孤立的工作沒(méi)有產(chǎn)生任何影響.

1939 年，前蘇聯(lián)數(shù)學(xué)家L. Kantorovich 在其《生產(chǎn)組織與計(jì)劃的數(shù)學(xué)方法》一書(shū)中提出“解乘數(shù)法”，已經(jīng)涉及線性規(guī)劃模型及其求解，可惜未引起當(dāng)局注意，在國(guó)際學(xué)術(shù)界也鮮為人知. F. L. Hitchcock 于1941 年發(fā)表了一篇很好的有關(guān)運(yùn)輸問(wèn)題的論文，但一直未受關(guān)注，直到40 年代末50 年代初被重新發(fā)現(xiàn)，已是單純形法問(wèn)世之后.

人類的實(shí)踐活動(dòng)是一切科學(xué)理論和方法的原動(dòng)力. 第二次世界大戰(zhàn)給人類帶來(lái)了巨大的損失、傷亡和災(zāi)難，然而戰(zhàn)事的需求也極大地推動(dòng)了科學(xué)技術(shù)的發(fā)展，催生了許多新興學(xué)科. 而怎樣運(yùn)用現(xiàn)有條件(如人員和裝備等) 取得最大戰(zhàn)場(chǎng)利益的現(xiàn)實(shí)需求催生了最優(yōu)化和運(yùn)籌學(xué).

George B. Dantzig 1946 年獲得博士學(xué)位后，成為第二次世界大戰(zhàn)期間美國(guó)空軍審計(jì)部門(mén)的一位數(shù)學(xué)顧問(wèn). 他研究如何借助當(dāng)時(shí)的計(jì)算工具更快地完成計(jì)劃工作. 在第11 屆國(guó)際數(shù)學(xué)規(guī)劃大會(huì)(Bonn, 1982) 上Dantzig 回憶當(dāng)時(shí)的情形時(shí)，他給出一個(gè)有趣例子：

如何將70 件不同的工作分派給70 個(gè)人去做？

盡管只有有限多個(gè)指派方案(70! > 10100)，但要逐一比較從中找出最優(yōu)方案卻不現(xiàn)實(shí)，因?yàn)槟鞘莻�(gè)天文數(shù)字. 設(shè)想用每秒運(yùn)算100 萬(wàn)次的計(jì)算機(jī)從150 億年前宇宙大爆炸開(kāi)始計(jì)算，能在1990 年給出答案嗎？答案是不能. 即使用每秒可比較10 億種方案的計(jì)算機(jī)，答案也是不能. 甚至將地球裝滿這種計(jì)算機(jī)且進(jìn)行并行計(jì)算，答案仍然是否定的. 假如將太陽(yáng)和1040 個(gè)地球都裝滿這種計(jì)算機(jī)，從宇宙大爆炸開(kāi)始進(jìn)行并行計(jì)算，那么也許要到太陽(yáng)變冷才能得到結(jié)果. 這個(gè)例子說(shuō)明了1947 年以前人們?cè)谶x擇最優(yōu)方案時(shí)面臨的困境. 當(dāng)時(shí)只能以上司、權(quán)威人士的經(jīng)驗(yàn)或判斷訂立若干基本原則，設(shè)法得到一個(gè)可以接受的方案. 如果用單純形法處理上述指派問(wèn)題，在IBM370-168 上只需一秒鐘即得最優(yōu)方案，更不用說(shuō)使用當(dāng)前更先進(jìn)的計(jì)算機(jī).

Dantzig 于1947 年夏天提出了線性規(guī)劃模型和單純形法，一般被認(rèn)為標(biāo)志著一個(gè)新學(xué)科的誕生. 當(dāng)年10 月3 日，他拜訪了科學(xué)家J. von Neumann，向他介紹了這些結(jié)果. Neumann 很快就抓住了方法的基本思想，并指出與自己正在研究的對(duì)策論存在可能的內(nèi)在聯(lián)系，讓Dantzig 獲益匪淺. 1948 年，Dantzig 參加了一個(gè)在Wisconsin 召開(kāi)的計(jì)量經(jīng)濟(jì)學(xué)會(huì)議，參加者包括當(dāng)時(shí)一些非常著名的統(tǒng)計(jì)學(xué)家和數(shù)學(xué)家，如von Neumann 和H. Holelling 及著名的經(jīng)濟(jì)學(xué)家，如T. C. Koopmans. 年輕的Dantzig 報(bào)告了線性規(guī)劃和單純形法后，會(huì)議主席請(qǐng)大家提問(wèn). 會(huì)上先是“死一般的沉寂”，接著Hotelling 站起來(lái)說(shuō)：“但是，我們都知道世界是非線性的.”在一群大人物面前，當(dāng)時(shí)還名不見(jiàn)經(jīng)傳的Dantzig 一時(shí)不知所措. 幸好von Neumann在征得同意后為他解了圍：“報(bào)告人命題為‘線性規(guī)劃’并詳細(xì)論述了他的原理. 如果實(shí)際問(wèn)題滿足這些原理就好好應(yīng)用，否則不去用它就是.”當(dāng)然Hotelling 說(shuō)的沒(méi)錯(cuò)，世界的確是高度非線性的；然而幸運(yùn)的是，現(xiàn)實(shí)中的非線性關(guān)系常�？捎镁�性關(guān)系近似.

20 世紀(jì)40 年代電子計(jì)算機(jī)的問(wèn)世給世界帶來(lái)了巨大的變化，稱之為劃時(shí)代和革命性的一點(diǎn)也不為過(guò). 計(jì)算機(jī)以其無(wú)與倫比的穿透力，深刻地改變了(并還正在改變著) 幾乎所有學(xué)科的面貌，也使線性規(guī)劃如虎添翼、迅速發(fā)展. 單純形法的計(jì)算機(jī)實(shí)現(xiàn)發(fā)端于美國(guó)標(biāo)準(zhǔn)局(National Bureau of Standards). 1952 年前后，美國(guó)標(biāo)準(zhǔn)局的A. Ho?man 團(tuán)隊(duì)將單純形法在一些試驗(yàn)問(wèn)題上進(jìn)行了試算，與當(dāng)時(shí)流行的T. Motzkin 的方法進(jìn)行比較大獲全勝. 1953 到1954 年間，W. Orchard-Hays開(kāi)始了他開(kāi)創(chuàng)性的工作，基于單純形法編制了第一個(gè)商業(yè)性軟件，在早期的計(jì)算機(jī)上求解線性規(guī)劃問(wèn)題. 他的實(shí)現(xiàn)技術(shù)隨后被M. A. Saunders 和R. E. Bixby 等許多學(xué)者應(yīng)用和發(fā)展，使單純形法從理論變?yōu)閺?qiáng)有力的工具，激發(fā)了整個(gè)領(lǐng)域的快速發(fā)展. 不少諾貝爾經(jīng)濟(jì)學(xué)獎(jiǎng)的獲獎(jiǎng)工作與線性規(guī)劃的應(yīng)用密切相關(guān)，如上面提到的L. V. Kantorovich 和T. C. Koopmans 因?qū)�資源最優(yōu)配置理論的貢獻(xiàn)分享1975 年諾貝爾經(jīng)濟(jì)學(xué)獎(jiǎng). 單純形法的應(yīng)用也帶來(lái)了巨大的經(jīng)濟(jì)和社會(huì)效益，美國(guó)物理研究所和IEEE 計(jì)算機(jī)學(xué)會(huì)刊物“科學(xué)和工程計(jì)算”(Computing in Science andEngineering)2000 年第1 期選出對(duì)20 世紀(jì)科學(xué)和工程的實(shí)踐與發(fā)展影響最大的十個(gè)算法(Cipra, 2000)，單純形法名列其中. 歷史一再表明，正是實(shí)踐的沃土使理論和方法之樹(shù)根深葉茂、碩果累累.

然而，人們不久發(fā)現(xiàn)單純形法具有指數(shù)時(shí)間復(fù)雜性(Klee and Minty, 1972)，而一般認(rèn)為具有多項(xiàng)式時(shí)間復(fù)雜性才是“好”算法(見(jiàn)3.8 節(jié)). 實(shí)際上，單純形法甚至不具有限性，不能保證有限步終止(Beale, 1955; Ho?man, 1953). 1979 年，前蘇聯(lián)數(shù)學(xué)家L. G. Khachiyan (1979) 提出了求解線性規(guī)劃問(wèn)題的第一個(gè)多項(xiàng)式時(shí)間算法(橢球方法)，實(shí)現(xiàn)了一次重大的理論突破. 可惜發(fā)現(xiàn)其實(shí)際效果不佳，遠(yuǎn)不如單純形法. 實(shí)際上，所謂\多項(xiàng)式時(shí)間" 只是最壞情形復(fù)雜性；而較為適當(dāng)?shù)氖瞧骄鶗r(shí)間復(fù)雜性. K. H. Borgward (1982a, b) 證明，使用某個(gè)主元規(guī)則的單純形法求解原始數(shù)據(jù)服從一定分布的線性規(guī)劃問(wèn)題，所需迭代次數(shù)的數(shù)學(xué)期望不超過(guò)O(n4m).S. Smale (1983a, b) 也給出類似結(jié)果. 這些結(jié)果表明單純形法具有平均多項(xiàng)式時(shí)間復(fù)雜性，與其杰出的實(shí)際表現(xiàn)相吻合.

1984 年，印度數(shù)學(xué)家N. Karmarkar 提出一個(gè)具多項(xiàng)式時(shí)間復(fù)雜性的內(nèi)點(diǎn)法，比橢球法具更低的多項(xiàng)式階，且在隨后的數(shù)值試驗(yàn)中表現(xiàn)不凡，引起學(xué)術(shù)界廣泛關(guān)注，迅速激發(fā)內(nèi)點(diǎn)法熱，涌現(xiàn)了一批出色的研究成果. 以致不少學(xué)者一度認(rèn)為內(nèi)點(diǎn)法在求解大規(guī)模稀疏線性規(guī)劃問(wèn)題上超越了單純形法.

另一方面，單純形法也未止步不前. P. M. J. Harris(1973) 首次成功地試驗(yàn)了近似最陡邊主元規(guī)則. J. J. H. Forrest 和D. Goldfarb (1992) 給出了最陡邊規(guī)則的若干變形和相應(yīng)的遞推公式，報(bào)告了極好的數(shù)值試驗(yàn)結(jié)果，促成了單純形法與內(nèi)點(diǎn)法伯仲難分的態(tài)勢(shì).

基本上，算法的評(píng)估是個(gè)實(shí)踐問(wèn)題. 一個(gè)算法的價(jià)值，其效率、精度、可靠性或穩(wěn)定性最終取決于實(shí)際表現(xiàn). 太拘泥于理論并非明智之舉. 實(shí)際上，有限性或復(fù)雜性甚至有誤導(dǎo)之虞；畢竟，有限或多項(xiàng)式時(shí)間算法的表現(xiàn)一般遠(yuǎn)不及非有限或非多項(xiàng)式時(shí)間算法，而迄今應(yīng)用中的主角也是后者而非前者. 鑒于此，作者以實(shí)踐作為本書(shū)的著眼點(diǎn)和內(nèi)容取舍的依據(jù)，著力于同實(shí)際計(jì)算密切相關(guān)或行之有效的算法、理論和實(shí)現(xiàn)技術(shù). 而在描述算法的同時(shí)，盡可能配以例題演示.

1.2 從實(shí)際問(wèn)題到數(shù)學(xué)模型

由實(shí)際問(wèn)題入手建立數(shù)學(xué)模型是應(yīng)用線性規(guī)劃的第一步. 而好的模型的建立，需要充分了解實(shí)際情況并占有詳實(shí)數(shù)據(jù)，再加上知識(shí)、智慧、經(jīng)驗(yàn)和技巧. 詳細(xì)討論這方面的論題已超出本書(shū)的范圍. 為讓讀者對(duì)此有個(gè)基本了解，不妨先看下面的簡(jiǎn)單例子.

例1.2.1 某公司有1100 噸原木，按合約規(guī)定要為一企業(yè)加工某種規(guī)格的板材470 噸. 在加工過(guò)程中的損耗為6%. 現(xiàn)在公司的決策者面臨的情況是，板材的售價(jià)在簽約后沒(méi)變化但生產(chǎn)成本卻上升了，實(shí)際上原木作為原材料出售更賺錢(qián). 那么如何在遵守合約的前提下獲利最大呢？

這樣的問(wèn)題可用簡(jiǎn)單的代數(shù)方法解決. 設(shè)作為原材料出售的原木為x 噸，用于加工板材的原木為y 噸. 用于加工板材的y 噸原木中有6% 要在生產(chǎn)過(guò)程中損耗掉，故板材的實(shí)際產(chǎn)量為y-0:06y，而產(chǎn)量必須等于合約規(guī)定的470 噸，即

y-0:06y = 470:

另一方面，加工后還余下1100?y 噸原木，將其全部出售顯然獲利最大，于是又有

1100-y = x:

由上面兩個(gè)等式聯(lián)立得二元一次方程組

y-0:06y = 470;

1100-y = x;(1.1)

僅有唯一解

x = 600; y = 500:

換言之，該公司只有唯一的決策方案，即將500 噸原木用于生產(chǎn)板材，而將其余600 噸出售.

然而更大量的問(wèn)題并非如此，通常存在多個(gè)(甚至無(wú)限多) 方案供決策者選擇，如下面這個(gè)例子.

例1.2.2 某公司生產(chǎn)兩種玩具，小狗和小熊. 每只玩具狗的利潤(rùn)為2 元，每只玩具熊的利潤(rùn)為5 元. 若公司的設(shè)備能力都投入使用的話，每天可生產(chǎn)玩具狗60000 只或者玩具熊40000 只. 由于某種顏料有限，每天最多可供30000 只玩具熊的生產(chǎn). 另外該公司僅有每天50000 只玩具的包裝能力. 經(jīng)營(yíng)者每天應(yīng)安排生產(chǎn)多少玩具狗和玩具熊才能獲得最大利潤(rùn)？

設(shè)每天應(yīng)生產(chǎn)x 萬(wàn)只玩具狗和y 萬(wàn)只玩具熊，總共可獲得f(x; y) = 2x + 5y萬(wàn)元利潤(rùn). 變量x 和y 的一組取值代表一個(gè)決策，而函數(shù)f 的對(duì)應(yīng)值即為采用該決策所獲利潤(rùn). 這里需要確定變量x 和y 的值使函數(shù)f(x; y) 取最大值，或著說(shuō)使其“極大化”.

顯然，如果對(duì)兩種玩具的生產(chǎn)沒(méi)有限制的話，可獲得任意大的利潤(rùn). 當(dāng)然情況并非如此. 客觀條件的限制如下：從公司的設(shè)備能力來(lái)看，生產(chǎn)玩具狗和玩具熊的平均速率分別為6 萬(wàn)/天和4 萬(wàn)/天，可推出變量x 和y 所應(yīng)滿足的不等式為

x

6

+ y

4 6 1;

即

2x + 3y 6 12:

從包裝能力看又有

x + y 6 5;

而從顏料供應(yīng)的情況有

y 6 3:

另外，按實(shí)際背景還應(yīng)有x; y > 0 的限制(為簡(jiǎn)單計(jì)，這里忽略了玩具個(gè)數(shù)為整數(shù)的限制).

上述分析結(jié)果可歸納為如下問(wèn)題：

max f(x; y) = 2x + 5y;

s:t: ?2x-3y > ?12;

? x-y > ?5;

?y > ?3;

x; y > 0:

(1.2)

這就是例1.2.2 的數(shù)學(xué)模型. 其中x 和y 為決策變量；f(x; y) 為目標(biāo)函數(shù)；其余各行不等式為加于決策變量的限制，稱為約束條件；滿足約束條件的每對(duì)變量值稱為可行解，而可行解的全體稱為可行集或可行域. 使目標(biāo)函數(shù)達(dá)到最大值的可行解稱為最優(yōu)解. 所謂求解一個(gè)模型就是尋找它的最優(yōu)解，從而找到?jīng)Q策者所應(yīng)采取的最優(yōu)策略. (1.2) 僅涉及線性函數(shù)，稱之為線性規(guī)劃問(wèn)題(模型). 這類問(wèn)題是本書(shū)的討論對(duì)象.

例1.2.1 只有一個(gè)可行解，也為其最優(yōu)解，完全由方程組(1.1) 確定，因而無(wú)需任何優(yōu)化方法就能解決. 而例1.2.2 不同. 其可行域可表示為

P = f(x; y) j 2x + 3y 6 12; x + y 6 5; y 6 3; x > 0; y > 0g:

該集合包含無(wú)限多個(gè)可行解. 幾何上，由于實(shí)數(shù)對(duì)與平面直角坐標(biāo)系中的點(diǎn)一一對(duì)應(yīng)，可行域P 可用與之對(duì)應(yīng)的一個(gè)區(qū)域來(lái)表示. 如圖1.2.1 所示，x 坐標(biāo)軸表示玩具狗的數(shù)量，y 坐標(biāo)軸表示玩具熊的數(shù)量，以萬(wàn)為單位. 每個(gè)約束不等式都對(duì)應(yīng)一個(gè)閉半平面，圖上標(biāo)明了其邊界直線的方程. 所有這些閉半平面的交集，即它們的公共部分即對(duì)應(yīng)P，其中每一點(diǎn)都對(duì)應(yīng)一個(gè)可行解.

圖1.2.1 例1.2.2 的可行域

現(xiàn)在問(wèn)題歸結(jié)為如何從區(qū)域P 中找到對(duì)應(yīng)函數(shù)f(x; y) = 2x+5y 最大值的點(diǎn)，即所謂“最大點(diǎn)”. 因?yàn)樵搮^(qū)域包含無(wú)限多個(gè)點(diǎn)，用窮舉的方法，即取出所有的可行點(diǎn)一一比較顯然行不通. 而大規(guī)模問(wèn)題的求解則更為困難和具挑戰(zhàn)性. 線性規(guī)劃方法是處理這些問(wèn)題的有力工具.

現(xiàn)實(shí)中通常存在大量方案供決策者選擇，不同方案可能導(dǎo)致大相徑庭的結(jié)果，這在激烈的競(jìng)爭(zhēng)中可能生死攸關(guān)，也為決策者們提供了盡顯其聰明才智的舞臺(tái). 但毫無(wú)疑問(wèn)，單憑經(jīng)驗(yàn)決策不能與借助線性規(guī)劃方法同日而語(yǔ).

1.3 線性規(guī)劃模型實(shí)例

線性規(guī)劃的應(yīng)用十分廣泛，幾乎涉及所有需要進(jìn)行決策或管理的領(lǐng)域. 這些領(lǐng)域中產(chǎn)生的線性規(guī)劃模型形形色色，本節(jié)給出一些典型例子. 嚴(yán)格地說(shuō)，其中部分例子涉及的變量取值必須為非負(fù)整數(shù)，但這里將忽略這個(gè)限制.

例1.3.1(生產(chǎn)計(jì)劃問(wèn)題) 某公司生產(chǎn)A，B，C 三種產(chǎn)品. 其生產(chǎn)過(guò)程都需經(jīng)過(guò)零件加工、電鍍和裝配三道工序. 各工序每天的生產(chǎn)能力折合成有效工時(shí). 各產(chǎn)