第1 章導(dǎo)論

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

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

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

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

1.1 線性規(guī)劃源起

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

y-0:06y = 470:

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

1100-y = x:

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

y-0:06y = 470;

1100-y = x;(1.1)

僅有唯一解

x = 600; y = 500:

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

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

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

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

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

x

6

+ y

4 6 1;

即

2x + 3y 6 12:

從包裝能力看又有

x + y 6 5;

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

y 6 3:

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

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

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ù)；其余各行不等式為加于決策變量的限制，稱為約束條件；滿足約束條件的每對變量值稱為可行解，而可行解的全體稱為可行集或可行域. 使目標(biāo)函數(shù)達到最大值的可行解稱為最優(yōu)解. 所謂求解一個模型就是尋找它的最優(yōu)解，從而找到?jīng)Q策者所應(yīng)采取的最優(yōu)策略. (1.2) 僅涉及線性函數(shù)，稱之為線性規(guī)劃問題(模型). 這類問題是本書的討論對象.

例1.2.1 只有一個可行解，也為其最優(yōu)解，完全由方程組(1.1) 確定，因而無需任何優(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:

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

圖1.2.1 例1.2.2 的可行域

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

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

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

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

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