应用数学系列讲座--最优化理论与方法.doc

应用数学系列讲座--- 最优化理论与方法肖伟 Part 1 最优化发展的历史背景最优化亦称数学规划,她追求一种尽善尽美之道,此乃人类贪婪之本性、追求极致之欲念。可以说,最优化首先是这种理念,然后才是一种方法。她是人类追求完美的一种最佳决策理念与方法。 1 .问题在人类的生活、科学研究、工程、经济、工业、军事等领域都会遇到许多最优化问题: ( 1 )运输问题。生产厂家要将自己的产品运输到用户,如何运输既能满足用户需求,又能花费最少? ( 2 )金融投资问题。如何设计比较好的证券组合或投资项目组合,以便在可接受的风险限度内获得最大的投资回报? ( 3 )产业结构调整、人员优化组合、多种商品的生产计划与调度等资源分配问题。如何分配有效的资源以便在特定的空间与时间内谋求最大的经济效益? ( 4 )工程设计问题。在工程设计中如何选择适当的参数使得工程方案既满足实际需要,又能够降低工程造价? ( 5 )曲面选择问题。如何设计汽车、飞机、宇宙飞船的最佳外形,既保证其运动的稳定性,又减少运动阻力,甚至满足隐身要求? ( 6 )飞行器的最优轨迹问题。导弹防御系统的开发与部署的有效性实际上就是能否在敌方导弹到达己方某一重要区域之前,对飞行目标的轨迹进行准确跟踪和预测,并且引导***将其摧毁? ( 7)过程控制问题。如何控制一个化学过程或者机械装置,既优化其性能, 又满足鲁棒性要求? 2 .背景最优化作为一门学科,孕育于 20世纪 30年代,诞生于 20世纪 40年代第二次世界大战弥漫的硝烟中,以线性规划模型(美国空军军力规划问题、运输问题、资源分配问题等)和单纯行算法的出现为标志。因此,最优化的历史,早期也就是线性规划的历史。作为最优化理念与方法,无论国内,还是国外,都可以追溯到很久以前。 1637 年, Fermat 发表了“求极大和极小的方法”,文中包含了 Fermat 定理结论。 1684 年, Newton 和 Leibniz 发明的微积分为求解一大类单变量极值问题提供了通用工具。当年 Leibniz 发表的第一篇微分学论文被定名为“一种求极大与极小值和求切线的新方法”。后来, Euler , Poincare , Hilbert 将 Fermat 定理推广到多变量、无穷个变量、特定条件的极值问题。 1826 年, Fourier 的工作涉及到后来发展线性规划的核心理论,线性不等式组的研究。 1847 年, Cauchy 研究了函数值沿着什么方向下降最快问题,这就是现在的无约束最优化的最速下降法。 1939 年,前苏联, Kantorovich 出版了著作《生产组织与计划中的数学方法》, 建立了线性规划模型,用来解决下料问题和运输问题。标志线性规划的诞生。遗憾地是他的努力在当时的俄罗斯并没有重视(直到 Dantzig )。 1947 年以前, Koopmans 给出了古典经济学理论的线性规划分析结构,并进行了与经济学有关的研究。 1947 年, Dantzig 正式提出了线性规划数学模型,并发展了有效解决线性规划的单纯行方法,并沿用至今。当时他是联邦空军审计部地一名数学顾问,开发了一个数学工具,用来制定军队的训练、部署、后勤保障的方案。由于空军的计划问题可以用一个不等式组来描述,他就将论文题目定为“线性结构的规划”( programming ina linear structure )。 1948 年夏天,美国的 Koopmans 和 Dantzig 参观兰德公司期间提出了线性规划这一名称,直到今天。 1949 年, Koopmans 在美国芝加哥组织了数学规划第一次会议,主编了《生产与分配的活动分析》( Activity analysis of production and allocation ) ,这对数学规划的发展产生过重大影响。说明: 1975 年 10月 14 日,瑞典皇家科学院将 Nobel 经济学奖颁给了 和 。原因是他们创造了线性规划方法,并成功地应用于经济学领域,为经济学的发展做出了卓越贡献。其实,我们知道 是线性规划之父,应该获得 Nobel 奖,而不是 Kantorovich 和 Koopmans 。可惜他的单纯行方法太数学化,无法获得 Nobel 奖。 1972 年, Klee 和 Minty 证明,单纯行算法不是求解线性规划问题的优良算法,于是人们自然问,线性规划是否存在优良算法? 1979 年, Khachiyan 肯定地回答了上面的问题, 提出了求解线性规划的椭球法,她避免了单纯行法的最坏情形下的指数时间算法。 1984 年,美国 AT&T 贝尔实验室的 Karmarkar 提出了求解线性规划的多项式时间内点法,她避免了 Kh