资源描述
单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,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 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,4,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,5,1,绪论,-,学科概述,最优化是从所有可能的方案中选择最合理,的一种方案,以达到最佳目标 的科学,.,达到最佳目标的方案是最优方案,寻找最优,方案的方法,-,最优化方法,(,算法,),这种方法的数学理论即为最优化理论,.,是运筹学的方法论之一,.,是其重要组成部分,.,运筹学的,“,三个代表,”,模型,理论,算法,最优化首先是一种理念,其次才是一种方法,.,TP SHUAI,6,绪论,-,运筹学（,Operations Research-OR,）,运筹学方法,随机过程方法,统计学方法,最优化,/,数学规划方法,连续优化：线性规划、非线性规划、非光滑优化、全局优化、变分法、二次规划、分式规划等,离散优化：组合优化、,网络优化、整数规划,等,几何规划,动态规划,不确定规划：随机规划、模糊规划等,多目标规划,对策论等,统计决策理论,马氏过程,排队论,更新理论,仿真方法,可靠性理论等,回归分析,群分析,模式识别,实验设计,因子分析等,TP SHUAI,7,优化树,TP SHUAI,8,最优化的发展历程,费马,:,1638;,牛顿,1670,欧拉,1755,Min f(,x,1,x,2,x,n,),f(,x,)=0,TP SHUAI,9,欧拉，拉格朗日：无穷维问题，变分学,柯西：最早应用最速下降法,拉格朗日，,1797,Min f(,x,1,x,2,x,n,),s.t.g,k,(,x,1,x,2,x,n,)=0,k=1,2,m,TP SHUAI,10,1930,年代，康托诺维奇：线性规划,1940,年代，,Dantzig,：单纯形方法，,冯 诺依曼：对策论,1950,年代，,Bellman,：动态规划，最优性原理；,KKT,条件；,1960,年代：,Zoutendijk,Rosen,Carroll,etc.,非线性规划算法，,Duffin,，,Zener,等几何规划，,Gomory,，整数规划,Dantzig,等随机规划,6-70,年代：,Cook,等复杂性理论，组合优化迅速发展,电子计算机,-,最优化,TP SHUAI,11,最优化应用举例,具有广泛的实用性,运输问题，车辆调度，员工安排，空运控制等,工程设计，结构设计等,资源分配，生产计划等,通信：光网络、无线网络，,ad hoc,等,.,制造业：钢铁生产，车间调度等,医药生产，化工处理等,电子工程，集成电路,VLSI etc.,排版（,TEX,Latex,etc.,）,TP SHUAI,12,1.,食谱问题,我每天要求一定量的两种维生素，,V,c,和,V,b,。,假设这些维生素可以分别从牛奶和鸡蛋中得到。,维生素,奶中含量,蛋中含量,每日需求,V,c,(mg),2,4,40,V,b,(mg),3,2,50,单价,(US$),3,2.5,需要确定每天喝奶和吃蛋的量，,目标,以便以最低可能的花费购买这些食物，,而,满足,最低限度的维生素需求量。,TP SHUAI,13,1.,食谱问题,（续）,令,x,表示要买的奶的量，,y,为要买的蛋的量。食谱问题可以写,成如下的数学形式：,运筹学工作者参与建立关于何时出现最小费用,（或者最大利润）的排序，或者计划，早期被标示为,programs,。,求最优安排或计划的问题，称作,programming,问题。,Min 3,x,+2.5,y,s.t.2,x,+4,y,40,3,x,+2,y,50,x,y,0.,极小化目标函数,可行区域（单纯形）,可行解,TP SHUAI,14,2,运输问题,设某种物资有,m,个产地,A,1,A,2,A,m,各产地的产量是,a,1,a,2,a,m,;,有,n,个销地,B,1,B,2,B,n,.,各销地的销量是,b,1,b,2,b,n,.,假定从产地,A,i,(i=1,2,m),到销地,B,j,(j=1,2,n),运输单位物品的运价是,c,ij,问怎样调运这些物品才能使总运费最小？,如果运输问题的总产量等于总销量，即有,则称该运输问题为产销平衡问题；反之，称产销不平衡问题。,TP SHUAI,15,令,x,ij,表示由产地,A,i,运往销地,B,j,的物品数量，则产销平衡问题的数学模型为：,2,运输问题（续）,TP SHUAI,16,以价格,q,i,购买了,s,i,份股票,i,i=1,2,n,股票,i,的现价是,p,i,你预期一年后股票的价格为,r,i,在出售股票时需要支付的税金,=,资本收益,30%,扣除税金后，你的现金仍然比购买股票前增多,支付,1%,的交易费用,例如：将原先以每股,30,元的价格买入,1000,股股票，以每股,50,元的价格出售，则净现金为：,50,1000-0.3(50-30)1000-0.150 1000=39000,3,税下投资问题,TP SHUAI,17,我们的目标是要使预期收益最大。,X,i,：当前抛出股票,i,的数量。,3,税下投资问题（续）,TP SHUAI,18,4,选址问题（,1,）,实例,:,一组潜在位置（地址）,一组顾客集合及相应的,利润和费用数据；,解,:,设施开放,(,使用,),的数目，他们的位置，以及顾客,被哪个设施服务的具体安排方案；,目标：总的利润最大化。,数据与约束,J=1,2,n:,放置设施的可能的潜在位置集合,I=1,2,m:,顾客集合,其要求的服务需要某设施所提 供,.,TP SHUAI,19,4,选址问题（,2,）,TP SHUAI,20,4,选址问题（,3,）,TP SHUAI,21,5,负载平衡,(1),实例,:,网络,G(V,E),及一组,m,个数的集合,s,d,0,，表示,连接源点,s,与汇点,d,之间的流量,解,:,s,d,0,的一组路由,即,G(V,E),中,m,条,s,与,d,间的路,表示连接,s,与,d,的负载流量的路径。,目标,:,极小化网络负载,TP SHUAI,22,5,负载平衡,(2),TP SHUAI,23,6.,结构设计问题,两杆桁架的最优设计问题。,由两根空心圆杆组成对称的两杆桁架，其顶点承受负载为,2p,，两支座之间的水平距离为,2L,，圆杆的壁厚为,B,，杆的比重为,，弹性模量为,E,，屈吸强度为,。求在桁架不被破坏的情况下使桁架重量最轻的桁架高度,h,及圆杆平均直径,d,。,TP SHUAI,24,受力分析图,圆杆截面图,桁杆示意图,6.,结构设计问题,TP SHUAI,25,6.,结构设计问题,此应力要求小于材料的屈吸极限，即,解：桁杆的截面积为：,桁杆的总重量为：,负载,2p,在每个杆上的分力为：,于是杆截面的应力为：,圆杆中应力小于等于压杆稳定的临界应力。,由材料力学知：压杆稳定的临界应力为,由此得稳定约束：,6.,结构设计问题,另外还要考虑到设计变量,d,和,h,有界。,从而得到两杆桁架最优设计问题的数学模型：,6.,结构设计问题,TP SHUAI,28,基本概念,在上述例子中,有的目标函数和约束函数,都是线性的,称之为,线性规划问题,而有的模型中含有非线性函数,称之为非线性规划,.,在线性与非线性规划中,满足约束条件的点称为,可行点,全体可行点组成的集合称为,可行集,或,可行域,.,如果一个问题的可行域是整个空间,则称此问题为,无约束问题,.,TP SHUAI,29,基本概念,最优化问题可写成如下形式,:,TP SHUAI,30,基本概念,Df 1.1,设,f(x),为目标函数，,S,为可行域，,x,0,S,若对每一个,x,S,成立,f(x)f(x,0,),则称,x,0,为极小化问题,min,f,(,x,),x S,的,最优解,（,整体最优解,）,则称,x,0,为极小化问题,min,f,(,x,),x S,的,局部最优解,Df 1.2,设,f(x),为目标函数，,S,为可行域，,TP SHUAI,31,Thank you very much for your attendance!,优化软件,
展开阅读全文