《信息技術和電氣工程學科國際知名教材中譯本系列:網路最佳化:連續和離散模型》不僅詳細介紹了經典的線性網路最佳化模型、理論和方法，還分別對非線性網路最佳化問題和具有一般性整數約束的網路最佳化問題進行了廣泛而深入的討論，所涉及的網路最佳化知識非常全面。書中不少材料源自作者本人在網路最佳化相關領域多年的研究成果和研究心得，內容新穎，富有啟發性，與同類書籍相比具有鮮明的特色。
基本介紹
- 書名：信息技術和電氣工程學科國際知名教材中譯本系列:網路最佳化:連續和離散模型
- 作者：博賽卡斯 (Dimitri P.Bertsekas)
- 出版日期：2013年1月1日
- 語種：簡體中文
- ISBN：9787302300526
- 品牌：清華大學出版社
- 外文名：Network Optimization:Continuous and Discrete Models
- 出版社：清華大學出版社
- 頁數：500頁
- 開本：16
- 定價：59.00
基本介紹,內容簡介,作者簡介,圖書目錄,文摘,
基本介紹
內容簡介
《信息技術和電氣工程學科國際知名教材中譯本系列:網路最佳化:連續和離散模型》每章都配備了大量習題，適合用作網路最佳化相關課程的教材。書中各章節內容既相互關聯，又相對獨立，便於教師根據課時安排進行適當的選擇。
作者簡介
作者：（美國）博賽卡斯 譯者：王書寧 牟曉牧 李星野
圖書目錄
第1章引言
1.1圖和流
1.1.1路和環
1.1.2流和散度
1.1.3路流和共軛分解
1.2網路流模型一例子
1.2.1最小費用流問題
1.2.2凸費用網路流問題
1.2.3多商品流問題
1.2.4離散網路最佳化問題
1.3網路流算法——綜述
1.3.1原費用改進
1.3.2對偶費用改進
1.3.3拍賣
1.3.4好算法，壞算法及多項式算法
1.4注釋，文獻和習題
第2章最短路問題
2.1問題表述與套用
2.2通用最短路算法
2.3標記設定（Dijkstra）法
2.3.1標記設定法的性能
2.3.2二叉堆法
2.3.3 Dial算法
2.4標記修正法
2.4.1 Bellman—Ford算法
2.4.2 D’Esopo—Pape算法
2.4.3 SLF算法和LLL算法
2.4.4閾值算法
2.4.5標記設定法和標記修正法的比較
2.5單起點單終點算法
2.5.1標記設定
2.5.2標記修正
2.6拍賣算法
2.7多起點多終點算法
2.8注釋，文獻和習題
第3章最大流問題
3.1最大流最小割問題
3.1.1圖的割集
3.1.2最大流最小割定理
3.1.3最大和最小飽和割集
3.1.4不可行網路問題的分解
3.2 Ford—Fulkerson算法
3.3基於價格的增廣路算法
3.3.1基於價格的路構造算法
3.3.2基於價格的最大流算法
3.4注釋，文獻和習題
第4章最小費用流問題
4.1變換和等價
4.1.1置流量下限為零
4.1.2消除流量上限
4.1.3簡化為循環形式
4.1.4簡化為指派問題
4.2對偶
4.2.1互補鬆弛條件和對偶問題的解釋
4.2.2非負約束的對偶和互補鬆弛條件
4.3注釋，文獻和習題
第5章單純形法
5.1單純形法的主要思想
5.1.1利用價格確定入邊
5.1.2確定出邊
5.1.3處理退化情況
5.2基本單純形法
5.2.1單純形法的終止性質
5.2.2單純形法的初始化
5.3推廣到具有上下界約束的問題
5.4實現問題
5.5注釋，文獻和習題
第6章對偶上升方法
6.1對偶上升
6.2原對偶（序貫最短路）方法
6.3鬆弛方法
6.4求解已解決問題的變形
6.5實現問題
6.6注釋，文獻和習題
第7章拍賣算法
7.1指派問題的拍賣算法
7.1.1主拍賣算法
7.1.2近似坐標下降解釋
7.1.3拍賣算法的變形
7.1.4複雜性一E一伸縮
7.1.5處理不可行性
7.2拍賣算法的推廣
7.2.1逆向拍賣
7.2.2非對稱指派問題的拍賣算法
7.2.3同類人員拍賣算法
7.3最大流的預流推進法
7.3.1分析與複雜性
7.3.2實現問題
7.3.3與拍賣算法的關係
7.4 ε—鬆弛方法
7.4.1計算複雜性——ε—伸縮
7.4.2實現問題
7.5拍賣/序貫最短路算法
7.6注釋，文獻和習題
第8章非線性網路最佳化
8.1凸可分問題
8.2有附加約束的問題
8.3多商品流問題
8.4整數約束
8.5有增益的網路
8.6最優性條件
8.7對偶性
8.8算法和近似
8.8.1可行方向法
8.8.2分片線性近似
8.8.3內點法
8.8.4罰函式和增廣Lagrange方法
8.8.5近鄰最小化
8.8.6光滑化
8.8.7變換
8.9注釋，文獻和習題
第9章凸可分網路問題
9.1單變數凸函式
9.2最優性條件
9.3對偶性
9.4對偶函式可微性
9.5可微對偶問題算法
9.6拍賣算法
9.6.1 ε—鬆弛法
……
第10章整數約束網路問題
附錄A有關數學知識回顧
參考文獻
索引
1.1圖和流
1.1.1路和環
1.1.2流和散度
1.1.3路流和共軛分解
1.2網路流模型一例子
1.2.1最小費用流問題
1.2.2凸費用網路流問題
1.2.3多商品流問題
1.2.4離散網路最佳化問題
1.3網路流算法——綜述
1.3.1原費用改進
1.3.2對偶費用改進
1.3.3拍賣
1.3.4好算法，壞算法及多項式算法
1.4注釋，文獻和習題
第2章最短路問題
2.1問題表述與套用
2.2通用最短路算法
2.3標記設定（Dijkstra）法
2.3.1標記設定法的性能
2.3.2二叉堆法
2.3.3 Dial算法
2.4標記修正法
2.4.1 Bellman—Ford算法
2.4.2 D’Esopo—Pape算法
2.4.3 SLF算法和LLL算法
2.4.4閾值算法
2.4.5標記設定法和標記修正法的比較
2.5單起點單終點算法
2.5.1標記設定
2.5.2標記修正
2.6拍賣算法
2.7多起點多終點算法
2.8注釋，文獻和習題
第3章最大流問題
3.1最大流最小割問題
3.1.1圖的割集
3.1.2最大流最小割定理
3.1.3最大和最小飽和割集
3.1.4不可行網路問題的分解
3.2 Ford—Fulkerson算法
3.3基於價格的增廣路算法
3.3.1基於價格的路構造算法
3.3.2基於價格的最大流算法
3.4注釋，文獻和習題
第4章最小費用流問題
4.1變換和等價
4.1.1置流量下限為零
4.1.2消除流量上限
4.1.3簡化為循環形式
4.1.4簡化為指派問題
4.2對偶
4.2.1互補鬆弛條件和對偶問題的解釋
4.2.2非負約束的對偶和互補鬆弛條件
4.3注釋，文獻和習題
第5章單純形法
5.1單純形法的主要思想
5.1.1利用價格確定入邊
5.1.2確定出邊
5.1.3處理退化情況
5.2基本單純形法
5.2.1單純形法的終止性質
5.2.2單純形法的初始化
5.3推廣到具有上下界約束的問題
5.4實現問題
5.5注釋，文獻和習題
第6章對偶上升方法
6.1對偶上升
6.2原對偶（序貫最短路）方法
6.3鬆弛方法
6.4求解已解決問題的變形
6.5實現問題
6.6注釋，文獻和習題
第7章拍賣算法
7.1指派問題的拍賣算法
7.1.1主拍賣算法
7.1.2近似坐標下降解釋
7.1.3拍賣算法的變形
7.1.4複雜性一E一伸縮
7.1.5處理不可行性
7.2拍賣算法的推廣
7.2.1逆向拍賣
7.2.2非對稱指派問題的拍賣算法
7.2.3同類人員拍賣算法
7.3最大流的預流推進法
7.3.1分析與複雜性
7.3.2實現問題
7.3.3與拍賣算法的關係
7.4 ε—鬆弛方法
7.4.1計算複雜性——ε—伸縮
7.4.2實現問題
7.5拍賣/序貫最短路算法
7.6注釋，文獻和習題
第8章非線性網路最佳化
8.1凸可分問題
8.2有附加約束的問題
8.3多商品流問題
8.4整數約束
8.5有增益的網路
8.6最優性條件
8.7對偶性
8.8算法和近似
8.8.1可行方向法
8.8.2分片線性近似
8.8.3內點法
8.8.4罰函式和增廣Lagrange方法
8.8.5近鄰最小化
8.8.6光滑化
8.8.7變換
8.9注釋，文獻和習題
第9章凸可分網路問題
9.1單變數凸函式
9.2最優性條件
9.3對偶性
9.4對偶函式可微性
9.5可微對偶問題算法
9.6拍賣算法
9.6.1 ε—鬆弛法
……
第10章整數約束網路問題
附錄A有關數學知識回顧
參考文獻
索引
文摘
著作權頁：
插圖：
網路流問題是最重要且最經常遇到的最佳化問題之一。它們自然地出現於通信、交通和製造網路這樣一些大系統的分析和設計問題中。它們也可用於描述指派、最短路和旅行商路線這樣一些組合問題。
籠統地說，網路流問題由供給點和需求點以及連線它們的若干路徑所組成，其作用是將供給轉運到需求。這些路徑可能包含中問轉運點。通常可以用圖的節點表示供給點、需求點以及轉運點，用圖的路表示路徑。另外，可能有多種“類型”的供給/需求（或“商品”）共享某些路徑。對路徑的特性也可能有某些約束，比如它們的載貨能力，使用特定路徑時還會有相應的費用。這些問題可以自然地建模為網路流最佳化問題，粗略地說，我們試圖通過網路流最佳化選出能夠以最小的費用將供給轉運到需求的路徑。
本書所處理的網路流最佳化問題非常廣泛，包括線性和非線性費用函式。我們應特別注意四類主要問題：
（1）轉運或最小費用流問題，包括一種商品和一個線性費用函式。該問題有若干重要特例，比如最短路、最大流、指派以及運輸問題。
（2）單商品凸費用網路流問題。該問題和前面的轉運問題相同，只是費用函式是凸函式而不僅是線性函式。
（3）多商品線性或凸費用網路流問題。該問題將前面的兩類問題推廣到多商品情況。
（4）離散網路最佳化問題。在這些問題中，沿著網路路徑傳輸的量只能取有限個數值。很多組合最佳化問題可以這樣建模，其中有些問題的網路結構並不很明顯。某些離散最佳化問題的計算非常困難，實踐中只能近似求解。它們的求解算法經常涉及求解前面三類“連續”的子問題。
上面提到的所有網路流問題都可以用和圖相關的概念建立數學模型。我們在1.1節引入有關符號和術語；在1.2節給出網路流最佳化模型的數學公式和實際例子；最後在1.3節對後面章節將提出的一些算法給出一個概述。
1.1圖和流
本節我們引入一些基本定義，涉及圖、路、流以及其他概念。圖的概念非常直觀，可以按照提示性圖形來理解，但也經常隱含一些微妙之處。因此讀者可能需要以後再回顧本節內容，並對有關定義的一些細微點進行更仔細的閱讀。
插圖：
網路流問題是最重要且最經常遇到的最佳化問題之一。它們自然地出現於通信、交通和製造網路這樣一些大系統的分析和設計問題中。它們也可用於描述指派、最短路和旅行商路線這樣一些組合問題。
籠統地說，網路流問題由供給點和需求點以及連線它們的若干路徑所組成，其作用是將供給轉運到需求。這些路徑可能包含中問轉運點。通常可以用圖的節點表示供給點、需求點以及轉運點，用圖的路表示路徑。另外，可能有多種“類型”的供給/需求（或“商品”）共享某些路徑。對路徑的特性也可能有某些約束，比如它們的載貨能力，使用特定路徑時還會有相應的費用。這些問題可以自然地建模為網路流最佳化問題，粗略地說，我們試圖通過網路流最佳化選出能夠以最小的費用將供給轉運到需求的路徑。
本書所處理的網路流最佳化問題非常廣泛，包括線性和非線性費用函式。我們應特別注意四類主要問題：
（1）轉運或最小費用流問題，包括一種商品和一個線性費用函式。該問題有若干重要特例，比如最短路、最大流、指派以及運輸問題。
（2）單商品凸費用網路流問題。該問題和前面的轉運問題相同，只是費用函式是凸函式而不僅是線性函式。
（3）多商品線性或凸費用網路流問題。該問題將前面的兩類問題推廣到多商品情況。
（4）離散網路最佳化問題。在這些問題中，沿著網路路徑傳輸的量只能取有限個數值。很多組合最佳化問題可以這樣建模，其中有些問題的網路結構並不很明顯。某些離散最佳化問題的計算非常困難，實踐中只能近似求解。它們的求解算法經常涉及求解前面三類“連續”的子問題。
上面提到的所有網路流問題都可以用和圖相關的概念建立數學模型。我們在1.1節引入有關符號和術語；在1.2節給出網路流最佳化模型的數學公式和實際例子；最後在1.3節對後面章節將提出的一些算法給出一個概述。
1.1圖和流
本節我們引入一些基本定義，涉及圖、路、流以及其他概念。圖的概念非常直觀，可以按照提示性圖形來理解，但也經常隱含一些微妙之處。因此讀者可能需要以後再回顧本節內容，並對有關定義的一些細微點進行更仔細的閱讀。
