本书系统介绍了禁忌搜索、模拟退火、遗传算法、人工神经网络和拉格朗日松弛等现代优化计算方法的模型与理论、应用技术和应用案例。

    全书共6章，第1章介绍算法复杂性的基本概念和启发式算法的评价方法，后5章分别介绍各个现代优化计算方法。

    本书可作为数学、管理科学、计算机科学、工业工程等学科中相关优化专业的研究生教材，也可供相关专业研究人员参考。

最优化是人们在工程技术、科学研究和经济管理的诸多领域中经常遇到的问题。结构设计要

在满足强度要求等条件下使所用材料的总重量最轻；资源分配要使各用户利用有限资源产生

的

总效益最大；安排运输方案要在满足物资需求和装载条件下使运输总费用最低；编制生产计

划要按照产品工艺流程和顾客需求，尽量降低人力、设备、原材料等成本使总利润最高。可

以预料，随着科学技术尤其是计算机技术的不断发展，以及数学理论与方法向各门学科和各

个应用领域的更广泛、更深入的渗透，在即将到来的21世纪信息时代，最优化理论和技术必

将在社会的诸多方面起着越来越大的作用。

解决实际生活中优化问题的手段大致有以下几种：一是靠经验的积累，凭主观作判断；二是

做试验选方案，比优劣定决策；三是建立数学模型，求解最优策略。虽然由于建模时要作适

当简化，可能使结果不一定非常完善，但是它基于客观数据，求解问题简便、灵活、经济，

而且规模可以很大(将来会越来越大)。人们还可以吸收从经验得到的规则，用实验来不断校

正建立的模型。随着数学方法和计算机技术的进步，用建模和数值模拟解决优化问题这一手

段，将会越来越显示出它的效能和威力。显然，在决策定量化、科学化的呼声日益高涨的今

天，数学建模方法的推广应用是符合时代潮流和形势发展需要的。

最优化理论、模型与方法所包含的内容很多，国内已出版了不少教材和专著介绍其各个分支

。但是一方面，近年来发展起来的、有着广泛应用背景的规划模型(如随机规划、模糊规划

等)，以及一些已经为许多人采用、受到广泛关注的优化算法(如模拟退火、遗传算法等)，

还缺乏详细和系统的介绍；另一方面，一些偏重优化理论和方法的教材，其要求难以与工科

学生的数学知识衔接，也缺少对于应用来说十分重要的建模过程和软件介绍，而一些比较通

俗的运筹学教材，则在加强理论基础，适应学生将来从事科研工作需要上考虑较少。我们这

套教材试图弥补以上两方面的缺陷，力求体现下述特点：

1 内容既包含传统的线性规划与非线性规划等部分，又纳入有广泛应用前景的随机规划和

模糊规划；在传统内容中，既注重典型的数学思想和方法的系统叙述，又引入丰富的建模实

例。

2 数学基础既与工科学生所学知识衔接，又考虑到研究生阅读文献、从事科研工作的需要

，适当提高理论基础的起点。

3 对一般教材介绍的诸多算法进行精选，配合介绍一些应用软件，并引入近年来迅速发展

的若干新算法。

本系列教材将陆续出版，首批四册为：《线性与非线性规划》、《网络优化》、《现代优化

计算方法》、《随机规划与模糊规划》。

由于水平所限，书中难免有缺陷和错误，诚恳希望读者予以批评指正。

《最优化基础——模型与方法》系列教材编委会

1998年5月

序言Ⅶ

第1章概论1

1.1组合最优化问题1

1.2计算复杂性的概念5

1.3邻域概念11

1.4启发式算法13

1.5NP,NPC和NPhard概念28

1.6小结48

练习题49

参考文献51

第2章禁忌搜索算法53

2.1局部搜索53

2.2禁忌搜索57

2.3技术问题62

2.4应用实例77

练习题87

参考文献88

第3章模拟退火算法90

3.1模拟退火算法及模型90

3.2马尔可夫链96

3.3时齐算法的收敛性102

3.4非时齐算法收敛性简介109

3.5实现的技术问题114

3.6应用案例——下料问题129

练习题136

参考文献138

第4章遗传算法140

4.1遗传算法140

4.2模板理论149

4.3马尔可夫链收敛分析156

4.4实现的技术问题165

4.5遗传模拟退火算法181

4.6应用案例——生产批量问题183

练习题189

参考文献191

第5章人工神经网络193

5.1人工神经网络的基本概念195

5.2单层前向神经网络198

5.3多层前向神经网络210

5.4竞争学习神经网络222

5.5反馈型神经网络224

练习题245

参考文献245

第6章拉格朗日松弛算法247

6.1基于规划论的松弛方法248

6.2拉格朗日松弛方法的理论252

6.3拉格朗日松弛的进一步讨论263

6.4拉格朗日松弛算法273

6.5拉格朗日松弛在能力约束单机排序问题中

的应用282

练习题290

参考文献293

索引及英文关键词294