北邮最优化课件0最优化理论与算法引言-课件（PPT-精）.ppt

最优化理论 * * 应力定义为“单位面积上所承受的附加内力”。公式记为σij=lim(ΔFj/ΔAi) (ΔAi??)其中，σ表示应力；ΔFj 表示在j 方向的施力；ΔAi 表示在i 方向的受力面积。 *TP SHUAI TP SHUAI * 最优化理论与算法 帅天平 北京邮电大学数学系 TP SHUAI * 提纲 1. 线性规划 对偶定理 2. 非线性规划 K-K-T 定理 3. 组合最优化 算法设计技巧 使用教材： 最优化理论与算法 陈宝林 参考书 ： 数学规划 黄红选， 韩继业 清华大学出版社 TP SHUAI * 其他参考书目 Nonlinear Programming - Theory and Algorithms Mokhtar S. Bazaraa, C. M. Shetty John Wiley Sons, Inc. 1979 (2nd Edit, 1993，3nd Edit，2006) Linear and Nonlinear Programming David G. Luenberger Addison-Wesley Publishing Company, 2nd Edition, 1984/2003.. Convex Analysis R. T. Rockafellar Princeton Landmarks in Mathematics and Physics, 1996. Optimization and Nonsmooth Analysis Frank H. Clarke SIAM, 1990. TP SHUAI * Linear Programming and Network Flows M. S. Bazaraa, J. J. Jarvis, John Wiley Sons, Inc., 1977. 运筹学基础手册 徐光辉、刘彦佩、程侃 科学出版社，1999 组合最优化算法和复杂性 Combinatorial Optimization 蔡茂诚、刘振宏 Algorithms and Complexity 清华大学出版社，1988 Printice-Hall Inc.,1982/1998 其他参考书目 TP SHUAI * 1,绪论----学科概述 最优化是从所有可能的方案中选择最合理 的一种方案,以达到最佳目标 的科学. 达到最佳目标的方案是最优方案,寻找最优 方案的方法----最优化方法(算法) 这种方法的数学理论即为最优化理论. 是运筹学的方法论之一.是其重要组成部分. 运筹学的“三个代表” 模型 理论 算法 最优化首先是一种理念, 其次才是一种方法. TP SHUAI * 绪论---运筹学（Operations Research - OR） 运筹学方法 随机过程方法 统计学方法 最优化/数学规划方法 连续优化：线性规划、非线性规划、非光滑优化、全局优化、变分法、二次规划、分式规划等 离散优化：组合优化、网络优化、整数规划等 几何规划 动态规划 不确定规划：随机规划、模糊规划等 多目标规划 对策论等 统计决策理论 马氏过程 排队论 更新理论 仿真方法 可靠性理论等 回归分析 群分析 模式识别 实验设计 因子分析等 TP SHUAI * 优化树 TP SHUAI * 最优化的发展历程 费马:1638;牛顿,1670 欧拉,1755 Min f(x1 x2 ··· xn ) ? f(x)=0 TP SHUAI * 欧拉，拉格朗日：无穷维问题，变分学 柯西：最早应用最速下降法 拉格朗日，1797 Min f(x1 x2 ··· xn) s.t. gk (x1 x2 ··· xn )=0, k=1,2,…,m TP SHUAI * 1930年代，康托诺维奇：线性规划 1940年代，Dantzig：单纯形方法， 冯 诺依曼：对策论 1950年代，Bellman：动态规划，最优性原理； KKT条件； 1960年代：Zoutendijk,Rosen,Carroll,etc.非线性规划算法，Duffin，Zener等几何规划，Gomory，整数规划,Dantzig等随机规划 6-70年代：Cook等复杂性理论，组合优化迅速发展 电子计算机----------?最优化 TP SHUAI * 最优化应用举例 具有广泛的实用性 运输问题，车辆调度，员工安排，空运控制等 工程设计，结构设计等 资源分配，生产计划等 通信：光网络、无线网络，ad hoc 等. 制造业：钢铁生产，车间调度等