網絡優化：連續和離散模型（簡體書）

《信息技術和電氣工程學科國際知名教材中譯本系列．網絡優化：連續和離散模型》不僅詳細介紹了經典的線性網絡優化模型、理論和方法，還分別對非線性網絡優化問題和具有一般性整數約束的網絡優化問題進行了廣泛而深入的討論，所涉及的網絡優化知識非常全面。書中不少材料源自作者本人在網絡優化相關領域多年的研究成果和研究心得，內容新穎，富有啟發性，與同類書籍相比具有鮮明的特色。通過閱讀《信息技術和電氣工程學科國際知名教材中譯本系列．網絡優化：連續和離散模型》，能夠對網絡優化模型、理論和方法建立完整的認識。
《信息技術和電氣工程學科國際知名教材中譯本系列．網絡優化：連續和離散模型》每章都配備了大量習題，適合用作網絡優化相關課程的教材。書中各章節內容既相互關聯，又相對獨立，便於教師根據課時安排進行適當的選擇。

《信息技術和電氣工程學科國際知名教材中譯本系列:網絡優化:連續和離散模型》每章都配備了大量習題，適合用作網絡優化相關課程的教材。書中各章節內容既相互關聯，又相對獨立，便于教師根據課時安排進行適當的選擇。

第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．3Dial算法
2．4標記修正法
2．4．1Bellman-Ford算法
2．4．2D'Esopo-Pape算法
2．4．3SLF算法和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．2Ford-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章單純形法
第6章對偶上升方法
第7章拍賣算法
第8章非線性網絡優化
第9章凸可分網絡問題
第10章整數約束網絡問題

附錄A有關數學知識回顧

參考文獻
索引

網絡流問題是最重要且最經常遇到的優化問題之一。它們自然地出現于通信、交通和制造網絡這樣一些大系統的分析和設計問題中。它們也可用于描述指派、最短路和旅行商路線這樣一些組合問題。
籠統地說，網絡流問題由供給點和需求點以及連接它們的若干路徑所組成，其作用是將供給轉運到需求。這些路徑可能包含中問轉運點。通常可以用圖的節點表示供給點、需求點以及轉運點，用圖的路表示路徑。另外，可能有多種“類型”的供給／需求（或“商品”）共享某些路徑。對路徑的特性也可能有某些約束，比如它們的載貨能力，使用特定路徑時還會有相應的費用。這些問題可以自然地建模為網絡流優化問題，粗略地說，我們試圖通過網絡流優化選出能夠以最小的費用將供給轉運到需求的路徑。
本書所處理的網絡流優化問題非常廣泛，包括線性和非線性費用函數。我們應特別注意四類主要問題：
（1）轉運或最小費用流問題，包括一種商品和一個線性費用函數。該問題有若干重要特例，比如最短路、最大流、指派以及運輸問題。
（2）單商品凸費用網絡流問題。該問題和前面的轉運問題相同，只是費用函數是凸函數而不僅是線性函數。
（3）多商品線性或凸費用網絡流問題。該問題將前面的兩類問題推廣到多商品情況。
（4）離散網絡優化問題。在這些問題中，沿著網絡路徑傳輸的量只能取有限個數值。很多組合優化問題可以這樣建模，其中有些問題的網絡結構并不很明顯。某些離散優化問題的計算非常困難，實踐中只能近似求解。它們的求解算法經常涉及求解前面三類“連續”的子問題。
上面提到的所有網絡流問題都可以用和圖相關的概念建立數學模型。我們在1.1節引入有關符號和術語；在1.2節給出網絡流優化模型的數學公式和實際例子；最后在1.3節對后面章節將提出的一些算法給出一個概述。
1.1圖和流
本節我們引入一些基本定義，涉及圖、路、流以及其他概念。圖的概念非常直觀，可以按照提示性圖形來理解，但也經常隱含一些微妙之處。因此讀者可能需要以后再回顧本節內容，并對有關定義的一些細微點進行更仔細的閱讀。