離散最優化算法（簡體書）

最優化算法是20世紀中葉發展起來的一門學科，既有久遠的歷史淵源，又有廣闊的應用前景。在計算機時代，最優化算法更呈現出異彩紛呈的發展態勢。劉振宏、馬紹漢編著的《離散最優化算法》共八章，前四章介紹最優化算法的經典內容，後四章包含了最優化算法近年來的發展，如逆最優化問題和近似算法。書中還講述了作者在組合優化領域所做的創造性的工作。為便於消化和理解書中的內容，每章末附有習題和參考文獻。
《離散最優化算法》可作為高等院校運籌學與控制論、計算機應用、系統工程等學科的高年級本科生、研究生的教材，也可供從事這方面工作的科技工作者參考。

《中創軟件叢書:離散最優化算法》可作為高等院校運籌學與控制論、計算機應用、系統工程等學科的高年級本科生、研究生的教材，也可供從事這方面工作的科技工作者參考。

第一章線性規劃
1.1線性規劃的基本概念
1.2單純形算法
1.3線性規劃的對偶理論
1.4對偶單純形算法
1.5原始一對偶算法
1.6單純形算法是非多項式算法
1.7線性規劃問題的多項式時間算法
習題
參考文獻

第二章整數線性規劃
2.1引言
2.2分數對偶割平面算法
2.3整數對偶割平面算法
2.4混合整數規劃的割平面算法
2.5分支估界算法
2.60-1規劃的隱數法（implicitentimeration）
習題
參考文獻

第三章網絡規劃
3.1圖的搜索算法
3.1.1無向圖的深探法（DFS）
3.1.2無向圖的廣探法（BFS）
3.2網絡流模型及解的整數性
3.3網絡中的最短路
3.3.1非負權網絡的最短路算法
3.3.2無負回路網絡中的最短路算法
3.3.3所有點對之間的最短路算法
3.4網絡中的最大流
3.4.1最大流的Ford-Fulkerson算法
3.4.2最大流的Dinits算法
3.4.3容量具有上下界的最大流算法
3.4.4可行性定理及其組合應用
3.5最小費用流
3.5.1模型Ⅱ的相繼最短路算法
3.5.2最小費用循環流的平均圈算法
習題
參考文獻

第四章樹與擬陣
4.1樹的基本性質
4.2樹的中心與重心
4.3無向網絡中的最優生成樹
4.4有向樹
4.5擬陣的基本概念與性質
4.5.1擬陣的定義與例子
4.5.2擬陣的～些基本性質
4.6擬陣與Greedy算法
4.7擬陣的最大交
4.8最大權交的算法
習題
參考文獻

第五章動態規劃
5.1網絡中兩點間的最優路問題
5.2用動態規劃方法解某些非線性規劃
5.3用動態規劃方法解某些整數規劃
5.4生產計劃與資源分配問題
5.4.1生產計劃問題
5.4.2資源分配問題
5.5排序問題
5.5.1排序問題
5.5.2貨郎問題
5.6矩陣鏈與公共子序列
5.6.1矩陣鏈中矩陣相乘的順序問題
5.6.2最長公共子序列問題
習題
參考文獻

第六章逆最優化問題
6.1逆線性規劃的一般模型
6.2在范數l1下式（6.1.5）和式（6.1.6）的解
6.2.1給定的可行解x0為0-1的解
6.2.2在范數l1下模型LP2的解
6.3在范數l∞下式（6.1.5）和式（6.1.6）的解
6.4組合優化的逆問題一般模型
6.5各種逆最優化問題的歸結
6.6瓶頸擴張問題的一例
習題
參考文獻

第七章算法、複雜性與NP-完全理論
7.1問題、算法與複雜性
7.2多項式算法P類和NP類
7.3多項式變換與NPC類
7.4NP-完全問題的證明舉例
7.5關於NP-完全性的另一些概念
7.5.1Co-NP類
7.5.2NP-hard類
7.5.3偽多項式算法與強NP-完全性
習題
參考文獻

第八章近似算法及其分類
8.1近似算法的基本概念
8.2非空閒策略
8.3Greedy算法
8.4局部搜索
8.5基於線性規劃的近似算法
8.6基於動態規劃的近似算法
8.7絕對近似類
8.8相對近似類
8.9PTAS類與FPTAS類
8.10隨機近似算法
8.11近似算法的概率分析
習題
參考文獻

第四章 樹與擬陣
擬陣（matroid）是矩陣（matrix）的衍生詞。擬陣概念是Whitney在1935年提出來的，它是向量空間中線性獨立性質的抽象，擬陣中所用的若干術語多半來自于代數和圖論。
在20個世紀40年代，R.Rado將擬陣理論應用到組合數學中的“代表系”問題，從而推廣了P.Hall的著名“Marriage定理”，大約與此同時，R.F.Dilworth建立了擬陣與格論之間的聯系。這樣一來，擬陣就成為組合數學中的一個分支。大約20世紀60年代中期，W.T.Tutte從圖論觀點較詳細地研究了擬陣的一些基本性質，給出了多種類型的擬陣的例子。1975年R.Von.Randow綜合了幾種不同的公理系統，并證明了它們之間的等價性質，此后擬陣理論已廣泛應用到圖論、格論、投影幾何、電網絡和開關理論等方面。J.Edmonds和E.Lowler等把擬陣理論應用于離散最優化問題，給出了求一個擬陣的最大權獨立集和兩個擬陳最大權交的算法，從而把離散最優化中若干問題給出了統一描述和統一的算法。
本章從網絡中最優樹和最優樹形圖出發，介紹了它們的求解方法，并由此引出擬陣的定義、性質以及求擬陣的最大權獨立集和兩個擬陣最大權交的算法。由于擬陣是一種抽象的系統，所以在介紹這些概念時，盡量用比較直觀的網絡結構和向量空間的向量相關性等加以說明，因此，讀者需要具備圖論的基本知識，如果需要可查閱文獻[徐利治，20003。
4.1樹的基本性質
一個圖G=（V，E），若G連通且不含圈，則稱G為一棵樹。設T=（V，E）是n個頂點的圖，則下述諸結論等價：
1）T是一棵樹。
2）T有n—1條邊且無圈。
3）T有n—1條邊且連通。
4）T連通，但去掉T中任一條邊后，則剩下的圖就不連通了。
5）丁中任何一對頂點間有唯一一條路。
6）T無圈，但在T中增加任何一條邊，則有唯一一個圈。
同樣，這n—1個割向量構成G的割空間，在模2域上，G的任一個割都可以用這個n—1個割表示。可以證明，在模2域上圈空間和割空間是正交的，即G的任何一個圈向量和任何一個割向量的內積，在模2下等于0，或者說任何一個圈C和任何一個割Ω，恒有｜C∩Ω ｜≡0（mod2），這一性質在后面還要多次用到。