|
从齐王与田忌赛马谈起 什么是运筹学?通俗地说，就是动脑筋，想办法。 从字面上解释“运筹”，就是制定策略，筹划的意思。早在《汉书·高帝记》一书中，就记载了“上(刘邦)曰:'夫运筹帷幄之中，决胜于千里之外……’”，意思是指在后方决定作战策略。这是最早提到“运筹”一词的书。至于利用运筹学的思想处理问题，还可以追溯到战国时期。“齐王赛马”的故事就是一个典型例子。 故事是这样的:战国时期，齐国的国王有一天提出要与田忌赛马。田忌答应后，双方约定:每人都从上、中、下三个等级的马中各出一匹，每匹马都得参加比赛，而且只参加一次，每次比赛各出一匹马，一共比赛三次，每次比赛后负者要给胜者一千金。当时的情况是，在三种不同等级的马中，齐王的马都比田忌的马强一些。显然田忌是处于劣势看来要输掉三场了。但是田忌手下的谋士给田忌出了一个主意:每次比赛先让齐王说出他要出哪一四马，然后让田忌用下马对齐王的上马，用中马对齐王的下马，用上马对齐王的中马。比赛结果，田忌二胜一负，反而得了一千金。 这个问题的中心意思是寻找一个最优策略战胜对方。这就是对策论的思想萌芽。而现在对策论已经成为运筹学的重要分支之一。 我们再讲一个历史上的故事。在东普鲁士的哥尼斯堡城(现在的加里宁格勒)，城中有一条河叫做普雷格尔河，河中有两座小岛，河上有七座桥，将两个小岛与城市的其他部分联结起来(如图1)。  当地居民热衷于这样一个问题:从自己的住所出发，走过七座桥，且每座桥只经过一次又回到出发地。这个题目似乎不难，许多人都作了试验，但总是失败。这件事引起了当时一位数学家欧拉(Euler1707-1783)的注意，他在1736年从理论上证明了,这样的路线是不存在的，并在圣彼得堡科学院作了一次报告，从而解决了这个疑案。 这个故事所叙述的是古典图论中的一个著名问题。随着现代科学技术的发展和计算机的出现，使图论的理论得到飞速发展，现在它已成为一门独立的学科。利用图论可以解决许多工程建设和管理决策中的优化问题。关于这方面的问题，我们将在以后作详细介绍。 在这里特别值得提出两个与图论有密切关系的问题，它们都是中国数学家提出的。 一个是著名数学家华罗庚教授从事并领导的统筹方法的研究，在经济建设中取得了明显的效果。 另一个是著名运筹学专家管梅谷教授，1958年在山东省推广运筹学的热潮中提出的“最短邮递员路线问题”。提法是这样的:一个邮递员每次送信要走遍他负责的投递范围内的街道，然后再回到邮局，问他应按什么样的路线走，使所走的路程最短?和这个问题类似的还有警察的巡逻路线、洒水汽车(扫雪汽车)的行车路线等，它们的共同点是，寻找一条优化路线，以便能节省体力，节约燃料，从而提高效率。 管梅谷教授的文章最先刊登在中国的杂志上，所以世界运筹学界称这类问题是“中国邮递员问题”。 当前，在工农业生产、交通运输、财贸工作等各种经济活动中，一个重要任务是如何提高经济效益。一般来说，提高经济效益有两个途径。一个是属于技术方面的，如更换设备、引进新技术、使用新型原材料等;另一个是提高管理水平，对现有的生产组织和计划加以改造。换句话说，就是合理使用人力和物力资源，合理地组织生产过程，在现有的资源条件下，统筹安排，使总的经济效益最好。这后一个问题，是属于运筹学研究的内容。 许多人认为理论科学、应用技术和管理是现代社会的三大支柱。而现代化管理的显著特点之一，就是利用各种数学方法来解决复杂的经营管理问题。在美国把“管理科学”(Management science)和“运筹学”(Operationsresearch)这两个词几乎当作同义词，可见它们的关系是多么密切了。 下面我们将从运筹学的发展历史中，看到它们是怎样联系到一起的。 运筹学的起源和发展 (一)运筹学的创建阶段(1945~1954) 早期运筹学的内容是和战争紧密联系在一起 的。在第一次世界大战时期，美国的托马斯·爱迪生接受了一项任务，就是找出商船的运行策略，使其最有效地减少敌人潜艇对商船的损害。在同一时期，一位在哥本哈根电话公司工作的瑞典工程师爱尔朗(AKErlang)进行了关于电话自动拨号设备对电话需求影响的试验。大家认为他的工作是排队论数学模型的基础。以上这些都是运筹学的早期工作。 在第二次世界大战期间，为了解决作战行动和军需物资的生产与供应中所发生的问题，英国的军事管理部门邀请了各种不同领域的科学家来研究这方面的问题。例如，为防备德国空军的轰炸，曾研究如何在英国本土上布置防空雷达网;为了封锁德国潜水艇在比士考海湾的活动，研究过如何决定侦察机的飞行路线、侦察飞机的架数和起飞时间;为了轰炸德军潜水艇，曾研究过深水炸弹在什么深度起爆才会有最大的杀伤力等等。 此后，美国的军事部门也成立了类似的小组，他们为了保护在大西洋中运输船队的安全，曾研究过如何护航的问题。 在军事物资生产方面，为了在一定时间内供应大量合格物资，就要着手解决产品验收，提高生产效率等问题。 在解决这些问题时，不增加现有武器装备、材料、人力，而是运用数学方法合理安排这些人力和物力，使其达到最大效果。 第二次世界大战以后，许多军事工业转为民用工业，当年搞军事运筹学的专家转到民用工业部门工作，他们为了解决在经济计划、工农业生产、交通运输和公用事业中提出的大量关于提高生产率，增加利润，降低成本等问题，先后成立了一些研究机构。在英国于1950年首先成立了“OR 俱乐部”，俱乐部除了讨论运筹学在生产和服务部门应用的可能性外，还为创办《运筹学》杂志奠定基础。俱乐部在1953年改为英国运筹学会。美国在1952年成立了“OR学会”，在这些组织中，运筹学工作者研究运筹学的理论和应用，并且获得了极其丰富的成果。 在这个发展阶段中，值得提出的是美国数学家丹捷格(G.B.Dantzig)，在1947年提出的解决线性规划问题的单纯形方法。 丹捷格当时是美国空军审计官的数学顾问，正在为取得博士学位作准备。他在第二次世界大战的经历中，常常碰到需要解决诸如部队训练、后勤供应、战斗部队调动的计划以及日程安排等问题。他把这些问题称为规划(Programing)，而且大多是线性型的规划。在具体解决时，往往要解一组线性不等式。而线性不等式组是很不好解的，为了解决这一困难，丹捷格提出了解线性规划的单纯形方法，这一方法直到今天还在使用。 （二)运筹学的成长阶段(1955~现在) 这个阶段有以下几个特点。 1.运筹学的理论发展迅速。 自从丹捷格提出解线性规划的单纯形法以后，使得运筹学的许多分支可以充分利用这一成果迅速发展，在此基础上，又提出了许多新的理论。例如，1958年柯莫瑞(RE.Gomory)提出了解整数线性规划的割平面法以后，使整数规划逐步形成一个分支。在近几年，整数规划的理论又有了很大进展，论文数量增多，有时在短短的两个月内就可收到8000篇论文。又如，1951年美国数学家贝 尔 曼(R·Bellman)等人,根据一类多阶段决策问题的特性，提出了解决这类问题的“最优化原理”，从而创立了解决最优化问题的新方法--动态规划。再如，决策论的形成也是在这一阶段。详细情况我们将在后面介绍。 目前，运筹学已经是一个庞大的家族了。她的家族成员有:线性规划、整数规划、分数规划、参数规划、非线性规划、动态规划、几何规划、目标规划和多目标规划，这些都属于规划论的内容。另外还有排队论、决策论、对策论、存贮论、可靠性理论、图论和网络流、随机控制与模拟技术、模型论、组合最优化等近二十个分支。 可以预料，运筹学的理论研究将会得到进一步系统的、深入的发展。以数学规划论为例，它由分散的、具体的研究方向，开始向统一的、抽象的研究方向发展，也就是用一种或几种方法及其理论，把它们统一在一个系统之下进行研究。 2.算机的发展是推动运筹学发展的巨大动力。 运筹学的方法之所以广泛地应用于实际，是和计算机的发展分不开的。运筹学要解决的问题大都是一类优化问题，这类问题需要在众多的方案中选出一个最优方案，供决策者参考。为此，要进行大量的计算，如果只依靠人工去计算,不仅工作量大，而且有时是难以实现的。 在1951年时，由于计算机的容量很小，因此解有10个约束条件的线性规划问题，就达到了国际水平。而到了1963年，利用计算机就可以解1000~10000个约束条件的大规模线性规划问题了。从计算速度上看，1956年解带有67个约束条件的线性规划问题需要计算1小时，而在1963年解同样规模的线性规划问题，只需要28秒。 现在，不仅计算机已广泛应用于运筹学的各个分支，而且解题规模之大，速度之快也是前所未有的。如今运筹学的许多分支的算法都有了标准程序，供实际工作者随时调用。 只有计算机的发展而无运筹学的理论上的进展以及算法的更新，也是很难解决实际问题的。 我们举个例子说明。现在要分配70个人做70项工作，要求是:每人都有工作做，每项工作必须有人干。但是由于每个人的专长不同，因此他们于每一件工作的效率不同，这样一来，就存在着一个如何安排工作，使总的效益最佳的问题。在这个问题中总的分配方案有70!种，这个数字比10100还要大。如果我们对每一个方案进行计算比较其优劣，大概要算多长时间呢?说得形象些，如果在150亿年以前，我们的祖先就有了一台高速电子计算机，那么从那时开始计算到今天也算不完。然而使用了线性规划的单纯形法的标准软件，仅用1分钟就可获得最优分配方案。 有人曾经预言，今后十年，运筹学和计算机方法的界限将消除，并将脱离各自的领域，组合成更适用、更广泛的科学管理形式。 3.运筹学在世界范围内普及。 在四十年代，运筹学刚刚开始形成时，只有十几个人组成的运筹学小组，仅限于研究军事上提出的问题。到第二次世界大战结束时，参加运筹学工作的科学家估计已超过了七百人。目前，仅以美国为例，搞军事运筹学的人，估计有一万名到一万五千名的样子。在各企业中搞一般应用的人就更多了。 1955年召开了第一次国际运筹学会，目前已有三十多个国家参加了国际运筹学会。我国于1980年成立了中国运筹学会，并创办了《运筹学杂志》及《运筹学通讯》。 1982年我国参加了国际运筹学会，使我国有机会与世界各国的运筹学工作者进行学术交流。1985年我国又作为发起国成立了亚太地区运筹学会，以推动这个地区的运筹学研究和普及教育工作。 我国的运筹学普及工作是从1956年开始的。首先在中国科学院力学研究所成立运筹室。1959年组织了全国运筹学讲习班，以后又在一些高等学校中设立了运筹学专业，有的院校还有了运筹学专业的研究生。目前我国已有二十多所院校设有运筹学专业。1985年6月在成都召开了全国首届运筹学正规教育和普及教育讨论会，会议希望在全国理工类、财经类院校普及开设运筹学选修课，在有条件的地方，还可向中学生普及运筹学知识。中国人民解放军总参谋部已决定，全军各院校开设运筹学必修课。 以上这些事实预示着，在不久的将来，运筹学之花将会开遍祖国大地。 |
|
|
