1.1 发展简史

虽然现代运筹学学科的诞生是在20世纪，但人们使用量化方法来优化决策活动的实践由来已久，朴素的运筹优化观念伴随人类发展的历史。古今中外有很多事例，我国古代兵书《孙子兵法》中就有很多应用数量分析来优化作战决策的论述，《史记》中记载的“田忌赛马”故事则直接体现了古人运筹博弈的智慧（对应于现代运筹学，是一个典型的两人零和对策模型）；西方则有18世纪大数学家欧拉（L.Euler）解决柯尼斯堡七桥问题的经典事例。进入20世纪后，运筹学早期的典型事件包括：1913年美国工程师哈里斯（F.W.Harris）最早提出存储优化的经济订货批量公式，1916年英国工程师兰彻斯特（F.W.Lanchester）首次提出了描述作战双方兵力损耗的数学方程——Lanchester方程，以及1917年丹麦工程师爱尔朗（A.K.Erlang）在研究电话系统时最先提出了排队论研究的思路。

尽管20世纪30年代前，已经有不少相关成果出现，但学者普遍认为，真正意义上的运筹分析研究起源于第二次世界大战前的相关工作，这些工作都是为战争服务的。下面简要说明在这段时间及其后运筹学的发展历程，可分为萌芽时期、形成时期和发展时期。

1.1.1 萌芽时期

20世纪30年代末，在第二次世界大战爆发前夕，英国为了应对德军的空中威胁，积极研究雷达系统的作战运用问题，从事这一工作的科学家小组负责人罗威（A.P.Rowe）在1938年将这一工作称为“Operational Research”（20世纪50年代引入到我国后，译为运筹学）。这一工作后来被证明价值巨大，使用的方法和研究模式被广泛推广，促进了运筹学学科的最终形成。20世纪30年代至40年代中期被认为是现代运筹学的萌芽时期。

【案例1.1】　分析、评估与改进——用科学方法研究战争问题

1935年，德国法西斯政权已经开始了积极扩军备战，欧洲上空战争阴云密布。为了应对德国空中力量的严重威胁，英国开始了认真的战争准备，其中一个重要工作就是研制能够利用电波远程探测敌机的系统，后来这类系统被称为雷达（RADAR，无线电探测与测距的英文缩写）。如何更有效使用这一新系统呢？在其后几年间，英国的科学家们、英国皇家空军的官兵以及其他相关人员密切合作，进行了一系列的试验，他们在英国东海岸安装了雷达系统，并进行了各类实战化模拟测试。逐渐地，他们确定了跟踪和报告敌机位置的方法，但为了有效地拦截敌机，还必须对英国战斗机加以控制和引导，让它们及时到达适当的地点实施起飞拦截。因此，工作重点就由技术性试验转化为有效的系统使用战术研究，并评估该战术的效率，提出改进的措施建议。

其后参与雷达运用研究工作的部分成员被派到英国皇家空军作战指挥部参与另一项战术应用研究工作，并在1939—1940年的2年间同学者和作战人员合作，取得了很大的成果和广泛的影响，以至于后来在英国空军负责空中轰炸、潜艇作战以及防空作战的部门都成立了类似的研究小组，他们积极参与作战问题研究，提供高质量的决策建议。

1940年秋季，德国开始对英国实施空中大轰炸，英军防空指挥部面临严峻的挑战，为了应对复杂的技术问题和作战问题，其迅速成立了一个由诺贝尔物理学奖得主布莱凯特（P.M.S Blackett）领导的运筹研究小组，成员包括物理学家、化学家、数学家、心理学家、统计员和军官。由于成员复杂，被人们戏称为布莱凯特马戏团。这一早期的运筹研究小组工作极为有效，对于英国成功抗击德军的空袭做出了重要贡献。1941年后，在布莱凯特的建议下，英国皇家海军也成立了类似的研究机构。

在1941年12月珍珠港事件后，美国投入了战争，美国海军和陆军航空作战部队（当时美国空军尚未成立，1947年9月才独立为军种）很快注意到英军中使用科学家研究作战的情况。1942年后，为了应对大西洋上的德国潜艇，美国海军成立了反潜战运筹研究小组，并请麻省理工学院的物理学家莫尔斯（Philip W.Morse）来领导，这一小组后来提出了提高反潜作战效率的诸多建议，为盟军反潜战的胜利做出了重要贡献；同时，美国陆军航空作战部队则成立了“作战分析小组”，研究空战的相关问题。盟国中的加拿大皇家空军也几乎同期成立了多个运筹研究小组。

1945年战争将近结束时，在盟军中提供各类服务的运筹研究小组已经有几十个，保守估计，参与相关研究工作的科学家约700多名。他们不仅提供技术上的帮助，更重要的是研究了各种各样的战果评价和战术革新工作，将各类科学知识应用到作战计划制订、战略决策选择等方面，为最后盟军获得战争胜利做出了重要贡献。作为对照，德意日轴心国方面在整个战争期间，没有类似的研究工作。

比战争中这些学者的贡献更重要的是，很多人在其中看到了一门新学科的萌芽，这门新学科要解决的核心问题是，通过定性定量的科学分析，更好地设计和使用各类系统，为决策者提供有量化依据的、高质量的意见建议。这类问题不但在战争或军事组织中普遍存在，还在平时各类社会经济组织中普遍存在。实际上，由于没有了迫切的战争威胁，大部分战时研究者在战后把注意力更多地转向了国防建设、经营计划、企业生产甚至社会管理等领域的问题，大大拓展了研究范围，使得运筹学在工业和大学中有了快速的发展。

1.1.2 形成时期

第二次世界大战后，大多数战时运筹研究者回到了原来的工作岗位，很多人在战争中的研究工作得到了其他形式的延续。第一种形式是和军事组织继续合作，开展装备发展论证、作战效能评价、国防建设规划等研究。最为典型的是美军，其战时的海军运筹小组战后扩大为作战评价机构，并与大学建立了合作关系，研究海军武器装备发展的新问题；美国空军则扩大了其战时建立的作战分析小组，在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多门运筹学课程，专业化教育的形成也从另一方面标志着运筹学作为一门学科正式形成。

1.1.3 发展时期

如果说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%。