组合优化
点击看大图基本信息
- 原书名： Combinatorial Optimization
- 原出版社： Wiley-Interscience
- 作者： William J. Cook William H. Cunningham William R. Pulleyblank Alexander Schrijver [作译者介绍]
- 译者： 李学良 史永堂
- 丛书名： 组合数学丛书
- 出版社：高等教育出版社
- ISBN：9787040319590
- 上架时间：2011-4-2
- 出版日期：2011 年3月
- 开本：16开
- 页码：323
- 版次：1-1
- 所属分类：
数学 > 代数，数论及组合理论 > 组合数学
编辑推荐
组合优化是当今应用数学中最令人兴奋的领域之一
本书对组合优化做了全面、易懂的介绍
内容简介回到顶部↑
组合优化，作为应用数学中最年轻而又至关重要的领域之一，整合了组合数学、线性规划以及算法理论的方法和技巧。由于它在解决从远程通讯到超大规模集成电路、从产品运销到航班机组排班等领域内困难问题方面的成功，这一领域在过去的十年里取得了巨大的、超乎寻常的发展。
《组合优化》是对这一数学分支的一个理想介绍，它适用于离散数学、计算机科学以及运筹学专业的本科高年级学生和研究生。本书由公认的专家团队撰写而成，对经典概念和最新结果都提供了全面而又易懂的讲解。主要涉及以下课题：
·网络流问题
·最优匹配
·多面体的整性
·拟阵
·np-完全性
《组合优化》以通畅而连贯的讲解、基本和高深概念的清晰解释、众多现实生活中的实例、以及颇有助益的技巧训练习题为特征，一定会成为未来许多年里本领域内的标准教科书。
《组合优化》是对这一数学分支的一个理想介绍，它适用于离散数学、计算机科学以及运筹学专业的本科高年级学生和研究生。本书由公认的专家团队撰写而成，对经典概念和最新结果都提供了全面而又易懂的讲解。主要涉及以下课题：
·网络流问题
·最优匹配
·多面体的整性
·拟阵
·np-完全性
《组合优化》以通畅而连贯的讲解、基本和高深概念的清晰解释、众多现实生活中的实例、以及颇有助益的技巧训练习题为特征，一定会成为未来许多年里本领域内的标准教科书。
作译者回到顶部↑
本书提供作译者介绍
William J. Cook 现任美国佐治亚理工学院教授, 1983 年获得加拿大滑铁卢大学博士学位, 1998 年被邀请在国际数学家大会上作45 分钟报告, 2003 年、2004年、2009 年分别担任Beale-Orchard-Hays 奖、George Polya 奖、Fulkerson 奖的评审主席. 主要研究领域为整数规划与组合优化, 所出版的专著《The TravelingSalesman Problem: A Computational Study》于2007 年获Lanchester 奖.William H. Cunningham 现任加拿大滑铁卢大学数学系教授, 1971 年获得博士学位, 主要研究领域为组合优化、多面体组.. << 查看详细
目录回到顶部↑
《组合优化》
著者简介
序言
译者序
第一章问题和算法 1
x1.1 两个问题 1
x1.2 度量运行时间 4
第二章最优树和最优路 9
x2.1 最小生成树 9
x2.2 最短路 18
第三章最大流问题 35
x3.1 网络流问题 35
x3.2 最大流问题 35
x3.3 最大流和最小割的应用 43
x3.4 压入重标记最大流算法 57
x3.5 无向图中的最小割 66
3.5.1全局最小割(66) 3.5.2割树(72)
x3.6 多商品流 78
第四章最小费用流问题 83
x4.1 最小费用流问题 83
著者简介
序言
译者序
第一章问题和算法 1
x1.1 两个问题 1
x1.2 度量运行时间 4
第二章最优树和最优路 9
x2.1 最小生成树 9
x2.2 最短路 18
第三章最大流问题 35
x3.1 网络流问题 35
x3.2 最大流问题 35
x3.3 最大流和最小割的应用 43
x3.4 压入重标记最大流算法 57
x3.5 无向图中的最小割 66
3.5.1全局最小割(66) 3.5.2割树(72)
x3.6 多商品流 78
第四章最小费用流问题 83
x4.1 最小费用流问题 83
译者序回到顶部↑
《组合优化》的四位作者William J. Cook, William H. Cunningham, William R.Pulley-blank, Alexander Schrijver 均为组合优化方面的著名专家, 他们不仅研究成果卓著, 而且出版了一些很有影响力的著作和教材. 这本《组合优化》就是其中的一部经典教材.
《组合优化》共分九章, 另外还添加了一个附录A. 第一章从旅行售货商问题和匹配问题这两个重要例子出发, 简单介绍了什么是组合优化问题, 什么是算法, 以及如何度量算法的运行时间; 第二章介绍了最小生成树和最短路算法; 第三章从对最大流问题的刻画开始, 详细阐述了最大流与最小割定理及其在多个不同实际问题中的应用, 深入探讨了最大流算法, 另外还简单介绍了多商品流问题; 第四章介绍了最小费用流问题及相关算法, 其中包括原始对偶算法和对偶尺度放大算法; 第五章介绍了最优匹配问题及相关算法, 包括最大匹配的花算法、最小权完美匹配的花算法、一般匹配问题的算法等, 还讨论了匹配算法在邮递员问题及双层嵌入等问题中的应用; 第六章介绍了整多面体和有界多面体的相关概念和基本知识, 针对匹配问题介绍了割平面算法和整数线性规划算法; 第七章介绍了旅行售货商问题的多种启发式算法, 以及割平面算法和分支定界法; 第八章介绍了拟阵的相关概念和基本知识, 阐述了拟阵交算法及其相关应用; 第九章简单介绍了NP 类问题和NP-完全性, 并证明了几个著名问题的NP-完全性, 形式地定义了问题、算法及运行时间, 并简单介绍了图灵机; 最后, 附录A 罗列了线性规划的基本知识, 这在前面的章节中将要用到.
受高等教育出版社的邀请翻译这本著名教材, 我们感到非常荣幸, 但也感到诚惶诚恐, 而且越翻译就越感到压力大. 我们深深地感到, 读懂一部原著是一回事, 而翻译好一部原著又是一回事, 区别关键在于精准上. 我们本着尽量遵循作者原意的原则进行翻译, 而不是像自己重写一部这方面的教材那样, 以便使得读者能够品尝到本书的原味. 但由于我们的翻译水平有限, 不妥之处在所难免, 错误之处还请读者不吝赐教, 我们当深表感谢.
《组合优化》的翻译初稿是在2009 学年讲授组合优化这门课程时形成的, 我们要感谢参加的博士研究生, 他们是李莎莎、李玮、李静、火博丰、马红平、李磊、孙跃方、李一阳、计省进、陈莉莉、刘蒙蒙. 初稿之后, 我们又核对了多遍, 并对有些单词反复查询词典, 体会作者的用意, 在此过程中, 前三位博士生付出了很多的时间和精力. 本书由高等教育出版社引进出版, 编辑赵天夫先生一直鼓励我们翻译此书, 并耐心回答我们的各种问题, 我们衷心地感谢他为本书的出版所做的努力, 可以说没有他的鼓励和督促就没有这本翻译教材. 最后感谢南开大学组合数学中心对译者们的大力支持.
译者
2011 年1 月
南开大学组合数学中心
《组合优化》共分九章, 另外还添加了一个附录A. 第一章从旅行售货商问题和匹配问题这两个重要例子出发, 简单介绍了什么是组合优化问题, 什么是算法, 以及如何度量算法的运行时间; 第二章介绍了最小生成树和最短路算法; 第三章从对最大流问题的刻画开始, 详细阐述了最大流与最小割定理及其在多个不同实际问题中的应用, 深入探讨了最大流算法, 另外还简单介绍了多商品流问题; 第四章介绍了最小费用流问题及相关算法, 其中包括原始对偶算法和对偶尺度放大算法; 第五章介绍了最优匹配问题及相关算法, 包括最大匹配的花算法、最小权完美匹配的花算法、一般匹配问题的算法等, 还讨论了匹配算法在邮递员问题及双层嵌入等问题中的应用; 第六章介绍了整多面体和有界多面体的相关概念和基本知识, 针对匹配问题介绍了割平面算法和整数线性规划算法; 第七章介绍了旅行售货商问题的多种启发式算法, 以及割平面算法和分支定界法; 第八章介绍了拟阵的相关概念和基本知识, 阐述了拟阵交算法及其相关应用; 第九章简单介绍了NP 类问题和NP-完全性, 并证明了几个著名问题的NP-完全性, 形式地定义了问题、算法及运行时间, 并简单介绍了图灵机; 最后, 附录A 罗列了线性规划的基本知识, 这在前面的章节中将要用到.
受高等教育出版社的邀请翻译这本著名教材, 我们感到非常荣幸, 但也感到诚惶诚恐, 而且越翻译就越感到压力大. 我们深深地感到, 读懂一部原著是一回事, 而翻译好一部原著又是一回事, 区别关键在于精准上. 我们本着尽量遵循作者原意的原则进行翻译, 而不是像自己重写一部这方面的教材那样, 以便使得读者能够品尝到本书的原味. 但由于我们的翻译水平有限, 不妥之处在所难免, 错误之处还请读者不吝赐教, 我们当深表感谢.
《组合优化》的翻译初稿是在2009 学年讲授组合优化这门课程时形成的, 我们要感谢参加的博士研究生, 他们是李莎莎、李玮、李静、火博丰、马红平、李磊、孙跃方、李一阳、计省进、陈莉莉、刘蒙蒙. 初稿之后, 我们又核对了多遍, 并对有些单词反复查询词典, 体会作者的用意, 在此过程中, 前三位博士生付出了很多的时间和精力. 本书由高等教育出版社引进出版, 编辑赵天夫先生一直鼓励我们翻译此书, 并耐心回答我们的各种问题, 我们衷心地感谢他为本书的出版所做的努力, 可以说没有他的鼓励和督促就没有这本翻译教材. 最后感谢南开大学组合数学中心对译者们的大力支持.
译者
2011 年1 月
南开大学组合数学中心
序言回到顶部↑
组合优化(也称为组合最优化), 是应用数学的一个活跃领域, 它把组合数学、线性规划以及算法理论的技术结合起来解决离散结构上的最优化问题. 这个领域里已经有许多经典的教材, 但我们觉得还存在空间对这门学科进行新的论述, 以覆盖过去十年里所取得的一些进展. 我们本来打算将这些素材形成一本适合一个学期课程的基本教材, 然而事实证明包含前沿课题的迫切要求是不可抵挡的, 因而手稿内容逐渐增加, 最终超过了人们对一学期课程所能覆盖内容的合理期望. 本书可以允许教师从所论述的众多课题中适当挑选授课内容, 我们希望这是一个优点. 这样, 本书可以作为数学系、运筹学系和计算机科学系本科生和研究生的教程. 高等理论课程可能需要用一到两次课讲授第二章、3.1 和3.2 节, 然后集中讲授3.3、3.4、4.1 节以及第五、六章的大部分和第八、九章的一些部分. 入门课程可能要覆盖第二章、3.1 到3.3 节、4.1 节、4.2 或者4.3 节两节之一, 以及5.1 到5.3 节. 更多关于整数线性规划和多面体方法的课程可以主要基于第六、七章, 并将包含3.6 节.
最具挑战性的习题已经用黑体标出, 这些应该只可能用在高等课程中.阅读我们的教材仅需的先决条件是有一定的数学基础. 我们频繁地使用了线性规划对偶, 因此不熟悉这个主题的读者应该在学习课本主要内容之前预先学习附录中的线性规划.许多阅读过本书早期手稿的同行们给出了中肯贴切的评论和建议, 我们从中获益很大. 特别地, 我们要感谢Hernan Abeledo, Dave Applegate, Bob Bixby,Andre Bouchet, Eddie Cheng, Joseph Cheriyan, Collette Coullard, Satoru Fu-jishige, Grigor Gasparian, Jim Geelen, Luis Goddyn, Michel Goemans, Mark Hartmann, Mike Jaunger, Jon Lee, Tom McCormick, Kazuo Murota, Myriam Preiss-mann, Irwin Pressman, Maurice Queyranne, Andre Rohe, Andras Sebo, Eva Tar-dos 以及Don Wagner. 这本书是在Bellcore、Bonn 大学、Carleton 大学、CWIAmsterdam、IBM Watson Research、Rice 大学以及Waterloo 大学完成的.有关本书的信息, 包括勘误表, 能够在网站
http://www.math.uwaterloo.ca/swhcunnin/bookpage.html上找到.
最具挑战性的习题已经用黑体标出, 这些应该只可能用在高等课程中.阅读我们的教材仅需的先决条件是有一定的数学基础. 我们频繁地使用了线性规划对偶, 因此不熟悉这个主题的读者应该在学习课本主要内容之前预先学习附录中的线性规划.许多阅读过本书早期手稿的同行们给出了中肯贴切的评论和建议, 我们从中获益很大. 特别地, 我们要感谢Hernan Abeledo, Dave Applegate, Bob Bixby,Andre Bouchet, Eddie Cheng, Joseph Cheriyan, Collette Coullard, Satoru Fu-jishige, Grigor Gasparian, Jim Geelen, Luis Goddyn, Michel Goemans, Mark Hartmann, Mike Jaunger, Jon Lee, Tom McCormick, Kazuo Murota, Myriam Preiss-mann, Irwin Pressman, Maurice Queyranne, Andre Rohe, Andras Sebo, Eva Tar-dos 以及Don Wagner. 这本书是在Bellcore、Bonn 大学、Carleton 大学、CWIAmsterdam、IBM Watson Research、Rice 大学以及Waterloo 大学完成的.有关本书的信息, 包括勘误表, 能够在网站
http://www.math.uwaterloo.ca/swhcunnin/bookpage.html上找到.
加载中...
