最优化理论与算法引言精.ppt

《最优化理论与算法引言精.ppt》由会员分享，可在线阅读，更多相关《最优化理论与算法引言精.ppt（38页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、最优化理论与算法引言第1页，本讲稿共38页提纲1.线性规划 对偶定理对偶定理2.非线性规划 K-K-T 定理定理3.组合最优化 算法设计技巧算法设计技巧使用/参考教材：数学规划数学规划 黄红选，黄红选，韩继业韩继业 最优化理论与算法最优化理论与算法 陈宝林陈宝林 清华大学出版社清华大学出版社第2页，本讲稿共38页参考书目参考书目Nonlinear Programming-Theory and AlgorithmsMokhtar S.Bazaraa,C.M.ShettyJohn Wiley&Sons,Inc.1979(2nd Edit,1993，3nd Edit，2006)Linear and

2、Nonlinear Programming David G.LuenbergerAddison-Wesley Publishing Company,2nd Edition,1984/2003.Convex Analysis R.T.RockafellarPrinceton Landmarks in Mathematics and Physics,1996.Optimization and Nonsmooth Analysis Frank H.Clarke SIAM,1990.第3页，本讲稿共38页Linear Programming and Network Flows M.S.Bazaraa,

3、J.J.Jarvis,John Wiley&Sons,Inc.,1977.运筹学基础手册徐光辉、刘彦佩、程侃科学出版社，1999组合最优化算法和复杂性 Combinatorial Optimization 蔡茂诚、刘振宏 Algorithms and Complexity 清华大学出版社，1988 Printice-Hall Inc.,1982/1998 参考书目参考书目第4页，本讲稿共38页1,绪论绪论-学科概述学科概述最优化是从所有可能的方案中选择最合理 的一种方案,以达到最佳目标 的科学.达到最佳目标的方案是最优方案,寻找最优 方案的方法-最优化方法(算法)这种方法的数学理论即为最优化理

4、论.运筹学的方法论之一.是其一重要组成部分.运筹学的“三个代表”模型模型理论理论算法算法最优化首先是一种理念最优化首先是一种理念,其次才是一种方法其次才是一种方法.第5页，本讲稿共38页1,绪论绪论-学科概述学科概述 最优化技术工作被分成两个方面，一是由实际生产或科技问题形成最优化的数学模型，二是对所形成的数学问题进行数学加工和求解。对于第二方面的工作，目前已有一些较系统成熟的资料，但对于第一方面工作即如何由实际问题抽象出数学模型，目前很少有系统的资料，而这一工作在应用最优化技术解决实际问题时是十分关键的基础，没有这一工作，最优化技术将成为无水之源，难以健康发展。第6页，本讲稿共38页绪论绪论

5、-运筹学（运筹学（Operations Research-OR）n广义：管理科学广义：管理科学/决策科学决策科学(MS/DS)、系统科学、系统科学/工程工程(SS/SE)、工业工程、工业工程(IE)、运作、运作管理管理(OM)n狭义：运筹数学狭义：运筹数学-最优化、对最优化、对策论、排队论等策论、排队论等 连续优化：数学规划（线性规划、非线性规划）连续优化：数学规划（线性规划、非线性规划）、非光滑优化、全局优化等、非光滑优化、全局优化等 离散优化：组合优化、网络优化、整数规划等离散优化：组合优化、网络优化、整数规划等 不确定规划：随机规划、模糊规划等不确定规划：随机规划、模糊规划等OMOR/M

6、S/DSSS/SEIE/EM第7页，本讲稿共38页Optimization Tree 第8页，本讲稿共38页最优化的发展历程最优化的发展历程费马:1638;牛顿,1670欧拉,1755Min f(x1 x2 xn)f(x)=0第9页，本讲稿共38页欧拉，拉格朗日：无穷维问题，变分学拉格朗日，1797Min f(x1 x2 xn)s.t.gk(x1 x2 xn)=0,k=1,2,m第10页，本讲稿共38页最优化应用举例具有广泛的实用性运输空运控制，员工安排等通信：光网络、无线网络，ad hoc etc.制造业：钢铁生产，车间调度医药工程，电子，集成电路VLSI etc.排版（TEX,Latex,

7、etc.）第11页，本讲稿共38页1.食谱问题我每天要求一定量的两种维生素，Vc和Vb。假设这些维生素可以分别从牛奶和鸡蛋中得到。维生素奶中含量蛋中含量每日需求Vc(mg)2440Vb(mg)3250单价(US$)32.5需要确定每天喝奶和吃蛋的量，目标目标以便以最低可能的花费购买这些食物，而满足满足最低限度的维生素需求量。第12页，本讲稿共38页1.食谱问题（续一）令x表示要买的奶的量，y为要买的蛋的量。食谱问题可以写成如下的数学形式：运筹学工作者参与建立关于何时出现最小费用（或者最大利润）的排序，或者计划，早期被标示为programs。求最优安排或计划的问题，称作programming问题

8、。Min 3x+2.5y s.t.2x +4y 40 3x +2y 50 x,y 0.极小化目标函数极小化目标函数可行区域（单纯形）可行区域（单纯形）可行解可行解第13页，本讲稿共38页2 运输问题数据第14页，本讲稿共38页2 运输问题第15页，本讲稿共38页以价格qi 购买了si份股票i,i=1,2,n股票i的现价是pi你预期一年后股票的价格为ri 在出售股票时需要支付的税金=资本收益30%扣除税金后，你的现金仍然比购买股票前增多支付1%的交易费用例如：将原先以每股30元的价格买入1000股股票，以每股50元的价格出售，则净现金为：50 1000-0.3(50-30)1000-0.150

9、1000=390003 税下投资问题第16页，本讲稿共38页我们的目标是要使预期收益最大。Xi：当前抛出股票i的数量。3 税下投资问题第17页，本讲稿共38页4 制造业问题第18页，本讲稿共38页4 制造业问题第19页，本讲稿共38页数据和约束5 能源扩充问题第20页，本讲稿共38页决策变量5 能源扩充问题第21页，本讲稿共38页5 能源扩充问题第22页，本讲稿共38页决策变量6 调度问题第23页，本讲稿共38页6 调度问题第24页，本讲稿共38页7 选址问题Instance:A set of potential sites,a set of clients,and relevant Prof

10、it and cost dataSolution:the number of facilities to open,their locations and an allocation of each client to an open facility.Objective:The profit is maximumData and constraint第25页，本讲稿共38页7 选址问题第26页，本讲稿共38页7 选址问题第27页，本讲稿共38页8 Load BalanceInstance:A network G(V,E)and a set of m numberss,d0 represent

11、ing the traffic of connection between source s and destination dSolution:A routing of s,d0,that is a set of m paths in G(V,E)between s and d,representing the routes carrying the traffic of connection between source s and destination dObjective:Minimizing the network load第28页，本讲稿共38页8 Load Balance第29

12、页，本讲稿共38页9.结构设计问题结构设计问题两杆桁架的最优设计问题。由两根空心圆杆组成对称的两杆桁架，其顶点承受负载为2p，两支座之间的水平距离为2L，圆杆的壁厚为B，杆的比重为，弹性模量为E，屈吸强度为。求在桁架不被破坏的情况下使桁架重量最轻的桁架高度h及圆杆平均直径d。第30页，本讲稿共38页 受力分析图圆杆截面图桁杆示意图9.结构设计问题结构设计问题第31页，本讲稿共38页9.结构设计问题结构设计问题此应力要求小于材料的屈吸极限，即解：桁杆的截面积为：桁杆的总重量为：负载2p在每个杆上的分力为：于是杆截面的应力为：第32页，本讲稿共38页 圆杆中应力小于等于压杆稳定的临界应力。由材料力

13、学知：压杆稳定的临界应力为 由此得稳定约束：9.结构设计问题结构设计问题第33页，本讲稿共38页 另外还要考虑到设计变量d和h有界。从而得到两杆桁架最优设计问题的数学模型：9.结构设计问题结构设计问题第34页，本讲稿共38页基本概念在上述例子中,有的目标函数和约束函数都是线性的,称之为线性规划问题线性规划问题,而有的模型中含有非线性函数,称之为非线性规称之为非线性规划划.在线性与非线性规划中,满足约束条件的点称为可行点可行点,全体可行点组成的集合称为可行集可行集或可行域可行域.如果一个问题的可行域是整个空间,则称此问题为无约束问题无约束问题.第35页，本讲稿共38页基本概念最优化问题可写成如下

14、形式:第36页，本讲稿共38页基本概念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的局部最优解局部最优解Df 1.2 设f(x)为目标函数，S为可行域，第37页，本讲稿共38页优化软件http:/www.cas.mcmaster.ca/cs777/http:/www-neos.mcs.anl.gov/http:/neos.mcs.anl.gov/neos/solvers/index.html优化课件www.cas.mcmaster.ca/cs4te3/第38页，本讲稿共38页