《最优化理论与算法完整版课件》由会员分享，可在线阅读，更多相关《最优化理论与算法完整版课件（902页珍藏版）》请在金锄头文库上搜索。
1、TP SHUAI,1,最优化理论与算法,TP SHUAI,2,提纲,1. 线性规划 对偶定理 2. 非线性规划 K-K-T 定理 3. 组合最优化 算法设计技巧,使用教材： 最优化理论与算法 陈宝林 参考书 ： 数学规划 黄红选， 韩继业 清华大学出版社,TP SHUAI,3,其他参考书目,Nonlinear Programming - Theory and Algorithms Mokhtar S. Bazaraa, C. M. Shetty John Wiley & Sons, Inc. 1979 (2nd Edit, 1993，3nd Edit，2006),Linear and Nonl
2、inear Programming David G. Luenberger Addison-Wesley Publishing Company, 2nd Edition, 1984/2003,TP SHUAI,4,Linear Programming and Network Flows M. S. Bazaraa, J. J. Jarvis, John Wiley & Sons, Inc., 1977.,运筹学基础手册 徐光辉、刘彦佩、程侃 科学出版社，1999,组合最优化算法和复杂性 Combinatorial Optimization 蔡茂诚、刘振宏 Algorithms and Comp
3、lexity 清华大学出版社，1988 Printice-Hall Inc.,1982/1998,其他参考书目,TP SHUAI,5,1,绪论-学科概述,最优化是从所有可能的方案中选择最合理的一种方案,以达到最佳目标 的科学. 达到最佳目标的方案是最优方案,寻找最优方案的方法-最优化方法(算法) 这种方法的数学理论即为最优化理论. 是运筹学的方法论之一.是其重要组成部分.,运筹学的“三个代表” 模型 理论 算法,最优化首先是一种理念, 其次才是一种方法.,TP SHUAI,6,绪论-运筹学（Operations Research - OR）,运筹学方法,TP SHUAI,7,优化树,TP SH
4、UAI,8,最优化的发展历程,费马:1638;牛顿,1670,欧拉,1755,Min f(x1 x2 xn ) f(x)=0,TP SHUAI,9,欧拉，拉格朗日：无穷维问题，变分学 柯西：最早应用最速下降法,拉格朗日，1797,Min f(x1 x2 xn)s.t. gk (x1 x2 xn )=0, k=1,2,m,TP SHUAI,10,1930年代，康托诺维奇：线性规划 1940年代，Dantzig：单纯形方法，冯 诺依曼：对策论 1950年代，Bellman：动态规划，最优性原理；KKT条件； 1960年代：Zoutendijk,Rosen,Carroll,etc.非线性规划算法，D
5、uffin，Zener等几何规划，Gomory，整数规划,Dantzig等随机规划6-70年代：Cook等复杂性理论，组合优化迅速发展,电子计算机-最优化,TP SHUAI,11,最优化应用举例,具有广泛的实用性 运输问题，车辆调度，员工安排，空运控制等 工程设计，结构设计等 资源分配，生产计划等 通信：光网络、无线网络，ad hoc 等. 制造业：钢铁生产，车间调度等 医药生产，化工处理等 电子工程，集成电路VLSI etc. 排版（TEX,Latex,etc.）,TP SHUAI,12,1. 食谱问题,我每天要求一定量的两种维生素，Vc和Vb。 假设这些维生素可以分别从牛奶和鸡蛋中得到。,
6、需要确定每天喝奶和吃蛋的量， 目标以便以最低可能的花费购买这些食物， 而满足最低限度的维生素需求量。,TP SHUAI,13,1. 食谱问题（续）,令x表示要买的奶的量，y为要买的蛋的量。食谱问题可以写 成如下的数学形式：,运筹学工作者参与建立关于何时出现最小费用 （或者最大利润）的排序，或者计划，早期被标示为programs。 求最优安排或计划的问题，称作programming问题。,Min 3x +2.5ys.t. 2x + 4y 403x + 2y 50x, y 0.,极小化目标函数可行区域（单纯形） 可行解,TP SHUAI,14,2 运输问题,设某种物资有m个产地A1,A2,Am,各
7、产地的产量是a1,a2,am;有 n个销地B1,B2,Bn.各销地的销量是b1,b2,bn.假定从产地Ai(i=1,2,m)到销地Bj(j=1,2,n)运输单位物品的运价是cij问怎样调运这些物品才能使总运费最小？,如果运输问题的总产量等于总销量，即有,则称该运输问题为产销平衡问题；反之，称产销不平衡问题。,TP SHUAI,15,令xij表示由产地Ai运往销地Bj的物品数量，则产销平衡问题的数学模型为：,2 运输问题（续）,TP SHUAI,16,以价格qi 购买了si份股票i,i=1,2,n 股票i的现价是pi 你预期一年后股票的价格为ri 在出售股票时需要支付的税金=资本收益30% 扣除
8、税金后，你的现金仍然比购买股票前增多 支付1%的交易费用 例如：将原先以每股30元的价格买入1000股股票，以每股50元的价格出售，则净现金为： 50 1000-0.3(50-30)1000-0.150 1000=39000,3 税下投资问题,TP SHUAI,17,我们的目标是要使预期收益最大。 Xi：当前抛出股票i的数量。,3 税下投资问题（续）,TP SHUAI,18,4 选址问题（1）,实例:一组潜在位置（地址）, 一组顾客集合及相应的利润和费用数据；解: 设施开放(使用)的数目，他们的位置，以及顾客被哪个设施服务的具体安排方案； 目标：总的利润最大化。,数据与约束 J=1,2,n:放
9、置设施的可能的潜在位置集合 I=1,2,m:顾客集合,其要求的服务需要某设施所提 供.,TP SHUAI,19,4 选址问题（2）,TP SHUAI,20,4选址问题（3）,TP SHUAI,21,5负载平衡(1),实例: 网络G(V,E) 及一组m 个数的集合s,d0，表示连接源点 s与汇点d 之间的流量 解: s,d0的一组路由, 即G(V,E) 中m 条s 与 d间的路,表示连接s与d 的负载流量的路径。 目标:极小化网络负载,TP SHUAI,22,5 负载平衡(2),TP SHUAI,23,6.结构设计问题,两杆桁架的最优设计问题。 由两根空心圆杆组成对称的两杆桁架，其顶点承受负载为
10、2p，两支座之间的水平距离为2L，圆杆的壁厚为B，杆的比重为，弹性模量为E，屈吸强度为。求在桁架不被破坏的情况下使桁架重量最轻的桁架高度h及圆杆平均直径d。,TP SHUAI,24,6.结构设计问题,TP SHUAI,25,6.结构设计问题,此应力要求小于材料的屈吸极限，即,解：桁杆的截面积为 ：,桁杆的总重量为：,负载2p在每个杆上的分力为：,于是杆截面的应力为：,圆杆中应力小于等于压杆稳定的临界应力。 由材料力学知：压杆稳定的临界应力为,由此得稳定约束：,6.结构设计问题,另外还要考虑到设计变量d和h有界。从而得到两杆桁架最优设计问题的数学模型：,6.结构设计问题,TP SHUAI,28,
11、基本概念,在上述例子中,有的目标函数和约束函数 都是线性的,称之为线性规划问题,而有的模型中含有非线性函数,称之为非线性规划. 在线性与非线性规划中,满足约束条件的点称为可行点,全体可行点组成的集合称为可行集或可行域.如果一个问题的可行域是整个空间,则称此问题为无约束问题.,TP SHUAI,29,基本概念,最优化问题可写成如下形式:,TP SHUAI,30,基本概念,Df 1. 1 设f(x)为目标函数，S为可行域，x0S,若对每一个x S,成立f(x)f(x0),则称x0为极小化问题min f(x), x S的最优解（整体最优解）,则称x0为极小化问题min f(x),x S的局部最优解,
12、Df 1.2 设f(x)为目标函数，S为可行域，,TP SHUAI,31,Thank you very much for your attendance!,优化软件 http:/www-neos.mcs.anl.gov/ http:/neos.mcs.anl.gov/neos/solvers/index.html,TP SHUAI,32,最优化理论与算法,帅天平 北京邮电大学数学系 Email:, Tel:62281308,Rm:主楼814 1 预备知识,TP SHUAI,33,1， 预备知识,1.线性空间 2.范数 3.集合与序列 4.矩阵的分解与校正,TP SHUAI,34,1.线性空间,
13、Df 1.3:给定一非空集合G以及在G上的一种代数运算+:GGG(称为加法),若下述条件成立:,则称为一个群.若还满足对任意的a,bG,有a+b=b+a,则称为一个阿贝尔群(&交换群),TP SHUAI,35,1.线性空间,Df 1.4:给定一非空集合V和一个域F,并定义两种运算加法 +:VVV以及数乘: FVV.若构成一交换群, 且两种运算满足下面性质:,则称V在域F上关于加法和数乘 运算构成一线性空间,简称V为F上的线性空间.记为V(F).若V的非空子集合S关于加法 和数乘运算在F上也构成一线性空间,则S称为F上的线性子空间.,TP SHUAI,36,1.线性空间,例子,TP SHUAI,
14、37,1.线性空间,TP SHUAI,38,1.线性空间,Th1.1 线性空间V(F)的非空子集S的线性扩张L(S)是V中 包含S的最小子空间.,TP SHUAI,39,1.线性空间,TP SHUAI,40,1.线性空间,TP SHUAI,41,2.范数,TP SHUAI,42,2.范数,TP SHUAI,43,2.范数,TP SHUAI,44,3.集合与序列,TP SHUAI,45,3，集合与序列,TP SHUAI,46,3.集合与序列,TP SHUAI,47,3.集合与序列,TP SHUAI,48,4.矩阵的分解与校正,Th1.5 若n阶矩阵A可逆，则存在一个排列矩阵P,单位下 三角矩阵L
15、和上三角矩阵U，使得PA=LU,TP SHUAI,49,4.矩阵的分解与校正,Th1.6 设A为对称正定矩阵，则 （1）矩阵A可唯一的分解成A=LDLT, 其中L为单位下三角矩阵，D为对角矩阵 （2）存在可逆的下三角矩阵L，使得A=LLT. 当L的对角元素为正时，分解是唯一的。(Cholesky分解),TP SHUAI,50,4.矩阵的分解与校正,TP SHUAI,51,4.矩阵的分解与校正,TP SHUAI,52,5.函数的可微性与展开,TP SHUAI,53,5.函数的可微性与展开,当f(x)在x点存在二阶偏导时,函数f在点x的Hesse矩阵定义为,TP SHUAI,54,5.函数的可微性与展开,TP SHUAI,55,5.函数的可微性与展开,TP SHUAI,56,5.函数的可微性与展开,TP SHUAI,57,最优化理论与算法,帅天平 北京邮电大学数学系 Email:, Tel:62281308,Rm:主楼8142，凸分析与凸函数,TP SHUAI,58,2. 凸集与凸函数,2.1 凸集与锥,TP SHUAI,59,2. 凸集与凸函数,TP SHUAI,60,2. 凸集与凸函数,TP SHUAI,61,2. 凸集与凸函数,TP SHUAI,62,运用定义不难验证如下命题：,2. 凸集与凸函数,TP SHUAI,63,2. 凸集与凸函数,
