发布时间:2013-06-14 阅读量:110138
来源:http://www.bulletin.cas.cn/gkml/1111/xkfz11/201203/P020120320350064710465.pdf
运筹学发展的回顾与展望
胡晓东 袁亚湘 章祥荪
(中国科学院数学与系统科学研究院,北京100190)
摘要
运筹学是自二十世纪三四十年代发展起来的一门新兴交叉学科,它主要研究如何应用数学和计算的理论与方法对社会系统和工程系统做出最优或满意的决策。本文概述了运筹学的主要特征和方法,简述了运筹学的发展历程,综述了运筹学几个主要分支的发展状况,介绍了运筹学中十几个有代表性的难题,展望了运筹学未来发展的方向。
关键词 运筹学,建模,优化,算法
Review and Prospect for the Development of Operations Research
Hu Xiaodong Yuan Yaxiang Zhang Xiangsun
(Academy of Mathematics and System Science, CAS, Beijing 100190)
Abstract
Operations Research (OR) is an interdisciplinary subject emerged in 1930s. It mainly studies how to make optimal or satisfactory solutions through mathematical and computational theories and methods for social and engineering systems. In this paper, we first summarize the features and methodology of OR and make a brief review on the development of OR. Then, we survey the status of some main directions of this discipline along with some its typical open problems. In the end of the survey we prospect for the trend of OR in the future.
Keywords Operations Research, Mathematical modeling, Optimization, Algorithms
一、引言
运筹学是自二十世纪三四十年代发展起来的一门新兴交叉学科。它主要研究人类对各种资源的运用及筹划活动,以期通过了解和发展这种运用及筹划活动的基本规律,发挥有限资源的最大效益,达到总体最优的目标。从问题的形成开始,到构造模型、提出解案、进行检验、建立控制,直至付诸实施为止的所有环节构成了运筹学研究的全过程。运筹学研究对象的客观普遍性,以及强调研究过程完整性的重要特点,决定了运筹学应用的广泛性,它的应用范围遍及工农业生产、经济管理、工程技术、国防安全、自然科学等各个方面和领域。
运筹学从创建时期开始起就表现出其理论与实践结合的鲜明特点,在它的发展过程还充分表现出多学科的交叉结合,物理学家、化学家、数学家、经济学家、工程师等联合组织成研究队伍,各自从不同学科的角度出发提出各自对实际问题的认识和见解,促使解决大型复杂现实问题的新途径、新方法、新理论更快地形成。
运筹学主要包含三大部分:模型、理论和算法。无论是早期解决二战中的兵力部署和武器调配,还是生产组织问题或交通、通讯问题,相关领域的运筹学工作者都建立了各种各样的模型,在这些模型下逐步地建立了比较完整的理论体系,提出了求解相应问题的各种类型的算法。
运筹学经过六十多年的发展,已经逐步形成了一套系统的解决和研究实际问题的方法,它可以概括为以下几个阶段。(1)构建所关心问题的数学模型,将一个实际问题表示为一个运筹学问题。(2)分析问题(最优)解的性质和求解问题的难易程度,寻求合适的求解方法。(3)设计求解相应问题的算法,并对算法的性能进行理论分析。(4)编程实现算法,并分析模拟数值结果。(5)判断模型和解法的有效性,提出解决原始实际问题的方案。这些阶段并不是相互独立的,也决非依次进行的。正如邦德(美国工程院院士;曾任美国军事运筹学会主席和美国运筹学会主席)[8] 在谈到他几十年建模和分析的体会时指出的那样:“对于模型的开发应该是一种连续的研究、开发、分析、改进 …… 的过程,是一个原型化和呈螺旋状发展的过程,而不是一个单个事件!在短期内建造一个原型(假若有必要,加上一些不切实际的假设),然后通过去除那些不切实际的假设,增加过程,增加系统等等不断地将模型改进”。
邦德 [8] 在回顾运筹学在美国军事力量的改造中所起的重要作用时指出:“对一个过程、一个系统、或者一个企业的建模是一种艺术。这项艺术在于确定哪些因素与活动需要包含在模型之中,哪些是变量、常数、随机的、约束等;在建立变量之间关系时,应做些什么假设;以及在逐步运作中,如何排除在建立初始模型是所引入的某些不切实际的假设。并且,这是一种可以学习的艺术。”希望本文能对我国运筹学的普及、研究、应用和发展有所帮助。
二、运筹学发展历程
1. 运筹学发展简史
朴素的运筹思想在中国古代历史发展中源远流长。公元前六世纪的著作《孙子兵法》研究如何筹划兵力以争取全局胜利,是我国古代军事运筹思想最早的典籍。同一时期,我国创造的轮作制、间作制与绿肥制等先进的耕作技术暗含了现代运筹学中二阶段决策问题的雏形。总之,统筹、多阶段决策、多目标优化、合理运输、选址问题、都市规划、资源综合利用等运筹思想方法屡见不鲜,但很少有人从数学的角度将这些运筹思想和方法得到提升。
西方国家的科学家一方面试图从朴素的运筹问题和运筹思想中发展新的数学内涵,另一方面又试图利用已经建立的数学概念和方法解决实际问题。 1736年,欧拉用图论思想成功地解决了哥尼斯堡七桥问题。1738年,贝努利首次提出了效用的概念,并以此作为决策的标准。1777年,布冯发现了用随机投针试验来计算的方法,这是随机模拟方法(蒙特卡洛法)最古老的试验。1896年,帕累托首次从数学角度提出多目标优化问题,引进了帕累托最优的概念。1909年,丹麦电话工程师埃尔朗利用概率论,开展了关于电话局中继线数目的话务理论的研究,开创了排队论研究的先河。1912年,策梅洛首次用数学方法来研究博弈问题。
现代运筹的思想萌芽于一战时期,这段时间人们开始用数学的方法探讨各种运筹问题,只是由于人力不足,资料有限,经费不足的原因限制了运筹研究的深度。1915年,哈里斯对商业库存问题的研究是库存论模型最早的工作。1916年,兰彻斯特开展了关于战争中兵力部署的理论,这是现代军事运筹最早提出的战争模型。1921年,博雷尔引进了对策论中最优策略的概念,对某些对策问题证明了最优策略的存在。1926年,博鲁夫卡最早发现了拟阵与组合优化算法之间的关系。1928年,冯. 诺依曼提出了二人零和博弈的一般理论。1932年,威布尔研究了维修问题和替换问题,这是可靠性数学理论最早的工作。1939年,康托罗维奇开创性地提出线性规划,并据此模型研究了工业生产的资源合理利用和计划等问题,因而在1975年获得了诺贝尔经济奖。上述这些先驱性的成就对运筹学的发展有着深远的影响。
现代运筹学真正起源于20世纪二次大战期间,并因其在军事作战方面的大量成功运用而得到蓬勃发展。1935~1938年被视作运筹学基本概念酝酿期。英国为了正确运用新研制的雷达系统来对付德国飞机的空袭,在皇家空军中组织了一批科学家,进行新战术试验和战术效率的研究,并取得了满意的效果。他们把自己从事的这种工作叫做“Operational Research”(我国翻译成“运筹学”)。二战期间英军每一个大的指挥部大都成立了这种运筹研究小组。在美国和加拿大的军事部门也成立了若干运筹研究小组,称之为“Operations Research”。他们广泛地研究有关战果评价、战术革新、技术援助、战略决策和战术计划等问题。
1949年,美国成立了著名的兰德公司,与此同时,许多运筹学工作者逐步从军方转移到政府及产业部门进行研究。在新的、更宽阔的环境中,运筹学的理论和应用研究得到了蓬勃的发展。随之产生的理论成果主要有线性规划、整数规划、图论、网络流、几何规划、非线性规划、大型规划、最优控制理论等;同时也为欧美等国创造了巨大的社会财富。
研究优化模型的规划论,研究排队(或服务)模型的排队论(或随机服务系统),及研究对策模型的对策论(或博弈论)是运筹学最早的三个重要分支,通常称为运筹学早期的三大支柱。 随着学科的发展和计算机的出现,现在分支更细,名目更多;例如线性与整数规划、图与网络、组合优化、非线性规划、多目标规划、动态规划、随机规划、对策论、随机服务系统(排队论)、库存论、可靠性理论、决策分析、马尔可夫决策过程(或马尔可夫决策规划)、搜索论、随机模拟、管理信息系统等基础学科分支,工程技术运筹学、管理运筹学、工业运筹学、农业运筹学、军事运筹学等交叉与应用学科分支也先后形成。
在运筹学飞速发展的过程中,至少还有两个因素起了非常重要的作用:(1)运筹学方法的实质性改进。二次世界大战以后,许多参加过运筹学小组或者听说过这项工作的科学家都对相关领域进行了更深入的研究。很多欧美国家的大学里设立了运筹系、管理科学系、工业工程系、系统科学系,在这些系和数学系及计算机科学系开设了运筹学及其一些分支学科的课程。(2)现代计算机的诞生、发展和应用。运筹学中的复杂问题的求解通常需要进行大量的计算工作,借助于计算机人们所能完成的计算工作量要比手工计算快千百万倍。计算机及相关软件的普及更易于人们应用运筹学的方法解决实际问题,从而大大地推动了运筹学的进一步发展。比克斯比 [8](美国工程院院士;曾任数学规划学会主席)在回顾求解线性规划的实际问题的几十年的发展历程时指出:“计算机的进步对线性规划的实际应用起到了巨大的作用;我们知道,如果没有计算机的话,那么线性规划根本就不可能存在。”
2. 中国运筹学发展简史
现代运筹学被引入中国是在五十年代后期。中国第一个运筹学小组是在钱学森、许国志先生的推动下,在1956年于中国科学院力学研究所成立。钱学森先生在麻省理工学院取得硕士学位,在加州理工大学取得博士学位后成为该校的第一位戈达德讲座教授。许国志先生在堪萨斯大学取得博士学位后,在马里兰大学流体力学和应用数学研究所当研究员。他们两人于1955年回到祖国致力于新中国的科技事业。可见在中国运筹学一开始就被理解为与工程有密切联系的学科。
1959年,第二个运筹学部门在中国科学院数学研究所成立,这是大跃进中数学家们投身于国家建设的一个产物。力学所小组与数学所的小组于1960年合并成为数学研究所的一个研究室,当时的主要研究方向为排队论、非线性规划和图论,还有人专门研究运输理论、动态规划和经济分析(例如投入产出方法)。1963年是中国运筹学教育史上值得一提的一年,数学研究所的运筹学研究室为中国科技大学应用数学系的第一届学生(58届)开设了较为系统的运筹学专业课,这是第一次在中国的大学里开设运筹学专业和授课。今天,运筹学的课程已成为几乎所有大学的商学院、工学院乃至数学系和计算机系的基本课程了。
五十年代后期,运筹学在中国的应用集中在运输问题上。其中一个代表性工作是研究“打麦场的选址问题”,解决在手工收割为主的情况下如何节省人力。此外,国际上著名的“中国邮路问题”模型也是在那个时期由管梅谷教授提出的。可以看出现在非常热门的“物流学”,在当时就形成一些研究雏形,但可惜中国在计划经济体制下,大工业落后,使我国在相当长的时期中远离了当代“物流学”的发展主流。
中国运筹学早期普及与推广工作的亮点是由华罗庚先生点燃的。在文化大革命期间,他身为中国数学会理事长和中科院数学所所长,亲自率领一个小组,大家称为“华罗庚小分队”,到农村、工厂讲解基本的优化技术和统筹方法,使用于日常的生产和生活中。自1965年起的十年中,他到了约二十个省和无数个城市,受到各界人士的欢迎,他的辛勤劳动得到了毛泽东主席的肯定和表扬。华罗庚先生这一时期的推广工作播下了运筹学哲学思想的种子,大大推动了运筹学在中国的普及和发展。直到今天,许多中国人还记得“优选法”和“统筹法”。
自上个世纪八十年代以来,随着改革开放,国内外学术交流不断增加。中国运筹学有了快速地发展,运筹学工作者取得了一批有国际影响的理论和应用成果,他们因在组合优化、生产系统优化、图论和非线性规划领域的突出贡献曾先后获得国家自然科学奖二等奖四项,因在经济信息系统评估和粮食产量预测方面取得突出成绩曾先后获得国际运筹学会联合会运筹学进展奖一等奖二项。
3. 运筹学发展的动力
人类对物质世界的不断探索及认识和人类社会进步的需求是数学最初的、也是能持续发展的核心驱动力,而数学自身矛盾的解决和体系的完善是数学健康发展的内在驱动力。这两股力量相互作用和促进也是运筹学不断向前发展的推动力。
著名科学家冯·诺伊曼 [6] 曾经这样分析这两股力量对数学的影响:“当数学学科走向远离其经验泉源或更远些时,当这门学科进入第二代,第三代,仅能依靠来自‘现实’思想的间接的启迪时,它就会被很严重的困难所包围。它变得越来越纯审美的,越来越纯粹地为艺术而艺术的。当然,这也不一定是坏事,因为这个领域可能仍然与那些更接近经验的有关学科交融着,或者这个学科处在具有极高鉴赏能力的人们的影响之下。但是存在着很大的危险,这个领域会沿着最省力的方向再向前发展,这条发自源头的川流会分道为数目众多的,无意义的支流,这个学科将会成为既琐碎又复杂的一团杂乱无章之物。换句话说,在远离其经验泉源之后,在过于“抽象的”内部繁殖之后,一个数学学科处于退化的危险之中。不论怎样,只要到了这个地步,我认为唯一的解决办法就是使之返老还童,回到其源,回到或多或少的直接经验的概念。我确信这样做是使这门学科保持新鲜的生命力的必要条件;这一点在未来仍将是正确的”。
著名数学家韦尔 [6] 也曾经说道:“当一个数学分支不再引起除去其专家以外的任何人的兴趣时,这分支就快要僵死了,只有把它重新栽入生气勃勃的科学土壤之中才能挽救它”。这实际上也指出了运筹学研究一旦脱离现实世界将给其发展带来的后果。如何才能使得运筹学保持活力,使其健康发展呢?美国的运筹学发展自始至终处于世界领先地位,他们在运筹学的研究和应用中所积累的丰富经验值得借鉴。库珀(美国管理科学学会首任主席)[8] 回忆他与查尼斯等人开展线性规划在工业领域的应用时提到,他们两位冯·诺伊曼理论奖获得者在长期合作中形成了“应用驱动理论”的运筹学研究方法:“首先解决提出的问题并导致成功的应用。然后为了完善、扩展与推广这一应用去研究文献。最后将这些进一步描述获得结果写成文章发表,并且报告应用的结果;此外转向更进一步的应用,等等”。
三、运筹学发展状况
六十多年以来,运筹学在研究与解决复杂的实际问题中不断地发展和创新,各种各样的新模型、新理论和新算法不断涌现,有线性的和非线性的,连续的和离散的、确定性的和不确定性的。至今它已成为一个庞大的、包含多个分支的学科 [5],其中一些已经发展得比较成熟,另外一些还有待完善,还有一些才刚刚形成。
1、数学规划
数学规划是在决策变量满足一定约束下求一个或多个函数的极小值或者极大值。它以大量实践中抽象出来的典型最优化模型为研究对象,利用数学工具研究这些模型的数学性质,构造与实现求解方法,以及将算法应用于实际问题。自从1939年康托罗维奇提出线性规划模型、1947年丹齐格提出求解线性规划问题的单纯形法、卡罗胥和库恩与塔克先后分别独立地给出一般非线性规划问题的最优性条件以来,数学规划得到了快速发展,形成了多个分支。
1.1 线性规划
自1939年苏联数学家康托罗维奇提出线性规划问题和1947年美国数学家丹齐格求解线性规划问题的通用方法──单纯形法以来,线性规划可以说是研究得最为透彻的一个研究方向。单纯形法统治线性规划领域达四十年之久,而且至今仍是最好的应用最广泛的算法之一。虽然它在最坏情况具有指数复杂性,但在平均意义下已经证明是一个多项式算法。目前,关于单纯形算法的研究主要在于如何选取主元。另一大类算法是内点法,它起源于1979年苏联数学家卡奇扬提出的多项式椭球算法,而因1984年美籍印度裔数学家卡玛卡提出的多项式时间算法而迅速成为国际热点,各式各样的算法大量涌现:诸如仿射变换法、势函数方法、对数罚函数法、路径跟踪法、原始对偶法、不可行内点法等等。目前线性规划的内点法也趋于成熟,这方面的研究者们目前大都致力于以线性规划作为特例的锥规划,以及如何利用线性规划松弛求解整数规划等方面的研究。然而,就线性规划而言,是否存在强多项式算法仍然是一个重要且困难的理论问题。
1.2. 非线性规划
等式约束规划问题的最优性条件可追溯到拉格朗日,一般非线性规划问题的最优性条件则归功于卡罗胥和库恩与塔克,是他们奠定了非线性规划的理论基础。然而,目前还有不少人试图在没有强互补的条件下进行理论分析和算法研究。对偶理论是非线性规划理论研究的另一个重点。在计算方法方面,早期的方法以最速下降法和牛顿法为主。1959年拟牛顿法的引入和1964年非线性共轭梯度法的出现,吸引了许多研究者研究非线性规划。目前,序列二次规划算法是一类被用于广泛求解一般非线性规划的有效算法,同时也还有许多研究者在为改善这类算法作努力,其中包括序列线性规划算法以及内点算法等。非线性规划算法通常使用线搜索策略选取步长,或通过求解信赖域子问题而得到新的迭代点。这两个方面的研究非常基本,但仍有改善的空间。2001年弗莱彻和勒斐通过将非线性规划问题视为双目标问题而提出的滤子方法和2002年鲍威尔提出的基于二次插值的直接法是近些年来两个重要的算法进展。对于约束规划问题,如何推广鲍威尔的直接法;对于大规模问题,如何设计子空间算法;以及如何有效求解一般非线性规划的全局最优,和一些来自于图像处理等领域的特殊的非光滑问题是目前非线性规划比较重要的研究问题。总之,尽管在表面上看非线性规划已经有许许多多的研究,但由于非线性的存在,好的研究结果还将会不断出现,并且随着问题的不同而产生更加具有针对性的特殊算法。
1.3.锥规划
锥规划是线性空间中凸锥上的数学规划,它是线性规划与非线性规划的推广。自上世纪九十年代中期开始,它一直是国际优化领域的研究热点。相关的研究带动了数学规划学科的深入发展,促进代数、群论、拓扑学、几何学、非线性分析等分支在数学规划中的融合,及优化理论与技术在工程、交通、经济与金融、管理等领域的广泛应用。
目前的锥规划方面的研究成果主要包括以下四个方面:(1)二阶锥优化和半定优化。线性二阶锥优化和半定优化已经得到了很好的发展,并且广泛地应用于各种实际问题。近些年,人们开始致力于非线性二阶锥优化和非线性半定优化的理论与算法的研究。(2)对称锥优化。上个世纪末国际优化专家开始致力于这一领域的研究工作,主要集中在求解对称锥上线性优化问题的内点算法方面。近几年,人们开始探讨对称锥上的非线性优化问题和非凸优化问题的理论与各种算法。(3)齐次锥优化。齐次锥的理论早在1963年就有相关研究,但齐次锥优化问题的研究最近才开始。(4)双曲锥优化。这方面目前只有很少的理论研究,需要寻求合适的工具开展其理论与算法的研究。
1.4.矩阵规划
在众多的科学领域与社会经济中,很多优化问题的决策变量是一个具有特殊结构的矩阵,这样的优化问题被称为矩阵优化或者矩阵规划。矩阵规划的早期研究可以追溯到1981年,然而真正的研究是在20世纪90年代,它以被誉为21世纪的线性规划-半定规划为研究起点。至今,线性半定规划的理论趋于完善,人们正在发掘它在实际中的应用。然而,目前的数值软件只能有效的求解矩阵维数小于500的小规模线性半定规划问题,因此,开展大规模半定规划的数值方法研究是当前一项十分迫切而又重要的课题。此外,由著名华人数学家陶哲轩等人在2006年提出的压缩传感理论而引发的低秩矩阵问题,其理论与算法研究是当今优化领域与信息科学领域(例如,信号处理、图像恢复与重建)共同关心的热点研究课题。在未来一段时期里,矩阵(锥)优化理论与算法、张量(锥)优化理论与算法、多项式优化理论与算法研究等方向必将引起人们的关注。
1.5. 变分不等式与互补问题
变分不等式与互补问题是一类具有普遍意义的均衡优化模型。它不仅为非线性优化、极大极小、对策论、非线性方程、微分方程等提供了一个统一的理论框架,而且在力学工程、交通、经济、管理等实际部门有广泛的应用。互补问题首先由丹齐格和科特尔于1963年提出。次年,科特尔在他的博士论文中第一次提出求解它的非线性规划算法。变分不等式问题首先被哈特曼和斯塔姆巴切在1966年提出。后来发现,变分不等式是互补问题的一个推广,且其数学性质和应用有惊人的相似之处。所以,它们经常在文献中成对出现。变分不等式与互补问题被提出后,很快引起了当时运筹学界和应用数学界的广泛关注和浓厚兴趣,许多人参与了这类问题的研究。经过40余年的探索,特别是20世纪最后10年的研究,人们在理论与算法方面取得了丰富、系统的成果, 并在科技与经济中得到了广泛的应用。
当前主要是对于广义变分不等式和锥互补问题的研究,而对于不确定信息下变分不等式和互补问题的研究无疑是发展的必然。归纳起来,对它们的研究可分为理论与算法两方面:前者主要研究解的存在性、唯一性、稳定性与灵敏度分析、以及它们与其他数学问题的联系等;后者则主要建立有效的求解方法及相应的理论和数值分析。
1.6. 整数规划
整数规划是带整数变量的最优化问题,即求解一个全部或部分变量为整数的多元函数受约束于一组等式和不等式条件的最优化问题。整数规划的历史可以追溯到上世纪50年代,丹齐格首先发现可以用0-1变量来刻画最优化模型中的固定费用、变量上界、非凸分片线性函数等。他和富尔克森和约翰逊对旅行商问题的研究成为后来分枝-割方法和现代混合整数规划算法的开端。1958年戈莫里发现了第一个一般线性整数规划的收敛算法-割平面方法。随着整数规划理论和算法的发展,整数规划已成为应用最广泛的最优化方法之一,特别是近年来整数规划算法技术和软件系统的发展和推广,整数规划得到了广泛的应用和发展。
整数规划问题的困难和挑战来源于三个方面:一是大部分整数规划问题都是NP-难的,故本质上不太可能存在和线性规划和凸规划一样有效的算法;二是对整数点集合(如多面体格点理论和全单模理论)和整数变量的函数在数学上缺乏有力的理论和工具;三是实际问题的规模往往超过现有算法的求解能力,尽管现有的一些整数规划软件可以求解任意线性、二次和非线性整数规划问题,但往往不能处理来源于实际问题的整数规划模型,例如运输和交通中的大规划0-1混合线性整数规划问题,金融优化中的离散约束问题等。整数规划未来发展方向和关键问题包括:1. 整数多面体凸包的刻画;2. 随机整数规划;3. 多层整数规划;4. 混合0-1二次整数规划;5. 协正规划;6. 半定整数规划。
1.7. 动态规划
当系统模型具备马尔科夫性,同时目标函数可分且嵌套单调时,基于贝尔曼提出的最优性原理,运用动态规划可将求解多阶段全局最优决策问题分解为一系列在各个时间段上的局部优化问题。相比其它解法,特别是在有扰动或在随机情况下,动态规划总是能有效地提供一个在当前信息集下的最优反馈控制策略。在过去的若干年里,动态规划取得了不少可喜的进展,特别是它被扩展到多目标动态规划;动态规划应用在本世纪前后的一个重大突破是其在海量数据分析中的应用,特别是人类基因组计划完成以后,它成为生物信息学的一个基本模型和工具。
然而,在克服被贝尔曼称之为“维数灾”的这一动态规划致命弱点的方面,至今尚未取得突破性的进展。所以寻求克服维数灾的有效算法对动态规划在高维问题中的应用具有它的紧迫性。另外,求解不可分优化问题得到的最优策略并不满足最优性原理,或不具备时间一致性。这牵涉到不可分优化问题模型本身的合理性。因此怎样找出一组可分优化问题来逼近一个给定的不可分优化问题也对动态规划发展具有它显然的重要性。
1.8. 向量优化
近几十年来向量优化(亦称多目标优化)理论研究有了迅猛发展,在各种解的存在性、稳定性以及最优性条件等方面获得了丰富的结果,并创造性地建立了向量优化问题解集的结构定理、连通性定理和稠密性定理并应用其到经济问题中。通过向量广义凸性的研究,很好地处理了一大类非线性向量优化问题;通过提出向量变分不等式模型,开拓了研究向量优化问题的新方向。由于向量优化中衡量向量“大小”的是不完全的偏序,致使大量的向量优化问题没有解,甚至在向量目标函数光滑并有下界的情况下没有数值优化意义下的近似解。由于任何优化问题算法每一步获得的迭代项都是该优化问题的一个近似解,因此研究向量优化问题近似解的存在性以及拉格朗日和卡罗胥-库恩-塔克等优化性条件仍然是具有基础性作用的主要问题也是求解算法的有力保障。分式向量优化问题是具有重要经济意义的数学模型,关于这类模型的求解问题,也是今后向量优化问题研究的重点。利用次微分,使用变分分析技术和方法研究非光滑向量优化问题,就变分分析和向量优化进行交叉研究仍将是未来很有生命力的方向。
1.9. 全局优化
全局优化是非线性规划的一个分支,主要研究求解非凸优化问题的全局最优或近似全局最优解。由于非凸优化问题可能存在多个不同的局部最优点,基于导数信息的卡罗胥-库恩-塔克最优性条件不再适用于刻画非凸问题的全局最优性,从而,经典的局部优化方法不能保证收敛到全局最优解。全局优化较系统的研究始于上世纪70年代。 图伊和霍斯特是早期全局优化研究的先驱者,他们在凹规划的系统研究成果使全局优化开始形成一个真正的学科。在90年代初全局优化作为非线性规划的一个分支开始受到广泛的关注,越来越多的研究者开始从事该领域的研究,特别是对一些具有特殊结构的非凸优化问题的研究取得了许多突破性的成果,如非凸二次规划,非凸多项式规划,机会约束问题的凸逼近,以及在实际应用中遇到的许多特殊形式的非凸优化问题的研究都有很多深刻的研究成果。一些基于分支-定界的全局优化通用软件的发展及其在优化建模系统中的嵌入应用使学术界和工业界可以方便地求解一定规模的非凸问题的全局解。
全局优化问题的困难在于非凸性使卡罗胥-库恩-塔克条件一般不足以保证全局最优性,从而我们无法利用局部优化算法寻找全局最优点。本质上,由于导数是局部性质,因而不能期望基于导数性质的传统优化算法有希望求到全局解,全局算法需要函数和问题的全局性质。目前的数学理论很难或无法刻画一般多元函数的全局性质,这是全局优化问题的本质困难所在。全局优化的未来发展方向和关键问题包括:1. 凸逼近和凸松弛方法;2. 非凸二次规划;3. 基于模拟仿真技术的全局优化算法;4. 特殊结构的全局优化问题。
除了上面所介绍的九个分支外,数学规划在近些年来兴起了若干新的分支。例如,近十年来国际上对鲁棒优化,微分方程所控制的优化,多项式优化,稀疏优化的研究相当重视,这些新方向的研究十分活跃。在即将举行的第21届国际数学规划大会上这些新兴的分支都安排了专题报告。我国数学规划工作者,特别是青年科技工作者要充分重视这些新的方向,力争在国际上刚刚起步的阶段参与研究,这样有可能很快取得国际制高点。
2. 组合优化
组合优化是20世纪60年代逐渐发展起来的一个交叉学科分支,它的研究对象是有限集合上的极值问题。一个组合优化问题由三部分构成:已知条件的输入,可行解的描述,目标函数的定义。经典的组合优化问题包括网络流、旅行商、排序、装箱、着色、覆盖、最短网络等等。组合优化的一个理论基础是计算复杂性理论,据此组合优化的可以分为两类:P-问题类和NP−难问题类;属于前者的问题有多项式时间算法,属于后者的问题一般认为不存在多项式时间算法,通常采用穷举法、启发式算法和近似算法等方法求解。组合优化与图论、组合学、数理逻辑等有密切关系,在计算机科学、信息科学、管理科学和生命科学等学科有广泛的应用。
2.1 图论及算法
1736年欧拉解决了哥尼斯堡的七桥问题,这被公认为图论的第一个结果。此后的二百多年里,图论并不被视为是数学的一个分支,图论的问题通常被看作一类智力游戏。然而,自上个世纪三十年代始,图论通过其广泛的应用以及与数学其他分支的紧密联系日显其重要性。尤其是,图论作为计算机科学的基础之一,在运筹学中扮演着不可或缺的角色,很多非常难解的组合优化问题都属于NP-完全的图论问题。
在图论近几十年的研究中,学者们在取得一系列重要成果的同时,提出了包括整数流、子图覆盖和经典拉姆齐函数的估值在内的许多猜想或未解的难题。未来受人关注的一些课题包括 [3]:(1)图论中大多数结果都可以推广到超图中(通常推广方式不至一种),相应的超图问题有很多没有解决。对超图的相应性质和问题的研究不仅仅可以发现新的有意义的研究课题,而且还有助于解决图论中的一些已有问题。(2)对随机图的一些特殊性质的刻画,特别是随机图在生成的过程中,其结构有时会发生突变,这种变化常常与日常的某种物理现象相关,对这种相变现象的研究是非常具有挑战性的课题。(3)对超大图或者无限网络的研究将是图论的一个新热点方向。它有广泛的应用背景,其中包括实实在在的计算机通讯网络,无形而无处不在的万维网,基于因特网的社交网络,人脑的神经网络等等。对这些超大图的性质的研究,需要新的数学工具;引入连续化方法,让这些超大图趋于“无穷”,然后研究其“极限图”的性质,是一个探索方向。这一方向同目前受到物理学界、控制论界重视的“复杂网络”研究相重合。
2.2 近似算法设计与分析
近似算法是求解组合优化问题的一类多项式时间算法,它们尽管不能确保对问题的每一个实例都可以求得最优解,但是可以保证求得的解的目标值与最优解的目标值相差不多。自上个世纪六十年代末格雷厄姆在研究排序问题时提出第一个近似算法以后,特别是七十年代初库克首次证明了存在NP-完全问题以来,为各种各样的组合优化问题设计近似算法就一直是组合优化领域的一个重要研究方向。它主要包括三个方面,设计近似比越来越小的近似算法,设计运行时间越来越短的近似算法,证明近似比的下界或者不可近似性。已有的大量研究主要都集中在第一个方面,人们先后提出了对偶、半定规划、随机算法、平面划分和次模函数等技巧。第二方面的工作主要是针对存在多项式时间近似方案的NP-难问题,而第三方面的工作主要是利用上个世纪九十年代阿罗拉等人提出的概率可验证明系统。这一方向中有很多问题有待解决。
2.3 组合多面体
给定一个线性系统,判定其是否定义了一个整数多面体、是否为全对偶整数系统、是否为盒式对偶整数系统,这三个判定问题是整数规划的核心问题,也构成了组合多面体理论的基本内容;这是因为当一个整数规划实例是由一个整数多面体所定义的,那么它可以在多项式时间内求解(一般的整数规划是NP-难解的)。包括罗瓦兹、施瓦维尔和埃德蒙兹在内的许多著名数学家都研究过组合多面体的结构刻画、计算复杂性等相关问题。另外,由于很多组合优化问题都可以非常容易地表示为整数规划问题,因而这些问题也是组合优化的重要研究课题。比如,组合优化中的一大类问题都可以用超图中的装填问题和覆盖问题来描述;装填问题是求含有边数最多的装填,而覆盖问题是求一个顶点覆盖其中所有顶点的权值之和最小。已经知道装填问题和覆盖问题都是NP-难解的,因此除非P=NP,它们都不存在多项式时间的算法。这两个组合优化问题都可以通过组合多面体的理论和方法研究,特别是:有向图和无向图上的圈装填和覆盖对偶关系和有向图上的装填和反馈集覆盖对偶关系。
2.4 生物分子网络
生物分子网络是系统生物学的基本出发点和主要研究对象,因为从系统的观点看,生命系统是通过基因之间、蛋白之间、代谢物之间以及基因、蛋白质、代谢物、环境与功能和表象之间的相互作用来运行的,正是这些相互作用确定了细胞、组织、器官和生物个体的动态行为。所以系统生物学的根本挑战在于建立完整的、细致的生物分子间联系的描述,并籍此在分子水平及系统的观点来探索生命机理,解释复杂生命现象。最优化理论包括连续优化、组合优化和网络优化等运筹学方法和理论在生物分子网络的研究中都起到了重要作用。典型的研究内容和问题包括,基因调控网络和蛋白质相互作用网络的数学建模,从生物进化角度出发的生物分子网络进化模型和算法,从高通量生物实验数据出发的网络重构算法,着眼于功能预测与标注的基因蛋白功能联系网络的构建和分析,以及生物分子网络的功能模块探测、网络比对等系统生物学和生物信息学算法。这些研究可以用于蛋白质功能预测和注释,以及进一步地为研究某些与特殊疾病相关的蛋白质功能注释提供有效的工具。
3. 随机最优化
随机最优化问题是特指带有随机因素的最优化问题,需要利用概率统计、随机过程以及随机分析等工具。所谓的随机因素,包括环境的随机因素、控制变量不确定因素、准则值的不确定因素等等。例如,在考虑水库优化调度问题的时候,天然来水一般是三阶皮尔逊分布的随机变量。在考虑库存管理问题时,变动的需求常常考虑为外生的随机变量。这些都属于环境的不确定因素。在排队系统中服务速率确定后,真实的服务时间依然是随机变化的,这属于控制变量的不确定因素。使用药物最终能够达到的效果往往不是确定的,评判最优的值函数在很多问题中也具有不确定性等等。通常人们处理随机因素的方式有期望值方法,将随机的因素用它的期望值代替,将问题转化为确定性问题考虑。第二种方法是在概率意义下考虑优化问题。例如在置信区间范围内考虑优化问题,将问题转换为概率约束或者是机会约束的优化问题;又例如考虑极大化某些事件的概率问题,也称为相关机会约束问题。第二种方法相对于期望值方法的优点是考虑到各种风险的影响,缺点是使得问题的处理变得相对困难。
3.1 排队论
排队论模型被人们广泛用于半导体生产加工与设计、计算机通讯网络、交通运输等行业。随着科学技术的发展,描述上述类型的排队网络变得极为复杂,使得与传统的排队网络有很多本质的区别。 当今人们对复杂的随机排队网络关心的问题有三个:一是它的遍历性问题,即给定一个随机排队网络、若网络中每一服务台的服务强度严格小于1,那末描述系统的马氏过程是不是遍历?二是在便利条件下,当每一服务台服务强度趋向于1,描述系统的指标如队长、等待时间其扩散逼近是不是存在?三是在遍历的条件下如何找出最优的服务规则?第一个问题归结为针对排队系统、找出构造李雅普诺夫函数的一般有效方法,第二个问题的解决归结为具有可料性的动态补问题。
3.2 马氏决策的理论研究
随着人们对实际问题的深入理解,马氏决策理论的应用范畴越来越广泛。因此,提出的马氏决策理论问题越来越具有特殊性和广泛性。研究特殊结构的马氏决策理论越来越具有重要的意义。例如大规模对抗与合作系统的问题、金融监管的需求、一般监管理论的研究等等,都为马氏决策理论带来了新挑战。非标准准则的深入研究是应对这些需求的必要条件,如有超大状态空间问题的求解问题、带有纳什均衡的多阶段决策问题、带有适应性参数影响的非时齐问题等等。这些研究工作对于国民经济中的重大问题研究有着重要的帮助。
3.3 系统可靠性理论与复杂系统可靠性理论
现代化技术和设备的飞速发展和更新,使得人们面对的系统越来越复杂,而诱发了许多人们无法理解的现象,例如:利用原来的系统可靠性理论得到的可靠性与实际系统人们感觉到的完全不同。如何发展相关的数学分析工具以解释这些问题就显得非常重要。在人们已经做出的工作中,已经出现一些有意义研究,例如:功能相依性分析、功能冗余性研究、概率理论的深入研究等等。因此,如何将系统可靠性理论的结论和方法上升到解决复杂系统可靠性问题中是核心的难点。
3.4 软件可靠性理论
软件是随着计算机硬件诞生的同时产生的,其重要程度是不言而喻,现在已经成为人们生活中必不可缺的成分,特别是科技水平越高,就越离不开软件的支持。由于软件系统的高度复杂性(其复杂程度远远高于通常的复杂系统,事实上,软件系统往往不是一个有限的系统了)导致了人们通常在系统可靠性中使用的方法完全无效。人们有必要探索有效的相关理论,特别是数学工具,以有效的研究软件可靠性问题。事实上,将软件可靠性问题与软件测试过程结合是一种有效的方法。一方面,可以有效的指导软件的测试过程(目前,用于软件测试的费用已经占到整个软件开发费用的50%);一方面,可以正确的评估软件的可靠性。将测试过程与软件可靠性分析结合的过程中,人们发现必须发展诸如随机过程、排队理论、马氏决策理论以及相关的数学方法,以适用于分析软件的问题。
3.5 供应链的优化设计
随机环境下的复杂供应链系统的优化与设计问题是从管理科学中提出的数学问题。与传统的供应链模型相比,描述系统的随机性不再由简单的普阿松过程与独立同分布随机变量序列给出,而由相依的一些高斯过程来刻画。通常面临三个基本数学问题:一是如何来找出求解人们所关心的系统数量指标的一般方法?二是找出这些求解方法之后,基于这些解、如何找出最优策略?三是供应链协调时,如何找出最优的协调策略即平衡点。这些问题的解决需要借助随机分析、随机最优控制和博弈论,且根据模型的自身特点,发展一套新的数学方法和理论。
4. 其他方向
4.1 算法博弈论
现代博弈论起源于上个世纪初,以策梅洛、博雷尔和冯·诺依曼等人的工作为代表。二次世界大战为博弈论的应用提供了广泛的背景,加快了博弈论体系的形成。冯·诺伊曼和莫尔根施特恩在1944年合著的《博弈论与经济行为》完善了博弈论的数学理论,使之系统化和公理化。此外,纳什等人也对博弈论做出了重大贡献,奠定了非合作博弈的基础。博弈论的研究对象与社会、政治、军事、经济、科学、技术等很多领域都有密切关系和广泛应用,一直是运筹学及相关领域的重要研究热点。
近二十年以来,算法博弈论逐渐成为博弈论的一个热点方向。它将一个系统的形成和运行看作一个博弈过程,假设规划者从整体利益出发,优化设计系统以达到全局最优,但博弈的参与者却从自身利益出发,做出自私的行动选择以达到个体最优;这常常使得系统的实际性能低于规划者期望的全局最优。算法博弈论研究的主要问题包括:(1)如何描述和计算参与者的自私行为所导致的系统性能;(2)如何分析和刻画博弈中参与者的自私行为与系统整体性能之间的关系;(3)如何设计一个合理的机制使得其系统在实际运行中能够真正实现整体利益最大化。算法博弈论的特点是,它不仅仅关心均衡解和机制的存在性,还强调计算它们的复杂性,并设计有效的算法求出(或者近似)它们。
4.2 应急管理
应急管理主要是研究围绕非常规突发事件的一系列科学问题。它是本世纪以来人们十分关心的热点问题之一,得到国际上学术界和政府有关管理部门越来越多的关注。应急管理所涉及的突发公共事件包括,自然灾害、事故灾难、公共卫生事件和社会安全事件。它们具有突发性、紧迫性、弱经济性、信息不确定性和物资需求量大等特点。目前的研究大都局限在个案的研究上,缺乏以数学为基础的系统理论 [2]。事实上,这种理论的形成已经有了雏形,例如:随机混杂系统的理论研究工作渐渐成为描述应急过程一种有效工具。随着两种时间尺度差异的变大,微观与宏观之间的相互影响机制在这种变化中不断显现,而应急过程在不同环境下的差异性变化被有效地刻画,随着环境变化的决策方案的适时性和有效性可以充分体现。这正是应急管理所关心的核心内容,即包括了应急事件的发起,也包括了应急事件的发展,还包括了应急事件恢复的控制等等。另外,将预备阶段的预案和实施阶段的调整方案紧密结合在一起,使预案在实际应用时能根据所得的实时信息做出迅速调整,这种研究非常必要。针对应急管理的不同问题的数学模型需研究它们相应的求解算法,特别是大规模问题的快速求解算法的设计,也值得重视和深入研究。
4.3统计和优化
统计学是一门研究如何有效地收集数据和分析数据的学科。它以数据为对象,研究各种实验和现象中的数量关系,以概率论等为基础,发展了一套系统地处理数据的统计理论和方法。随着科技进步和社会经济的发展,我们面临的数据量正以指数量级的速度增长,产生了许多高维数据、缺失数据和复杂结构数据。对这些复杂数据,人们已经很难依赖直观对现象进行判断,高维复杂数据的有效分析遇到了前所未有的挑战,这些挑战为统计学的发展创造了难得的历史机遇。现在经常遇到一些复杂现象中产生的海量数据,我们对这些复杂现象缺乏理解,需要从这些数据出发来寻找和发现规律,这就要求开展“数据驱动”的研究。以概率论和随机分析为基础,以计算机为工具、引入最优化思想的统计方法将会成为一个发展方向。
四、运筹学中若干难题
爱因斯坦曾经说过:“提出一个问题往往比解决一个问题更为重要”。形成一个公认的科学难题的过程本身就是科学研究的一个结果,同时也是开启新的、未知大门的敲门砖。在许多科学家看来,科学难题是科学进步的阶梯。随着一个又一个科学难题的解决,科学技术不断登上新的台阶,人类文明上升到一个新的高度。上个世纪伊始,著名数学家希尔伯特在国际数学家大会上提出了23个数学难题。在过去的一百年里,这些问题激发了众多数学家的热情,引导了数学研究的方向,对现代数学的发展产生了难以估量的巨大影响。
在运筹学发展的六十多年里,几代运筹学工作者在运筹学的各个方向取得了许许多多的成果,应用数学的理论和方法奠定了运筹学的基础,也对数学的发展做出了贡献。著名数学科普作家卡斯蒂 [1] 在总结上个世纪意义重大的数学成果时,他从众多的数学定理中遴选出了五个,其中四个都与运筹学有非常紧密的关系,它们是:极小极大定理(博弈论),单纯形法(线性规划),停机定理(计算的理论),布劳威尔不动点定理(博弈论的基础工具)。
著名数学家波利亚曾经说过:“数学就是解决问题的艺术”。随着一个又一个运筹学难题的解决,新的难题不断地从新的土壤破土而出。其中一些不仅仅是运筹学的相关研究方向的重大问题,也是数学及相关学科的一些核心问题。在著名数学家斯米尔 [4] 给出的本世纪18个数学难题中,其中以下4个就与运筹学相关:(3)“P是否等于NP”,也被列为本世纪的七个数学难题之一;(4)单变量多项式整解的个数;(8)可描述价格调整的一般均衡理论的数学模型;(9)实系数线性规划是否多项式时间可解。
以下12个问题是运筹学相关方向具有一定代表性的未解难题 [7]:(1)凸多面体的d-步猜想;(2)有限多个二次函数最大值的极小化问题;(3)推广的Lax猜想;(4)DFP拟牛顿法的收敛性;(5)最小阻力凸体问题;(6)是否存在求解性线性规划的强多项式时间算法?(7)组合优化反问题的计算复杂性;(8)求解旅行商问题的更好的近似算法;(9)k-服务器猜想;(10)装箱问题是否存在绝对近似算法;(11)随机排队网络的遍历性;(12)PH-分布的最小表示。
显然,运筹学未解的难题远不止上述这些。特别是,这些问题在运筹学的各个分支之间的分布不平衡,个别方向甚至未能得到反映;它们对运筹学的理论及应用的意义和重要性各不相同,难易程度也有千差万别。有兴趣的读者可以在此基础上开展研究,也可以提出和研究其他有意义的问题。毕竟发现问题、提出问题、分析问题和解决问题的过程构成了运筹学的发展进程。
五、运筹学发展态势
社会进步的需要就是学科发展的泉源。从数学几千年来发展的历程来看,从埃及因土地测量而引发的关于初等几何图形的考虑、直至欧几里德的《几何原本》的完成,以及随之而来的亚历山大城的博物馆的衰落,可以视为农业时期的数学;而再从刻画连续变化状态而产生的微积分学的出现到19世纪中叶,经典数学趋于完善,可以看成是工业革命时期的数学 [6];上个世纪随着计算机的诞生及信息科技的飞速发展,逐渐形成以离散结构为对象的信息时代的数学。
本世纪随着生物科技的日新月异的发展,经济发展的全球化,可以预测在探索生命和社会发展规律的过程中将形成崭新的数学。而运筹学将在这一过程中,起到重要作用,并形成新的交叉领域与学科增长点。
5.1 运筹学与生命科学的交叉
这里所指的生命科学包括生物学、医学和药物学等。传统的生命科学和其他自然科学如物理学相比,更多地关注于定性的研究,而不是定量的研究。但是这种现象正在迅速改变。20世纪中期,随着蛋白质空间结构的解析和DNA双螺旋结构的发现,形成了以遗传信息载体核酸和生命功能执行者蛋白质为主要研究对象的分子生物学。而21世纪初人类基因组计划的完成,标志着生命科学研究进入了一个崭新的后基因组时代,其特征和标志包括:高通量生物技术的成熟应用、大型生物数据库的建立、从单个的组学(如基因组学、蛋白质组学等)到系统生物学的研究方法等。
运筹学已经逐步应用到生物信息学和系统生物学等诸多新兴的生命科学研究领域,发挥着重要的作用。目前在生命科学中得到广泛应用的运筹学分支有:图论与组合数学、动态规划、人工神经网络、线性规划、非线性规划、整数规划等。例如,基于动态规划的序列比对算法是目前最重要的生物信息学基本工具之一。线性规划、非线性规划和整数规划在蛋白质结构比对和结构预测中作为重要工具经常使用。另一方面,现代生命科学对运筹学理论和方法提出了新的需求和巨大的挑战。例如基因组学和蛋白质组学中的数学模型大多涉及求解总体极值和大规模变量的问题,促进了启发式算法和近似算法的研究。生命科学的迅猛发展和对运筹学理论和方法的巨大需求,吸引了大量的运筹学家加入了运筹学与生命科学交叉领域的研究。运筹学理论和方法在生命科学的研究中越来越普遍和重要,而运筹学本身也从中得到了发展的动力。
运筹学是一门“优化的科学(Science of Better)”,而生命的进化过程本身就是一个自然选择和遗传优化的过程,所以许多生命科学问题的数学模型都与优化有关。而且这些模型大多是NP-难的,所以近似算法和启发式算法的研究在这方面起到重要的作用。生命科学被称为二十一世纪的科学,从过去十年的发展可以预见,未来的三十年将是生命科学飞速发展的时期。在日新月异的现代生物实验和医学技术的帮助下,生物学家和医学工作者对生命和疾病的过程和机制的了解将越来越深刻,生命科学领域的数据和数学模型也会越来越多。运筹学工作者应该抓住这个难得的机会,使运筹学成为未来三十年中生命科学研究的主要工具之一。
与运筹学发展早期的工业生产、经济管理等领域类似,未来三十年生命科学领域与运筹学的联系将越来越紧密。运筹学不仅可以帮助生命科学研究人员建立从微观(基因、蛋白、细胞器、细胞)到宏观(组织、器官、物种)的数学模型,帮助生命科学研究人员更好、更合理地设计实验和改进技术,还可以通过模型优化来更好地探寻生命科学中的规律和机制,更好地为人类健康服务。
运筹学与生命科学的交叉研究将更加全面和深入。首先,除了已经在生命科学中得到广泛应用的分支(如线性规划、动态规划等)将继续得到重视,运筹学的其他分支将找到用武之地。例如随机优化模型可能用于研究细胞内部的调控策略和信号传导机制;博弈论可能帮助分子遗传进化研究找到新的突破。其次,运筹学与生命科学的交叉研究将扩展到更多的生命科学分支领域,例如生命起源的研究、个性化医疗中的最优医疗策略等。
最重要的是,与生命科学的交叉研究可能促进新的运筹学理论和方法的出现,甚至产生新的运筹学分支。可能对运筹学发展产生促进作用的因素有很多,例如生命科学的海量数据对计算复杂性的挑战、现有运筹学模型在描述复杂生命系统时的不足、生命系统和其他物理系统的显著差异、生命过程和生命现象的不确定性和随机性等。
此外,系统生物学尚处在起步阶段。它要成为一门独立的分支学问,在未来的30年内,需要建立自己的“公理系统”、“基本理论”、以及实验和算法体系,运筹学将在这一过程中起到其独特的作用。
5.2 运筹学与网络科学的交叉研究
网络科学是本世纪刚刚兴起的一个新的交叉学科。它以复杂网络为主要研究对象,通过对复杂网络特性的提取和刻画,探究其所反应的复杂系统的普遍规律。网络科学是将运筹学的思想和方法应用于生命科学(特别是系统生物学)的主要桥梁之一。网络科学在过去的十余年间飞速发展,在计算机、社会学、生物学等领域都产生了重大影响,已经成为研究复杂系统、解决复杂性问题的重要理论和方法。例如大量基于复杂网络社团结构(模块)的分析方法已经成为系统生物学中研究生物功能的基本工具。运筹学的各个分支,特别是最优化方法和图论已经在网络科学中发挥了重要作用。
今后几十年内网络科学预期将有重大的突破,并成为应用科学的主流性分支。运筹学同网络理论有着天然的联系:运筹学有可能给出网络的表达方式和描述理论,以及分析方法。未来三十年网络科学和运筹学的交叉研究可能在以下两个方面有所突破。
(1)网络生成模型。随着各种实际网络数据的大量产生,人们对实际网络基本特征的认识必将深化,对普适性的网络和个性化的网络建立合适的网络模型的时机将更为成熟。例如生命科学中,各种生物网络迅速积累和扩张。在过去十余年间伴随着网络科学的发展,生物网络相关研究已经成为系统生物学研究最基本的部分。但是网络数据的复杂性和实际网络的不确定性都使得刻画网络的产生机制成为重要且极具挑战性的问题。可以预见的是,随着网络数据的积累和发展,人们终将认识其产生机制。运筹学的最优化理论、图论与随机运筹模型和方法等,将会在模型的建立与分析起到无可替代的作用。
(2)网络演化特征的刻画。现实的网络是一个不断更新、变化着的复杂系统。揭示和刻画网络演化的特征对理解网络的功能和结构具有重要的意义。随着生物技术与计算机的高速发展,大规模时序数据的积累将成为可能,如何有效的分析和利用这些数据,运筹学、统计学等应用数学分支将会为彻底的认识、解决这一问题起到无比重要的作用。
此外,网络科学目前尚处于实证研究为主的阶段。它要真正成为一门独立的科学分支,必须建立其基础理论、运算理论,以及从目前的实证地从实际世界中提炼网络模型,发展到应用网络理论去建立自然界的或技术性的系统,使其具有特定的性质。在这一过程中,运筹学可以成为一个主要的工具。在这一方面,运筹学的发展历史可以借鉴。在线性规划的算法背后,是强有力的对偶理论;在非线性规划算法的后面,是收敛性理论和凸分析理论;在图论和组合方面,是计算复杂性理论。由此构成运筹学这门学科。而网络理论势必在以后的30年中完成这一过程。
除了上述的两个交叉领域,由于任何存在决策的问题都是优化问题,任何有参数需要选取的问题都是运筹问题,所以运筹学的应用到处可见。运筹学的广泛应用使得它和其他科学领域的交叉将日益加强。这些交叉不仅为运筹学的应用提供了很好的舞台,同时也为运筹学的新兴分支的产生和发展提供了土壤。运筹学与信息领域的交叉是一个很成功的例子。信息领域中的许多问题,如数据挖掘,模式识别,图像处理,分类,信息安全,互联网数据分析,无线传感定位问题,多通道通讯干扰最小问题等等都归结于运筹问题。这些问题极大地推动了运筹学的发展。
当运筹学经过六十多年的发展,其理论越来越艰深,应用愈来愈广泛,目前已经没有任何一个人可以是运筹学所有方向的专家。因而对未来运筹学的任何一个具有挑战性的课题的研究,尤其是对出现在新的学科交叉领域的重大问题的探索,就更需要一组具有运筹学的不同专长的人才组成的类似于运筹学发展初期时的研究团队,其中还应该包含概率论、统计学、经济学、工商管理、计算机科学、行为科学等学科背景的人才,才能做出重要的科学发现和贡献。
六、结束语
本文是对运筹学的发展历程、现状和态势的一个概要性的介绍。它不太可能对运筹学发展的各个时期、每一个相关研究方向都有所涉及。我们只是希望能引起从事运筹学及相关领域研究、应用和教学的科研人员和教师对运筹学的发展有进一步的思考,为运筹学的发展做出自己的贡献;让对运筹学及相关学科感兴趣的师生对这个学科有比较全面的了解,引导他们学习、应用和研究运筹学的问题。
最后,衷心感谢国内运筹学界的十几位学者在编写本文的过程中,给予我们的大力支持和帮助。
参考文献
[1] John L. Casti, Five Golden Rules: Great Theories of 20th Century Mathematics and Why They Matter, John Wiley & Sons, Inc, 1996. (中译本:《二十世纪数学的五大指导理论:它们为什么至关重要》,叶其孝、刘宝光译,上海教育出版社,2000。)
[2] 韩继业、刘德刚、朱建明,运筹学在应急物流中的一些应用,《重庆师范大学学报(自然科学版)》,28 (5) (2011),1-6。
[3] L. Lovasz, Graph theory over 45 years, An Invitation to Mathematics – From Competitions to Research, D. Schleicher and M. Lackmann (eds), Springer, 2011,85 - 95.
[4] S. Smale, Mathematical problems for the next century, The Mathematical Intelligencer, 20 (2) (1998), 7-15.
[5] 王元、文兰、陈木法(编辑),《数学大辞典》,科学出版社,2010年。
[6] 越民义,关于数学发展之我见,《中国数学会通讯》,2011年,总第119期,16-25。
[7] 10000个科学难题数学编委会,《10000个科学难题(数学卷)》,科学出版社,2009。
[8] 章祥荪、刘德刚、章璟、吴凌云、王勇(编辑),50周年纪念特刊中文译本,《运筹与管理》(增刊),2004年。
作者简介
胡晓东 中国科学院数学与系统科学研究院研究员,博士生导师。现任中国运筹学会秘书长。主要研究领域为组合优化和博弈算法。已出版学术专著2部、编写教材2册、发表学术论文一百余篇。电子邮件:xdhu@amss.ac.cn
袁亚湘 中国科学院院士,中国科学院数学与系统科学研究院研究员,博士生导师。现任中国运筹学会理事长。1996年获第三届“中国青年科学家奖”;1998年获“中国十大杰出青年”称号;2005年获中国科协“全国优秀科技工作者”称号;2006年获国家自然科学二等奖;2011年当选美国工业与应用数学学会会士。主要研究领域为最优化计算方法。已出版学术专著3部、发表学术论文一百二十余篇。电子邮件:yyx@lsec.cc.ac.cn
章祥荪 中国科学院数学与系统科学研究院研究员,博士生导师。现为中国运筹学会名誉理事长,国际运筹学会联合会副主席。1988年获国家自然科学奖三等奖;1996年获国际运筹学会联合会“运筹学进展奖”一等奖;1999年获全国五一劳动奖章,2010年获中国科协“全国优秀科技工作者”称号。主要研究领域为最优化理论与应用和生物信息学等。已出版学术专著3部、发表学术论文一百四十余篇。电子邮件:zxs@amt.ac.cn