运筹学

本教材充分考虑到运筹学的学科特点，问题都来源于当今信息时代的实际案例，并上升到理性，再回到实践中去，解决实践中的问题。积极尝试运用新的思维和科研成果改进教材内容。根据运筹学课程在相关专业能力体系中的作用，希望本教材能够在知识维度提供优化理论和方法，在能力维度能够培养学生解决实际优化问题的能力、推理和分析能力、定量分析问题解决问题的能力、系统分析问题的能力；在态度维度能够更理性的认识问题，学会用数学的语言来描述一个实际问题。本书适合作为普通高等院校开设“运筹学”课程的教材或参考书。

目录前言第1章线性规划111线性规划建模112线性规划的解613线性规划的图解法714线性规划的基本定理1115单纯形法1216单纯形法的进一步讨论1817应用举例28习题31第2章线性规划的对偶理论3521线性规划的对偶问题3522对偶理论4023影子价格4424对偶单纯形法4525灵敏度分析48习题53第3章线性规划的扩展5631运输问题5632目标规划8033数据包络分析89习题98第4章整数规划10441整数规划问题及其数学模型10442分支定界法10643割平面法113440-1整数规划11645指派问题12146整数规划案例125习题128第5章非线性规划13251概述13252非线性规划问题的解13453凸函数和凸规划13754下降迭代算法14055一维搜索14256无约束极值问题的求解算法14857约束极值问题的性条件15458约束极值问题的求解算法159习题164第6章动态规划16661多阶段决策问题16662动态规划的基本概念和基本方程16863化原理与性定理17564动态规划问题的求解17765动态规划的应用举例182习题194第7章图与网络19871图与网络基础概念19872树20273短路问题20574流问题21075小费用流问题21576中国邮递员问题21977网络计划222习题229第8章决策论23381决策的概念与分类23382确定型决策分析23683不确定型决策分析23684风险型决策分析23985多准则决策分析24686效用函数 25587行为决策理论258习题263第9章博弈论26691博弈的基本要素与分类26692完全信息静态博弈26893零和博弈277习题289第10章排队论292101排队服务系统的基本概念292102到达间隔与服务时间的分布 296103生灭过程与系统状态方程 299104单服务台负指数分布排队模型301105多服务台排队模型307106其他类型排队模型312107排队系统的优化317习题319第11章存储论321111存储论概述321112确定性需求的存储模型 323113随机需求的基本存储模型334习题344附录A线性规划问题的Excel求解346附录B名词术语中英文对照361参考文献365

前言朴素的运筹思想古已有之，在我国古代文献中有许多记载。如战国时期流传后世的赛马比赛——田忌赛马,就是一个经典的博弈案例。田忌赛马的故事说明事前的筹划安排是十分重要的。在已有的条件下，经过精心筹划、安排，选择一个好的方案，就会取得满意的效果。敌我双方交战，要克敌制胜就要在了解双方情况的基础上，研究制定的对付敌人的策略和战术，这就是所谓的“运筹帷幄之中，决胜千里之外”。 运筹学这个名词早出现于1938年，当时的英国为了研究整个防空作战系统的合理运行，以便有效地防备德国飞机入侵，成立了由来自物理、数学等不同学科领域的科学家组成的研究小组，他们的研究工作在有效打击敌人和减少盟军的损失方面发挥了重要作用。他们在一份研究报告中首次使用了Operation Reseach一词。第二次世界大战结束后，运筹学研究的重点转向民用领域，并获得成功。1947年，美国数学家GBDantzig提出了求解线性规划模型的有效方法——单纯形法,并于20世纪50年代初应用电子计算机求解线性规划问题获得成功。到20世纪50年代末，学者们对企业中的一些普遍性优化问题，如库存、资源分配、设备更新、任务分派等问题进行研究，并成功地应用到建筑、纺织、钢铁、煤炭、石油、电力、农业等诸多行业。20世纪60年代，运筹学方法又广泛应用到了服务性行业和社会公共事业。 运筹学一词在英国称为OperationalResearch，在美国称为OperationsResearch，缩写为OR。《大英百科全书》中阐明：“运筹学是一门应用于管理有组织系统的科学，运筹学为掌握这类系统的人提供决策目标和数量分析工具”。 运筹学早主要研究经济活动和军事活动中能用数量来表达的有关策划、管理方面的问题。随着时代的进步和科学技术的发展，运筹学的应用更为广泛,而且解决问题的规模也越来越大、越来越复杂。现实中的优化问题虽然千差万别，但用运筹学来分析和处理问题时，一般都遵循以下几个工作步骤：确定目标、制订方案、建立模型、提出解法。不同类型的问题可归结为多类不同的数学模型，从而形成了不同的运筹学学科分支,如数学规划（包含线性规划、非线性规划、整数规划、动态规划等）、图论与网络流、决策论、对策论、排队论、存储论，等等。 数学规划的研究对象是为一般的优化问题，即在给定的限制条件下，按某一衡量指标来寻找方案。它可以表示为求函数在满足约束条件下的极大或极小值问题。数学规划中简单的一种问题就是线性规划。线性规划及其单纯形法对运筹学的发展起到了重大的推动作用。许多实际问题都可以转化成线性规划来解决，单纯形法是解决线性规划的一个行之有效的算法，而计算机技术的发展，使一些大型复杂的实际优化问题的解决成为现实。 图论是一种用直观的图形来表述和解决一类优化问题的运筹学分支。小支撑树、短路、流等问题是图论中经典的化问题。一些不具有图形特征的优化问题也可以用图形来表述和求解，并且更为直观和简便，如匹配问题、设备更新问题等。网络分析技术则利用图形来描述一个工程项目中各项活动之间的关联和时间进度，从而可以对项目进度进行控制和优化。 现实生活中，人们常常需要在一些可选方案中进行选择，而选择的情景可能是不确定的或有风险的，或者是评价方案的目标有多个。如何进行选择或决策，就是决策论要解决的问题。而如果决策者面对一个与他有竞争的决策者时，决策问题就变成了一个博弈问题，前面提到的田忌赛马就是典型的博弈案例。研究博弈问题的理论和方法就是博弈论（也叫作对策论）。 排队论是运筹学的一个重要分支，它又叫作随机服务系统理论。它的研究目的是要回答如何改进服务机构或如何组织被服务的对象，使得某种指标达到的问题。比如一个港口应该有多少个码头，银行营业厅应设置多少服务窗口等。排队是一个随机现象，因此在研究排队问题时，需要以概率论作为分析工具。 存储论是研究如何平衡供给与需求之间矛盾的理论与方法。其基本的数学问题就是在特定的需求假设下，确定的订货量或生产量。 和所有的其他数学分支一样，运筹学的内容有其经典不变的一面,但是随着社会经济的发展和科学技术的变革，其应用对象所呈现出的丰富性和复杂性也与日俱增。因此，运筹学的理论研究和应用前景都面临更大的机遇和挑战。比如，随着人们对决策行为的关注，已经提出行为运筹学的概念。此外，随着移动互联网技术的发展，可获得海量的实际数据，这些为运筹学的应用提供了更为广阔的空间，使其能够发挥越来越重要的作用。迪士尼游乐场的Fastpass系统中就运用了排队论方法。又如目前交通出行的叫车App应用软件，其中也包含了匹配等优化算法。 本书着重介绍运筹学的主要分支内容,在选材上详略得当，重点突出,对专业词汇给出中英文对照；注重内容阐述的启发性和新颖性，对经典方法的讲解由浅入深，适当增加了运筹学的研究理论和方法，拓展读者视野；注重内容理论阐述的严密性，给出必要的理论性证明和推理；注重案例的时代性，教材中引入了一些新的应用案例，由案例问题引出理论分析方法，再回到实际问题的解决过程；案例及附件中介绍了如何用Excel来求解模型，增强了本书的实用性。 本书由周晶担任主编，徐薇担任副主编，负责教材内容选择和审定。其中周晶参与编写了第7章、第9章、第10章和第11章。徐薇负责编写第1章、第2章和第5章；朱振涛、鲁涛负责编写第3章和第4章；安智宇负责编写第6章；伊俊敏负责编写第7章；徐红利负责编写第8章；吴孝灵负责编写第9章；王虹负责编写第10章；孙玉玲负责编写第11章。 编者