本书共9章,内容包括运筹学概述、朴素优化范式、线性规划、网络最优化、动态规划、网络计划、排队系统分析、库存优化、旅行商问题等。在内容选择方面,本书遵循“重打基础、直抵核心、精心留白”的原则,突出内容的基础性、理论的简洁性、案例建模计算的完整性,以激发读者的学习兴趣,使其快速入门。
本书适合有一定线性代数、概率论基础的初学者使用,也可供各类数学建模竞赛、计算机算法设计竞赛的人员参考。
运筹学应用高级分析技术优化决策,而能够优化决策的高级分析技术有很多,因此运筹学的分支很庞大,应用领域也很广泛。最初运筹学应用于军事领域,后来扩展到工业、商业、政府等民用领域。
运筹学紧密结合数学、计算机、经济学、管理学等各领域的知识解决优化问题。虽然运筹学的基础理论在起源后的几十年已经基本成熟,但是由于计算机、经济学、管理学以及应用领域的不断发展变化,运筹学面临的新问题以及优化决策的基本范式也在不断发展。本书将运筹学的优化范式总结梳理为朴素优化范式、机械优化范式、仿真优化范式、智能优化范式、数据驱动优化范式等,便于读者在入门阶段对运筹学有一个宏观的认识。
运筹学是一门学科,也是一个专业,还是一门课程。作为入门课程,给学生开好头,激发其学习兴趣,保持对未来实践有益的方向和理念,是运筹学课程的重要任务。像学习钢琴一样,一般有一定乐理知识的人都能够在短期内上手弹奏简单的曲目,但是更高级别的演奏,需要付出更加持续的努力和进行系统的练习。 在开始的时候,保持持续学习的动力和兴趣,是走得更远的重要因素。
本书是编者在多年运筹学学习、研究和教学的基础上编写而成的,力求将运筹学的基础理论学习与计算机求解、系统化的解决方案训练等统筹结合,将运筹学面向实践和应用的特色突显出来。在内容选择方面,本书遵循“重打基础、直抵核心、精心留白”的原则,突出内容的基础性、理论的简洁性、案例建模计算的完整性,以激发读者的学习兴趣,使其快速入门。首先,如果在有限的时间内,学习的都是关于运筹学的数学理论和技术,则很容易让人认为运筹学是数学工具的集合,从而丧失学习兴趣。运筹学不是单纯的数学工具的集合,因此,在内容的设计上,本书力求与计算机算法的设计和求解紧密结合,用理论解决“为什么”的问题,用算法解决“怎么做”的问题,用代码抛砖引玉解决实际中“动手难”的问题。其次,运筹学需要给出解决问题的系统方案。因此,在典型案例或者应用中,力争开放、发散,有时即使是一道简单的习题,也会展开发散性的思考讨论,这看似小题大做,实则对培养学生的系统意识会有意想不到的好处。最后,凡非必要,尽量减少了非应用领域的概念,而重在分析问题、解决问题的方法思路和解决手段上。
本书由宋志华和周中良主编。本书编写组的杨建军、魏靓、陈士涛、许建虹、李宗哲、赵保军、张晗、盛晟、周宇、方甲永、刘铭、古清月、高杨军、傅超琦、宋晓博、何苹等在素材收集、算法设计、案例编写、书稿校对等方面做了许多工作,对本书的出版有着非常重要的贡献,张多林、杨建军等对本书提出了许多宝贵的意见,在此表示衷心的感谢。
由于编者水平有限,书中不足之处在所难免,敬请广大读者批评指正。
第1章 运筹学概述 1
1.1 运筹学的起源 1
1.2 运筹学的定义 3
1.3 运筹学的模型 4
1.3.1 线性规划模型 4
1.3.2 网络模型 5
1.3.3 动态规划模型 5
1.3.4 生灭过程模型 5
1.3.5 神经网络模型 6
1.3.6 启发式模型 6
1.3.7 仿真模型 6
1.4 运筹学的优化范式 7
1.4.1 朴素优化范式 7
1.4.2 机械优化范式 8
1.4.3 仿真优化范式 8
1.4.4 智能优化范式 8
1.4.5 数据驱动优化范式 8
1.5 运筹学应用的过程 8
1.5.1 定位 10
1.5.2 问题定义 10
1.5.3 数据收集 10
1.5.4 模型构建 11
1.5.5 模型求解 12
1.5.6 验证与分析 12
1.5.7 实施与监控 12
习题1 13
第2章 朴素优化范式 14
2.1 生成测试范例 14
2.2 枚举法 15
2.3 深度优先搜索 16
2.4 广度优先搜索 18
2.5 贪婪算法 21
2.6 启发式算法 22
2.7 拓展应用:玻璃球硬度测试实验设计问题 23
习题2 25
第3章 线性规划 26
3.1 约束目标标准型 26
3.1.1 线性规划的一般形式 26
3.1.2 线性规划的标准形式 26
3.1.3 整数线性规划 27
3.2 从无穷到有限之基解 28
3.2.1 可行解 28
3.2.2 基解 29
3.2.3 基解三定理 29
3.2.4 基解的枚举 31
3.2.5 基解的启发寻优 33
3.3 单纯形法 33
3.3.1 起点 33
3.3.2 邻域中的改进解 33
3.3.3 终止 35
3.3.4 算例 35
3.4 对偶问题 38
3.4.1 机会成本与影子价格 38
3.4.2 对偶问题的模型 39
3.5 运输问题 40
3.5.1 真假运输问题 40
3.5.2 运输问题模型 41
3.5.3 运输问题算法 44
3.5.4 从不平衡到平衡 49
3.6 典型案例 50
3.6.1 投资方案的规划 50
3.6.2 防御兵力的部署 54
3.6.3 火车站售票的规划 56
3.6.4 武器目标分配问题 58
习题3 59
第4章 网络最优化 63
4.1 最小支撑树问题 63
4.1.1 最小费用连通问题 63
4.1.2 两个属性 64
4.1.3 三大算法 66
4.1.4 拓展应用:k聚类分析 71
4.1.5 拓展应用:战备通信节点的建设问题 73
4.2 最短路问题 77
4.2.1 线性规划模型 77
4.2.2 最优性条件 78
4.2.3 标号法 78
4.2.4 拓展应用:数据约减 82
4.3 最大流问题 86
4.3.1 线性规划模型 86
4.3.2 剩余容量图 86
4.3.3 增广链法 86
4.3.4 拓展应用:弹药目标最大化匹配问题 88
4.3.5 拓展应用:最大投送能力评估问题 89
4.4 最小费用流问题 91
4.4.1 线性规划模型 91
4.4.2 三个最优性条件 92
4.4.3 两个算法 93
4.4.4 拓展应用:网络上的最小费用最大流问题 94
4.5 二分匹配问题 97
4.5.1 指派问题 97
4.5.2 稳定婚配问题 99
习题4 102
第5章 动态规划 106
5.1 多阶段决策问题 106
5.2 网络模型 108
5.3 Bellman递归方程 109
5.3.1 最优性原则 109
5.3.2 两个推论 112
5.3.3 两个方程 112
5.3.4 多阶段最短路问题的求解 113
5.4 典型案例 114
5.4.1 背包问题 114
5.4.2 设备更新问题 117
5.4.3 过河问题 121
5.4.4 炮兵阵地问题 125
5.4.5 巡逻队分配问题 131
习题5 135
第6章 网络计划 139
6.1 网络计划的发展历程 140
6.2 网络建模 140
6.3 关键路线法CPM 142
6.3.1 关键路线的计算 142
6.3.2 几个时间参数的计算 143
6.4 计划评审技术PERT 145
6.5 时间费用优化 149
习题6 152
第7章 排队系统分析 154
7.1 排队现象及范例 154
7.2 排队系统分类 155
7.3 Little定律 155
7.4 排队系统的解析 156
7.4.1 指数分布 157
7.4.2 生灭过程 158
7.4.3 应用案例:自助洗车机排队系统解析 159
7.5 排队系统仿真 161
7.5.1 问题描述 161
7.5.2 仿真想定 161
7.5.3 仿真运行 163
7.5.4 仿真优化 164
7.6 排队系统的多目标优化 165
习题7 166
第8章 库存优化 168
8.1 库存系统 168
8.2 经典EOQ 168
8.3 分段价格EOQ 170
8.4 带有储存上限的多种货物EOQ 172
8.5 动态EOQ 174
习题8 176
第9 章 旅行商问题 178
9.1 TSP的构造启发式算法 178
9.2 线性规划模型 179
9.3 TSP路径构造的贪婪启发式算法 179
9.3.1 最近邻算法 179
9.3.2 插入算法 181
9.3.3 Merger算法 183
9.4 TSP的改进启发式算法 183
9.4.1 2opt操作 184
9.4.2 kopt操作 186
9.5 TSP的遗传算法 186
9.5.1 基本原理与步骤 186
9.5.2 算法设计要点 187
习题9 188
参考文献 190