線性規(guī)劃計(jì)算（上）

內(nèi)容概要

　　《運(yùn)籌與管理科學(xué)叢書12：線性規(guī)劃計(jì)算（上）》論述與線性規(guī)劃實(shí)際計(jì)算有緊密聯(lián)系的理論、方法和實(shí)現(xiàn)技術(shù)，既包括這一領(lǐng)域的基礎(chǔ)和傳統(tǒng)內(nèi)容，也著力反映最新成果和進(jìn)展。本書分為上、下兩卷。上卷以基礎(chǔ)和傳統(tǒng)內(nèi)容為主：線性規(guī)劃模型、可行域幾何、單純形法、對偶原理和對偶單純形法、單純形法實(shí)現(xiàn)技巧、原始和對偶主元規(guī)則、原始和對偶I階段法、靈敏度分析、大規(guī)模問題分解法、Kamlarkar算法、原始和對偶仿射尺度算法及路徑跟蹤算法等。所有算法都盡可能配以例題。
　　《運(yùn)籌與管理科學(xué)叢書12：線性規(guī)劃計(jì)算（上）》可作為數(shù)學(xué)及相關(guān)專業(yè)高年級本科生和研究生教材，也可供決策管理人員、科研和工程技術(shù)人員參考。作為教材時(shí)，可視具體情況決定內(nèi)容取舍。

書籍目錄

序
前言
符號表
第1章 導(dǎo)論
1.1 線性規(guī)劃源起
1.2 從實(shí)際問題到數(shù)學(xué)模型
1.3 線性規(guī)劃模型實(shí)例
1.4 標(biāo)準(zhǔn)線性規(guī)劃模型
1.5 高斯一若爾當(dāng)消去
1.6 浮點(diǎn)運(yùn)算誤差
第2章 可行域幾何
2.1 多面凸集和可行域
2.2 可行域的幾何結(jié)構(gòu)
2.3 最優(yōu)界面和最優(yōu)頂點(diǎn)
2.4 最優(yōu)解的啟發(fā)式特征
2.5 可行方向和積極約束
第3章 單純形法
3.1 單純形表
3.2 表格單純形法
3.3 單純形法的啟動(dòng)
3.4 退化和循環(huán)
3.5 有限主元規(guī)則
3.6 修正單純形表
3.7 單純形法
3.8 計(jì)算復(fù)雜性
第4章 對偶原理和對偶單純形法
4.1 對偶線性規(guī)劃問題
4.2 對偶原理
4.3 最優(yōu)性條件和對偶的經(jīng)濟(jì)解釋
4.4 表格對偶單純形算法
4.5 對偶單純形算法
4.6 最優(yōu)解集的獲取
4.7 注記
第5章 主元規(guī)則
5.1 部分計(jì)價(jià)
5.2 最陡邊規(guī)則
5.3 近似最陡邊規(guī)則
5.4 最大距離規(guī)則
5.5 嵌套規(guī)則
5.6 最大距離嵌套規(guī)則
5.7 簡約價(jià)格的計(jì)算
第6章 對偶主元規(guī)則
6.1 對偶最陡邊規(guī)則
6.2 近似對偶最陡邊規(guī)則
6.3 對偶最大距離規(guī)則
6.4 對偶嵌套規(guī)則
第7章 I階段法
7.1 不可行和法
7.2 單人工變量法
7.3 最鈍角列規(guī)則
7.4 簡約價(jià)格攝動(dòng)法
第8章 對偶I階段法
8.1 對偶不可行和法
8.2 對偶單人工變量法
8.3 最鈍角行規(guī)則
8.4 右端列攝動(dòng)法
第9章 單純形法的實(shí)現(xiàn)
9.1 概述
9.2 預(yù)處理：調(diào)比
9.3 稀疏Lu分解
9.4 Lu分解校正
9.5 初始基：闖入策略
9.6 Harris實(shí)用行規(guī)則和容限擴(kuò)展
9.7 線性規(guī)劃問題的等價(jià)變形
9.7.1 簡約問題
……
第10章 靈敏度分析
第11章 大規(guī)模問題分解法
第12章 內(nèi)點(diǎn)法
附錄A MPS文件
附錄B 線性規(guī)劃試驗(yàn)問題
參考文獻(xiàn)
《運(yùn)籌與管理科學(xué)叢書》已出版書目

章節(jié)摘錄

第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ōu)化”，簡言之即以盡可能小的代價(jià)達(dá)成盡可能好的結(jié)果.如怎樣分配有限的資源(人力、金錢、物資等)使獲益最大化，或以最小的代價(jià)達(dá)成一定目標(biāo)等.人們根據(jù)所占有的信息和數(shù)據(jù)，將實(shí)際問題用數(shù)學(xué)語言，如數(shù)字、方程或函數(shù)等恰當(dāng)表述，即建立數(shù)學(xué)模型；然后用最優(yōu)化數(shù)學(xué)方法求解模型，從而為決策提供科學(xué)可靠的定量依據(jù).這種將問題數(shù)學(xué)化并用數(shù)學(xué)手段加以解決的方法因電子計(jì)算機(jī)的使用而具有無可估量的革命性意義. 線性規(guī)劃模型具有非常簡單的數(shù)學(xué)結(jié)構(gòu)，其中所涉及的函數(shù)或方程均為線性.不過其規(guī)模卻可以很大，涉及成千上萬個(gè)變量或方程已習(xí)以為常，而其求解也并非易事.借助計(jì)算機(jī)，目前線性規(guī)劃計(jì)算技術(shù)已有能力求解很大規(guī)模的問題.包含數(shù)十個(gè)甚至數(shù)百個(gè)約束條件和變量的只算是小問題，有成千上萬約束條件和變量的可算中等規(guī)模問題，而有數(shù)十萬或數(shù)百萬以上也許才算是大規(guī)模問題.20世紀(jì)90年代初，美國運(yùn)籌學(xué)家成功地求解了一個(gè)有一千多萬個(gè)變量的線性規(guī)劃問題，為一家航空公司乘務(wù)人員的工作安排提供了最佳方案(Bixby，1992).然而隨著全球化趨勢日益明顯，為追求大系統(tǒng)整體效益而建立的線性規(guī)劃模型越來越大，對算法和軟件的效率及穩(wěn)定性等提出了更高的極具挑戰(zhàn)性的要求. 本書旨在從實(shí)用的角度介紹線性規(guī)劃的理論、方法和實(shí)現(xiàn)技術(shù)，既包括這一領(lǐng)域的基礎(chǔ)和傳統(tǒng)內(nèi)容，也著力反映最新研究成果和進(jìn)展. 1.1線性規(guī)劃源起 對線性規(guī)劃的源起和發(fā)展作一個(gè)簡要回顧是有益、富有情趣和給人啟迪的. 線性規(guī)劃的萌芽可以追溯到19世紀(jì)20年代.法國數(shù)學(xué)家J.B.J.Fourier(因其冠名的級數(shù)而著名)于1823年、比利時(shí)數(shù)學(xué)家V.Poussin于1911年分別寫過一篇涉及線性規(guī)劃的論文，然而這些孤立的工作沒有產(chǎn)生任何影響. 1939年，前蘇聯(lián)數(shù)學(xué)家L.Kantorovich在其《生產(chǎn)組織與計(jì)劃的數(shù)學(xué)方法》一書中提出“解乘數(shù)法”，已經(jīng)涉及線性規(guī)劃模型及其求解，可惜未引起當(dāng)局注意，在國際學(xué)術(shù)界也鮮為人知.F.L.Hitchcock于1941年發(fā)表了一篇很好的有關(guān)運(yùn)輸問題的論文，但一直未受關(guān)注，直到40年代末50年代初被重新發(fā)現(xiàn)，已是單純形法問世之后. 人類的實(shí)踐活動(dòng)是一切科學(xué)理論和方法的原動(dòng)力.第二次世界大戰(zhàn)給人類帶來了巨大的損失、傷亡和災(zāi)難，然而戰(zhàn)事的需求也極大地推動(dòng)了科學(xué)技術(shù)的發(fā)展，催生了許多新興學(xué)科.而怎樣運(yùn)用現(xiàn)有條件(如人員和裝備等)取得最大戰(zhàn)場利益的現(xiàn)實(shí)需求催生了最優(yōu)化和運(yùn)籌學(xué). GeorgeB.Dantzig1946年獲得博士學(xué)位后，成為第二次世界大戰(zhàn)期間美國空軍審計(jì)部門的一位數(shù)學(xué)顧問.他研究如何借助當(dāng)時(shí)的計(jì)算工具更快地完成計(jì)劃工作.在第11屆國際數(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萬次的計(jì)算機(jī)從150億年前宇宙大爆炸開始計(jì)算，能在1990年給出答案嗎？答案是不能.即使用每秒可比較10億種方案的計(jì)算機(jī)，答案也是不能.甚至將地球裝滿這種計(jì)算機(jī)且進(jìn)行并行計(jì)算，答案仍然是否定的.假如將太陽和1040個(gè)地球都裝滿這種計(jì)算機(jī)，從宇宙大爆炸開始進(jìn)行并行計(jì)算，那么也許要到太陽變冷才能得到結(jié)果.這個(gè)例子說明了1947年以前人們在選擇最優(yōu)方案時(shí)面臨的困境.當(dāng)時(shí)只能以上司、權(quán)威人士的經(jīng)驗(yàn)或判斷訂立若干基本原則，設(shè)法得到一個(gè)可以接受的方案.如果用單純形法處理上述指派問題，在IBM370-168上只需一秒鐘即得最優(yōu)方案，更不用說使用當(dāng)前更先進(jìn)的計(jì)算機(jī). Dantzig于1947年夏天提出了線性規(guī)劃模型和單純形法，一般被認(rèn)為標(biāo)志著一個(gè)新學(xué)科的誕生.當(dāng)年10月3日，他拜訪了科學(xué)家J.vonNeumann，向他介紹了這些結(jié)果.Neumann很快就抓住了方法的基本思想，并指出與自己正在研究的對策論存在可能的內(nèi)在聯(lián)系，讓Dantzig獲益匪淺.1948年，Dantzig參加了一個(gè)在Wisconsin召開的計(jì)量經(jīng)濟(jì)學(xué)會(huì)議，參加者包括當(dāng)時(shí)一些非常著名的統(tǒng)計(jì)學(xué)家和數(shù)學(xué)家，如vonNeumann和H.Holelling及著名的經(jīng)濟(jì)學(xué)家，如T.C.Koopmans.年輕的Dantzig報(bào)告了線性規(guī)劃和單純形法后，會(huì)議主席請大家提問.會(huì)上先是“死一般的沉寂”，接著Hotelling站起來說：“但是，我們都知道世界是非線性的.”在一群大人物面前，當(dāng)時(shí)還名不見經(jīng)傳的Dantzig一時(shí)不知所措.幸好vonNeumann在征得同意后為他解了圍：“報(bào)告人命題為‘線性規(guī)劃’并詳細(xì)論述了他的原理.如果實(shí)際問題滿足這些原理就好好應(yīng)用，否則不去用它就是.”當(dāng)然Hotelling說的沒錯(cuò)，世界的確是高度非線性的；然而幸運(yùn)的是，現(xiàn)實(shí)中的非線性關(guān)系常?？捎镁€性關(guān)系近似. 20世紀(jì)40年代電子計(jì)算機(jī)的問世給世界帶來了巨大的變化，稱之為劃時(shí)代和革命性的一點(diǎn)也不為過.計(jì)算機(jī)以其無與倫比的穿透力，深刻地改變了(并還正在改變著)幾乎所有學(xué)科的面貌，也使線性規(guī)劃如虎添翼、迅速發(fā)展.單純形法的計(jì)算機(jī)實(shí)現(xiàn)發(fā)端于美國標(biāo)準(zhǔn)局(NationalBureauofStandards).1952年前后，美國標(biāo)準(zhǔn)局的A.Ho?man團(tuán)隊(duì)將單純形法在一些試驗(yàn)問題上進(jìn)行了試算，與當(dāng)時(shí)流行的T.Motzkin的方法進(jìn)行比較大獲全勝.1953到1954年間，W.Orchard-Hays開始了他開創(chuàng)性的工作，基于單純形法編制了第一個(gè)商業(yè)性軟件，在早期的計(jì)算機(jī)上求解線性規(guī)劃問題.他的實(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源最優(yōu)配置理論的貢獻(xiàn)分享1975年諾貝爾經(jīng)濟(jì)學(xué)獎(jiǎng).單純形法的應(yīng)用也帶來了巨大的經(jīng)濟(jì)和社會(huì)效益，美國物理研究所和IEEE計(jì)算機(jī)學(xué)會(huì)刊物“科學(xué)和工程計(jì)算”(ComputinginScienceandEngineering)2000年第1期選出對20世紀(jì)科學(xué)和工程的實(shí)踐與發(fā)展影響最大的十個(gè)算法(Cipra,2000)，單純形法名列其中.歷史一再表明，正是實(shí)踐的沃土使理論和方法之樹根深葉茂、碩果累累. 然而，人們不久發(fā)現(xiàn)單純形法具有指數(shù)時(shí)間復(fù)雜性(KleeandMinty,1972)，而一般認(rèn)為具有多項(xiàng)式時(shí)間復(fù)雜性才是“好”算法(見3.8節(jié)).實(shí)際上，單純形法甚至不具有限性，不能保證有限步終止(Beale,1955;Ho?man,1953).1979年，前蘇聯(lián)數(shù)學(xué)家L.G.Khachiyan(1979)提出了求解線性規(guī)劃問題的第一個(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ī)劃問題，所需迭代次數(shù)的數(shù)學(xué)期望不超過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ī)劃問題上超越了單純形法. 另一方面，單純形法也未止步不前.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)勢. 基本上，算法的評估是個(gè)實(shí)踐問題.一個(gè)算法的價(jià)值，其效率、精度、可靠性或穩(wěn)定性最終取決于實(shí)際表現(xiàn).太拘泥于理論并非明智之舉.實(shí)際上，有限性或復(fù)雜性甚至有誤導(dǎo)之虞；畢竟，有限或多項(xiàng)式時(shí)間算法的表現(xiàn)一般遠(yuǎn)不及非有限或非多項(xiàng)式時(shí)間算法，而迄今應(yīng)用中的主角也是后者而非前者.鑒于此，作者以實(shí)踐作為本書的著眼點(diǎn)和內(nèi)容取舍的依據(jù)，著力于同實(shí)際計(jì)算密切相關(guān)或行之有效的算法、理論和實(shí)現(xiàn)技術(shù).而在描述算法的同時(shí)，盡可能配以例題演示. 1.2從實(shí)際問題到數(shù)學(xué)模型 由實(shí)際問題入手建立數(shù)學(xué)模型是應(yīng)用線性規(guī)劃的第一步.而好的模型的建立，需要充分了解實(shí)際情況并占有詳實(shí)數(shù)據(jù)，再加上知識(shí)、智慧、經(jīng)驗(yàn)和技巧.詳細(xì)討論這方面的論題已超出本書的范圍.為讓讀者對此有個(gè)基本了解，不妨先看下面的簡單例子. 例1.2.1某公司有1100噸原木，按合約規(guī)定要為一企業(yè)加工某種規(guī)格的板材470噸.在加工過程中的損耗為6%.現(xiàn)在公司的決策者面臨的情況是，板材的售價(jià)在簽約后沒變化但生產(chǎn)成本卻上升了，實(shí)際上原木作為原材料出售更賺錢.那么如何在遵守合約的前提下獲利最大呢？ 這樣的問題可用簡單的代數(shù)方法解決.設(shè)作為原材料出售的原木為x噸，用于加工板材的原木為y噸.用于加工板材的y噸原木中有6%要在生產(chǎn)過程中損耗掉，故板材的實(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噸出售. 然而更大量的問題并非如此，通常存在多個(gè)(甚至無限多)方案供決策者選擇，如下面這個(gè)例子. 例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的一組取值代表一個(gè)決策，而函數(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 461; 即 2x+3y612: 從包裝能力看又有 x+y65; 而從顏料供應(yīng)的情況有 y63: 另外，按實(shí)際背景還應(yīng)有x;y>0的限制(為簡單計(jì)，這里忽略了玩具個(gè)數(shù)為整數(shù)的限制). 上述分析結(jié)果可歸納為如下問題： maxf(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ù)達(dá)到最大值的可行解稱為最優(yōu)解.所謂求解一個(gè)模型就是尋找它的最優(yōu)解，從而找到?jīng)Q策者所應(yīng)采取的最優(yōu)策略.(1.2)僅涉及線性函數(shù)，稱之為線性規(guī)劃問題(模型).這類問題是本書的討論對象. 例1.2.1只有一個(gè)可行解，也為其最優(yōu)解，完全由方程組(1.1)確定，因而無需任何優(yōu)化方法就能解決.而例1.2.2不同.其可行域可表示為 P=f(x;y)j2x+3y612;x+y65;y63;x>0;y>0g: 該集合包含無限多個(gè)可行解.幾何上，由于實(shí)數(shù)對與平面直角坐標(biāo)系中的點(diǎn)一一對應(yīng)，可行域P可用與之對應(yīng)的一個(gè)區(qū)域來表示.如圖1.2.1所示，x坐標(biāo)軸表示玩具狗的數(shù)量，y坐標(biāo)軸表示玩具熊的數(shù)量，以萬為單位.每個(gè)約束不等式都對應(yīng)一個(gè)閉半平面，圖上標(biāo)明了其邊界直線的方程.所有這些閉半平面的交集，即它們的公共部分即對應(yīng)P，其中每一點(diǎn)都對應(yīng)一個(gè)可行解. 圖1.2.1例1.2.2的可行域 現(xiàn)在問題歸結(jié)為如何從區(qū)域P中找到對應(yīng)函數(shù)f(x;y)=2x+5y最大值的點(diǎn)，即所謂“最大點(diǎn)”.因?yàn)樵搮^(qū)域包含無限多個(gè)點(diǎn)，用窮舉的方法，即取出所有的可行點(diǎn)一一比較顯然行不通.而大規(guī)模問題的求解則更為困難和具挑戰(zhàn)性.線性規(guī)劃方法是處理這些問題的有力工具. 現(xiàn)實(shí)中通常存在大量方案供決策者選擇，不同方案可能導(dǎo)致大相徑庭的結(jié)果，這在激烈的競爭中可能生死攸關(guān)，也為決策者們提供了盡顯其聰明才智的舞臺(tái).但毫無疑問，單憑經(jīng)驗(yàn)決策不能與借助線性規(guī)劃方法同日而語. 1.3線性規(guī)劃模型實(shí)例 線性規(guī)劃的應(yīng)用十分廣泛，幾乎涉及所有需要進(jìn)行決策或管理的領(lǐng)域.這些領(lǐng)域中產(chǎn)生的線性規(guī)劃模型形形色色，本節(jié)給出一些典型例子.嚴(yán)格地說，其中部分例子涉及的變量取值必須為非負(fù)整數(shù)，但這里將忽略這個(gè)限制. 例1.3.1(生產(chǎn)計(jì)劃問題)某公司生產(chǎn)A，B，C三種產(chǎn)品.其生產(chǎn)過程都需經(jīng)過零件加工、電鍍和裝配三道工序.各工序每天的生產(chǎn)能力折合成有效工時(shí)。

圖書封面

評論、評分、閱讀與下載

---

    線性規(guī)劃計(jì)算（上） PDF格式下載

---