运筹学基础

前   言

运筹学是近几十年发展起来的一门新兴学科,研究目的是形成和求解所谓“优化”问题，问题的优化往往对应着更好的决策，意味着在相同条件下获得更高的社会、经济或军事效益。因此，运筹学有着很强的实用性，在经济管理、工程实践、军事作战、卫生医疗等领域都有着广泛的应用，特别是作为人工智能和大数据分析的基础支撑学科，已经成为高等院校热门的专业基础课程。
本书基于作者十多年的一线教学经验编写，广泛参考了中外多类运筹学教材，矫正了多处国内中文教材中常见的不准确之处，同时充分考虑了读者自主学习的需求，力争做到“体例完整、深入浅出”。书中主要内容均围绕运筹学典型问题展开，依次说明经典运筹学分支所针对的问题、问题适用的模型、模型的通用求解算法及结论的实践应用。此外，针对各类创新竞赛和解决实际问题的需求，增加Lingo软件求解的部分。
内容与特色
本书作为系列教材的本，内容包括绪论、运筹学研究方法、线性规划与单纯形法、对偶理论与灵敏度分析、运输问题、线性目标规划、整数线性规划、图与网络分析共8章，主要是运筹学中使用确定性模型的分支，具体内容选择上兼顾了理论深度和应用广度。书中考虑多类专业领域的需求，增加了具有实际背景的多类案例，同时在附录A中给出了12类综合实践项目供读者选用，这些项目在作者的教学实践中取得了较好的应用效果。
面向的读者
本书预设的读者对象为学习过高等数学（主要是线性代数）的低年级大学生，需要提前了解的基础数学知识主要包括线性相关与线性无关、矩阵的运算和求逆等，如果读者还能了解有关线性空间的知识会更好（如果不知道，也没有很大影响）。
本书可作为高等院校相关专业的门运筹学课程的教材。由于编排时充分考虑了自主学习的需求，也适宜作为对运筹学感兴趣读者或参加数学建模活动的读者的自学参考书。
软件的使用
本书使用Lingo作为求解软件，该软件由Lindo System Inc公司开发，读者可从该公司官网（www.lindo.com）获得免费试用版（对于入门用户来说，试用版已可满足一般需求），本书附录B提供了一个简易教程，供读者参考。
致谢
本书编写的具体分工为李志猛负责本书总体，以及第1～5章、第8章，刘进负责第6章和第7章及课后习题的审核，另有多位老师参与审校和提出意见。在本书编写和出版中，国防科技大学系统工程学院和作战运筹与规划系的两级领导十分关心，特别感谢学院在经费保障等方面的支持。教研室马满好主任对本书的出版赋予了很大的期待，协调了很多工作，使得作者有一段相对稳定的时间来撰写本书；邱涤珊教授和徐培德教授作为前辈，在作者多年教学生涯中一直关爱有加，作者将他们的教诲铭记在心；祝江汉教授作为作者运筹学教学的领路人，对本书的编写给予了切实帮助；运筹学教学团队的其他老师和作者多年并肩作战，坚持在教学一线，对本书的形成助益良多，他们是朱晓敏老师、伍国华老师、张昆仑老师，这里一并向他们致谢和致敬！
本书经过多个教学班的试用，很多同学为本书的形成付出了辛苦的劳动，包括但不限于以下同学：于绪虎、万珊珊、何家辉、姜智文、李旻浩、黄欢欢、侯文哲、宫铨志、余京、杨君燕、石家豪、卢伟峰、李振龙、侯衍波、姚远征、田硕、楼新星。
春去秋来，韶华易去，转眼间从教已近二十年，个中滋味，甘苦自知。风雨多年，我要特别感谢妻子蔡孟和儿子李准，是你们包容了我工作上的繁忙，我的欢乐来自你们，我爱你们！
在出版过程中，电子工业出版社的编辑队伍认真负责、尽心尽力，保证了本书的顺利出版。本书也参考了多位前辈、同仁和网上资料，难以一一列举，一并向他们致谢。当然本书编写仓促，难免有错讹之处，这些概由作者负责。也请发现错误的读者能够及时告知作者，以便再版修订，联系方式为zmli@nudt.edu.cn。

李志猛         
2019年1月于德雅村

本书在作者十多年一线教学经验的基础上编写而成，同时，广泛参考了中外多类运筹学教材，体例上充分考虑了读者自主学习的需求。书中主要内容围绕运筹学典型问题展开，依次说明经典运筹学分支所针对的问题、问题适用的模型、模型的通用求解算法及结论的实践应用。编写中针对各类创新竞赛的要求，本书增加了LINGO软件求解的介绍。本书作为系列教材的*本，内容包括绪论、运筹学研究方法、线性规划与单纯形法、对偶理论与灵敏度分析、运输问题、线性目标规划、整数线性规划、图与网络分析，共8章。全书考虑多类专业领域的实际，具有一定的深度和广度。附录A中给出了12类综合实践项目供读者选用，这些项目在作者的教学实践中取得了较好的应用效果。本书中部分内容难度稍大，用“*”标记，供读者选修。本书可作为高等院校理工科专业的教材，也可作为感兴趣读者的自学参考书。

李志猛，国防科技大学副教授，博士，军事运筹学硕士研究生导师，加拿大约克大学、美国亚利桑那州立大学访问学者。先后获应用数学专业理学学位、军事运筹学专业硕士学位、管理科学与工程博士学位，主要研究方向为军事运筹理论与方法，在运筹学、军事运筹学方面从事了10余年的教学科研工作，获学校与军队级教学奖励十余项，参与军队统编教材编写1部，出版专著2部，在国内外重要期刊发表论文20多篇，主持科研项目6项，获军队科技进步二等奖1项。

目 录 
第1章 绪论 001 
1.1 发展简史 002 
1.1.1 萌芽时期 003 
1.1.2 形成时期 005 
1.1.3 发展时期 006 
1.2 定义与性质 007 
1.3 主要分支简介 010 
1.4 应用与展望 012 
习题 016 
参考文献 016 
第2章 运筹学研究方法 017 
2.1 一般研究过程 018 
2.1.1 问题定义 018 
2.1.2 数据收集 020 
2.1.3 模型构建 021 
2.1.4 模型求解 023 
2.1.5 模型检验 025 
2.1.6 结论实施 026 
2.2 常用建模方法 027 
2.3 基本结论 031 
习题 032 
参考文献 032 

第3章 线性规划与单纯形法 034 
3.1 线性规划的数学模型 035 
3.1.1 线性规划问题示例 035 
3.1.2 线性规划模型的形式 038 
3.2 线性规划的图解法 040 
3.2.1 图解法示例 040 
3.2.2 解的4种情况 041 
3.3 单纯形法的求解思路 042 
3.3.1 数学模型的标准形式 043 
3.3.2 代数法的基本思路 045 
3.3.3 单纯形法的基本过程 049 
3.4 单纯形法的理论基础 055 
3.5 单纯形法的一般步骤 065 
3.6 单纯形法的拓展讨论 078 
3.6.1 单纯形法的矩阵表示 078 
3.6.2 处理人工变量的“两阶段”法 082 
3.6.3 退化问题及其解决办法 084 
3.6.4 单纯形法的效率分析 086 
3.7 线性规划的LINGO求解 089 
3.8 应用举例 093 
3.8.1 下料问题 094 
3.8.2 排班问题 095 
3.8.3 配料问题 097 
3.8.4 兵力使用规划问题 099 
习题 101 
参考文献 107 
第4章 对偶理论与灵敏度分析 109 
4.1 对偶问题的提出 110 
4.1.1 对偶问题的案例 111 
4.1.2 对称形式数学模型 113 
4.1.3 标准形式数学模型 115 
4.1.4 一般形式数学模型 116 
4.2 对偶理论 118 
4.2.1 对偶问题的基本性质 119 
4.2.2 对偶理论的应用 125 
4.3 影子价格——对偶变量的实践解释 128 
4.3.1 影子价格的经济意义解释 129 
4.3.2 影子价格的军事意义解释 131 
4.4 对偶单纯形法 132 
4.4.1 基本思路 133 
4.4.2 计算步骤 133 
4.4.3 优缺点分析 136 
4.5 灵敏度分析 137 
4.5.1 约束条件中资源数量变化的分析 139 
4.5.2 目标函数中价值系数变化的分析 141 
4.5.3 系数矩阵中技术系数变化的分析* 143 
4.5.4 增加一类新产品的分析* 146 
4.5.5 增加一类新约束的分析* 147 
4.6 参数线性规划* 149 
4.6.1 价值系数作为参数的变化分析 149 
4.6.2 资源限量作为参数的变化分析 151 
4.7 对偶问题的LINGO求解 153 
4.7.1 对偶变量的LINGO求解 153 
4.7.2 使用LINGO进行灵敏度分析 154 
习题 155 
参考文献 160 
第5章 运输问题 161 
5.1 运输问题的数学模型 162 
5.1.1 运输问题数学模型的表达形式 162 
5.1.2 运输问题数学模型的特点 165 
5.2 表上作业法 171 
5.2.1 初始基可行解的确定 172 
5.2.2 解的判别 176 
5.2.3 解的改进 180 
5.2.4 几个问题的说明 181 
5.3 非标准的运输问题 183 
5.3.1 产销不平衡的运输问题 183 
5.3.2 求化的运输问题 187 
5.3.3 带有附加要求的运输问题 189 
5.3.4 有转运的运输问题 191 
5.4 运输问题的LINGO求解 193 
习题 196 
参考文献 200 
第6章 线性目标规划 201 
6.1 线性目标规划的数学模型 203 
6.1.1 问题的提出 203 
6.1.2 问题建模 207 
6.2 线性目标规划的解法 209 
6.2.1 图解法 210 
6.2.2 单纯形法 211 
6.3 线性目标规划的LINGO求解 214 
6.4 应用举例 217 
6.4.1 案例1 217 
6.4.2 案例2 220 
习题 223 
参考文献 226 
第7章 整数线性规划 227 
7.1 问题的提出 229 
7.1.1 数学模型 229 
7.1.2 求解思路 231 
7.2 分枝定界法 233 
7.3 割平面法 238 
7.4 0-1型整数规划与隐枚举法 244 
7.4.1 问题的提出 244 
7.4.2 隐枚举法 247 
7.5 指派问题 249 
7.5.1 问题的提出 249 
7.5.2 匈牙利法 251 
7.5.3 非标准指派问题的转化 256 
7.6 整数线性规划问题的LINGO求解 257 
7.6.1 背包问题的LINGO求解 257 
7.6.2 指派问题的LINGO求解 259 
7.6.3 选址问题的LINGO求解 260 
习题 262 
参考文献 267 
第8章 图与网络分析 268 
8.1 图的基本概念 269 
8.1.1 图模型的提出 269 
8.1.2 基本概念 272 
8.1.3 图论基本定理 274 
8.2 图的连通与遍历 276 
8.2.1 基础概念 276 
8.2.2 图的矩阵表示 281 
8.2.3 欧拉图问题 286 
8.2.4 哈密尔顿图问题 287 
8.2.5 中国邮递员问题 289 
8.2.6 旅行商问题 290 
8.3 树 292 
8.3.1 “树”模型的提出 292 
8.3.2 树的性质 293 
8.3.3 支撑树问题 296 
8.3.4 小支撑树问题 298 
8.4 短路问题 301 
8.4.1 问题定义 301 
8.4.2 Dijkstra算法 302 
8.4.3 Floyd算法 306 
8.4.4 应用举例 310 
8.5 流问题 313 
8.5.1 问题定义 313 
8.5.2 理论基础 319 
8.5.3 流标号算法 322 
8.5.4 应用举例 326 
8.6 小费用流问题 328 
8.6.1 问题定义 328 
8.6.2 理论基础 330 
8.6.3 小费用流求解算法 332 
8.6.4 应用举例 337 
8.7 图模型的LINGO求解 338 
8.7.1 图模型的LINGO表达 338 
8.7.2 短路问题的LINGO求解 339 
8.7.3 流问题的LINGO求解 341 
8.7.4 小费用流问题的LINGO求解 343 
习题 345 
参考文献 352 
附录A 综合实践项目 353 
项目1：单纯形算法程序设计与实现 354 
项目2：短路算法程序设计与实现 355 
项目3：奶制品的加工计划问题 355 
项目4：蔬菜市场的调运问题 356 
项目5：铁路平板车问题 358 
项目6：投资的收益和风险 358 
项目7：网络数据的传输问题 360 
项目8：灾情巡视路线 361 
项目9：日常饮食的营养优化问题 362 
项目10：一周时间利用的优化安排 362 
项目11：选修课选择的优化方案 363 
项目12：网络购物的调查与优化 363 
附录B LINGO使用说明 364

本书在作者十多年一线教学经验的基础上编写而成，同时，广泛参考了中外多类运筹学教材，体例上充分考虑了读者自主学习的需求。书中主要内容围绕运筹学典型问题展开，依次说明经典运筹学分支所针对的问题、问题适用的模型、模型的通用求解算法及结论的实践应用。编写中针对各类创新竞赛的要求，本书增加了LINGO软件求解的介绍。本书作为系列教材的*本，内容包括绪论、运筹学研究方法、线性规划与单纯形法、对偶理论与灵敏度分析、运输问题、线性目标规划、整数线性规划、图与网络分析，共8章。全书考虑多类专业领域的实际，具有一定的深度和广度。附录A中给出了12类综合实践项目供读者选用，这些项目在作者的教学实践中取得了较好的应用效果。本书中部分内容难度稍大，用“*”标记，供读者选修。本书可作为高等院校理工科专业的教材，也可作为感兴趣读者的自学参考书。

李志猛，国防科技大学副教授，博士，军事运筹学硕士研究生导师，加拿大约克大学、美国亚利桑那州立大学访问学者。先后获应用数学专业理学学位、军事运筹学专业硕士学位、管理科学与工程博士学位，主要研究方向为军事运筹理论与方法，在运筹学、军事运筹学方面从事了10余年的教学科研工作，获学校与军队级教学奖励十余项，参与军队统编教材编写1部，出版专著2部，在国内外重要期刊发表论文20多篇，主持科研项目6项，获军队科技进步二等奖1项。