第一章 線性規划
1.1 線性規划的基本概念
1.2 單純形算法
1.3 字典序單純形算法
1.4 對偶理論
1.5 內點算法
第二章 多面體理論
2.1 多面體的定義及其維數
2.2 用有效不等式與邊界面來描述多面體
2.3 用極點和極射向表示多面體
第三章 圖與網絡規划
3.1 圖的基本知識
3.2 幾類重要的圖
3.3 最短路間題
3.4 最小權支撐樹問題
3.5 最大流問題
第四章 動態規划方法
4.1 多階段決策問題與動態規划的基本概念
4.2 動態規划方法的基本思想與最優性定理
4.3 最小權問題
4.4 背包問題
4.5 旅行商問題
第五章 算法復雜性概論
5.1 引言
5.2 基本概念
5.3 多項式時間算法與指數時間算法
第六章 問題復奈性的分類
6.1 判定問題與語言
6.2 算法的嚴格定義與P類問題。
6.3 NP類問題
6.4 多項式變換與MD完全問題
6.5 強MD完全問題
6.6 CO-NP類問題
6.7 NP困難問題
6.8 空間復雜性簡介
第七章 證明問題為NP完全的或P的方法
7.1 證明問題為NPC的一般步驟
7.2 限制法(Restr1ct1on)
7.3 局部置換法(Local Rep1acement)
7.4 分量設計法(Component Des1gn)
7.5 證明問題屬於P類的方法
第八章 NP完全理論在分析、求解新問題中的應用
8.1 分析新問題復雜性的雙向研究方法
8.2 子問題分析法
8.3 求解NPC問題的算法類型
第九章 近似算法的性能度量與NP完全理論的應用
9.1 近似算法的性能度量
9.2 NP完全理論在限定問題可近似程度中的應用
第十章 一般整數規划的基本性質
10.1 一般整數規划問題
10.2 整數規划與線性規划之間的關系
10.3 整數規划問題解的有界性
10.4 整數規划問題的計算復雜性
第十一章 割平面算法
11.1 分數割平面算法
11.2 整數割平面算法
11.3 導出有效不等式的方法
11.4 混合整數規划問題的求解
11.5 覆蓋問題的割平面算法
第十二章 分解算法
12.1 拉格朗日松弛法
12.2 Benders分解
12.3 一般分解方法
12.4 選址問題的分解算法
第十三章 分枝定界法
13.1 一般分枝定界法
13.2 使用線性規划松弛的分枝定界算法
13.3 0-1背包問題的分枝定界算法。
第十四章 匹配問題
14.1 匹配問題簡介
14.2 最大匹配問題
14.3 加權匹配問題
14.4 b匹配問題與其他相關論題
第十五章 近似算法的設計與分類
15.1 近似算法概述
15.2 貪婪算法(Greedy Algor1thms)
15.3 局部搜索法(Local Search Heur1st1cs)
15.4 原始-對偶法
15.5 近似算法的其他設計方法
15.6 近似算法的分類
第十六章 對稱旅行商問題
16.1 有效不等式的構造
16.2 松弛問題的構造
16.3 近似算法
16.4 精確算法
參考文獻
