现代运筹学的发展历史
虽然现代运筹学学科的诞生是在20世纪,但人们使用量化方法来优化决策活动的实践由来已久,朴素的运筹优化观念伴随人类发展的历史。古今中外有很多事例,我国古代兵书《孙子兵法》中就有很多应用数量分析来优化作战决策的论述,《史记》中记载的“田忌赛马”故事则直接体现了古人运筹博弈的智慧(对应于现代运筹学,是一个典型的两人零和对策模型);西方则有18世纪大数学家欧拉(L.Euler)解决柯尼斯堡七桥问题的经典事例。进入20世纪后,运筹学早期的典型事件包括:1913年美国工程师哈里斯(F.W.Harris)最早提出存储优化的经济订货批量公式,1916年英国工程师兰彻斯特(F.W.Lanchester)首次提出了描述作战双方兵力损耗的数学方程——Lanchester方程,以及1917年丹麦工程师爱尔朗(A.K.Erlang)在研究电话系统时最先提出了排队论研究的思路。
尽管20世纪30年代前,已经有不少相关成果出现,但学者普遍认为,真正意义上的运筹分析研究起源于第二次世界大战前的相关工作,这些工作都是为战争服务的。下面简要说明在这段时间及其后运筹学的发展历程,可分为萌芽时期、形成时期和发展时期。
萌芽时期
20世纪30年代末,在第二次世界大战爆发前夕,英国为了应对德军的空中威胁,积极研究雷达系统的作战运用问题,从事这一工作的科学家小组负责人罗威(A.P.Rowe)在1938年将这一工作称为“Operational Research” (20世纪50年代引入到我国后,译为运筹学)。这一工作后来被证明价值巨大,使用的方法和研究模式被广泛推广,促进了运筹学学科的最终形成。20世纪30年代至40年代中期被认为是现代运筹学的萌芽时期。
形成时期
第二次世界大战后,大多数战时运筹研究者回到了原来的工作岗位,很多人在战争中的研究工作得到了其他形式的延续。第一种形式是和军事组织继续合作,开展装备发展论证、作战效能评价、国防建设规划等研究。最为典型的是美军,其战时的海军运筹小组战后扩大为作战评价机构,并与大学建立了合作关系,研究海军武器装备发展的新问题;美国空军则扩大了其战时建立的作战分析小组,在1948年设立了空军运筹局,并在道格拉斯飞机公司启动了兰德(RAND,英文中“研究与发展”的缩写)计划,后者在1949年演变为后来赫赫有名的兰德公司;第二种形式是根据工业生产、城市规划等非军事领域的实际需要,发展出更多的运筹学分支,如更一般的数学规划、动态规划、排队论、计算机模拟等。其中最主要的贡献是由时任美军数学顾问的丹捷格(G.B.Dantzig)在1947年提出的线性规划单纯形解法。
由于研究领域的拓展和研究人员逐步增多,专业化的学术机构相继出现,最早建立运筹学学会的国家是英国(1948年),随后是美国(1952年)和法国(1956年),到20世纪70年代,世界上主要国家基本都建立了运筹学学会或类似专业组织。同时在1959年,国际运筹学学会联合会(INFORS)正式成立,并在英国牛津举行了第一届国际会议。相关专著也相继出现,对第二次世界大战中研究工作进行总结的专著《运筹学方法》( Methods of Operations Research )1951年公开出版(其原版1946年由P.M.Moose和G.E.Kimball写成,但被政府认定需要保密而没能出版),这本书被称为历史上第一本运筹学专著,而被公认为第一本运筹学教材的是《运筹学导论》( Introduction to Operations Research ),出版于1957年。20世纪60年代以后,各类运筹学学术著作和教材已经如雨后春笋般出现。几乎与专业学术机构的发展同步,这些国家的大学在20世纪50年代开始出现专门的运筹学课程,根据美国运筹学学会1973年的统计,截至当时,美国大学中已经出现了50多门运筹学课程,专业化教育的形成也从另一方面标志着运筹学作为一门学科正式形成。
发展时期
如果说20世纪50年代运筹学学会、研究专著和大学课程的出现标志着运筹学这门学科的正式形成,那么20世纪50年代后,美国、西欧等地区工业化生产的蓬勃发展则为运筹学学科的发展提供了强大的需求动力。到20世纪60年代中期,美国大型企业在经营管理中已经大量应用运筹学,用于生产计划制订、资源分配、设备更新等方面,甚至政府和一些公用事业开始雇佣运筹学专家来从事相关方法和模型的研究,以减少成本和提高效率。同时计算机的普及应用解决了手工大规模计算的难题,为运筹学中各类算法的兴起提供了基础条件(1951年,在美国空军支持建成的一台计算机上,最早的通用单纯形算法程序就被编写出来了)。
20世纪50—60年代可称为运筹学发展史上的“大爆发”时期,运筹学各经典分支中的大部分模型和算法都被提出来,运筹学的基础性教材中涉及的大多数内容,包括线性规划的对偶理论、对偶单纯形算法、线性目标规划与解法、求解整数规划的分支定界法和割平面法、求解指派问题的匈牙利算法、动态规划方法、最小支撑树问题与算法、最短路问题及其算法、最大流最小截算法、中国邮递员问题及其解法、对策论中的纳什均衡理论、存储论等都是这一阶段的研究成果。同时一些更为现代的运筹学理论方法,如计算复杂度、启发式算法、蒙特卡洛模拟、决策分析等问题也被提出。
20世纪70—90年代,运筹学各分支的基础理论不断完善,研究范围也不断拓展。求解线性规划的多项式算法——椭圆算法和内点法先后被提出,非线性规划的凸优化理论被系统地阐述,NP和NP-完全问题在20世纪70年代被提出,一些更为现代的优化求解新理念和方法也被逐一提出,包括神经网络模型、模拟退火算法、禁忌搜索方法等。同时,一些商用运筹优化软件被研制出来,本书使用的LINGO软件的早期版本就是1980年由美国芝加哥大学的Linus E.Schrage教授设计开发的。
在应用方面,随着运筹学应用深度和广度的拓展,运筹优化的理念广泛渗入工业生产、经营管理、运输规划、工程优化等社会生产、生活的各个方面,成为现代社会不可或缺的部分,同时也使运筹学和其他关联学科的边界日益模糊,特别是运筹学(OR)和管理科学(MS)日益融合,很多时候OR/MS总是一起使用。
在我国,运筹学最早在20世纪50年代由钱学森、许国志等人由西方引入 ,1956年,他们在中国科学院建立了第一个运筹研究机构,在多个领域开展运筹学研究和应用工作。后来,以华罗庚教授为代表的一批数学家加入运筹学的研究队伍,在生产、生活中广泛推广运筹学知识。1982年,我国加入了国际运筹学联合会,成为这一国际组织的一员,其后随着我国运筹学界与国际交往的增多,我国有更多机会接触运筹学研究的前沿,使得我国在一些运筹学分支上很快达到了国际先进水平。
2000年以后,随着我国社会经济的发展和信息技术的普及应用,运筹学在国民经济规划计划、工业供应链优化、物流网络建设甚至电子商务等方面有着前所未有的深度应用,读者可以从网络购物、快递配送、旅行计划等很多身边的事情发掘其中的运筹优化实例,并从中体会运筹优化对于生产、生活的广泛影响。这同时意味着社会对于运筹专业人才需求会日益旺盛,一个可以参考的事实是:1992—2005年,美国对运筹学应用分析人员的需求从5万多人增长到10万人,增长率超过70%。