出版時間:2012-12 出版社:清華大學(xué)出版社 作者:博賽卡斯 頁數(shù):500
Tag標(biāo)簽:無
前言
優(yōu)化問題可分為兩種主要類型:連續(xù)型和離散型。網(wǎng)絡(luò)優(yōu)化就居于這兩類問題的分界線上。線性規(guī)劃和組合優(yōu)化問題之間存在聯(lián)系是因為可以將多面體約束集表示為其極點的凸包。當(dāng)涉及到網(wǎng)絡(luò)時,由于多面體的極點是整數(shù)向量,并且它們所表示的是看上去和線性規(guī)劃不相干的組合問題的解,上述聯(lián)系變得緊密得多。正由于這種結(jié)構(gòu),也由于它們的直觀特性,網(wǎng)絡(luò)模型為解釋連續(xù)優(yōu)化和離散優(yōu)化中的很多基本思想提供了理想的工具?! 【W(wǎng)絡(luò)模型除了具有引人入勝的方法論方面的特點之外,在實踐中也被廣泛應(yīng)用,其應(yīng)用范圍還在持續(xù)擴大??傮w上看確實如此,諸如最短路、指派、最大流、運輸、轉(zhuǎn)運、生成樹、匹配、旅行商、廣義指派、車輛路徑選擇以及多商品流這些網(wǎng)絡(luò)問題已構(gòu)成大多數(shù)常見類型的實際優(yōu)化問題。在網(wǎng)絡(luò)問題的求解方法方面已經(jīng)發(fā)生了穩(wěn)定的進步,事實上,由于算法和技術(shù)的進步,上述求解方法方面的進步在過去十五年里呈現(xiàn)加速發(fā)展的趨勢?! ”緯康氖菍€性、非線性和離散網(wǎng)絡(luò)優(yōu)化問題提供相當(dāng)全面的最新的介紹。書中突出連續(xù)結(jié)構(gòu)和離散結(jié)構(gòu)之間的聯(lián)系,從廣泛的視野討論相關(guān)的分析和算法問題,并對重要的網(wǎng)絡(luò)模型和應(yīng)用提供指導(dǎo)?! ?/pre>內(nèi)容概要
《信息技術(shù)和電氣工程學(xué)科國際知名教材中譯本系列·網(wǎng)絡(luò)優(yōu)化:連續(xù)和離散模型》不僅詳細介紹了經(jīng)典的線性網(wǎng)絡(luò)優(yōu)化模型、理論和方法,還分別對非線性網(wǎng)絡(luò)優(yōu)化問題和具有一般性整數(shù)約束的網(wǎng)絡(luò)優(yōu)化問題進行了廣泛而深入的討論,所涉及的網(wǎng)絡(luò)優(yōu)化知識非常全面。書中不少材料源自作者本人在網(wǎng)絡(luò)優(yōu)化相關(guān)領(lǐng)域多年的研究成果和研究心得,內(nèi)容新穎,富有啟發(fā)性,與同類書籍相比具有鮮明的特色。通過閱讀《信息技術(shù)和電氣工程學(xué)科國際知名教材中譯本系列·網(wǎng)絡(luò)優(yōu)化:連續(xù)和離散模型》,能夠?qū)W(wǎng)絡(luò)優(yōu)化模型、理論和方法建立完整的認識。 《信息技術(shù)和電氣工程學(xué)科國際知名教材中譯本系列·網(wǎng)絡(luò)優(yōu)化:連續(xù)和離散模型》每章都配備了大量習(xí)題,適合用作網(wǎng)絡(luò)優(yōu)化相關(guān)課程的教材。書中各章節(jié)內(nèi)容既相互關(guān)聯(lián),又相對獨立,便于教師根據(jù)課時安排進行適當(dāng)?shù)倪x擇。作者簡介
作者:(美國)博賽卡斯 譯者:王書寧 牟曉牧 李星野書籍目錄
第1章引言 1.1圖和流 1.1.1路和環(huán) 1.1.2流和散度 1.1.3路流和共軛分解 1.2網(wǎng)絡(luò)流模型一例子 1.2.1最小費用流問題 1.2.2凸費用網(wǎng)絡(luò)流問題 1.2.3多商品流問題 1.2.4離散網(wǎng)絡(luò)優(yōu)化問題 1.3網(wǎng)絡(luò)流算法——綜述 1.3.1原費用改進 1.3.2對偶費用改進 1.3.3拍賣 1.3.4好算法,壞算法及多項式算法 1.4注釋,文獻和習(xí)題 第2章最短路問題 2.1問題表述與應(yīng)用 2.2通用最短路算法 2.3標(biāo)記設(shè)置(Dijkstra)法 2.3.1標(biāo)記設(shè)置法的性能 2.3.2二叉堆法 2.3.3 Dial算法 2.4標(biāo)記修正法 2.4.1 Bellman—Ford算法 2.4.2 D’Esopo—Pape算法 2.4.3 SLF算法和LLL算法 2.4.4閾值算法 2.4.5標(biāo)記設(shè)置法和標(biāo)記修正法的比較 2.5單起點單終點算法 2.5.1標(biāo)記設(shè)置 2.5.2標(biāo)記修正 2.6拍賣算法 2.7多起點多終點算法 2.8注釋,文獻和習(xí)題 第3章最大流問題 3.1最大流最小割問題 3.1.1圖的割集 3.1.2最大流最小割定理 3.1.3最大和最小飽和割集 3.1.4不可行網(wǎng)絡(luò)問題的分解 3.2 Ford—Fulkerson算法 3.3基于價格的增廣路算法 3.3.1基于價格的路構(gòu)造算法 3.3.2基于價格的最大流算法 3.4注釋,文獻和習(xí)題 第4章最小費用流問題 4.1變換和等價 4.1.1置流量下限為零 4.1.2消除流量上限 4.1.3簡化為循環(huán)形式 4.1.4簡化為指派問題 4.2對偶 4.2.1互補松弛條件和對偶問題的解釋 4.2.2非負約束的對偶和互補松弛條件 4.3注釋,文獻和習(xí)題 第5章單純形法 5.1單純形法的主要思想 5.1.1利用價格確定入邊 5.1.2確定出邊 5.1.3處理退化情況 5.2基本單純形法 5.2.1單純形法的終止性質(zhì) 5.2.2單純形法的初始化 5.3推廣到具有上下界約束的問題 5.4實現(xiàn)問題 5.5注釋,文獻和習(xí)題 第6章對偶上升方法 6.1對偶上升 6.2原對偶(序貫最短路)方法 6.3松弛方法 6.4求解已解決問題的變形 6.5實現(xiàn)問題 6.6注釋,文獻和習(xí)題 第7章拍賣算法 7.1指派問題的拍賣算法 7.1.1主拍賣算法 7.1.2近似坐標(biāo)下降解釋 7.1.3拍賣算法的變形 7.1.4復(fù)雜性一E一伸縮 7.1.5處理不可行性 7.2拍賣算法的推廣 7.2.1逆向拍賣 7.2.2非對稱指派問題的拍賣算法 7.2.3同類人員拍賣算法 7.3最大流的預(yù)流推進法 7.3.1分析與復(fù)雜性 7.3.2實現(xiàn)問題 7.3.3與拍賣算法的關(guān)系 7.4 ε—松弛方法 7.4.1計算復(fù)雜性——ε—伸縮 7.4.2實現(xiàn)問題 7.5拍賣/序貫最短路算法 7.6注釋,文獻和習(xí)題 第8章非線性網(wǎng)絡(luò)優(yōu)化 8.1凸可分問題 8.2有附加約束的問題 8.3多商品流問題 8.4整數(shù)約束 8.5有增益的網(wǎng)絡(luò) 8.6最優(yōu)性條件 8.7對偶性 8.8算法和近似 8.8.1可行方向法 8.8.2分片線性近似 8.8.3內(nèi)點法 8.8.4罰函數(shù)和增廣Lagrange方法 8.8.5近鄰最小化 8.8.6光滑化 8.8.7變換 8.9注釋,文獻和習(xí)題 第9章凸可分網(wǎng)絡(luò)問題 9.1單變量凸函數(shù) 9.2最優(yōu)性條件 9.3對偶性 9.4對偶函數(shù)可微性 9.5可微對偶問題算法 9.6拍賣算法 9.6.1 ε—松弛法 …… 第10章整數(shù)約束網(wǎng)絡(luò)問題 附錄A有關(guān)數(shù)學(xué)知識回顧 參考文獻 索引章節(jié)摘錄
版權(quán)頁: 插圖: 網(wǎng)絡(luò)流問題是最重要且最經(jīng)常遇到的優(yōu)化問題之一。它們自然地出現(xiàn)于通信、交通和制造網(wǎng)絡(luò)這樣一些大系統(tǒng)的分析和設(shè)計問題中。它們也可用于描述指派、最短路和旅行商路線這樣一些組合問題。 籠統(tǒng)地說,網(wǎng)絡(luò)流問題由供給點和需求點以及連接它們的若干路徑所組成,其作用是將供給轉(zhuǎn)運到需求。這些路徑可能包含中問轉(zhuǎn)運點。通常可以用圖的節(jié)點表示供給點、需求點以及轉(zhuǎn)運點,用圖的路表示路徑。另外,可能有多種“類型”的供給/需求(或“商品”)共享某些路徑。對路徑的特性也可能有某些約束,比如它們的載貨能力,使用特定路徑時還會有相應(yīng)的費用。這些問題可以自然地建模為網(wǎng)絡(luò)流優(yōu)化問題,粗略地說,我們試圖通過網(wǎng)絡(luò)流優(yōu)化選出能夠以最小的費用將供給轉(zhuǎn)運到需求的路徑。 本書所處理的網(wǎng)絡(luò)流優(yōu)化問題非常廣泛,包括線性和非線性費用函數(shù)。我們應(yīng)特別注意四類主要問題: (1)轉(zhuǎn)運或最小費用流問題,包括一種商品和一個線性費用函數(shù)。該問題有若干重要特例,比如最短路、最大流、指派以及運輸問題。 (2)單商品凸費用網(wǎng)絡(luò)流問題。該問題和前面的轉(zhuǎn)運問題相同,只是費用函數(shù)是凸函數(shù)而不僅是線性函數(shù)。 (3)多商品線性或凸費用網(wǎng)絡(luò)流問題。該問題將前面的兩類問題推廣到多商品情況。 (4)離散網(wǎng)絡(luò)優(yōu)化問題。在這些問題中,沿著網(wǎng)絡(luò)路徑傳輸?shù)牧恐荒苋∮邢迋€數(shù)值。很多組合優(yōu)化問題可以這樣建模,其中有些問題的網(wǎng)絡(luò)結(jié)構(gòu)并不很明顯。某些離散優(yōu)化問題的計算非常困難,實踐中只能近似求解。它們的求解算法經(jīng)常涉及求解前面三類“連續(xù)”的子問題。 上面提到的所有網(wǎng)絡(luò)流問題都可以用和圖相關(guān)的概念建立數(shù)學(xué)模型。我們在1.1節(jié)引入有關(guān)符號和術(shù)語;在1.2節(jié)給出網(wǎng)絡(luò)流優(yōu)化模型的數(shù)學(xué)公式和實際例子;最后在1.3節(jié)對后面章節(jié)將提出的一些算法給出一個概述。 1.1圖和流 本節(jié)我們引入一些基本定義,涉及圖、路、流以及其他概念。圖的概念非常直觀,可以按照提示性圖形來理解,但也經(jīng)常隱含一些微妙之處。因此讀者可能需要以后再回顧本節(jié)內(nèi)容,并對有關(guān)定義的一些細微點進行更仔細的閱讀。編輯推薦
《信息技術(shù)和電氣工程學(xué)科國際知名教材中譯本系列:網(wǎng)絡(luò)優(yōu)化:連續(xù)和離散模型》每章都配備了大量習(xí)題,適合用作網(wǎng)絡(luò)優(yōu)化相關(guān)課程的教材。書中各章節(jié)內(nèi)容既相互關(guān)聯(lián),又相對獨立,便于教師根據(jù)課時安排進行適當(dāng)?shù)倪x擇。圖書封面
圖書標(biāo)簽Tags
無評論、評分、閱讀與下載