0最优化理论与算法引言

1、最优化理论与算法计算数学与应用软件教研室理学院，北京邮电大学提纲1. 线性规划 对偶定理对偶定理2. 非线性规划 k-k-t 定理定理3. 组合最优化 算法设计技巧算法设计技巧使用教材：最优化理论与算法最优化理论与算法 陈宝林陈宝林参考书 ：数学规划数学规划 黄红选，黄红选， 韩继业韩继业 清华大学出版社清华大学出版社其他参考书目其他参考书目nonlinear programming - theory and algorithmsmokhtar s. bazaraa, c. m. shettyjohn wiley & sons, inc. 1979 (2nd edit, 1993，3nd ed

2、it，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 frank h. clarke siam, 1990.linear programming and network fl

3、ows m. s. bazaraa, j. j. jarvis, john wiley & sons, inc., 1977.运筹学基础手册徐光辉、刘彦佩、程侃科学出版社，1999组合最优化算法和复杂性 combinatorial optimization 蔡茂诚、刘振宏 algorithms and complexity 清华大学出版社，1988 printice-hall inc.,1982/1998 其他参考书目其他参考书目1,绪论绪论-学科概述学科概述 最优化是从所有可能的方案中选择最合理 的一种方案,以达到最佳目标 的科学. 达到最佳目标的方案是最优方案,寻找最优 方案的方法-最优化

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

5、。绪论绪论-运筹学（运筹学（operations research - or） 运筹学方法随机过程方法统计学方法最优化/数学规划方法l连续优化：线性规划、连续优化：线性规划、非线性规划、非光滑优非线性规划、非光滑优化、全局优化、变分法、化、全局优化、变分法、二次规划、分式规划等二次规划、分式规划等l 离散优化：组合优化、离散优化：组合优化、网络优化、整数规划等网络优化、整数规划等l几何规划几何规划l动态规划动态规划l不确定规划：随机规不确定规划：随机规划、模糊规划等划、模糊规划等l多目标规划多目标规划l对策论等对策论等l统计决策理论统计决策理论l马氏过程马氏过程l 排队论排队论l更新理论更新理

6、论l仿真方法仿真方法l可靠性理论等可靠性理论等l回归分析回归分析l群分析群分析l模式识别模式识别l实验设计实验设计l因子分析等因子分析等绪论绪论-运筹学（运筹学（operations research - or）n广义：管理科学广义：管理科学/决策科学决策科学(ms/ds)、系统科学、系统科学/工程工程(ss/se)、工业工程、工业工程(ie)、运、运作管理作管理(om)n狭义：运筹数学狭义：运筹数学 - 最优化、最优化、对策论、排队论等对策论、排队论等 连续优化：数学规划（线性规划、非连续优化：数学规划（线性规划、非线性规划）、非光滑优化、全局优化等线性规划）、非光滑优化、全局优化等 离散优

7、化：组合优化、网络优化、整离散优化：组合优化、网络优化、整数规划等数规划等 不确定规划：随机规划、模糊规划等不确定规划：随机规划、模糊规划等omor/ms/dsss/seie/em优化树最优化的发展历程最优化的发展历程费马: :1638;牛顿,1670min f(x) x:df(x) 0dx数欧拉,1755min f(x1 x2 xn ) f(x)=0欧拉，拉格朗日：无穷维问题，变分学柯西：最早应用最速下降法拉格朗日，1797min f(x1 x2 xn)s.t. gk (x1 x2 xn )=0, k=1,2,m1930年代，康托诺维奇：线性规划1940年代，dantzig：单纯形方法， 冯

8、 诺依曼：对策论1950年代，bellman：动态规划，最优性原理； kkt条件；1960年代：zoutendijk,rosen,carroll,etc.非线性规划算法，duffin，zener等几何规划，gomory，整数规划,dantzig等随机规划 6-70年代：cook等复杂性理论，组合优化迅速发展 电子计算机运筹学最优化应用举例 具有广泛的实用性 运输问题，车辆调度，员工安排，空运控制等 工程设计，结构设计等 资源分配，生产计划等 通信：光网络、无线网络，ad hoc 等. 制造业：钢铁生产，车间调度等 医药生产，化工处理等 电子工程，集成电路vlsi etc. 排版（tex,lat

9、ex,etc.）1. 食谱问题我每天要求一定量的两种维生素，vc和vb。假设这些维生素可以分别从牛奶和鸡蛋中得到。维生素vc(mg)vb(mg)单价(us$)奶中含量233蛋中含量422.5每日需求4050需要确定每天喝奶和吃蛋的量，目标目标以便以最低可能的花费购买这些食物，而满足满足最低限度的维生素需求量。1. 食谱问题（续）令x表示要买的奶的量，y为要买的蛋的量。食谱问题可以写成如下的数学形式：运筹学工作者参与建立关于何时出现最小费用（或者最大利润）的排序，或者计划，早期被标示为programs。求最优安排或计划的问题，称作programming问题。min 3x +2.5y s.t. 2

10、x + 4y 40 3x + 2y 50 x, y 0.极小化目标函数极小化目标函数可行区域（单纯形）可行区域（单纯形）可行解可行解2 运输问题设某种物资有m个产地a1,a2,am,各产地的产量是a1,a2,am;有 n个销地b1,b2,bn.各销地的销量是b1,b2,bn.假定从产地ai(i=1,2,m)到销地bj(j=1,2,n)运输单位物品的运价是cij问怎样调运这些物品才能使总运费最小？如果运输问题的总产量等于总销量，即有minjjiba11则称该运输问题为产销平衡问题；反之，称产销不平衡问题。令xij表示由产地ai运往销地bj的物品数量，则产销平衡问题的数学模型为：nimjijijx

11、cz11min111,2,.1,2,1,2,01,2,nijijmijjiijxaimstxbjnimxjn2 运输问题（续） 以价格qi 购买了si份股票i,i=1,2,n 股票i的现价是pi 你预期一年后股票的价格为ri 在出售股票时需要支付的税金=资本收益30% 扣除税金后，你的现金仍然比购买股票前增多 支付1%的交易费用 例如：将原先以每股30元的价格买入1000股股票，以每股50元的价格出售，则净现金为：50 1000-0.3(50-30)1000-0.150 1000=390003 税下投资问题niiii=1nnniiiiiiii=1i=1i=1max r(sx )s.t.p x0

12、.30(pq )x0.10p xc 我们的目标是要使预期收益最大。 xi：当前抛出股票i的数量。3 税下投资问题（续）4 选址问题实例实例:一组潜在位置（地址）, 一组顾客集合及相应的 利润和费用数据； 解解: 设施开放(使用)的数目，他们的位置，以及顾客被 哪个设施服务的具体安排方案；目标：总的利润最大化。目标：总的利润最大化。数据与约束j=1,2,n:放置设施的可能的潜在位置集合i=1,2,m:顾客集合,其要求的服务需要某设施所提 供.ijj c : ii, jj, ji f : jj, j利润在 处的设施服务顾客 所得的利润费用打开 处设施的费用4 选址问题（续1）jjijjj0-1 x

13、 : x1,open j1, i jy:ii,jj0, 每一变量顾客 由在 的设施服务否则5选址问题（续2）ijijjji ij jj jijj jijjjijmax c yf xs.t. y1 ii; yx , ii, jj; x0,1, jj; y0,1, ii, jj. 6负载平衡(续1)实例实例: 网络网络g(v,e) 及一组m 个数的集合s,d0，表示 连接源点 s与汇点d 之间的流量解解: s,d0的一组路由, 即g(v,e) 中m 条s 与 d间的路, 表示连接s与d 的负载流量的路径。目标目标:极小化网络负载极小化网络负载的流量。的流经过边到表示由用),(dsjisdijvvf

14、6 负载平衡(续2)sdi,jijs,dsdijs,ds,sdsdijjkikmin l (1)s.t. llf , (i,j)e (2) f0,or , (i,j)e (3) ffds,d, if sj, if dj (4)0, otherwise 7.结构设计问题结构设计问题两杆桁架的最优设计问题。由两根空心圆杆组成对称的两杆桁架，其顶点承受负载为2p，两支座之间的水平距离为2l，圆杆的壁厚为b，杆的比重为，弹性模量为e，屈吸强度为。求在桁架不被破坏的情况下使桁架重量最轻的桁架高度h及圆杆平均直径d。 1p2pp2hl2 受力分析图圆杆截面图bp2hl2桁杆示意图d7.结构设计问题结构设计

15、问题7.结构设计问题结构设计问题此应力要求小于材料的屈吸极限，即解：桁杆的截面积为 ：桁杆的总重量为：负载2p在每个杆上的分力为：于是杆截面的应力为：dbs222hldbwhhlppp221cosdhbhlsp2211dhbhlp22 圆杆中应力小于等于压杆稳定的临界应力。由材料力学知：压杆稳定的临界应力为 222228hlbde082222222dhbhlphlbde由此得稳定约束：7.结构设计问题结构设计问题 minmaxminmax22222222222080. .2minhhhddddhbhlphlbdedhbhlptshldb另外还要考虑到设计变量d和h有界。 从而得到两杆桁架最优设计问题的数学模型：7.结构设计问题结构设计问题基本概念基本概念 在上述例子中,有的目标函数和约束函数都是线性的,称之为线性规划问题线性规划问题,而有的模型中含有非线性函数,称之为非线性规划称之为非线性规划.在线性与非线性规划中,满足约束条件的点称为可行点可行点,全体可行点组成的集合称为可行集可行集或可行域可行域.如果一个问题的可行域是整个空间,则称此问题为无约束问题无约束问题.基本概念 最优化问题可写成如下形式:min ( ) -. . ( )0, ( )0,nx rijf xstg xiih xje目标函数基本概念df 1. 1 设f(x)为目标函数，s为可行域，x0s,若对每