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

內容概要

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

書籍目錄

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

章節(jié)摘錄

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

圖書封面

評論、評分、閱讀與下載

---

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

---