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

1、最优化理论与算法,提纲,1. 线性规划 对偶定理 2. 非线性规划 K-K-T 定理 3. 组合最优化 算法设计技巧,使用/参考教材： 数学规划 黄红选， 韩继业 最优化理论与算法 陈宝林 清华大学出版社,参考书目,Nonlinear Programming - Theory and Algorithms Mokhtar S. Bazaraa, C. M. Shetty John Wiley 牛顿,1670,欧拉,1755,Min f(x1 x2 xn ) f(x)=0,欧拉，拉格朗日：无穷维问题，变分学,拉格朗日，1797,Min f(x1 x2 xn) s.t. gk (x1 x2 xn

2、)=0, k=1,2,m,最优化应用举例,具有广泛的实用性 运输 空运控制，员工安排等 通信：光网络、无线网络，ad hoc etc. 制造业：钢铁生产，车间调度 医药 工程，电子，集成电路VLSI etc. 排版（TEX,Latex,etc.）,1. 食谱问题,我每天要求一定量的两种维生素，Vc和Vb。 假设这些维生素可以分别从牛奶和鸡蛋中得到。,需要确定每天喝奶和吃蛋的量， 目标以便以最低可能的花费购买这些食物， 而满足最低限度的维生素需求量。,1. 食谱问题（续一）,令x表示要买的奶的量，y为要买的蛋的量。食谱问题可以写 成如下的数学形式：,运筹学工作者参与建立关于何时出现最小费用 （或

3、者最大利润）的排序，或者计划，早期被标示为programs。 求最优安排或计划的问题，称作programming问题。,Min 3x +2.5y s.t. 2x + 4y 40 3x + 2y 50 x, y 0.,极小化目标函数 可行区域（单纯形） 可行解,2 运输问题,数据,2 运输问题,以价格qi 购买了si份股票i,i=1,2,n 股票i的现价是pi 你预期一年后股票的价格为ri 在出售股票时需要支付的税金=资本收益30% 扣除税金后，你的现金仍然比购买股票前增多 支付1%的交易费用 例如：将原先以每股30元的价格买入1000股股票，以每股50元的价格出售，则净现金为： 50 1000

4、-0.3(50-30)1000-0.150 1000=39000,3 税下投资问题,我们的目标是要使预期收益最大。 Xi：当前抛出股票i的数量。,3 税下投资问题,4 制造业问题,4 制造业问题,数据和约束,5 能源扩充问题,决策变量,5 能源扩充问题,5 能源扩充问题,决策变量,6 调度问题,6 调度问题,7 选址问题,Instance:A set of potential sites, a set of clients, and relevant Profit and cost data Solution:the number of facilities to open, their lo

5、cations and an allocation of each client to an open facility. Objective:The profit is maximum,Data and constraint,7 选址问题,7 选址问题,8 Load Balance,Instance: A network G(V,E) and a set of m numberss,d0 representing the traffic of connection between source s and destination d Solution: A routing of s,d0,

6、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 d Objective:Minimizing the network load,8 Load Balance,9.结构设计问题,两杆桁架的最优设计问题。 由两根空心圆杆组成对称的两杆桁架，其顶点承受负载为2p，两支座之间的水平距离为2L，圆杆的壁厚为B，杆的比重为，弹性模量为E，屈吸强度为。求在桁架不被破坏的情

7、况下使桁架重量最轻的桁架高度h及圆杆平均直径d。,9.结构设计问题,9.结构设计问题,此应力要求小于材料的屈吸极限，即,解：桁杆的截面积为 ：,桁杆的总重量为：,负载2p在每个杆上的分力为：,于是杆截面的应力为：,圆杆中应力小于等于压杆稳定的临界应力。 由材料力学知：压杆稳定的临界应力为,由此得稳定约束：,9.结构设计问题,另外还要考虑到设计变量d和h有界。 从而得到两杆桁架最优设计问题的数学模型：,9.结构设计问题,基本概念,在上述例子中,有的目标函数和约束函数 都是线性的,称之为线性规划问题,而有的模型中含有非线性函数,称之为非线性规划. 在线性与非线性规划中,满足约束条件的点称为可行点,全体可行点组成的集合称为可行集或可行域.如果一个问题的可行域是整个空间,则称此问题为无约束问题.,基本概念,最优化问题可写成如下形式:,基本概念,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为可行域，,Thank you very much for your attendance!,优化软件http:/www.cas.mc