第一章 线性规划 1
1.1 线性规划的基本概念 1
1.2 单纯形算法 4
1.3 字典序单纯形算法 7
1.4 对偶理论 10
1.5 内点算法 14
第二章 多面体理论 21
2.1 多面体的定义及其维数 21
2.2 用有效不等式与边界面来描述多面体 23
2.3 用极点和极射向表示多面体 26
第三章 图与网络规划 34
3.1 图的基本知识 34
3.1.1 图 34
3.1.2 有向图 36
3.1.3 图的表示 38
3.2 几类重要的图 41
3.3 最短路问题 42
3.4 最小权支撑树问题 44
3.5 最大流问题 45
第四章 动态规划方法 53
4.1 多阶段决策问题与动态规划的基本概念 53
4.2 动态规划方法的基本思想与最优性定理 55
4.3 最小权问题 59
4.4 背包问题 61
4.4.1 0-1背包问题 61
4.4.2 整数背包问题 63
4.5 旅行商问题 65
第五章 算法复杂性概论 68
5.1 引言 68
5.2 基本概念 69
5.3 多项式时间算法与指数时间算法 71
第六章 问题复杂性的分类 75
6.1 判定问题与语言 75
6.2 算法的严格定义与P类问题 78
6.3 NP类问题 80
6.4 多项式变换与NP完全问题 84
6.5 强NP完全问题 87
6.6 Co-NP类问题 90
6.7 NP困难问题 92
6.8 空间复杂性简介 95
第七章 证明问题为NP完全的或P的方法 97
7.1 证明问题为NPC的一般步骤 97
7.2 限制法(Restriction) 100
7.3 局部置换法(Local Replacement) 101
7.4 分量设计法(Component Design) 105
7.5 证明问题属于P类的方法 110
第八章 NP完全理论在分析、求解新问题中的应用 114
8.1 分析新问题复杂性的双向研究方法 114
8.2 子问题分析法 116
8.3 求解NPC问题的算法类型 119
第九章 近似算法的性能度量与NP完全理论的应用 125
9.1 近似算法的性能度量 125
9.2 NP完全理论在限定问题可近似程度中的应用 134
第十章 一般整数规划的基本性质 137
10.1 一般整数规划问题 137
10.2 整数规划与线性规划之间的关系 139
10.3 整数规划问题解的有界性 143
10.4 整数规划问题的计算复杂性 146
第十一章 割平面算法 150
11.1 分数割平面算法 150
11.2 整数割平面算法 154
11.3 导出有效不等式的方法 161
11.3.1 取整方法 161
11.3.2 同余方法 162
11.3.3 合并方法 162
11.3.4 超加函数法 163
11.4 混合整数规划问题的求解 167
11.5 覆盖问题的割平面算法 173
11.5.1 覆盖问题的描述 173
11.5.2 覆盖问题的割平面算法 175
第十二章 分解算法 179
12.1 拉格朗日松弛法 179
12.2 Benders分解 185
12.3 一般分解方法 188
12.4 选址问题的分解算法 192
13.1 一般分枝定界法 196
第十三章 分枝定界法 196
13.2 使用线性规划松弛的分枝定界算法 199
13.2.1 剪枝准则 199
13.2.2 分枝方法 200
13.2.3 结节选取方法 202
13.2.4 分枝变量选择力法 203
13.3 0-1背包问题的分枝定界算法 206
第十四章 匹配问题 210
14.1 匹配问题简介 210
14.2 最大匹配问题 212
14.2.1 二部图的匹配算法 214
14.2.2 非二部图的匹配算法 216
14.3 加权匹配问题 222
14.3.1 指派问题的求解 222
14.3.2 一般加权匹配问题 226
14.4.1 b匹配问题 232
14.4 b匹配问题与其他相关论题 232
14.4.2 匹配理论与算法的应用 236
第十五章 近似算法的设计与分类 240
15.1 近似算法概述 240
15.2 贪婪算法(Greedy Algorithms) 241
15.3 局部搜索法(Local Search Heuristics) 242
15.4 原始-对偶法 245
15.5 近似算法的其他设计方法 250
15.6 近似算法的分类 253
15.6.1 定常近似比算法 254
15.6.2 近似策略 255
15.6.3 最好可能近似比算法 258
15.6.4 比最好还要好的近似算法 260
15.6.5 与真正最优值仅一步之遥的近似算法 262
16.1 有效不等式的构造 264
第十六章 对称旅行商问题 264
16.2 松弛问题的构造 270
16.3 近似算法 273
16.3.1 最近邻法 274
16.3.2 最近插入法 274
16.3.3 贪婪可行法 275
16.3.4 k边交换法 275
16.3.5 三角不等式与贪婪型算法的性能 275
16.3.6 支撑树加倍法 279
16.3.7 支撑树加完美匹配法 280
16.4 精确算法 282
16.4.1 指派问题加分枝定界算法 283
16.4.2 拉格朗日松弛加分枝定界算法 284
16.4.3 分数割平面加分枝定界算法 285
参考文献 289