运筹学与最优化技术_吴沧浦.pdfVIP

运筹学与最优化技术_吴沧浦

专家文选

运筹学与最优化技术

吴沦浦

一、运筹学与最优化技术的发展之间的联系

作为具有相对独立性质的学科与技术，运筹学与最优化技术，其发展过程具有密切联

系，并且彼此之间在其发展中起着相辅相成的作用。在运筹学发展的初期，经典运筹

学强

调定量研究。这里的定量研究主要包括两个方面:其一是对于作为研究对象的运筹系

统

作出定量的描述，该描述可以用数学模型或仿真模型表达;其二是给出能够定量地衡

量运

筹系统的运作的优劣程度的效力度量，该度量必须能够明确地显示出它自身与系统的

决

策(控制)变量之间的依赖关系。经典运筹学之所以强调定量研究，其目的在于使决策

与

对于其所能选择或控制下的决策变量作出最优的选择。这里的最优是在下述的意义下

理

解的，即该选择能够使上述的效力度量达到最大值或最小值。由于在经典运筹学中，

效力

度量是以实数表示的，而且它能定量地反映运筹系统的运作的优劣程度，因而上述意

义下

的最优性是有意义的。由此不难理解，最优化技术成为经典运筹学中的主要工具，后

者成

为前者发展的主要推动力;反过来，最优化技术的发展又在运筹学经历了从经典运筹

学到

现代运筹学的进化中起了重大的作用。

在运筹学的奠基性专著—莫尔斯与金博尔合著的《运筹学方法》中，专门辟出一章

论述效力度量的使用。人们由此可以看到最优化技术在经典运筹学中所占有的重要位

置。另一方面，从国际运筹学会联合会所举办的最近两届(1996年于加拿大温哥华、

1999

年于中国北京)运筹学国际会议上发表的论文，以及新近出版的有关专著，例如，由

美国普

渡大学教授拉丁的《运筹学的最优化》及印地安那大学教授温斯顿的((运筹学:应用

与算

法》中，人们可以明显地看到，尽管时过半个世纪，最优化技术在现代运筹学中仍然

起着举

足轻重的重要作用。

二、最优化技术的发展

在文学界和艺术界，存在一种流传颇广的看法，即在文学和艺术中，存在一些“永恒”

的主题，例如，善与恶之间的斗争、真理与谬误之间的斗争、人与人之间的博爱(友

情、爱情

等)。从类似的角度出发，或许可以说，最优化技术是科学与技术中的一个“永恒”

的主题。

118钱学森科学贡献暨学术思想研讨会论文集

因为科学与技术无非是人类认识世界和改造世界的产物，而人类在认识世界和改造世

界

的行动过程中，在一定的主观和客观的条件下，自然而然地会要求其行为能够达到最

优的

效果。

事实上，最优化的思想的渊源可以追溯到人类的早期文明。早在公元前一个世纪左

右之时，古埃及的科学家就曾断言光在两点之间以最短途径传播。另一富有诗意的例

子

是由古罗马诗人威吉尔所给出的关于迩太基皇后狄多索取领地的传奇故事，她在北非

洲

面临大海处索取一块领地，其面积一张牛皮即可覆盖。然后她将一张牛皮做成一根绳

子，

以这根绳子面对大海以半圆弧划出一块地域作为领地。在给定周长的条件下，半圆弧

划

出的地域的面积达到最大。早在公元前两个世纪左右，阿基米德就曾对此事实作出猜

测，

但是直到两千多年后发明了变分法，此一事实才得到严格的证明。

上述两个例子从一个侧面表明，作为一门科学与技术，最优化理论与最优化技术最初

是在物理学和几何学的研究中得到发展的，随着欧拉一拉格朗日最小作用原理，哈密

尔顿

最小势能原理以及吉布斯最小自由能原理的发现，最优化理论和最优化技术在自然科

学

中的应用于18,19世纪间获得了辉煌的成就，相形之下，它们在包含运筹学的系统科

学方

面的应用的发展，却要晚得多。这一情况缘于具有实际背景的运筹学的最优化问题远

比

上述自然科学中的最优化问题复杂得多。线性规划与单纯形方法的创立者丹齐克在回

忆

他于开发单纯形方法之初在美国空军后勤部门所遇到的运筹问题的复杂性质，他在此

提

到的运筹问题乃一人事安排问题，即假设有70位工作人员要安排到70种不同的工作

岗位

上去，要求在某种线性的效力度量函数下使工作安排方案达到最优。在此问题中，可

供选

择的工作安排方案为70!如果以穷举法搜寻最优方案，即使使用当时计算速度最高的

计

算