运筹学学科发展报告

　　由中国运筹学会编著，介绍了运筹学学科发展情况，并对本学科的进展做了全面而准确的总结。学会对所负责的学科发展研究初稿进行研讨及学术交流后，为研究成果的后完成提出实质性修改意见和建议。整套丛书的特点：，确保权威性，注重研究工作的质量，确保研究报告为反映各学科发展情况的*权威性的指导性丛书；第二，体现前瞻性，学科涉及面较大的不要求面面俱到，应注重体现*热点、前瞻和重大学术进展；第三，将2007年第四季度学科发展的内容纳入进去，做到严谨、完整；第四，时效性好；第五，整体性强。

序 .. 韩启德
前言 .. 中国运筹学会
综合报告
中国运筹学新近进展及展望
一、引言
二、运筹学发展的历程
三、运筹学的作用
四、中国运筹学近年的理论研究项目
五、中国运筹学领域近年来的代表性成果
六、运筹学发展趋势
七、国内外运筹学发展的比较及思考
八、结束语
参考文献
专题报告
中国数学规划新近进展及展望
中国随机优化新近进展及展望
中国博弈论新近进展及展望
中国排序论新近进展及展望
中国供应链管理新近进展及展望
中国计算系统生物学新近进展及展望
目 录
ABSTRACTS IN ENGLISH
Comprehensive Report
Report on the Recent Advances in Operations Research in China
Reports on Special Topics
Recent Advances and Future Prospect of Mathematical Programming in China
Recent Advances and Future Prospect of Stochastic Optimization in China
Recent Advances and Future Prospect of Game Theory in China
Recent Advances and Future Prospect of Scheduling Theory in China
Recent Advances and Future Prospect of Supply Chain Management in China
Recent Advances and Future Prospect of Computational System Biology in China
索引

　　中国运筹学新近进展及展望
　　一、引言运筹学是自 20 世纪 30 年代发展起来的一门新兴交叉学科。它主要研究人类对各种资源的运用及筹划活动，通过了解和发展其基本规律和方法，发挥有限资源的效益，达到总体的目标。从问题的形成开始，到构造模型、提出解案、进行检验、建立控制，直至付诸实施为止的所有环节构成了运筹学研究的全过程。运筹学研究对象的客观普遍性，以及强调研究过程完整性的重要特点，决定了运筹学应用的广泛性，它的应用范围遍及工农业生产、经济管理、工程技术、国防安全、自然科学等各个方面和领域。
　　运筹学从创建时期起就表现出其理论与实践结合的鲜明特点，在它的发展过程中还充分表现出多学科的交叉结合，物理学家、化学家、数学家、经济学家、工程师等联合组织成研究队伍，各自从不同学科的角度出发提出各自对实际问题的认识和见解，促使解决大型复杂现实问题的新途径、新方法、新理论更快地形成。
　　运筹学的学科体系主要包含三大部分：模型、理论和算法。无论是早期解决第二次世界大战中的兵力部署和武器调配，还是生产组织问题或交通、通讯问题，相关领域的运筹学工作者都建立了各种各样的模型，在这些模型下逐步建立了比较完整的理论体系，提出了求解相应问题的各种类型的高效算法。
　　运筹学经过七十多年的发展，已经逐步形成了一套系统的研究和解决实际问题的方法，它可以概括以下五个阶段：
　　1）构建所关心问题的数学模型，将一个实际问题表示为一个运筹学问题。
　　2）分析问题（）解的性质和求解问题的难易程度，寻求合适的求解方案。
　　3）设计求解相应问题的算法，并对算法的性能进行理论分析。
　　4）编程实现算法，并分析模拟数值结果。
　　5）判断模型和解法的有效性，提出解决原始实际问题的具体实施方案。诚然，以上这五个阶段并不是相互独立的，也决非依次进行的。正如邦德（美国工程院院士；曾任美国军事运筹学会主席和美国运筹学会主席）
　　［1］在谈到他几十年建模和分析
　　的体会时指出的那样：“对于模型的开发应该是一种连续的研究、开发、分析、改进 ……的过程，是一个原型化和呈螺旋状发展的过程，而不是一个单个事件。在短期内建造一个原型（假若有必要，加上一些不切实际的假设），然后通过去除那些不切实际的假设，增加过程，增加系统等不断地将模型改进”。
　　线性规划是运筹学模型、理论和算法的典型的代表之一。20 世纪 40 年代前，学者们缺乏对事物进行优化的兴趣和动力，在文献中虽然有四五十篇关于线性不等式系统的文章，但其中没有一篇提及目标函数 ［1］。1947 年，丹齐格基于其第二次世界大战时担任实践计划规划者的经历，认识到多数的实际计划关系都可以用一组线性不等式来刻画，并用一个目标函数来取代为选取一个较好计划而设定的一组基本规则，从而提出了线性规划模型和求解方法——单纯形法。运筹学的发展表明，线性规划及单纯形法不仅是证明理论的一个有力的分析工具，还是一个强有力的计算工具，更是运筹学研究的一个催化剂。学者们对线性规划和单纯形法计算复杂性的持续研究，终产生了椭球算法和内点算法等一系列理论成果，并形成了新的研究课题。线性规划的产生和巨大成功极大地推动了数学规划的发展。
　　邦德［1］在回顾运筹学在美国军事力量的改造中所起的重要作用时指出：“对一个过程、一个系统、或者一个企业的建模是一种技艺。这种技艺在于确定哪些因素与活动需要包含在模型之中，哪些是变量、常数、随机的、约束等；在建立变量之间关系时，应做些什么假设；以及在逐步运作中，如何排除在建立初始模型时所引入的某些不切实际的假设。并且，这是一种可以学习的技艺。”曾任美国管理科学学会主席的马吉对建模的技艺是这样解读的：“要用简单的方法去解释现实，而不要让现实去迎合预先精心设计的模型”。在此意义下，我们不能简单地视运筹学为应用数学的一部分；实际上，我们更应将其视为是广义的解决问题方法的研究。
　　运筹学作为一门新兴的交叉学科，也已在军事国防、企业民生、科技工程、经济金融等领域中产生了深刻而广泛的影响。近年来，世界科技发展突飞猛进，经济全球化愈演愈烈，市场竞争日趋激烈；中国经济已经从计划体制转入市场体制的轨道，并持续高速发展，举国正在实施建设创新型国家的发展战略。在此形势下，我们希望本研究报告能对我国从事运筹学研究、教学和应用的学者、师生和实践者有所启迪，使得我国运筹学工作者能为现代科技日新月异的发展、社会和经济的可持续发展做出贡献。
　　二、运筹学发展的历程
　　数学既是所有学科的共同语言，也是有力的工具。运筹学作为一门有着不长历史的新兴交叉学科，已形成了比较完整的学科体系，但它通常还是作为数学的一个分支。实际上，数学与运筹学有着紧密的关系。数学是解决运筹问题和实现运筹思想的基本的工具之一。运筹学工作者主要用数学方法构造问题模型，建立相应理论，设计和分析求解算法。在这个过程中，他们不仅可以用数学方法解决实际问题，也可以发现新的数学问题，丰富数学的内涵，推动数学的发展。卡斯蒂在其著作［2］中列出了 20 世纪数学的五大指导理论，其中 4 个属于运筹学或与运筹学密切相关，即对偶定理、极大极小定理、停机定理和不动点定理。下面我们对运筹学的发展做一个简要的回顾［3，4］，籍此可以更好地理解运筹学的内涵和特征。
　　（一）运筹学发展简史“就技术发明对战争的影响或就为未来事件的筹划来说，运筹学可认为是起源于古中国或古埃及。”
　　［1］的确，朴素的运筹思想在中国古代历史发展中源远流长。公元前 6 世纪的著作《孙子兵法》研究如何筹划兵力以争取全局胜利，是我国古代军事运筹思想早的典籍。同一时期，我国创造的轮作制、间作制与绿肥制等先进的耕作技术暗含了现代运筹学中二阶段决策问题的雏形。总之，统筹、多阶段决策、多目标优化、合理运输、选址问题、都市规划、资源综合利用等运筹思想方法在中国古代的生产活动和日常生活中屡见不鲜，但很少有人从数学的角度将这些运筹思想和方法进行提升。
　　西方国家的科学家一方面试图从朴素的运筹问题和运筹思想中发展新的数学内涵，另一方面又试图利用已经建立的数学概念和方法解决实际问题。1736 年，欧拉用图论思想成功地解决了哥尼斯堡七桥问题。1738 年，贝努利首次提出了效用的概念，并以此作为决策的标准。1777 年，布·冯发现了用随机投针试验来计算 π 的方法，这是随机模拟方法古老的试验。1896 年，帕累托首次从数学角度提出多目标优化问题，引进了帕累托的概念。1909 年，丹麦电话工程师埃尔朗利用概率论，开展了关于电话局中继线数目的话务理论的研究，开创了排队论研究的先河。1912 年，策梅洛首次用数学方法来研究博弈问题。
　　现代运筹的思想萌芽于次世界大战时期，这段时间人们开始用数学的方法探讨各种运筹问题，只是由于人力和经费不足、资料有限等原因限制了运筹学研究的深度。1915年，哈里斯对商业库存问题的研究是库存论模型早的工作。1916 年，兰彻斯特开展了关于战争中兵力部署的理论，是现代军事运筹早提出的战争模型。1921 年，博雷尔引进了博弈论中策略的概念，对某些博弈问题证明了策略的存在。1926 年，博鲁夫卡发现了拟阵与组合优化算法之间的关系。1928 年，冯·诺依曼提出了二人零和博弈的一般理论。1932 年，威布尔研究了维修问题和替换问题，这是可靠性数学理论早的工作。1939年，康托罗维奇开创性地提出了线性规划，并据此模型研究了工业生产的资源合理利用和计划等问题，因而在 1975 年获得了诺贝尔经济奖。上述这些先驱性的成就对运筹学的发展有着深远的影响。
　　现代运筹学真正起源于第二次世界大战期间，并因其在军事作战方面的大量成功运用而得到蓬勃发展。1935—1938 年被视作运筹学基本概念酝酿期。英国为了有效地运用新研制的雷达系统来应对德国飞机的空袭，在皇家空军中组织了一批科学家，进行新战术试验和战术效率的研究，并取得了满意的效果。他们把自己从事的这种工作叫作“Operational Research”（译作“运筹学”）。第二次世界大战期间，英军的每一个大的指挥部大都成立了这种运筹研究小组。在美国和加拿大的军事部门也相继成立了若干运筹研究小组，称之为“Operations Research”。他们广泛地研究有关战果评价、战术革新、技术援助、战略决策和战术计划等问题。美国运筹学会创始人之一莫尔斯在 20 世纪 50 年代初给运筹学做出了如下定义：“运筹学是为领导机构对其控制下的业务活动作决策时提供定量依据的科学方法”，它反映出运筹学初期的主要作用。
　　1949 年，美国成立了著名的兰德公司，与此同时，许多运筹学工作者逐步从军方转移到政府及产业部门进行研究。在新的、更宽阔的环境中，运筹学的理论和应用研究得到了蓬勃的发展。随之产生的理论成果主要有线性规划、整数规划、图论、网络流、几何规划、非线性规划、大型规划、控制理论等，同时也为欧美等国创造了巨大的经济效益和社会财富。
　　研究优化模型的规划论，研究排队或服务模型的排队论（亦称随机服务系统），及研究博弈模型的博弈论是运筹学早的 3 个重要分支，通常称为运筹学早期的三大支柱。随着学科的发展和计算机的出现，现在分支更细，名目更多，例如线性与整数规划、图与网络、组合优化、非线性规划、多目标规划、动态规划、随机规划、博弈论、随机服务系统、库存论、可靠性理论、决策分析、马尔可夫决策过程、搜索论、随机模拟、管理信息系统等应用基础性学科分支，工程技术运筹学、管理运筹学、工业运筹学、农业运筹学、军事运筹学等交叉与应用学科分支也先后形成。
　　（二）中国运筹学发展简史
　　现代运筹学被引入中国是在 20 世纪 50 年代后期。中国个运筹学小组是在钱学森和许国志两位先生的积极推动下，在 1956 年于中国科学院力学研究所成立。钱学森先生在麻省理工学院取得硕士学位，在加州理工大学取得博士学位后成为该校的位戈达德讲座教授。许国志先生在堪萨斯大学取得博士学位后，在马里兰大学流体力学和应用数学研究所当研究员。他们两人于 1955 年回到祖国致力于新中国的科技事业。可见在中国运筹学一开始就被理解为与工程有密切联系的学科。
　　1959 年，第二个运筹学部门在中国科学院数学研究所成立。力学所的小组与数学所的小组于 1960 年合并成为数学研究所的一个研究室，当时的主要研究方向为排队论、非线性规划和图论，还有人专门研究运输理论、动态规划和经济分析（如投入产出方法）。1963 年是中国运筹学教育史上值得一提的一年，数学研究所的运筹学研究室为中国科技大学应用数学系的届学生（1958 届）开设了较为系统的运筹学专业课，这是次在中国的大学里开设运筹学专业和讲授运筹学的课程。今天在中国，运筹学的课程已成为大多数大学的商学院、工学院乃至数学系和计算机系的基本课程了。
　　20 世纪 50 年代后期，运筹学在中国应用集中在运输问题上。其中一个代表性工作是“打麦场的选址问题”，主要研究和解决在手工收割为主的情况下如何节省人力。此外，国际上著名的“中国邮路问题”模型也是在那个时期由管梅谷提出的。可以看出现在非常热门的“物流学”，在当时就形成了一些研究雏形。
　　中国运筹学早期普及与推广工作的亮点是由华罗庚先生点燃的。在“文化大革命”期间，他身为中国数学会理事长和中国科学院数学所所长，亲自率领一个小组，大家称其为“华罗庚小分队”，到农村、工厂讲解基本的优化技术和统筹方法，应用于日常的生产和生活中。自 1965 年起的 10 年中，他到了约 20 个省和无数个城市，受到各界人士的欢迎，他的辛勤劳动得到了主席的肯定和表扬。华罗庚先生这一时期的推广工作播下了运筹学哲学思想的种子，大大推动了运筹学在中国的普及和发展。直到今天，许多中国人还记得“优选法”和“统筹法”。
　　20 世纪六七十年代，许国志和越民义等中国运筹学的开拓者们在排队论的瞬时概率性态问题、非线性规划梯度算法收敛问题、组合优化中的排序问题等取得了一批重要成果，得到了国外同行的关注和好评。1977 年美国数学会出版的访华报告中指出：“在应用数学方面，中国在诸如排队论等领域已十分迅捷地达到了这些领域的前列。”相关成果在1978 年全国科学大会上获得大会奖和中国科学院重大成果奖；也为中国运筹学的发展打下了坚实的基础，同时培养了一批运筹学的学科带头人和研究骨干。
　　自 20 世纪 80 年代以来，随着改革开放，国内外学术交流不断增加。中国运筹学有了快速的发展，运筹学工作者取得了一批有国际影响的理论和应用成果。例如，将全局化、图论、神经网络等运筹学理论及方法应用于分子生物信息学中的若干应用基础性问题的研究中；将优化及决策分析方法，应用于金融风险控制与管理、资产评估与定价分析模型等相关问题研究中；将随机过程方法应用于排队网络的数量指标分析中；将随机动态规划模型应用于供应链管理中的多重决策的策略计算中。特别是运筹学工作者因在组合优化、生产系统优化、图论、非线性规划和城市交通领域的突出贡献曾先后获得国家自然科学奖二等奖 5 项，因在经济信息系统评估和粮食产量预测方面取得突出成绩曾先后获得国际运筹学会联合会运筹学进展奖一等奖 2 项。
　　此外，中国运筹学工作者继续坚持运筹学研究与国民经济建设等重大项目和问题紧密结合。他们在诸多项目如：山东省与大连市经济发展计划的制订、兰州铁路局铁路运输的优化安排、中外合资经营项目经济评价、宝钢和武钢等大型企业的调度优化、若干国家重大工程中的综合风险分析等方面都发挥了积极的作用，产生了良好的经济效益和社会效益。后值得一提的是，在中国运筹学几十年的发展过程中，中国运筹学会起到了非常重要的作用。中国运筹学会于 1980 年成立，当时是作为中国数学会的一个分会。届全国大会在山东省济南市召开，华罗庚被选为届理事长，副理事长有许国志和越民义。中国运筹学会在 1982 年加入国际运筹学联合会，成为其成员。在时任中国科协主席的钱学森先生的大力支持下，1992 年中国运筹学会获批从中国数学会独立出来，成为国家一级学会。这是中国运筹学发展史上的一个重要事件，它凸显了运筹学以数学为基础，但与数学学科有本质不同的特征。目前，中国运筹学会有 14 个专业分会，涵盖了现今运筹学的大多数分支方向。它在未来中国运筹学的发展中将起到更大的作用。