第1篇 绪论 第1章 运筹学概论 1.1运筹学的简史 运筹学作为科学名字出现在20世纪30年代末。当时英、美对付德国的空袭，雷达作为防空系 统的一部分，从技术上是可行的，但实际运用时却并不好用。为此一些科学家研究如何合理 运用雷达开始进行一类新问题的研究。因为它与研究技术问题不同，就称之为“运用研究”。 运筹学的英文名词operational research是英国人最早在20世纪30年代末提出来的，很快美国也跟上，但用了operations research，它们英文简写都是OR。我国在1956年曾用过运用学的名词，到1957年正式定名为运筹学 。为了进行运筹学研究，在英、美的军队中成立了一些专门小组，开展了护航舰队保护商船 队的编队问题和当船队遭受德国潜艇攻击时，如何使船队损失最少的问题的研究。研究了反 潜深水炸弹的合理爆炸深度后，使德国潜艇被摧毁数增加到400%； 研究了船只在受敌机攻击 时，提出了大船应急速转向和小船应缓慢转向的逃避方法。研究结果使船只在受敌机攻击时， 中弹数由47%降到29%。当时研究和解决的问题都是短期的和战术性的。第二次世界大战后在 英、美军队中相继成立了更为正式的运筹研究组织。 由于这门学问当时与军事有关，因此有些内容处于保密状态。很多年以后，到20世纪40年代末50年代初，其中一些与军事密切相关的内容才逐渐公开出来，其中莫尔斯(P.M.Morse)与金博尔(G.E.Kimball)1951年出版的《运筹学方法》(Methods of Operations Research)一书可以作为那段时期重要工作的总结。后来以兰德公司(RAND)为首的一些部门开 始着重研究战略性问题、未来的武器系统的设计和其可能合理运用的方法。例如为美国空军 评价各种轰炸机系统，讨论了未来的武器系统和未来战争的战略。他们还研究了苏联的军事 能力及未来的预报，分析苏联政治局计划的行动原则和将来的行动预测。到20世纪50年代， 由于开发了各种洲际导弹，到底发展哪种导弹，运筹学界也参与了争论。兰德公司接着提出了系统分析(systems analysis, SA)的名词及其相应技术和方法，其应用开始更偏重于战略方面。他们参与了战略力量的构成和数量问题研究。除军事方面的应用研究以外，相继在工业、农业、经济和社会问题等各领域都有应用，后来也有人把这两个词放在一起叫SA/OR。与此同时，运筹数学有了飞快的发展，并形成了运筹学 的许多分支。如数学规划(线性规划、非线性规则、整数规划、目标规划、动态规划、随机 规划等)、图论与网络、排队论(随机服务系统理论)、存储论、对策论、决策论、维修更新 理论、搜索论、可靠性和质量管理等。作为运筹学的早期工作其历史可追溯到1914年，军事 运筹学中的兰彻斯特(Lanchester)战斗方程是在1914年提出的。排队论的先驱者丹麦工程师 爱尔朗(Erlang)1917年在哥本哈根电话公司研究电话通信系统时，提出了排队论的一些著名 公式。存储论的最优批量公式是在20世纪20年代初提出的。在商业方面列温逊在20世纪30年 代已用运筹思想分析商业广告、 顾客心理。线性规划是由丹捷格(G.B.Dantzig)在1947年 发 表的成果。所解决的问题是美国制定空军军事规划时提出的，并提出了求解线性规划问题的 单纯形法。而早在1939年苏联学者康托洛维奇(Л.В.Канторович)在解 决工 业生产组织和计划问题时，已提出了类似线性规划的模型，并给出了“解乘数法”的求解方 法。由于当时未被领导重视，直到1960年康托洛维奇再次发表了《最佳资源利用的经济计算 》一书后，才受到国内外的一致重视。为此康托洛维奇得到了诺贝尔奖。值得一提的是丹 捷格认为线性规划模型的提出是受到了列昂节夫的投入产出模型(1932年)的影响； 后来列昂节夫的投入产出模型也得到了诺贝尔奖。关于线性 规划的理论是受到了冯·诺依曼(Von Neumann)的帮助。冯·诺依曼和摩根斯特恩(O.Morgen stern)合著的《博弈论与经济行为》(1944年)是对策论的奠基作，同时该书已隐约地指 出了对策论与线性规划对偶理论的紧密联系。线性规划提出后很快受到经济学家的重视 ，如在第二次世界大战中从事运输模型研究的美国经济学家库普曼斯(T.C.Koopmans)，他 很快看到了线性 规划在经济中应用的意义，并呼吁年轻的经济学家要关注线性规划。库普曼斯在1975年获诺贝尔经济奖。其中阿罗、萨谬尔逊、 西蒙、多夫曼和胡尔威茨等都获得了诺贝尔奖，并在运筹学某些领域中发挥过重要作用。 我们初步统计了到2007年为止共有19个诺贝尔奖获得者的研究与运筹学有关。 回顾一下最早投入运筹学领域工作的诺贝尔奖获得者、美国物理学家勃拉凯特(Blackett) 领导的第一个以运筹学命名的小组是有意义的。由于该小组的成员复杂，人们戏称它为勃拉凯 特马戏团，其实是一个由各方面专家组成的交叉学科小组。从以上简史可见，为运筹学 的建立和发展作出贡献的有物理学家、经济学家、数学家、其他专业的学者、军官和各行业 的实际工作者。 最早建立运筹学会的国家是英国(1948年)，接着是美国(1952年)、法国(1956年)、日本和印 度(1957年)等。到2005年为止，国际上已有48个国家和地区建立了运筹学会或类似的组织。 我国的运筹学会成立在1980年。1959年由英、美、法三国的运筹学会发起成立了国际 运筹学联合会(IFORS)，以后各国的运筹学会纷纷加入，我国于1982年加入该会。此外还有 一些地区性组织，如欧洲运筹学协会(EURO)成立于1975年，亚太运筹学协会(APORS)成立于 1985年。 20世纪50年代中期，钱学森、许国志等教授将运筹学由西方引入我国，并结合我国的特点在国内推 广应用。 他们最早在中国科学院力学所建立了运筹室, 在运筹学多个领域开展研究和应用工作, 其中在经济数学方面，特别是投入产出表的研究和应用开展较早。质量控制(后改为质 量管理)的应用也有特色。在此期间以华罗庚教授为首的一大批数学家加入到运筹学的研究 队伍，在中国科学院数学所也建立了运筹室，使运筹数学的很多分支很快跟上当时的国际水平。 1.2运筹学的性质和特点 运筹学是一门应用科学，至今还没有统一且确切的定义。提出以下几个定义来说明运筹学的 性质和特点。莫斯(P.M.Morse)和金博尔(G.E.Kimball)曾对运筹学下的定义是： “为决 策机 构在对其控制下业务活动进行决策时，提供以数量化为基础的科学方法。”它首先强调的是 科学方法，这含义不单是某种研究方法的分散和偶然的应用，而是可用于整个一类问题上， 并能传授和有组织的活动。它强调以量化为基础，必然要用数学。但任何决策都包含定量和 定性两方面，而定性方面又不能简单地用数学表示，如政治、社会等因素，只有综合多种因 素的决策才是全面的。运筹学工作者的职责是为决策者提供可以量化方面的分析，指出那些 定性因素的力度。另一定义是： “运筹学是一门应用科学，它广泛应用现有的科学技术知识和数 学方法，解决实际中提出的专门问题，为决策者选择最优决策提供定量依据。”这定义表明 运筹学具有多学科交叉的特点，如综合运用经济学、心理学、物理学、化学中的一些方法。 运筹学是 强调最优决策，“最”是过分理想了，在实际生活中往往用次优、满意等概念代替最优。因 此，运筹学的又一定义是： “运筹学是一种给出问题坏的答案的艺术，否则的话问题的结果 会更坏。” 为了有效地应用运筹学，前英国运筹学学会会长托姆林森提出六条原则： (1) 合伙原则。是指运筹学工作者要和各方面人，尤其是同实际部门工作者合作。 (2) 催化原则。在多学科共同解决某问题时，要引导人们改变一些常规的看法。 (3) 互相渗透原则。要求多部门彼此渗透地考虑问题，而不是只局限于本部门。 (4) 独立原则。在研究问题时，不应受某人或某部门的特殊政策所左右，应独立从事工作。 (5) 宽容原则。解决问题的思路要宽，方法要多，而不是局限于某种特定的方法。 (6) 平衡原则。要考虑各种矛盾的平衡，关系的平衡。 1.3运筹学的工作步骤 运筹学在解决大量实际问题过程中形成了自己的工作步骤。 (1) 提出和形成问题。即要弄清问题的目标，可能的约束，问题的可控变量以及有关参数， 搜集有关资料； (2) 建立模型。即把问题中可控变量、参数和目标与约束之间的关系用一定的模型表示出来 ； (3) 求解。用各种手段(主要是数学方法，也可用其他方法)将模型求解。解可以是最优解、 次优解、满意解。复杂模型的求解需用计算机，解的精度要求可由决策者提出； (4) 解的检验。首先检查求解步骤和程序有无错误，然后检查解是否反映现实问题； (5) 解的控制。通过控制解的变化过程决定对解是否要作一定的改变； (6) 解的实施。是指将解用到实际中必须考虑到实施的问题，如向实际部门讲清解的用法， 在实施中可能产生的问题和修改。 以上过程应反复进行。 1.4运筹学的模型 运筹学在解决问题时，按研究对象不同可构造各种不同的模型。模型是研究者对客观现实经 过思维抽象后用文字、图表、符号、关系式以及实体模样描述所认识到的客观对象。模型的 有关参数和关系式是较容易改变的，这样有助于问题的分析和研究。利用模型可以进行一定 预测、灵敏度分析等。 阿可夫等对运筹学的模型分类、构模等有较完整的描述。 模型有三种基本形式： ①形象模型； ②模拟模型； ③符号或数学模型。目前用得最多的是符 号或数学模型。构造模型是一种创造性劳动，成功的模型往往是科学和艺术的结晶，构模的 方法和思路有以下五种： (1) 直接分析法。按研究者对问题内在机理的认识直接构造出模型。运筹学中已有不少现存 的模型，如线性规划模型、投入产出模型、排队模型、存储模型、决策和对策模型等。这些 模型都有很好的求解方法及求解的软件，但用这些现存的模型研究问题时，要注意不能生搬 硬套。 (2) 类比法。有些问题可以用不同方法构造出模型，而这些模型的结构性质是类同的，这就 可以互相类比。如物理学中的机械系统、气体动力学系统、水力学系统、热力学系统及电路 系统之间就有不少彼此类同的现象。甚至有些经济系统、社会系统也可以用物理系统来类比 。在分析一些经济、社会问题时，不同国家之间有时也可以找出某些类比的现象。 (3) 数据分析法。对有些问题的机理尚未了解清楚，若能搜集到与此问题密切相关的大量数 据，或通过某些试验获得大量数据，这样可以运用统计分析法建模。 (4) 试验分析法。当有些问题的机理不清，又不能做大量试验来获得数据，这时只能通过做 局部试验的数据加上分析来构造模型。 (5) 想定(构想)法(scenario)。当有些问题的机理不清，又缺少数据，又不能做试验来获得 数据时，例如一些社会、经济、军事问题，人们只能在已有的知识、经验和某些研究的基础 上，对于将来可能发生的情况给出合乎逻辑的设想和描述。然后运用已有的方法构造模型， 并不断修正完善，直至比较满意为止。在研究社会问题时，国内外有人提出人工社会的构思, 与这条建模思路有相似之处，人们可以利用计算机先在人工社会中进行大量的计算机试验，然后在真实社会得到验证，或者通过人工社会获得在真实社会一时未能预知的方案和结果。 模型的一般数学形式可用下列表达式描述： 目标的评价准则U=f(xi,yj,ξk) 约束条件g(xi,yj,ξk)≥0 式中： xi——可控变量； yj——已知参数； ξk——随机因素。 目标的评价准则一般要求达到最佳(最大或最小)、适中、满意等。准则可以是单一的，也可 是多个的。约束条件可以没有，也可有多个。当g是等式时，即为平衡条件。当模型中无随 机因素时，称它为确定性模型，否则为随机模型。随机模型的评价准则可用期望值，也可用 方差，还可用某种概率分布来表示。当可控变量只取离散值时，称为离散模型，否则称为连 续模型。也可按使用的数学工具将模型分为代数方程模型、微分方程模型、概率统计模型、 逻辑模型等。若用求解方法来命名时，有直接最优化模型、数字模拟模型、启发式模型。也 有按用途来命名的，如分配模型、运输模型、更新模型、排队模型、存储模型等。还可以用 研究对象来命名，如能源模型、教育模型、军事对策模型、宏观经济模型等。 1.5运筹学的应用 在介绍运筹学的简史时，已提到了运筹学在早期的应用，主要在军事领域。第二次世界大战 后运筹学的应用转向民用，这里只能对某些重要领域给予简述。 (1) 市场销售。主要应用在广告预算和媒介的选择、竞争性定价、新产品开发、销售计划的 制订等方面。如美国杜邦公司在20世纪50年代起就非常重视将运筹学用于研究如何做好广告 工作，产品定价和新产品的引入。通用电气公司对某些市场进行模拟研究。 (2) 生产计划。在总体计划方面主要用于总体确定生产、存储和劳动力的配合等计划，以适 应波动的需求计划，用线性规划和模拟方法等。如巴基斯坦某一重型制造厂用线性规划安排 生产计划，节省10%的生产费用。还可用于生产作业计划、日程表的编排等。此外，还有在 合理下料、配料问题、物料管理等方面的应用。 (3) 库存管理。主要应用于多种物资库存量的管理，确定某些设备的能力或容量，如停车场 的大小、新增发电设备的容量大小、电子计算机的内存量、合理的水库容量等。美国某机器 制造公司应用存储论后，节省18%的费用。目前国外新动向是将库存理论与计算机的物资管 理信息系统相结合。如美国西电公司，从1971年起用5年时间建立了“西电物资管理系统” ，使公司节省了大量物资存储费用和运费，而且减少了管理人员。 (4) 运输问题。这涉及空运、水运、公路运输、铁路运输、管道运输、厂内运输。空运问题 涉及飞行航班和飞行机组人员服务时间安排等。为此在国际运筹学协会中设有航空组，专门 研究空运中的运筹学问题。水运有船舶航运计划、港口装卸设备的配置和船到港后的运行安 排。公路运输除了汽车调度计划外，还有公路网的设计和分析，市内公共汽车路线的选择和 行车时刻表的安排，出租汽车的调度和停车场的设立。铁路运输方面的应用就更多了。 (5) 财政和会计。这里涉及预算、贷款、成本分析、定价、投资、证券管理、现金管理等。 用得较多的方法是统计分析、数学规划、决策分析。此外还有盈亏点分析法、价值分析法等 。 (6) 人事管理。这里涉及六个方面，第一是人员的获得和需求估计； 第二是人才的开发，即 进行教育和训练； 第三是人员的分配，主要是各种指派问题； 第四是各类人员的合理利用问 题； 第五是人才的评价，其中有如何测定一个人对组织、社会的贡献； 第六是工资和津贴的 确定等。 (7) 设备维修、更新和可靠性、项目选择和评价。 (8) 工程的优化设计。这在建筑、电子、光学、机械和化工等领域都有应用。 (9) 计算机和信息系统。可将运筹学用于计算机的内存分配，研究不同排队规则对磁盘工作 性能的影响。有人利用整数规划寻找满足一组需求文件的寻找次序，利用图论、数学规划等 方法研究计算机信息系统的自动设计。 (10) 城市管理。这里有各种紧急服务系统的设计和运用，如救火站、救护车、警车等分布 点 的设立。美国曾用排队论方法来确定纽约市紧急电话站的值班人数。加拿大曾研究一城市的 警车的配置和负责范围，出事故后警车应走的路线等。此外有城市垃圾的清扫、搬运和处理 ； 城市供水和污水处理系统的规划等。 值得提出的是应用方面新的动向，例如，存储理论的应用已经从车间、工厂规模转向整个从用户、零售、批发、中间运输一直到工厂生产供应，形成现在的供应链的设计、管理和应用。在武器和大型装置方面，不单研究其运用，更转向设计和规划等。此外在银行、医院、经济、运输、信息系统、电子商务和电子政务等也都有了新的应用。由于涉及面太多，我们只想用美国运筹学和管理学研究协会组织举办的埃德曼奖的几个例子供大家参考。该奖由世界著名的运筹和管理科学家埃德曼(F. Edelman)于1971年创立，每年评一次，先评出一批候选奖，然后选出5~6名提名奖，最后从中评出一个最佳奖。埃德曼奖的评选原则包括： 运筹学和管理科学理论和方法的创新、应用工作对企业创造的直接经济效益，以及对社会和人类生活所做的积极贡献。 例如，2002年有30多个项目进入了初评。经过严格的筛选，法国标致汽车公司、美国糖果制造巨商玛氏公司、美国大陆航空公司、德国Rhenania catalog house、美国迅达电梯公司，以及美国先正达农业企业得到提名，并进入最终决赛。这6个项目组在经过激烈的角逐后，于刚领导的项目小组由于在大陆航空公司等民用航空企业所创造的实实在在的经济效益，以及对社会和人们生活所做出的贡献，成为2002年度大奖的获得者。于刚提交的项目内容主要是当民航班机受到各种干扰之后，航班机组人员如何以最快的时间和最佳的组合来使航班恢复正常运营。他领导开发的实时决策支持系统已在美国的联合航空公司，大陆航空公司，西北航空公司和西南航空公司运行多年。这些系统在一系列影响航班正常运营的重大事件时起到了极大的效果，例如2000年12月和2001年3月的美国北部暴风雪，2001年休斯敦的大洪水，这些对航班运营和管理所造成的重大影响都在开发的系统的支持下，将损失降低到最低程度。特别是对于2001年“9·11”事件所造成的影响，该系统为美国大陆航空公司挽回了至少3000万美元的损失。而其在2001年全年为该公司所创造的实际价值就超过了6000万美元。 下面我们再介绍2008年度的由6个最终提名奖中选出该年度大奖获得者荷兰铁路及其主要成果。 所提出报奖项目： 荷兰火车新时刻表。 问题： 到2006年荷兰的铁路从1970年的80亿人·千米增加到154亿人·千米。在不改变时刻表的结构情况下要求计划有更多更长的火车发出。2006年荷兰铁路要求开发一个新的时刻表。 运筹学解决方法： 构建了一个改进的、循环的时刻表，它每一小时可以重复。构造这样的时刻表需要求解一个复杂的组合优化问题。设计了4个求解程序： （1） CADANS求解网络时刻表问题； （2） STATIONS找出火车通过各个站时详细的路径； （3） ROSA处理铁路车辆的周转； （4） TURNI对乘员的时刻表安排。 价值： 从2007年对旅客数进行全时的记录。随着最大的时刻表的改进旅客数增加了10%~15%。在规定时刻表的时间内, 火车准点到达率(指误差在3分钟之内)从2006年的84.8%提高到2007年的87.0%。调查表明，公众意见很快从负面批评转向正面肯定。每年增加了4000万欧元的利润。在现有网络下还有可能减少拥堵和污染。 我国运筹学的应用是在1957年始于建筑业和纺织业。在理论联系实际的思想指导下，从1958 年开始在交通运输、工业、农业、水利建设、邮电等方面都有应用。尤其是在运输方面，从 物资调运、装卸到调度等。在粮食部门为解决合理粮食调运问题，提出了“图上作业法” 。我国的运筹学工作者从理论上证明了它的科学性。在解决邮递员合理投递路线时，管梅谷 提出了国外称之为“中国邮路问题”的解法。在工业生产中推广了合理下料，机床负荷分配 。在纺织业中曾用排队论方法解决细纱车间劳动组织，最优折布长度等问题。在农业中研究 了作业布局、劳力分配和麦场设置等。从20世纪60年代起我国的运筹学工作者在钢铁和石油 部门开展较全面的和深入的应用； 投入产出法在钢铁部门首先得到应用。从1965年起统筹法 的应用在建筑业、大型设备维修计划等方面取得可喜的进展。从1970年起在全国大部分省、 市和部门推广优选法。其应用范围有配方、配比的选择、生产工艺条件的选择、工艺参数的 确定、工程设计参数的选择、仪器仪表的调试等。在20世纪70年代中期最优化方法在工程设 计界得到广泛的重视。在光学设计、船舶设计、飞机设计、变压器设计、电子线路设计、建 筑结构设计和化工过程设计等方面都有成果。从20世纪70年代中期排队论开始应用于研究矿 山、港口、电讯和计算机的设计等方面。图论曾用于线路布置和计算机的设计、化学物品的 存放等。存储论在我国应用较晚，20世纪70年代末在汽车工业和其他部门取得成功。近年来 运筹学 的应用已趋向研究规模大和复杂的问题，如部门计划、区域经济规划等； 并已与系统工程难 以分解。 国际运筹学联合会为了表彰发展中国家运筹学应用好的项目设立了运筹进展奖, 下面列举近年来中国曾获该奖的项目。 （1） 中国国家经济信息系统的项目评价系统(章祥荪，崔晋川，中科院应用数学所, 1996)。 （2） 长江上游生态、经济、发展的最优化(刘光中、徐玖平等，成都科技大学，1996)。 （3） 中国粮食产量预测研究（陈锡康，潘晓明，杨翠红，中科院系统科学所,1999)。 （4） 运筹学在中国农业管理中应用(赵庆祯, 山东师范大学 ，曲阜师范大学，1999)。 （5） 北京公共交通区域运营组织模式的公共汽车运营总调度管理(沈吟东等，武汉科技学院，2005)。 中国运筹学会2008年颁发了中国运筹学会首届科学技术奖,越民义(中科院应用数学所)荣获首届中国运筹学科学技术奖,第二届2010年祁力群(中国香港理工大学）获该奖项。 1.6运筹学的展望 关于运筹学将往哪个方向发展，从20世纪70年代起西方运筹学工作者有种种观点，至今还未 说清。这里提出某些运筹学界的观点，供研究参考。美国前运筹学会主席邦特(S.Bonder) 认 为，运筹学应在三个领域发展： 运筹学应用、运筹科学和运筹数学。并强调发展前两者，从 整体讲应协调发展。事实上运筹数学到20世纪70年代已形成一系列强有力的分支，数学描述 相当完善，这是一件好事。正是这一点使不少运筹学界的前辈认为，有些专家钻进运筹数学 的深处，而忘掉了运筹学的原有特色，忽略了多学科的横向交叉联系和解决实际问题的客观需求 。近几年来出现一种新的批评，指出有些人只迷恋于数学模型的精巧、复杂化，使用高深的 数学工具，而不善于处理面临大量新的不易解决的实际问题。现代运筹学工作者面临的大量 新问题是经济、技术、社会、生态和政治等因素交叉在一起的复杂系统。因此，从20世纪70 年代末至80年代初不少运筹学家提出： 要大家注意研究大系统，注意与系统分析相结 合 。美国科学院国际开发署写了一本书，其书名就把系统分析和运筹学并列。有的运筹学家提 出了“要从运筹学到系统分析”的报告。