本书是罗纳德 L.拉丁所著的经典教材，时隔18年首次修订，面向本科生（姊妹篇Discrete Optimization针对研究生阶段的学生，1988年问世），首版于1998年，被美国工业工程师协会（IIE）评选为年度图书。
本书宗旨是给不同学科背景的读者提供运筹学学习的全面指南。
涵盖运筹学的全部内容（整数、非整数算法，网络编程，动态数学建模等）， 加入了众多主题和案例，每种算法和分析都配有一个小故事和计算练习。
修订版本提升了本书作为本科生教材的难度，与研究生阶段的内容衔接更为紧密，同时又可作为研究、专业人员的自学和参考用书。已被普渡大学、加州大学艾文分校、华盛顿大学等高校采用。
1
距离《运筹学》（Optimization in Operations Research）第1版出版已近20年了。在此期间上千学生和百余名教师、研究人员和相关从业者有机会从本书的连贯性内容和易读性设计中受益。诚然，这本书很难让所有读者都受益，但仍然有很多人通过书评或信件的方式表达了他们对这本书的赞许之情。美国工业工程师协会也高度评价了此书，并授予其1999年联合出版年度图书奖。
在第2版中，我尽量保留了上一版中最好的部分，并在其基础上加入了新的内容。本书的编写目标不变——给那些在学习过程中的高年级本科生或刚入学的研究生以及参照本书自学的研究人员和业界相关从业者提供优化建模和分析的工具，希望他们将学习到的相关知识技能与管理洞察力应用在实际操作中，为以后的工作提供帮助。
本书第2版中增加了许多新内容：
●在第4章随机优化问题中，第一次引入了随机规划的相关内容，并在第9章讨论了马尔可夫决策过程。
●关于线性规划的讨论，在第6章加入了两种对偶方法（即encompass dual和primal-dual方法）。
●新内容详细整理了最优化问题的各种情况，包括第6章的线性规划与第12章的割平面法。
●将匈牙利算法纳入作业部分，并在第10章加入最小/最大生成树方法的介绍。
●新加入的第13章介绍了大规模最优化问题的相关知识，包括延迟列生成算法、拉格朗日松弛定理、Dantzig-Wolfe分解与Benders分割法。
●新加入的第14章介绍了有关计算复杂度的各种理论，以便更精确地比较问题和算法。
●有关非线性规划的第17章现在涵盖了比较流行的序列二次规划方法。
●在整本教材中提高了数学的严谨性，比如细化了相关计算步骤。
为了满足读者的兴趣和需求，本书加入了很多新内容，使得关于最优化和数学规划问题的讨论更加全面。这些内容涵盖线性规划、整数规划、非线性规划、网络规划和动态规划模型及算法，以及这些问题应用领域的丰富案例。
由于本书内容面广，显然许多读者阅读和课程教学中很少会用到整本书的内容，也不会按照书中内容顺序来使用。所以，我尽量合理组织各章节内容，让它们尽可能通俗易懂并易于跳跃、重复阅读。
章节之间互相依赖的内容已尽可能删减，留下的部分也有清晰的引用标注。预备知识简明地梳理了与所学内容相关的基础知识。而定义、原理和算法被安排在显眼的框图中，便于读者查询和理解。当需要更多篇幅涉及计算和延伸讨论等细节内容时，为了易于阅读，它们被概括总结到例题中。每个章节最后都配有练习题，题前有相关图标标识哪些题目需要电脑软件（）、计算器（）和在网站配有参考答案（）。
为了能让不同知识背景的读者都感到最优化问题的教材有趣且易读，需要将最优化模型和问题相结合，这是我在撰写此书时一个坚定的想法。所以在应用案例中每个算法和分析都由一个简短的故事引入。而且在练习题中，计算题也通常会先将问题模型化。这些故事大部分都源于真实的运筹学案例。故事的设定有时看起来不太自然，但都能帮助读者理解模型的决策变量、约束和目标以及计算的步骤。比如相比于单单一个抽象的数学函数，故事中的某些变量能随着算法的引入而改善，那么这种改善建议就会给读者更直观的感受。同样，如果读者能体会到一些现实决策本质上是判断是否引入某项行动时，就更容易理解二元决策变量的含义了。
一般人认为学生通过作业练习题能更好地掌握相关的知识。这也是第2版延续第1版的传统，在每个章节最后加入练习题的原因。其中一些练习题摘自教材第1版，而大部分是新的或改良后的题目。这些题目涵盖范围十分广泛，有关于算法细节、定义及性质的证明题，用以加强对方法的理解；也加入了大量定量计算的练习题，包括对小型案例解决方法的说明与验证，和更加复杂困难的应用题的案例介绍。它们改编自实际运筹问题，有助于锻炼读者的数理能力。
早期最优化问题入门级教材很大程度关注于如何依靠算法来计算小案例的解。但随着现今实际问题逐渐改由大型计算机软件计算，教材有时会将注意力局限在构建数据集合而非算法——将计算过程本身看作黑箱。
我尽量避免了上述的两种极端。如果学生想掌握计算过程所基于的原理，那么实例的图解和算法实现就是十分重要的。本书第2版延续了上一版的模式，在介绍新概念时将篇幅着重于算法实现和求解过程。但是，没有读者会仅仅看到算法应用到小型例子中就能真切感受到最优化方法的力量，所以第1版和第2版的大部分案例和练习中都要求学生在课上使用软件求解更加庞大复杂的问题。这些问题不像小案例那样易于观察到答案，需要应用正确的求解方法。此外，书中一些部分还涉及了建模编程语言，例如AMPL。
本书的读者既有本科生也有低年级研究生，在平衡两类学生对于内容接受程度的过程中，最大的挑战就是数理内容严谨性的问题。初级教材仅简单介绍计算方法的内容，而很少证明其正确性。进阶的教材通常很快进入严谨的数学定理和公式的证明，几乎不包含任何关于基本策略和思路的讨论。
在第1版中我努力缩小两者的差异，在书中不仅关注于方法背后的策略和思路，同时提供了其正确性的相关讨论。在第2版中，为了更好地满足低年级研究生和自学者的需求，大幅度增加了数理讨论的严谨性。虽然它们没有体现在定理或证明中，但为此，基本原理大部分要素都进行了修改。
第2版的出版花费了很长时间，我对此感到很骄傲，在此期间我们努力将这本书修改得更加完善。我也希望读者能发现这本书比第1版的优秀之处，期盼着你们的意见和建议。
十分感谢佐治亚理工学院、普渡大学和阿肯色州立大学的数百名学生、朋友和同事在本书撰写时提供的建议和鼓励。在此特别感谢研究生助理对练习题和答案撰写的帮助，以及院系负责人Marlin Thomas、Dennis Engi、John English、Kim Needy和Ed Pohl的耐心支持。感谢我的家庭（特别是我的妻子Blanca和儿子Rob）在我长期工作中对我的耐心和鼓励。
管理科学
“运筹学”一直是高等院校经济管理、自动控制和应用数学等相关专业本科生和研究生的一门必修课程。它不仅讲授一般的优化技术与方法，更重要的是训练学生通过建模分析来定义问题并解决问题的理念与思路。国内现有的相关教材多侧重于讲授运筹学的优化原理，其相关模块与现实管理问题的结合相对薄弱。本书很好地弥补了上述局限。为了让不同知识背景的读者都能感到最优化问题的教材有趣且易读，本书将最优化模型和问题相结合。本书宗旨是给不同学科背景的读者提供运筹学学习的全面指南。
本书每个模块从案例出发来教学生一步一步地完成问题建模、优化求解以及结果分析等步骤。该教材浅显易懂，不需要学生有特别高深的数学基础，特别适用于经济管理类的本科生和研究生课堂使用。
在任何组织（包括政府部门、企业、非营利性组织等）中，管理者的主要职能都在于决策制定。这些决策分布在企业的战略、运营和操作等不同层面，跨越人力资源、财务、市场营销、生产运作等不同职能部门，需要考虑到短期目标与长期目标。如何通过科学的分析，在众多方案中找到符合决策者需求的选择？运筹学的一些基本模块（如线性规划、目标规划、整数规划、非线性规划、动态规划）为管理者的决策制定提供了有力的方法支持。特别是对于现实生活中高度复杂的决策问题，如果离开运筹方法的支持，管理决策几乎无从谈起。
“运筹学”一直是高等院校经济管理、自动控制和应用数学等相关专业本科生和研究生的一门必修课程。它不仅讲授一般的优化技术与方法，更重要的是训练学生通过建模分析来定义问题并解决问题的理念与思路。国内现有的相关教材多侧重于讲授运筹学的优化原理，其相关模块与现实管理问题的结合相对薄弱。阿肯色州费耶特维尔大学的罗纳德 L.拉丁教授（也是运筹学与管理科学协会会士）精心编写的《运筹学》很好地弥补了国内运筹学教材的上述局限。在40年左右的职业生涯中，拉丁教授的教学和研究都围绕优化方法与应用展开。本书是拉丁教授一辈子教学与科研工作心得体会的结晶。在书中每一个模块中，拉丁教授都从案例出发来教学生一步一步地完成问题建模、优化求解以及结果分析等步骤。该教材浅显易懂，不需要学生有特别高深的数学基础，特别适用于经济管理类的本科生和研究生课堂使用。
受机械工业出版社华章分社张有利编辑的委托，我们很荣幸承担了拉丁教授《运筹学》教材的翻译工作，也非常高兴能把这本优秀的教材推荐给中国高校的学生和教授。在目前的大数据背景下，越来越多的企业意识到了商务分析对于组织的价值。将数理统计、数据挖掘和运筹学等技术结合起来，通过定量的分析与决策为企业创造价值是大势所趋。我们认为，不仅仅经济管理类的学生应该掌握运筹学的基本理念和方法，和“高等数学”一样，“运筹学”应该普及到几乎所有专业的本科生和研究生。作为在清华大学讲授“运筹学”课程的教师，我们很愿意为在高校进一步普及运筹学尽点微薄之力。
本书的翻译工作由清华大学经济管理学院和清华大学现代管理研究中心的肖勇波教授和梁湧教授共同主持。初稿翻译得到了清华大学经济管理学院的多名本科生和研究生的帮助，他们是管理科学与工程专业的孙昊、张冲、胡晨、丁淑萍、慕遥、荣立松、邝仲弘、吴蕴之、唐润宇等研究生，以及房桢、吴史文、王旭红、唐雁寒、刘宇等本科生。孙昊、胡晨、马晓晨等同学在翻译协调和译稿校对中发挥了重要作用。全书最终的统稿和校对由肖勇波（1～8章）和梁湧（9～17章）完成。北京外国语大学的张继红教授、联想（北京）有限公司的刘晓玲女士、京东（北京）世纪贸易有限公司的许晔女士等提供了各种形式的支持，在此向他们表示深深的谢意！同时我们还要感谢机械工业出版社华章分社张有利编辑和冯小妹编辑的辛勤工作，他们使得本书能够顺利出版。
由于译者水平有限，再加上时间紧迫，译文中定有不妥和疏漏之处，敬请读者批评指正。
肖勇波 梁 湧
清华大学经济管理学院
清华大学现代管理研究中心
2018年6月
译者序
前 言
作者简介
第1章 运用数学模型解决问题1
1.1 运筹学应用案例1
1.2 优化及运筹学方法的步骤3
1.3 系统边界、敏感性分析、易处理性以及有效性7
1.4 描述性模型与仿真模拟9
1.5 数值搜索，精确解与启发解12
1.6 确定模型与随机模型14
1.7 本章小结16
练习题17
第2章 运筹学中的确定性优化模型19
2.1 决策变量、约束条件以及目标函数19
2.2 图解法和最优化产出22
2.3 大型优化模型及其标引32
2.4 线性规划与非线性规划38
2.5 离散（或者整数）规划43
2.6 多目标优化模型50
2.7 优化模型分类小结54
2.8 计算机求解技术以及AMPL54
练习题61
参考文献76
第3章 搜索算法77
3.1 搜索算法、局部和全局最优77
3.2 沿可行改进方向的搜索86
3.3 可行改进方向的代数条件93
3.4 线性目标和凸集的易处理性102
3.5 寻找初始可行解109
练习题116
参考文献119
第4章 线性规划120
4.1 资源分配模型120
4.2 混料模型124
4.3 运营规划模型128
4.4 排班和人员规划模型137
4.5 多阶段模型141
4.6 可线性化的非线性目标模型146
4.7 随机规划152
练习题157
参考文献175
第5章 线性规划的单纯形法176
5.1 线性规划的最优解和标准型176
5.2 顶点搜索和基本解187
5.3 单纯形法196
5.4 字典和单纯形表204
5.5 两阶段法208
5.6 退化与零步长217
5.7 单纯形法的收敛和循环220
5.8 力求高效：修正单纯形法222
5.9 有简单上下限的单纯形法233
练习题240
参考文献245
第6章 线性规划的对偶理论与灵敏度分析246
6.1 通用的活动视角与资源视角246
6.2 对线性规划模型系数变化的定性灵敏度分析250
6.3 线性规划模型系数灵敏度的定量分析：对偶模型259
6.4 构造线性规划的对偶问题267
6.5 计算机输出结果与单个参数变化的影响271
6.6 模型大幅度改动，再优化以及参数规划285
6.7 线性规划中的对偶问题和最优解292
6.8 对偶单纯形法的搜索304
6.9 原始—对偶单纯形法搜索308
练习题313
参考文献327
第7章 线性规划内点法328
7.1 在可行域内部搜索328
7.2 对当前解进行尺度变换336
7.3 仿射尺度变换搜索342
7.4 内点搜索的对数障碍法348
7.5 原始对偶内点法358
7.6 线性规划搜索算法的复杂性364
练习题365
参考文献371
第8章 目标规划372
8.1 多目标优化模型372
8.2 有效点和有效边界377
8.3 抢占式优化和加权目标382
8.4 目标规划387
练习题396
参考文献407
第9章 最短路与离散动态规划408
9.1 最短路模型408
9.2 利用动态规划解决最短路问题415
9.3 一对多的最短路问题：贝尔曼—福特算法422
9.4 多对多最短路问题：弗洛伊德—瓦尔肖算法428
9.5 无负权一对多最短路问题：迪杰斯特拉算法435
9.6 一对多无环图最短路问题440
9.7 CPM项目计划和最长路444
9.8 离散动态规划模型450
9.9 利用动态规划解决整数规划问题458
9.10 马尔科夫决策过程461
练习题466
参考文献476
第10章 网络流与图477
10.1 图、网络与流477
10.2 用于网络流搜索的圈方向487
10.3 消圈算法求最优流497
10.4 网络单纯形法求最优流504
10.5 最优网络流的整性512
10.6 运输及分配模型514
10.7 用匈牙利算法求解分配问题521
10.8 最大流与最小割527
10.9 多商品及增益／损耗流533
10.10 最小／最大生成树539
练习题544
参考文献560
第11章 离散优化模型561
11.1 块状/批量线性规划及固定成本561
11.2 背包模型与资本预算模型566
11.3 集合包装、覆盖和划分模型571
11.4 分配模型及匹配模型579
11.5 旅行商和路径模型588
11.6 设施选址和网络设计模型596
11.7 处理机调度及排序模型602
练习题613
参考资料630
第12章 离散优化求解方法631
12.1 全枚举法求解631
12.2 离散优化模型的松弛模型及其应用633
12.3 分支定界搜索649
12.4 分支定界法的改良660
12.5 分支切割法671
12.6 有效不等式组676
12.7 割平面理论681
练习题688
参考资料702
第13章 大规模优化方法703
13.1 列生成算法和分支定价算法703
13.2 拉格朗日松弛算法713
13.3 Dantzig-Wolfe分解算法726
13.4 Benders分解算法731
练习题737
参考文献742
第14章 计算复杂性理论743
14.1 问题、实例和求解的难度743
14.2 衡量算法复杂性及问题的难度745
14.3 可解问题的多项式时间验证标准748
14.4 多项式可解和非确定多项式可解749
14.5 多项式时间归约和NP难问题753
14.6 P问题和NP问题755
14.7 求解NP难问题757
练习题760
参考文献764
第15章 离散优化的启发式算法765
15.1 构造型启发式算法765
15.2 针对离散优化INLPs问题改进搜索启发式算法771
15.3 元启发式算法：禁忌搜索和模拟退火777
15.4 进化元启发式算法和遗传算法784
练习题787
参考文献793
第16章 无约束的非线性规划794
16.1 无约束非线性规划模型794
16.2 一维搜索803
16.3 导数、泰勒级数和多维的局部最优解条件812
16.4 凹凸函数和全局最优822
16.5 梯度搜索827
16.6 牛顿法831
16.7 拟牛顿法和BFGS搜索835
16.8 无导数优化和Nelder-Mead法842
练习题849
参考文献854
第17章 带约束的非线性规划855
17.1 带约束的非线性规划模型855
17.2 特殊的NLP：凸规划、可分离规划、二次规划和正项几何规划862
17.3 拉格朗日乘子法876
17.4 KARUSH-KUHN-TUCKER最优性条件882
17.5 惩罚与障碍法890
17.6 既约梯度法898
17.7 二次规划求解方法909
17.8 序列二次规划917
17.9 可分离规划方法920
17.10 正项几何规划方法927
练习题934
参考文献945
