《运筹学(第二版)》是在第一版的基础上修订完善而成的，第二版尽力保持了原版的特点，进一步完善了主要内容，提高了本书的可读性，扩大了适用范围。
《运筹学(第二版)》系统地介绍了运筹学的基本内容，重点讲解了线性规划、整数规划、动态规划、多目标规划、图与网络优化、网络计划技术、运输问题和排队论等方法。本书以培养学生运用运筹学方法解决管理决策问题的能力为目标，在掌握运筹学基本理论素养的基础上，重点培养学生的运筹学建模能力和软件求解能力。
《运筹学(第二版)》适合作为普通本科院校经济管理类专业本科生或高等职业院校本专科生教材，也可以作为相关学科研究生以及企业决策咨询部门和数据分析部门管理人员的参考书。
作者集成十几年运筹学教学经验和教学素材，编写了《运筹学(第二版)》，《运筹学(第二版)》具有以下特点。
(1) 在内容的选择上突出管理学科的特点，去掉了管理学科使用较少的非线性规划、与博弈论重复较多的对策论、在决策理论中要讲的决策分析以及物流管理中的库存论等内容。既避免了课程内容的重复，也适应了应用型人才培养中减少理论课时的趋势。
(2) 在教材结构的安排上，更加注重各章节的衔接，把运输问题放在图与网络优化之后，可以利用*小树的理论说明回路的*存在性。很多学校不讲对偶理论，因而在运输问题、*小费用流等章节不再使用对偶理论推导。
(3) 在内容的组织上沿着运用运筹学方法解决管理问题的过程，从问题入手，重点讲解建立模型的方法，然后介绍*优性条件和优化算法，*后讲解软件求解模型和案例分析，有利于培养学生运用运筹学方法解决实际问题的能力。
(4) 在内容的编写上充分考虑普通省属本科院校的现实，尽量减少高等数学的使用，用方程组消元法引入单纯形算法、利用拍卖过程介绍*小费用流算法，把一些难理解的章节和定理证明省略，因为这些内容在教学实践中也很少用到。
(5) 把十几年的教学实践融入教材中，用自己的理解重新编写了很多理论的推导过程，更容易让学生接受。把教学中发现的学生容易出错的地方用说明的方式加以注解，可以帮助学生减少错误。
本教材附录中给出了LINGO和SciLab两种软件的使用说明，配套的电子课件、基于SciLab的教学软件、实验指导书和习题参考答案等资料存放在清华大学出版社网站，读者也可以从山东财经大学精品课程网站上下载。
第二版前言
运筹学教材出版以后在山东财经大学和多所兄弟院校使用，大家的支持就是对作者最大的鼓励，在此向所有采用本教材的老师和同学表示感谢！由于作者能力有限，教材存在一些错误和不足，给读者带来了不便和困扰，在此向大家表示歉意。
运筹学(第二版)是在原有教材的基础上改编的，修改的主要内容包括以下几项：
(1) 修正了原有教材中发现的错误。
(2) 增加了对偶理论，作为选讲内容放在了第二章第八节，可以满足考研需要。
(3) 利用对偶理论给出了最小费用流和运输问题位势法的理论推导，作为延伸阅读放在相关章节后面，可以帮助读者更好地理解问题，也可以展示知识的关联性。
(4) 把附录三调整为正式内容，把其放在第二章第五节，可以在第二章第六节使用Excel规划求解的敏感性报告。
(5) 对部分章节的叙述进行了改编，主要包括第五章第二节、第六章第一节、第八章第三节等内容。
(6) 对部分图标进行了完善，使其更加美观。
限于作者的能力，第二版难免还会存在一些错误和不足，敬请读者指正。
第二版写作过程中得到了采用本教材的老师和同学们的帮助，第二版的出版得到了清华大学出版社的大力支持，在此向他们表示感谢！
第一版前言
运筹学在管理决策与工程设计中有广泛的应用，是经济管理、数学、计算机与工科等学科学生的基础课程或必修课。但各个学科对运筹学的要求不尽相同，数学学科的教学强调理论推导和算法思想，计算机学科的重点在于算法设计，管理与工程学科则是要运用运筹学方法解决实际问题，因而教学的重点在于运筹学模型的建立和求解。
作者从事运筹学教学13年，先后在教育部所属重点大学的数学院、计算机学院和普通省属院校的管理学院教授运筹学，对于它们的差异深有感触。特别是对于普通省属本科院校管理学科的学生，其数学基础不牢靠，对于运筹学的理论推导掌握起来比较困难。因而很有必要从管理学科运筹学教学的特点出发，编写一本适合普通省属本科院校管理学科学生使用的运筹学教材。
作者集成十几年运筹学教学经验和教学素材，编写了这本运筹学教材，本教材具有以下特点。
(1) 在内容的选择上突出管理学科的特点，去掉了管理学科使用较少的非线性规划、与博弈论重复较多的对策论、在决策理论中要讲的决策分析以及物流管理中的库存论等内容。既避免了课程内容的重复，也适应了应用型人才培养中减少理论课时的趋势。
(2) 在教材结构的安排上，更加注重各章节的衔接，把运输问题放在图与网络优化之后，可以利用最小树的理论说明回路的唯一存在性。很多学校不讲对偶理论，因而在运输问题、最小费用流等章节不再使用对偶理论推导。
(3) 在内容的组织上沿着运用运筹学方法解决管理问题的过程，从问题入手，重点讲解建立模型的方法，然后介绍最优性条件和优化算法，最后讲解软件求解模型和案例分析，有利于培养学生运用运筹学方法解决实际问题的能力。
(4) 在内容的编写上充分考虑普通省属本科院校的现实，尽量减少高等数学的使用，用方程组消元法引入单纯形算法、利用拍卖过程介绍最小费用流算法，把一些难理解的章节和定理证明省略，因为这些内容在教学实践中也很少用到。
(5) 把十几年的教学实践融入教材中，用自己的理解重新编写了很多理论的推导过程，更容易让学生接受。把教学中发现的学生容易出错的地方用说明的方式加以注解，可以帮助学生减少错误。
全书共分9章，讲授全书基本内容需要51课时，为了方便读者阅读，下面的框图给出了各章内容的相关性。
本教材附录中给出了LINGO和SciLab两种软件的使用说明，配套的电子课件、基于SciLab的教学软件、实验指导书和习题参考答案等资料存放在清华大学出版社网站，读者也可以从山东财经大学精品课程网站上下载。
本教材中的内容是作者所学运筹学知识的再现，作者从本科生、硕士研究生和博士研究生阶段都是在山东大学运筹学专业学习的。饮水思源，非常感谢山东大学运筹学专业各位老师，他们不仅传授给我知识，他们严谨负责的教风也深深影响着我。特别要感谢我的授业恩师刘家壮教授，跟随导师学习10年让我受益终生。在此向他们致以深深的敬意！
同时也要感谢我教过的所有学生，教学相长，在与你们互动的过程中我的教学经验得到积累、教学水平得到提升。
最后要感谢我的父母、妻子和儿子，家人的理解和支持让我更加安贫乐教。
本教材是山东省精品课程——运筹学(2011BK127)的配套教材，本教材的编写和出版得到了山东省高等教育质量工程建设项目的资助。
限于作者的水平，不妥与错误之处在所难免，恳请广大读者批评指正。
第一章 绪论 1
第一节 运筹学概述 2
一、运筹学的概念 2
二、运筹学的发展 3
三、运筹学的特点 4
四、运筹学的学科地位 5
第二节 管理中的运筹学问题与模型 6
一、管理中的优化问题 6
二、运筹学模型 8
第二章 线性规划 11
第一节 线性规划实例与模型 12
一、线性规划实例 12
二、线性规划模型 15
三、基本概念 16
四、模型转换 16
第二节 可行区域与基本可行解 19
一、图解法 19
二、可行域的几何结构 22
三、基可行解与基本定理 23
第三节 单纯形算法 27
一、最优性条件 27
二、迭代规则 28
三、算法步骤 29
四、单纯形表 30
第四节 初始基可行解 33
一、辅助规划 34
二、第一阶段 34
三、第二阶段 36
第五节 求解软件 39
一、LINGO软件 39
二、Excel的规划求解 42
第六节 灵敏度分析 47
一、灵敏度分析的概念 47
二、价值向量的灵敏度分析 48
三、右端向量的灵敏度分析 50
四、Excel中的敏感性报告 52
第七节 应用案例分析——生产计划
问题 52
一、问题描述 52
二、问题分析 53
三、线性规划模型 54
四、模型计算 55
第八节 对偶理论* 56
一、对偶规划 57
二、对偶理论 61
习题 65
第三章 整数规划 71
第一节 整数规划问题与模型 72
一、整数规划问题 72
二、整数规划模型 73
第二节 分支定界算法 75
一、算法的基本思想 75
二、关键技术 76
三、算法步骤 78
四、软件求解方法 81
第三节 应用案例分析 82
一、背包问题 82
二、人力资源分配问题 84
习题 86
第四章 动态规划 91
第一节 多阶段决策问题 92
一、多阶段决策问题实例 92
二、多阶段决策问题 94
第二节 最优化原理 95
一、最优化原理 96
二、最短路问题 98
三、动态规划递推关系式 99
第三节 管理中的多阶段决策问题 100
一、旅游售货员问题 100
二、背包问题 105
习题 109
第五章 多目标规划 111
第一节 多目标规划模型 112
一、多目标规划实例 112
二、一般模型 115
三、有效解 115
四、求解有效解的方法 117
第二节 目的规划 121
一、硬约束和软约束 122
二、偏差变量 122
三、优先因子 123
四、目的规划的求解 123
第三节 层次分析方法 125
一、层次分析方法的基本思想 125
二、判别矩阵 127
三、判别矩阵的一致性 128
四、特征根和特征向量的
近似求法 129
五、层次分析法的基本步骤 131
第四节 应用案例分析第三方物流
供应商选择 134
一、确定评价指标 134
二、构造判别矩阵并进行一致性检验 135
三、层次总排序 136
四、综合评比结果 137
习题 138
第六章 图与网络优化 141
第一节 图的基本概念 142
一、图与子图 142
二、图的表示方法 145
三、图的连通性与割集 149
第二节 最小支撑树 152
一、树及其基本性质 153
二、最小树 154
第三节 最短有向路 159
一、最短有向路方程 160
二、求最短有向路的Dijkstral
算法 162
三、SciLab求解最短有向路 164
第四节 最大流 165
一、最大流最小割定理 165
二、最大流算法 168
三、SciLab求解最大流 173
第五节 最小费用流 174
一、最小费用流问题的数学规划
模型 175
二、最小费用流问题的算法 175
三、SciLab求解最小费用流 181
习题 184
第七章 网络计划技术 187
第一节 网络计划图 188
一、基本术语 188
二、箭线图的绘制方法 188
三、节点图 192
第二节 时间参数与关键路线 192
一、作业时间 193
二、节点时间 193
三、工序时间 195
四、关键路线 196
第三节 网络计划的优化 197
一、数学规划方法 198
二、图上计算方法 199
习题 201
第八章 运输问题 207
第一节 运输问题的模型 208
一、运输问题的数学模型 208
二、运输问题数学模型的特点 209
第二节 表上作业法 210
一、表上作业法求解思路 210
二、初始可行方案 211
三、回路法 218
四、位势法 221
第三节 扩展的运输问题 225
一、产大于销的运输问题 225
二、产小于销的运输问题 226
三、转运问题 227
第四节 应用案例分析 229
一、带有约束的运输问题 229
二、生产与存储问题 232
习题 233
第九章 排队论 237
第一节 随机服务系统的基本概念 238
一、随机服务系统的组成 238
二、排队系统的描述符号 241
三、排队系统的评价指标 242
第二节 排队系统的概率分布和
随机过程 243
一、排队系统的概率分布 243
二、最简单流 244
三、生灭过程 246
第三节 无限源的排队系统 247
一、M/M/1/∞系统 247
二、M/M/1/N/系统 252
三、M/M/C/∞系统 255
第四节 应用案例分析——排队论在
物流系统设计中的应用 258
一、问题的背景 258
二、模型的建立 259
三、天车随机服务系统优化设计 260
四、结束语 261
习题 261
附录 265
附录一 LINGO软件的集合输入方法 266
一、LINGO中的集 266
二、模型的数据部分和初始部分 267
三、模型输入 269
四、运算符与常用函数 270
附录二 SciLab软件介绍 271
参考文献 276
第二章 线性规划
线性规划是运筹学中最重要的分支，也是运筹学的基础。线性规划问题最早是苏联学者康托洛维奇(L.V. Kantorovich，1912—1986)于1939年提出的，但他的工作当时并未广为人知。第二次世界大战中，美国空军的一个研究小组SCOOP(Scientific Computation Of Optimum Programs，最优程序的科学计算)在研究战时稀缺资源的最优化分配问题时，提出了线性规划问题。丹齐格(G.B.Dantzig)于1947年提出了求解线性规划问题的单纯形法，单纯形法至今还是求解线性规划最有效的方法之一。
本章将介绍线性规划的模型和基本概念以及单纯形法的基本原理、软件求解方法及线性规划在经济分析中的应用。
第一节 线性规划实例与模型
运用线性规划方法解决实际问题的前提是把实际问题转化为数学问题，也就是建立线性规划模型，不同类型的问题建立线性规划模型的方法不尽相同。下面通过具体实例学习建立线性规划模型的方法。
一、线性规划实例
线性规划的应用领域十分广泛，主要包括生产计划、物资调运、资源优化配置、物料配方和经济规划等问题，在第一章(绪论)中介绍了生产计划问题，下面介绍另外两种决策问题。
例2-1 合理配料问题。
某饲料厂用玉米胚芽粕、大豆饼和酒糟等3种原料生产3种不同规格的饲料，由于3种原料的营养成分不同，因而不同规格的饲料对3种原料的比例有特殊要求，具体要求及产品价格、原料价格、原料数量见表2-1，试制订总利润最大的生产计划。
表2-1 工厂生产数据
规格要求 产品Q1 产品Q2 产品Q3 原料单价/(元/kg) 原料可用量/kg
原料P1 ≥15% ≥20% 25% 1.7 1500
原料P2 ≥25% ≥10% 1.5 1000
原料P3 ≤40% 1.2 2000
单位产品的利润/(元/kg) 2 3 2.3
(1) 问题分析。
合理配料问题是一个特殊的生产计划，该问题与第一章中案例的生产计划的不同之处在于产品对原料的消耗量不明确，只给了一个限制范围，同时原料之间不发生化学反应，产品的产量等于原料之和。因而方案就不是只确定产品的产量，还需要明确生产不同产品原料的数量，设 为生产第 种饲料使用第 种原料的数量 ，则第 种饲料的产量为 ，第 种原料的使用量为 。
问题的目标是生产利润最大化，而利润等于销售收入减去成本，销售收入等于价格乘以产量，即 ，成本等于购买原料的支出，等于原料价格乘以原料需求数量，即 。所以总利润为
问题的约束包括原料供给限制、产品规格限制和变量自身限制，其中原料供给限制要求原料的需求量小于等于最大供给量，即
产品的规格限制要求不同原料占总产量的比例符合要求，即
上述约束是分式约束，为了写成线性规划形式，转化成以下等价形式，即
变量非负限制为
……
书单推荐
