运筹学发展概况 (一)

60 多年以来,运筹学在研究与解决复杂的实际问题中不断地发展和创新,各种各样的新模型、新理论和新算法不断涌现,有线性的和非线性的,连续的和离散的、确定性的和不确定性的。至今它已成为一个庞大的、包含多个分支的学科,其中一些已经发展得比较成熟,另外一些还有待完善,还有一些才刚刚形成。

数学规划

数学规划是在决策变量满足一定约束下求一个或多个函数的极小值或者极大值。它以大量实践中抽象出来的典型最优化模型为研究对象,利用数学工具研究这些模型的数学性质,构造与实现求解方法,以及将算法应用于实际问题。
自从1939 年康托罗维奇提出线性规划模型、1947 年丹齐格提出求解线性规划问题的单纯形法、卡罗胥和库恩与塔克先后分别独立地给出一般非线性规划问题的最优性条件以来,数学规划得到了快速发展,形成了多个分支。

线性规划

自1939 年苏联数学家康托罗维奇提出线性规划问题和1947 年美国数学家丹齐格求解线性规划问题的通用方法──单纯形法以来,线性规划可以说是研究得最为透彻的一个研究方向。单纯形法统治线性规划领域达40 年之久,而且至今仍是最好的应用最广泛的算法之一。虽然它在最坏情况具有指数复杂性,但在平均意义下已经证明是一个多项式算法。目前,关于单纯形算法的研究主要在于如何选取主元。

另一大类算法是内点法,它起源于1979 年苏联数学家卡奇扬提出的多项式椭球算法,而因1984 年美籍印度裔数学家卡玛卡提出的多项式时间算法而迅速成为国际热点,各式各样的算法大量涌现:诸如仿射变换法、势函数方法、对数罚函数法、路径跟踪法、原始对偶法、不可行内点法等等。

目前线性规划的内点法也趋于成熟,这方面的研究者们目前大都致力于以线性规划作为特例的锥规划,以及如何利用线性规划松弛求解整数规划等方面的研究。然而,就线性规划而言,是否存在强多项式算法仍然是一个重要且困难的理论问题。

非线性规划

等式约束规划问题的最优性条件可追溯到拉格朗日,一般非线性规划问题的最优性条件则归功于卡罗胥和库恩与塔克,是他们奠定了非线性规划的理论基础。然而,目前还有不少人试图在没有强互补的条件下进行理论分析和算法研究。对偶理论是非线性规划理论研究的另一个重点。在计算方法方面,早期的方法以最速下降法和牛顿法为主。1959 年拟牛顿法的引入和1964 年非线性共轭梯度法的出现,吸引了许多研究者研究非线性规划。目前,序列二次规划算法是一类被用于广泛求解一般非线性规划的有效算法,同时也还有许多研究者在为改善这类算法努力,其中包括序列线性规划算法以及内点算法等。非线性规划算法通常使用线搜索策略选取步长,或通过求解信赖域子问题而得到新的迭代点。这两个方面的研究非常基本,但仍有改善的空间。2001年弗莱彻和勒斐通过将非线性规划问题视为双目标问题而提出的滤子方法和2002 年鲍威尔提出的基于二次插值的直接法是近些年来两个重要的算法进展。对于约束规划问题,如何推广鲍威尔的直接法;对于大规模问题,如何设计子空间算法;以及如何有效求解一般非线性规划的全局最优,和一些来自于图像处理等领域的特殊的非光滑问题是目前非线性规划比较重要的研究问题。

总之,尽管在表面上看非线性规划已经有许许多多的研究,但由于非线性的存在,好的研究结果还将会不断出现,并且随着问题的不同而产生更加具有针对性的特殊算法。

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: