最优化理论与算法引言课件

最优化理论与算法提纲1.

线性规划

对偶定理2.

非线性规划

K-K-T定理3.组合最优化

算法设计技巧使用/参考教材：

数学规划黄红选，韩继业最优化理论与算法陈宝林清华大学出版社参考书目NonlinearProgramming-TheoryandAlgorithmsMokhtarS.Bazaraa,C.M.ShettyJohnWiley&Sons,Inc.1979(2ndEdit,1993，3ndEdit，2006)LinearandNonlinearProgramming

DavidG.LuenbergerAddison-WesleyPublishingCompany,2ndEdition,1984/2003..ConvexAnalysis

R.T.RockafellarPrincetonLandmarksinMathematicsandPhysics,1996.OptimizationandNonsmoothAnalysis

FrankH.ClarkeSIAM,1990.1,绪论----学科概述最优化是从所有可能的方案中选择最合理的一种方案,以达到最佳目标的科学.达到最佳目标的方案是最优方案,寻找最优方案的方法----最优化方法(算法)这种方法的数学理论即为最优化理论.运筹学的方法论之一.是其一重要组成部分.运筹学的“三个代表”模型理论算法最优化首先是一种理念,其次才是一种方法.1,绪论----学科概述

最优化技术工作被分成两个方面，一是由实际生产或科技问题形成最优化的数学模型，二是对所形成的数学问题进行数学加工和求解。对于第二方面的工作，目前已有一些较系统成熟的资料，但对于第一方面工作即如何由实际问题抽象出数学模型，目前很少有系统的资料，而这一工作在应用最优化技术解决实际问题时是十分关键的基础，没有这一工作，最优化技术将成为无水之源，难以健康发展。绪论---运筹学（OperationsResearch-OR）广义：管理科学/决策科学(MS/DS)、系统科学/工程(SS/SE)、工业工程(IE)、运作管理(OM)狭义：运筹数学-最优化、对策论、排队论等连续优化：数学规划（线性规划、非线性规划）、非光滑优化、全局优化等离散优化：组合优化、网络优化、整数规划等不确定规划：随机规划、模糊规划等OMOR/MS/DSSS/SEIE/EM最优化的发展历程费马:1638;牛顿,1670欧拉,1755Minf(x1x2···xn)

f(x)=0欧拉，拉格朗日：无穷维问题，变分学拉格朗日，1797Minf(x1x2···xn)s.t.gk(x1x2···xn)=0,k=1,2,…,m最优化应用举例具有广泛的实用性运输空运控制，员工安排等通信：光网络、无线网络，adhocetc.制造业：钢铁生产，车间调度医药工程，电子，集成电路VLSIetc.排版（TEX,Latex,etc.）1.

食谱问题（续一）令x表示要买的奶的量，y为要买的蛋的量。食谱问题可以写成如下的数学形式：运筹学工作者参与建立关于何时出现最小费用（或者最大利润）的排序，或者计划，早期被标示为programs。求最优安排或计划的问题，称作programming问题。Min3x+2.5ys.t.2x+4y403x+2y

50

x,y

0.极小化目标函数可行区域（单纯形）可行解2运输问题数据2运输问题我们的目标是要使预期收益最大。Xi：当前抛出股票i的数量。3税下投资问题4制造业问题4制造业问题决策变量5能源扩充问题5能源扩充问题决策变量6调度问题7选址问题Instance:Asetofpotentialsites,asetofclients,andrelevantProfitandcostdataSolution:thenumberoffacilitiestoopen,theirlocationsandanallocationofeachclienttoanopenfacility.Objective:TheprofitismaximumDataandconstraint7选址问题8LoadBalance9.结构设计问题两杆桁架的最优设计问题。由两根空心圆杆组成对称的两杆桁架，其顶点承受负载为2p，两支座之间的水平距离为2L，圆杆的壁厚为B，杆的比重为ρ，弹性模量为E，屈吸强度为δ。求在桁架不被破坏的情况下使桁架重量最轻的桁架高度h及圆杆平均直径d。

受力分析图圆杆截面图桁杆示意图9.结构设计问题9.结构设计问题此应力要求小于材料的屈吸极限，即解：桁杆的截面积为：桁杆的总重量为：负载2p在每个杆上的分力为：于是杆截面的应力为：

圆杆中应力小于等于压杆稳定的临界应力。由材料力学知：压杆稳定的临界应力为

由此得稳定约束：9.结构设计问题

另外还要考虑到设计变量d和h有界。从而得到两杆桁架最优设计问题的数学模型：9.结构设计问题基本概念在上述例子中,有的目标函数和约束函数都是线性的,称之为线性规划问题,而有的模型中含有非线性函数,称之为非线性规划.在线性与非线性规划中,满足约束条件的点称为可行点,全体可行点组成的集合称为可行集或可行域.如果一个问题的可行域是整个空间,则称此问题为无约束问题.基本概念最优化问题可写成如下形式:基本概念Df1.1设f(x)为目标函数，S为可行域，x0S,若对每一个xS,成立f(x)f(x0),则称x0为极小化问题min

f(x),xS的最优解（整体最优解）则称x0