组合优化导论 第二版
出版时间：2014年版
丛编项： 运筹与管理科学丛书
内容简介
《组合优化导论（第二版）》内容分为如下几个部分：（1）介绍组合优化这门学科的主要内容；（2）介绍排序问题中一些已经解决的经典问题，主要是整理前人的研究成果；（3）讲解一种启发式算法，这是根据20世纪70年代我与韩继业同志的一项工作中的想法，由韩发展起来的，据说实际效果不错。（4）本书其余部分则是介绍作者在20世纪后期所作的关于组合优化中几个著名问题的近似算法的改进。上述内容（除第一部分外）曾于2000年以《组合优化导论》为书名出版。十年过去了，该书的处理方法必须作重大的修改，例如，“装箱问题”一章，应将Karmarkar与Karp的工作包括进来，并从实用动力这一角度将两条途径的优劣进行比较。最后关于Steiner树的一章，有读者反映艰涩难懂，因此也必须完全重写。
目录
目录
第二版前言
第一版前言
第1章 概述 l
1.1 组合优化问题的算法 l
1.1.1 算法 1
1.1.2 算法的评估2
1.2 排序问题的记号和模型描述 2
1.2.1 排序问题的记号 2
1.2.2 排序问题的模型描述 3
第2章 一台机器上的排序 6
2.1 1
2 1.1 算法 6
2 1.2 最优性证明6
2.1.3 另一个问题 7
2.1.4 8
2.2 8
2.2.1 算法 8
2.2.2 最优性证明9
2.3 在某些工件必须按时交货的条件下的模型 12
2.3.1 算法 13
2.3.2 最优性证明 14
2.4 模型 17
2.4.1 算法 18
2.4.2 最优性证明 19
2.5 25
2.5.1 枚举树 26
2.5.2 消去准则 26
2.5.3 消去准则的应用 30
2.5.4 下界 31
2.6 35
2.6.1 算法 35
2.6.2 最优性证明 36
2.6.3 37
2.7 模型 37
2.7.1 无先后关系的模型 38
2.7.2 有先后关系的模型 40
2.8 一个应用例子——循环矩阵 42
2.8.1 问题的提出 42
2.8.2 实例 43
2.8.3 Hamilton循环 47
第3章 两台机器的情形 50
3.1 问题的提出 50
3.1.1 第一种情形 50
3.1.2 第二种情形 50
3.1.3 第三种情形 50
3.1.4 若干指标和记号 50
3.2 模型52
3.2.1 算法 52
3.2.2 最优性证明 52
3.3 模型56
3.3.1 算法 56
3.3.2 最优性证明 56
3.4 模型56
3.4.1 算法 56
3.4.2 最优性证明 58
3.5 模型60
3.5.1 问题的解法 60
3.5.2 模型的一般情况 61
3.6 树状或林状的工件加工系统：树状或林状 62
3.6.1 问题的提出 62
3.6.2 算法 63
3.6.3 最优性证明 64
3.7 65
3.7.1 算法 65
3.7.2 最优性证明 65
3.8 66
3.8.1 问题的提出 66
3.8.2 Fujii等的算法67
3.8.3 Edmonds的算法 67
3.8.4 M-花朵方法 69
3.8.5 CG方法 74
第4章 近似算法 77
4.1 概述 77
4 .1.1 设计算法 77
4.1.2 模拟求解 77
4.1.3 近似算法求解 77
4.2 近似解的定义 77
4.2.1 一些定义 77
4.2.2 实例 79
4.3 一些排序问题的近似计算 80
4.3.1 LPT算法 80
4.3.2 完工时间的估算 83
4.3.3 两台机器的情形 85
4.4 装箱问题 89
4.4.1 NF算法 90
4.4.2 FF算法 90
4.4.3 BF算法 96
4.5 装箱问题（续） 96
4.5.1 记导 97
4.5.2 引理和定理 98
4.5.3 例子 101
4.6 FFD算法 102
4.6.1 FFD算法的由来 102
4.6.2 定理和证明 103
4.6.3 更紧界的证明 111
4 6.4 紧界的证明 117
4.6.5 FFD算法对小物件装箱的渐近最坏性能比 123
4.6.6 附录：Csirik(1993)的有关结论及证明 129
4.7 排序问题与装箱问题的联系 144
4.7.1 问题简化法 144
4.7.2 权函数法 l45
4.7.3 FFD算法在排序问题上的运用 145
4 7.4 上界的改进 150
第5章 流水作业排序问题的最优算法 156
5.1 消去准则 156
5.1.1 排序问题的消去准则 156
5.1.2 消去准则的选取 159
5 1.3 任意条件下的消去准则 163
5.2 分枝定界方法 163
5.2.1 定义 163
5.2.2 分枝方法 l64
5.3 上界和下界的估计 165
5 3.1 瓶颈机器 165
5.3.2 下界计算 165
5.3.3 上界计算 l67
第6章 Steiner 比猜想 169
6.1 Steiner 比猜想 169
6 1.1 生成树 l69
6.1.2 Steiner树 171
6.1.3 简单回顾 l72
6.2 关子n=3，4，5的情况 172
6.2.1 n=3 173
6.2.2 n=4 176
6.2.3 n=5 l80
6.3 一般情况 186
6.3.1 问题的提出 186
6 3.2 预备知识 186
6.4 Steiner比猜想的证明 191
6.4.1 情形 19l
6.4.2 情形 195
6.4.3 其他情形 197
6.5 评注 197
第7章 多重算法 198
7.1 引言 198
7.1.1 简单回顾 198
7.1.2 最小反例 200
7.1.3 k件箱 202
7.2 若干引理 202
7.2.1 对△的分划 202
7.2.2 和 202
7.2.3 204
7.2.4 时的权函数 206
7.2.5 最优箱 209
7.3 无型物件或箱 213
7.3.1 无型物件 213
7.3.2 无型物件 214
7.4 不同数值的△的多重算法 219
7.4.1 219
7.4.2 220
7.4.3 221
7.4.4 223
7.4.5 的若干情况 226
参考文献 230
索引 234
