运筹学(第2版)

第二版前言
　　运筹学教材出版以后在山东财经大学和多所兄弟院校使用，大家的支持就是对作者的鼓励，在此向所有采用本教材的老师和同学表示感谢！由于作者能力有限，教材存在一些错误和不足，给读者带来了不便和困扰，在此向大家表示歉意。
　　运筹学(第二版)是在原有教材的基础上改编的，修改的主要内容包括以下几项：
　　(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

本书是在靠前版的基础上修订完善而成的，第二版尽力保持了原版的特点，进一步完善了主要内容，提高了本书的可读性，扩大了适用范围。本书系统地介绍了运筹学的基本内容，重点讲解了线性规划、整数规划、动态规划、多目标规划、图与网络优化、网络计划技术、运输问题和排队论等方法。本书以培养学生运用运筹学方法解决管理决策问题的能力为目标，在掌握运筹学基本理论素养的基础上，重点培养学生的运筹学建模能力和软件求解能力。本书适合作为普通本科院校经济管理类专业本科生或高等职业院校本专科生教材，也可以作为相关学科研究生以及企业决策咨询部门和数据分析部门管理人员的参考书。

作者集成十几年运筹学教学经验和教学素材，编写了《运筹学(第二版)》，《运筹学(第二版)》具有以下特点。
　　(1) 在内容的选择上突出管理学科的特点，去掉了管理学科使用较少的非线性规划、与博弈论重复较多的对策论、在决策理论中要讲的决策分析以及物流管理中的库存论等内容。既避免了课程内容的重复，也适应了应用型人才培养中减少理论课时的趋势。
　　(2) 在教材结构的安排上，更加注重各章节的衔接，把运输问题放在图与网络优化之后，可以利用小树的理论说明回路的存在性。很多学校不讲对偶理论，因而在运输问题、小费用流等章节不再使用对偶理论推导。
　　(3) 在内容的组织上沿着运用运筹学方法解决管理问题的过程，从问题入手，重点讲解建立模型的方法，然后介绍性条件和优化算法，后讲解软件求解模型和案例分析，有利于培养学生运用运筹学方法解决实际问题的能力。
　　(4) 在内容的编写上充分考虑普通省属本科院校的现实，尽量减少高等数学的使用，用方程组消元法引入单纯形算法、利用拍卖过程介绍小费用流算法，把一些难理解的章节和定理证明省略，因为这些内容在教学实践中也很少用到。
　　(5) 把十几年的教学实践融入教材中，用自己的理解重新编写了很多理论的推导过程，更容易让学生接受。把教学中发现的学生容易出错的地方用说明的方式加以注解，可以帮助学生减少错误。
　　本教材附录中给出了LINGO和SciLab两种软件的使用说明，配套的电子课件、基于SciLab的教学软件、实验指导书和习题参考答案等资料存放在清华大学出版社网站，读者也可以从山东财经大学精品课程网站上下载。

第二章  线性规划

线性规划是运筹学中重要的分支，也是运筹学的基础。线性规划问题早是苏联学者康托洛维奇(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) 问题分析。
合理配料问题是一个特殊的生产计划，该问题与章中案例的生产计划的不同之处在于产品对原料的消耗量不明确，只给了一个限制范围，同时原料之间不发生化学反应，产品的产量等于原料之和。因而方案就不是只确定产品的产量，还需要明确生产不同产品原料的数量，设 为生产第 种饲料使用第 种原料的数量 ，则第 种饲料的产量为 ，第 种原料的使用量为 。
问题的目标是生产利润化，而利润等于销售收入减去成本，销售收入等于价格乘以产量，即 ，成本等于购买原料的支出，等于原料价格乘以原料需求数量，即 。所以总利润为
 
问题的约束包括原料供给限制、产品规格限制和变量自身限制，其中原料供给限制要求原料的需求量小于等于供给量，即
 
产品的规格限制要求不同原料占总产量的比例符合要求，即
 
上述约束是分式约束，为了写成线性规划形式，转化成以下等价形式，即
 
变量非负限制为
 
(2) 模型。
该工厂的生产计划问题就是在原料需求不超过可用量的限制下使得总利润，因而对应的数学模型为
         (2-1)
提 示
(1) 配料问题是一种特殊的生产计划问题，其与章(绪论)中的生产计划问题的区别在于一般生产计划问题中生产单位产品对原料的消耗量是确定的，但配料问题中生产单位产品对原料的消耗量是不确定的，只给了一个数量限制范围，因而仅用每种产品的产量不能表示出原料的消耗量，需要把产品产量和原料的消耗量同时作为变量。
(2) 由于配料问题中没有发生化学反应，原料的数量和就是产品的产量，因而题目中把产品的产量用原料数量和替换，减少了3个变量。不替换也可以，但必须在约束中添加“产量等于原料消耗量和”这一组约束。
例2-2  运输问题。
一个啤酒公司在山东有 个生产厂，每个生产厂计划期内生产的数量为 。这 个生产厂的产品销往山东各市地，公司把山东市场分成了 个销售区，每个销售区计划期内的销售量预计为 。假设生产总量和预期销售总量相等，且已知从第 个生产厂运单位产品到第 个销售区的运价为 。问应如何组织运输才能使总运费小？
(1) 问题分析。
该问题是一个典型的运输问题，生产厂是供应地，销售区是需求地。问题的变量是从第 个生产厂运到第 个销售区的产品数量，设为 ，则总运费为 ，从第 个生产厂运出的总量为运到各销售区之和，即 ，运到第 个销售区的产品数量等于从各生产厂运输之和，即 。显然，运出的量不能超过生产量，运入的量不能低于需求量，由于生产总量和预期销售总量相等，所以每个生产厂运出量正好等于生产量，每个销售区的运入量等于需求量，即有约束
 
 
(2) 模型。
在供求约束下使得总费用小的线性规划模型为
                  (2-2)
该规划是针对一般情况建立的，不同公司的具体数据不同，把数据代入模型就可以得到具体实例的模型。
提 示
(1) 建立模型的基础是对问题的分析，分析问题需要明确问题的基本要素，问题的基本要素对应模型的变量、目标和约束等基本要素。
(2) 建立模型的过程就是用数学语言表述模型的3个基本要素的过程。首先确定变量，也就是主动改变量，然后用变量表示其他量，给出约束和目标函数。
(3) 在建立模型时不要遗漏变量非负约束，当变量表示数量时，如果取值不会为负值，则需要添加变量非负约束。
二、线性规划模型
通过上面3个实例可以看出，线性规划的目标可能是也可能是小，约束可能是等式也可能是不等式，3个实例的变量都是非负的，有时变量或部分变量要求允许取负值，称为自由变量。因而，一般的线性规划模型的形式为
           (2-3)
其中 为决策变量， 为目标函数系数， 为约束系数。记变量为 ，向量 为价值向量，向量 为右端向量，矩阵
 
为系数矩阵。
如果变量都是非负的，约束都是不等式，并且对于目标是求小的线性规划模型，不等号都是大于等于号，或者对于目标是