北邮最优化课件0最优化理论与算法引言.pptx

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

1、2023/5/17最优化理论TP SHUAITP SHUAI1最优化理论与算法帅天平北京邮电大学数学系2023/5/17最优化理论TP SHUAITP SHUAI2提纲1.线性规划 对偶定理对偶定理2.非线性规划 K-K-T 定理定理3.组合最优化 算法设计技巧算法设计技巧使用教材：最最优化理论与算法优化理论与算法 陈宝林陈宝林参考书：数学规划数学规划 黄红选，黄红选，韩继业韩继业 清华大学出版社清华大学出版社2023/5/17最优化理论TP SHUAITP SHUAI3其他参考书目其他参考书目Nonlinear Programming-Theory and AlgorithmsMokhtar

2、 S.Bazaraa,C.M.ShettyJohn Wiley&Sons,Inc.1979(2nd Edit,1993，3nd Edit，2006)Linear and 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

3、Frank H.Clarke SIAM,1990.2023/5/17最优化理论TP SHUAITP SHUAI4Linear 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 其他参考书目其他参考书目2023

4、/5/17最优化理论TP SHUAITP SHUAI51,绪论绪论-学科概述学科概述最优化是从所有可能的方案中选择最合理 的一种方案,以达到最佳目标 的科学.达到最佳目标的方案是最优方案,寻找最优 方案的方法-最优化方法(算法)这种方法的数学理论即为最优化理论.是运筹学的方法论之一.是其重要组成部分.运筹学的“三个代表”模型模型理论理论算法算法最优化首先是一种理念最优化首先是一种理念,其次才是一种方法其次才是一种方法.2023/5/17最优化理论TP SHUAITP SHUAI6绪论绪论-运筹学（运筹学（Operations Research-OR）运筹学方法随机过程方法统计学方法最优化/数学

5、规划方法l连续优化：线性规划、连续优化：线性规划、非线性规划、非光滑优非线性规划、非光滑优化、全局优化、变分法、化、全局优化、变分法、二次规划、分式规划等二次规划、分式规划等l 离散优化：组合优化、离散优化：组合优化、网络优化、整数规划网络优化、整数规划等等l几何规划几何规划l动态规划动态规划l不确定规划：随机规不确定规划：随机规划、模糊规划等划、模糊规划等l多目标规划多目标规划l对策论等对策论等l统计决策理论统计决策理论l马氏过程马氏过程l 排队论排队论l更新理论更新理论l仿真方法仿真方法l可靠性理论等可靠性理论等l回归分析回归分析l群分析群分析l模式识别模式识别l实验设计实验设计l因子分析

6、等因子分析等2023/5/17最优化理论TP SHUAITP SHUAI7优化树2023/5/17最优化理论TP SHUAITP SHUAI8最优化的发展历程最优化的发展历程费马:1638;牛顿,1670欧拉,1755Min f(x1 x2 xn)f(x)=02023/5/17最优化理论TP SHUAITP SHUAI9欧拉，拉格朗日：无穷维问题，变分学柯西：最早应用最速下降法拉格朗日，1797Min f(x1 x2 xn)s.t.gk(x1 x2 xn)=0,k=1,2,m2023/5/17最优化理论TP SHUAITP SHUAI101930年代，康托诺维奇：线性规划1940年代，Dant

7、zig：单纯形方法，冯 诺依曼：对策论1950年代，Bellman：动态规划，最优性原理；KKT条件；1960年代：Zoutendijk,Rosen,Carroll,etc.非线性规划算法，Duffin，Zener等几何规划，Gomory，整数规划,Dantzig等随机规划 6-70年代：Cook等复杂性理论，组合优化迅速发展 电子计算机-最优化2023/5/17最优化理论TP SHUAITP SHUAI11最优化应用举例具有广泛的实用性运输问题，车辆调度，员工安排，空运控制等工程设计，结构设计等资源分配，生产计划等通信：光网络、无线网络，ad hoc 等.制造业：钢铁生产，车间调度等医药生产

8、，化工处理等电子工程，集成电路VLSI etc.排版（TEX,Latex,etc.）2023/5/17最优化理论TP SHUAITP SHUAI121.食谱问题我每天要求一定量的两种维生素，Vc和Vb。假设这些维生素可以分别从牛奶和鸡蛋中得到。维生素奶中含量蛋中含量每日需求Vc(mg)2440Vb(mg)3250单价(US$)32.5需要确定每天喝奶和吃蛋的量，目标目标以便以最低可能的花费购买这些食物，而满足满足最低限度的维生素需求量。2023/5/17最优化理论TP SHUAITP SHUAI131.食谱问题（续）令x表示要买的奶的量，y为要买的蛋的量。食谱问题可以写成如下的数学形式：运筹学

9、工作者参与建立关于何时出现最小费用（或者最大利润）的排序，或者计划，早期被标示为programs。求最优安排或计划的问题，称作programming问题。Min 3x+2.5y s.t.2x +4y 40 3x +2y 50 x,y 0.极小化目标函数极小化目标函数可行区域（单纯形）可行区域（单纯形）可行解可行解2023/5/17最优化理论TP SHUAITP SHUAI142 运输问题设某种物资有m个产地A1,A2,Am,各产地的产量是a1,a2,am;有 n个销地B1,B2,Bn.各销地的销量是b1,b2,bn.假定从产地Ai(i=1,2,m)到销地Bj(j=1,2,n)运输单位物品的运价

10、是cij问怎样调运这些物品才能使总运费最小？如果运输问题的总产量等于总销量，即有则称该运输问题为产销平衡问题；反之，称产销不平衡问题。2023/5/17最优化理论TP SHUAITP SHUAI15令xij表示由产地Ai运往销地Bj的物品数量，则产销平衡问题的数学模型为：2 运输问题（续）2023/5/17最优化理论TP SHUAITP SHUAI16以价格qi 购买了si份股票i,i=1,2,n股票i的现价是pi你预期一年后股票的价格为ri 在出售股票时需要支付的税金=资本收益30%扣除税金后，你的现金仍然比购买股票前增多支付1%的交易费用例如：将原先以每股30元的价格买入1000股股票，以

11、每股50元的价格出售，则净现金为：50 1000-0.3(50-30)1000-0.150 1000=390003 税下投资问题2023/5/17最优化理论TP SHUAITP SHUAI17我们的目标是要使预期收益最大。Xi：当前抛出股票i的数量。3 税下投资问题（续）2023/5/17最优化理论TP SHUAITP SHUAI184 选址问题（1）实例实例:一组潜在位置（地址）,一组顾客集合及相应的 利润和费用数据；解解:设施开放(使用)的数目，他们的位置，以及顾客 被哪个设施服务的具体安排方案；目标：总的利润最大化。目标：总的利润最大化。数据与约束J=1,2,n:放置设施的可能的潜在位置

12、集合I=1,2,m:顾客集合,其要求的服务需要某设施所提 供.2023/5/17最优化理论TP SHUAITP SHUAI194 选址问题（2）2023/5/17最优化理论TP SHUAITP SHUAI204选址问题（3）2023/5/17最优化理论TP SHUAITP SHUAI215负载平衡(1)实例实例:网络网络G(V,E)及一组m 个数的集合s,d0，表示 连接源点 s与汇点d 之间的流量解解:s,d0的一组路由,即G(V,E)中m 条s 与 d间的路,表示连接s与d 的负载流量的路径。目标目标:极小化网络负载极小化网络负载2023/5/17最优化理论TP SHUAITP SHUAI

13、225 负载平衡(2)2023/5/17最优化理论TP SHUAITP SHUAI236.结构设计问题结构设计问题两杆桁架的最优设计问题。由两根空心圆杆组成对称的两杆桁架，其顶点承受负载为2p，两支座之间的水平距离为2L，圆杆的壁厚为B，杆的比重为，弹性模量为E，屈吸强度为。求在桁架不被破坏的情况下使桁架重量最轻的桁架高度h及圆杆平均直径d。2023/5/17最优化理论TP SHUAITP SHUAI24 受力分析图圆杆截面图桁杆示意图6.结构设计问题结构设计问题2023/5/17最优化理论TP SHUAITP SHUAI256.结构设计问题结构设计问题此应力要求小于材料的屈吸极限，即解：桁杆

14、的截面积为：桁杆的总重量为：负载2p在每个杆上的分力为：于是杆截面的应力为：圆杆中应力小于等于压杆稳定的临界应力。由材料力学知：压杆稳定的临界应力为 由此得稳定约束：6.结构设计问题结构设计问题 另外还要考虑到设计变量d和h有界。从而得到两杆桁架最优设计问题的数学模型：6.结构设计问题结构设计问题2023/5/17最优化理论TP SHUAITP SHUAI28基本概念基本概念在上述例子中,有的目标函数和约束函数都是线性的,称之为线性规划问题线性规划问题,而有的模型中含有非线性函数,称之为非线性规划称之为非线性规划.在线性与非线性规划中,满足约束条件的点称为可行点可行点,全体可行点组成的集合称为

15、可行集可行集或可行域可行域.如果一个问题的可行域是整个空间,则称此问题为无约束问题无约束问题.2023/5/17最优化理论TP SHUAITP SHUAI29基本概念最优化问题可写成如下形式:2023/5/17最优化理论TP SHUAITP SHUAI30基本概念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为可行域，2023/5/17最优化理论TP SHUAITP SHUAI31优化软件 http:/www-neos.mcs.anl.gov/http:/neos.mcs.anl.gov/neos/solvers/index.html