项目一　运筹学概述

1.1　运筹学的产生与发展

任何一门学科或理论都是为解决一些客观实际问题而出现并得以发展的，为了更好地理解和掌握今天的运筹学，有必要先了解一下运筹学发展的历史。虽然一定的运筹学思想和方法在很久以前已留下了被应用的痕迹，历代先驱所做的一些工作今天看来也具有一定的运筹学性质，但这些零散的活动还不足以标志作为系统知识体系的一门新学科的诞生。运筹学的产生很难有一个明确的时间界定，目前国际上公认的观点是运筹学产生于第二次世界大战前后。1937年，英国部分科学家被邀请去帮助皇家空军研究雷达的部署和运作问题，目的在于最大限度地发挥有限雷达的效用，以应对德军的空袭。1938年，波德塞（Bawdsey）雷达站的负责人罗伊（A．B．Rowe）提出了优化防空作战系统运行的问题，并用“operational research”一词作为对这一方面研究的描述，这就是直至今日我们仍然将运筹学称为“O．R．”的历史由来。1939年，从事此方面问题研究的科学家被召集到英国皇家空军指挥总部，成立了一个由布莱开特（P．M．S．Blacket）领导的军事科技攻关小组；由于其成员学科性质的多样性，这一最早成立的军事科技攻关小组被戏称为“布莱开特马戏团”。由于“布莱开特马戏团”的活动是第一次有组织的、系统的运筹学活动，所以后人将该小组的成立作为运筹学产生的标志。此后，O．R．小组的活动范围不断扩大，从最初仅限于空军，逐步扩展到海军和陆军；研究内容也从对军事战术性问题的研究，逐步扩展到对军事战略性问题的研究。由于科学家的天赋、战争的需要以及不同学科的交互作用，这一军事科技攻关小组在提高军事运筹水平方面取得了惊人的成就，这使得运筹学在整个军事领域迅速传播，到1941年，英国皇家陆、海、空三军都成立了这样的科学小组。比较典型的论题包括雷达布置策略、反空袭系统控制、海军舰队的编制和对敌潜艇的探测等，O．R．小组的巨大成就所显示出的神奇力量，促使其他盟军也纷纷效仿，建立了自己的研究小组。以美国为代表的一些英语国家称这类研究小组的工作为“operations research”。

二战后，许多从事运筹小组活动的科学家将其精力转向对早期仓促建立起来的运筹优化技术进行加工整理，探索应用运筹学思想和方法解决社会经济问题的可能性。首先接纳运筹学的非军事组织是一些效益较好的大公司，如石油公司和汽车公司。“大商业”引领运筹学应用的新潮流是很自然的事，因为虽然当时运筹学可以为任何一个经济组织提供获得竞争优势的方案，但由于运筹学还处于起步的基础研究时期，只有大公司才能承担起运筹学研究的巨大费用。后来，随着运筹学思想和方法的积累与程序化，不用太大的投入就能受益，运筹学才得到了广泛的应用。计算机的普及与发展是推动运筹学迅速发展的巨大动力，没有现代计算机技术，求解复杂的运筹学模型是不可设想的，也是不实际的；运筹学实践反过来又促进了计算机技术的发展，它不断地对计算机提出更大内存、更快运行速度的要求。可以说，运筹学在过去的半个多世纪里，既得益于计算机技术的应用与发展，同时也极大地促进了计算机技术的发展。

20世纪50年代，运筹学理论、方法及其活动发展到了一个新的水平，运筹学开始成为一门独立的学科，其标志是大量运筹学学会的创建和相应期刊的问世。继1948年英国创立运筹学学会之后，美国运筹学学会于1952年成立，它的宗旨是满足运筹学研究领域的科学家相互交流的需要，以促进O．R．理论与实践的发展。1953年，美国又成立了管理科学研究所。美国运筹学学会和管理科学研究所两个组织所创办的刊物《运筹学》和《管理科学》将许多零散的研究成果系统化，为构建运筹学新学科的知识体系作出了突出的贡献。在1956年至1959年短短的几年里，先后就有法国、印度、日本等十几个国家成立了运筹学学会，并有6种运筹学期刊问世。1957年，在英国牛津大学召开了第一届运筹学国际会议，1959年，成立了国际运筹学学会（International Federation of Operations Research Societies，IFORS）。截至1986年，国际上已有38个国家和地区成立了运筹学学会或类似的组织。

20世纪60年代以来，运筹学得到了迅速的普及和发展。运筹学细分为许多分支，许多高等院校把运筹学的规划理论引入教学课程，把规划理论以外的内容引入硕士、博士研究生的教学课程。运筹学的学科划分没有统一的标准，在工科学院、商学院、经济学院和数理学院的教学中都可以发现它的存在。

1.2　我国古代运筹学应用案例

运筹学作为科学概念是在20世纪中期提出来的，而运筹学思想可以追溯到很久以前。我国蜀汉时期即有所谓“夫运筹帷幄之中，决胜千里之外”的说法，充分体现了我国古代人民对于运筹学的分支“预测和规划论”的重视。秦始皇派蒙恬大军抗击匈奴时，从山东每调运192石粮草只有1石能到达在沙漠中与匈奴作战的将士手中；而清朝乾隆平息噶尔丹叛乱时，从江南每调运12石粮草就有1石粮草能到达在大漠中与噶尔丹叛军作战的将士手中，这与运筹实践水平的提高是分不开的。

我国古代的能人志士有许多采用运筹学思想指导实践的案例，至今对我们仍有很好的借鉴作用。

1.2.1　丁谓修宫，一举而三役济

宋真宗大中祥符年间，宫内失火，烧毁了大片宫殿、楼阁、凉亭和台榭。宋真宗任命晋国公丁谓负责修复这些建筑。该建筑工程需要解决三个难题：一是取土困难，因为要到郊区去取土，路途太远；二是与此相关的运输问题难以解决，包括运土和运输大量其他建筑材料；三是大量建筑垃圾的处理。丁谓运筹规划，终于制定了绝妙的施工方案。首先下令“凿通衢取土”，用以解决施工用土问题；然后引汴水入新挖的大沟，“引诸道竹木筏排及船运杂材，尽自堑中入至宫门”，从而解决了大批木材、石料的运输问题；最后待建筑运输任务完成之后，再排除堑水，把工地所有垃圾倒入沟内，重新填为平地。该方案的三个过程为：挖沟并取土—引水入沟并运输—填沟并处理垃圾。此方案“一举而三役济”“省费以亿万计”，大大缩短了工期。丁谓所设计的方案，其思想与如今运筹学中的统筹方法一致。

1.2.2　田忌赛马

战国初期，齐国的君主要求田忌和他赛马，规定各人从自己的上马（即头等马）、中马、下马中各选一匹马来比赛，并且说好每输一匹马就得支付一千两银子给获胜者。当时齐王的马比田忌的马强，结果每年田忌都要输掉三千两银子。孙膑给田忌出主意：上马虽不及齐王的上马，但却强于齐王的中马，因此用上马与齐王的中马比赛，同理用中马与齐王的下马比赛，而用下马与齐王的上马比赛。结果田忌反而赢得了一千两银子。田忌所用的策略就是如今运筹学中对策论的策略。

上述案例说明，从古代开始，我国就已经拥有了朴素的运筹学思想。

1.3　我国现代对运筹学的认识和应用

运筹学概念起源于欧美，在学科研究方面，欧美的水平也明显领先于我国。但我国的科学工作者们并不气馁，他们用自己的聪明才智和努力工作使运筹学的思想得以在全国普及，并指导人们的实践。1955年，运筹学的思想开始为我国科学工作者所认识，1956年中国科学院力学研究所建立了我国第一个运筹学研究组。20世纪60年代，华罗庚教授亲自指导青年科技工作者在全国推广运筹学方法。华罗庚的“优选法”和“统筹方法”被各部门采用，取得了很好的效果。杨纪珂教授亲自带领学生深入厂矿企业，推广应用“质量控制”技术，也取得了很好的效果，受到各界的好评。更重要的是，他们还为管理人员编写了通俗易懂的普及性读物，让更多的人学习和运用运筹学方法，使得运筹学的思想得以普及。

改革开放以来，运筹学的应用更为普遍，特别是在流通领域中。例如，运用线性规划进行全国范围的粮食、钢材，广东水泥的合理调运等：许多企业在作业调配、工序安排、场地选择时，创造性地使用了简单易行的“图上作业法”和“表上作业法”等运筹学方法，取得了显著的效果。

1.4　运筹学的主要研究方向

运筹学（operation research）也称为作业研究，是运用系统化的方法，通过建立数学模型及其测试，协助达成最佳决策的一门学科。它主要研究经济活动和军事活动中能用数量来表达的有关运用、筹划与管理等方面的问题。它根据问题的要求，通过数学的分析与运算，做出综合性的合理安排，以达到更加经济、有效地配置人力、物力、财力等资源的目的。

运筹学的主要分支有规划论、图论、网络分析、存储论、对策论和预测技术等，它们在管理学科中得到了广泛的应用。

1.4.1　规划论（programming theory）

在生产和经营管理工作中，经常要研究计划管理工作中有关安排和估计的问题，特别是如何有效地利用有限的人力、财力和物力来取得最优的经济效果。这类问题一般可以归纳为在满足既定的要求下，按某一衡量指标来寻求最优方案的问题。这类问题其实就是规划问题。

如果问题的目标函数和约束条件的数学表达式都是线性的，则称为“线性规划”（linear programming）问题。“线性规划”问题只有一个目标函数，其建模相对简单，有通用的算法和计算机软件。用线性规划可以解决的典型问题有生产计划问题、混合配料问题、下料问题和运输问题等。

如果问题的目标函数和约束条件的数学表达式不都是线性的，则称为“非线性规划”（nonlinear programming）问题。非线性规划在很多工程问题的优化设计中具有重要作用，是优化设计的有力工具。

如果所考虑的规划问题可划分为几个阶段求解，则称为“动态规划”（dynamic programming）问题。动态规划问题也有目标函数和约束条件。该方法根据多阶段决策问题的特点，提出了多阶段决策问题的最优性原理，可以解决生产管理和工程技术等领域中的许多实际问题，如最优路径问题、资源分配问题、生产计划问题和库存问题等。

1.4.2　图论和网络分析（graph theory and network analysis）

图论是运筹学一个古老但又十分活跃的分支，它是网络技术的基础。图论的创始人是数学家欧拉。1736年他发表了图论方面的第一篇论文，解决了著名的哥尼斯堡七桥难题。1847年基尔霍夫第一次应用图论的原理分析电网，从而把图论引入工程技术领域。20世纪50年代以来，图论的理论得到了进一步发展，用图描述复杂、庞大的工程系统和管理问题，可以解决很多工程设计和管理决策的最优化问题。例如，完成工程任务的时间最少、距离最短、费用最省等等。因此，图论受到数学、工程技术和经营管理等方面越来越广泛的重视。

生产管理中经常会遇到线路的合理衔接搭配、管道线路的通过能力、仓储设施的布局等问题。在运筹学中，可将这些问题抽象为节点、边（弧）所组成的图形问题。网络分析就是根据所研究的网络对象，赋予图中各边某个具体参数，如时间、流量、费用、距离等，规定图中节点为流动的始点、中转点和终点，然后进行网络流量的分析和优化。

1.4.3　存储论（inventory theory）

存储论是一种研究最优存储策略的理论和方法。在实际生产实践过程中，企业希望尽可能减少原材料和产成品的存储以减少流动资金和仓储费用。但是，过少的原材料仓储可能导致企业原材料供应不上，从而导致生产不能正常进行；过少的产成品存储则可能导致客户不能得到足够的商品，从而导致客户忠诚度的下降。存储论就是研究在不同需求、供货及到达方式等情况下，在什么时间点及一次提出多大批量的订货，使用于订购、存储和可能发生短缺的费用的总和最少。

1.4.4　排队论（queueing theory）

排队论又称为随机服务系统理论。1909年丹麦的电话工程师爱尔朗（A．K．Erlang）提出了排队问题；1930年以后，开始了更为一般的研究，取得了一些重要成果；1949年前后，开始了对机器管理、陆空交通等方面的研究；1951年以后，理论研究工作有了新的进展，逐渐奠定了现代随机服务系统的理论基础。排队论主要研究各种系统的排队队长、排队的等待时间及所提供的服务等各种参数，以便获得更好的服务。排队论是研究系统随机聚散现象的理论。

1.4.5　对策论（game theory）

对策论研究有关决策的问题。所谓决策，就是根据客观可能性，借助一定的理论、方法和工具，科学地选择最优方案的过程，决策问题由决策者和决策域构成，而决策域又由决策空间、状态空间和结果函数构成。研究决策理论与方法的科学就是决策科学。决策所要解决的问题是多种多样的，从不同角度有不同的分类方法。按决策者所面临的自然状态的确定与否可分为：确定型决策、风险型决策和不确定型决策；按决策所依据的目标个数可分为：单目标决策与多目标决策；按决策问题的性质可分为：战略决策和策略决策；以及按不同准则划分成的其他决策问题类型。

1.4.6　预测论（forecast theory）

预测是在科学理论的指导下做出有一定科学依据的假定。常见的预测方法有时间序列预测法和回归模型预测法两种。

1.5　运筹学的工作步骤

运筹学作为解决有限资源合理利用问题的系统的科学方法，具有其固有的工作步骤，现将这一步骤概括如下。

（1）提出和形成问题：即要弄清问题的目标、可能的约束、可控变量、有关的参数以及搜集有关信息资料。

（2）建立模型：即把问题中的决策变量、参数和目标、约束之间的关系用一定的模型表示出来。

（3）求解模型：根据模型的性质，选择相应的求解方法，求得最优或满意解，解的精度要求可由决策者提出。

（4）解的检验与转译：首先检查求解过程是否有误，然后再检查解是否反映客观实际。如果所得之解不能较好地反映实际问题，必须返回（1）修改模型，重新求解；如果所得之解能较好地反映实际问题，也必须仔细将模型结论转译成现实结论。

（5）解的实施：实施过程必须考虑解的应用范围及对各主要因素的敏感程度，向决策者讲清解的用法以及在实施中可能产生的问题和修改的方法。