北邮最优化课件0最优化理论与算法引言共32页.ppt

1、最优化理论1最优化理论与算法帅天平北京邮电大学数学系最优化理论2提纲1. 线性规划 对偶定理对偶定理2. 非线性规划 K-K-T 定理定理3. 组合最优化 算法设计技巧算法设计技巧使用教材：最优化理论与算法最优化理论与算法 陈宝林陈宝林参考书 ：数学规划数学规划 黄红选，黄红选， 韩继业韩继业 清华大学出版社清华大学出版社最优化理论3其他参考书目其他参考书目Nonlinear Programming - Theory and AlgorithmsMokhtar S. Bazaraa, C. M. ShettyJohn Wiley & Sons, Inc. 1979 (2nd Edit, 199

2、3，3nd Edit，2019)Linear and Nonlinear Programming David G. LuenbergerAddison-Wesley Publishing Company, 2nd Edition, 1984/2019.Convex Analysis R. T. RockafellarPrinceton Landmarks in Mathematics and Physics, 2019.Optimization and Nonsmooth Analysis Frank H. Clarke SIAM, 1990.最优化理论4Linear Programming

3、and Network Flows M. S. Bazaraa, J. J. Jarvis, John Wiley & Sons, Inc., 1977.运筹学基础手册徐光辉、刘彦佩、程侃科学出版社，2019组合最优化算法和复杂性 Combinatorial Optimization 蔡茂诚、刘振宏 Algorithms and Complexity 清华大学出版社，1988 Printice-Hall Inc.,1982/2019 其他参考书目其他参考书目最优化理论51,绪论绪论-学科概述学科概述 最优化是从所有可能的方案中选择最合理 的一种方案,以达到最佳目标 的科学. 达到最佳目标的方案

4、是最优方案,寻找最优 方案的方法-最优化方法(算法) 这种方法的数学理论即为最优化理论. 是运筹学的方法论之一.是其重要组成部分.运筹学的“三个代表” 模型模型 理论理论 算法算法最优化首先是一种理念最优化首先是一种理念, ,其次才是一种方法其次才是一种方法. .最优化理论6绪论绪论-运筹学（运筹学（Operations Research - OR） 运筹学方法随机过程方法统计学方法最优化/数学规划方法l连续优化：线性规划、连续优化：线性规划、非线性规划、非光滑优非线性规划、非光滑优化、全局优化、变分法、化、全局优化、变分法、二次规划、分式规划等二次规划、分式规划等l 离散优化：组合优化、离散

5、优化：组合优化、网络优化、整数规划网络优化、整数规划等等l几何规划几何规划l动态规划动态规划l不确定规划：随机规不确定规划：随机规划、模糊规划等划、模糊规划等l多目标规划多目标规划l对策论等对策论等l统计决策理论统计决策理论l马氏过程马氏过程l 排队论排队论l更新理论更新理论l仿真方法仿真方法l可靠性理论等可靠性理论等l回归分析回归分析l群分析群分析l模式识别模式识别l实验设计实验设计l因子分析等因子分析等最优化理论7优化树最优化理论8最优化的发展历程最优化的发展历程费马: :1638;牛顿,1670min f(x) x:df(x) 0dx数欧拉,1755Min f(x1 x2 xn ) f(

6、x)=0最优化理论9欧拉，拉格朗日：无穷维问题，变分学柯西：最早应用最速下降法拉格朗日，1797Min f(x1 x2 xn)s.t. gk (x1 x2 xn )=0, k=1,2,m最优化理论101930年代，康托诺维奇：线性规划1940年代，Dantzig：单纯形方法， 冯 诺依曼：对策论1950年代，Bellman：动态规划，最优性原理； KKT条件；1960年代：Zoutendijk,Rosen,Carroll,etc.非线性规划算法，Duffin，Zener等几何规划，Gomory，整数规划,Dantzig等随机规划 6-70年代：Cook等复杂性理论，组合优化迅速发展 电子计算机

7、-最优化最优化理论11最优化应用举例 具有广泛的实用性 运输问题，车辆调度，员工安排，空运控制等 工程设计，结构设计等 资源分配，生产计划等 通信：光网络、无线网络，ad hoc 等. 制造业：钢铁生产，车间调度等 医药生产，化工处理等 电子工程，集成电路VLSI etc. 排版（TEX,Latex,etc.）最优化理论121. 食谱问题我每天要求一定量的两种维生素，Vc和Vb。假设这些维生素可以分别从牛奶和鸡蛋中得到。维生素奶中含量蛋中含量每日需求Vc(mg)2440Vb(mg)3250单价(US$)32.5需要确定每天喝奶和吃蛋的量，目标目标以便以最低可能的花费购买这些食物，而满足满足最低

8、限度的维生素需求量。最优化理论131. 食谱问题（续）令x表示要买的奶的量，y为要买的蛋的量。食谱问题可以写成如下的数学形式：运筹学工作者参与建立关于何时出现最小费用（或者最大利润）的排序，或者计划，早期被标示为programs。求最优安排或计划的问题，称作programming问题。Min 3x +2.5y s.t. 2x + 4y 40 3x + 2y 50 x, y 0.极小化目标函数极小化目标函数可行区域（单纯形）可行区域（单纯形）可行解可行解最优化理论142 运输问题设某种物资有m个产地A1,A2,Am,各产地的产量是a1,a2,am;有 n个销地B1,B2,Bn.各销地的销量是b1

9、,b2,bn.假定从产地Ai(i=1,2,m)到销地Bj(j=1,2,n)运输单位物品的运价是cij问怎样调运这些物品才能使总运费最小？如果运输问题的总产量等于总销量，即有minjjiba11则称该运输问题为产销平衡问题；反之，称产销不平衡问题。最优化理论15令xij表示由产地Ai运往销地Bj的物品数量，则产销平衡问题的数学模型为：nimjijijxcz11min111,2,.1,2,1,2,01,2,nijijmijjiijxaimstxbjnimxjn2 运输问题（续）最优化理论16 以价格qi 购买了si份股票i,i=1,2,n 股票i的现价是pi 你预期一年后股票的价格为ri 在出售股

10、票时需要支付的税金=资本收益30% 扣除税金后，你的现金仍然比购买股票前增多 支付1%的交易费用 例如：将原先以每股30元的价格买入1000股股票，以每股50元的价格出售，则净现金为：50 1000-0.3(50-30)1000-0.150 1000=390003 税下投资问题最优化理论17niiii=1nnniiiiiiii=1i=1i=1max r(sx )s.t.p x0.30(pq )x0.10p xc 我们的目标是要使预期收益最大。 Xi：当前抛出股票i的数量。3 税下投资问题（续）最优化理论184 选址问题（1）实例实例:一组潜在位置（地址）, 一组顾客集合及相应的 利润和费用数据

11、； 解解: 设施开放(使用)的数目，他们的位置，以及顾客 被哪个设施服务的具体安排方案；目标：总的利润最大化。目标：总的利润最大化。数据与约束J=1,2,n:放置设施的可能的潜在位置集合I=1,2,m:顾客集合,其要求的服务需要某设施所提 供.最优化理论19ijj c : iI, jJ, ji f : jJ, j利润在 处的设施服务顾客 所得的利润费用打开 处设施的费用4 选址问题（2）jjijjJ0-1 x : x1,open j1, i jy:iI,jJ0, 每一变量顾客 由在 的设施服务否则最优化理论204选址问题（3）ijijjji Ij Jj Jijj Jijjjijmax c yf

12、 xs.t. y1 iI; yx , iI, jJ; x0,1, jJ; y0,1, iI, jJ. 最优化理论215负载平衡(1)实例实例: 网络网络G(V,E) 及一组m 个数的集合s,d0，表示 连接源点 s与汇点d 之间的流量解解: s,d0的一组路由, 即G(V,E) 中m 条s 与 d间的路, 表示连接s与d 的负载流量的路径。目标目标:极小化网络负载极小化网络负载的流量。的流经过边到表示由用),(dsjisdijvvF最优化理论225 负载平衡(2)sdi,jijs,dsdijs,ds,sdsdijjkikmin L (1)s.t. LLF , (i,j)E (2) F0,or

13、, (i,j)E (3) FFds,d, if sj, if dj (4)0, otherwise 最优化理论236.结构设计问题结构设计问题两杆桁架的最优设计问题。由两根空心圆杆组成对称的两杆桁架，其顶点承受负载为2p，两支座之间的水平距离为2L，圆杆的壁厚为B，杆的比重为，弹性模量为E，屈吸强度为。求在桁架不被破坏的情况下使桁架重量最轻的桁架高度h及圆杆平均直径d。最优化理论24 1p2pp2hL2 受力分析图圆杆截面图Bp2hL2桁杆示意图d6.结构设计问题结构设计问题最优化理论256.结构设计问题结构设计问题此应力要求小于材料的屈吸极限，即解：桁杆的截面积为 ：桁杆的总重量为：负载2p

14、在每个杆上的分力为：于是杆截面的应力为：dBS222hLdBWhhLppp221cosdhBhLsp2211dhBhLp22 圆杆中应力小于等于压杆稳定的临界应力。由材料力学知：压杆稳定的临界应力为 222228hLBdE082222222dhBhLphLBdE由此得稳定约束：6.结构设计问题结构设计问题 minmaxminmax22222222222080. .2minhhhddddhBhLphLBdEdhBhLptshLdB另外还要考虑到设计变量d和h有界。 从而得到两杆桁架最优设计问题的数学模型：6.结构设计问题结构设计问题最优化理论28基本概念基本概念 在上述例子中,有的目标函数和约束

15、函数都是线性的,称之为线性规划问题线性规划问题,而有的模型中含有非线性函数,称之为非线性规划称之为非线性规划.在线性与非线性规划中,满足约束条件的点称为可行点可行点,全体可行点组成的集合称为可行集可行集或可行域可行域.如果一个问题的可行域是整个空间,则称此问题为无约束问题无约束问题.最优化理论29基本概念 最优化问题可写成如下形式:min ( ) -. . ( )0, ( )0,nx Rijf xstg xiIh xjE目标函数最优化理论30基本概念Df 1. 1 设f(x)为目标函数，S为可行域，x0S,若对每一个x S,成立f(x)f(x0),则称x0为极小化问题min f(x), x S的最优解最优解（整体最优解整体最优解）00000N (x )x | xx,0 xSN (x ),f(x)f(x ) 若存在x 的 邻域使得对每个成立则称x0为极小化问题min f(x),x S的局部最优解局部最优解 Df 1.2 设f(x)为目标函数，S为可行域，最优化理论31优化软件 www-neos.mcs.anl.gov/ neos.mcs.anl.gov/neos/solvers/index.html