运筹学与最优化方法优化建模PPT课件

.,1,最优化方法,哈尔滨工业大学尚寿亭,建模原理算法,.,2,教材与参考1吴祈宗.运筹学与最优化方法.北京：机械工业出版社，2003.82薛嘉庆.最优化原理与方法（修订版）.北京：冶金工业出版社，1992.83解可新，韩立兴，林友联.最优化方法.天津：天津大学出版社，1997.14萧树铁，姜启源等.数学实验，北京：高等教育出版社，1999.75邢文训，谢金星.现代优化计算方法.北京：清华大学出版社，1999.86胡运权，运筹学基础及应用（第三版），哈尔滨工业大学出版社，1998,.,3,参考网站,1全国大学生数学建模竞赛网：2美国：数学及其应用联合会网站：,.,4,最优化方法实际问题与建模,.,5,1.经典极值问题,例1.车站选址问题一直线铁路经过钢厂A，矿区B位于距铁路最近处C为20km，AC相距150km。计划在铁路上设一站D，在AD之间筑一条直线公路，若矿石运费铁路为3元/kmt，公路为5元/kmt。问题：D站选在何处最好。yB（150，20）ox150 xADC,.,6,建模与求解建立模型：设：坐标系xoy，铁路线在ox-轴上，点A位于坐标原点o，点B位于（150，20）,点C位于（150，0）,站D选在x处，运费为f(x)。模型：（min-minimize）（1）其中：求解：应用导数求极值令，即（2）由（2）,.,7,移项后两边开方，解得：（3）由（2）知x=165为增根（）x=135为唯一驻点答案：站D应设在距钢厂A135km处。问题扩展：考虑筑路、建站、装卸等费用，如何建模？数学建模竞赛题：道路改造项目中碎石运输的设计相关网站：“中国电机工程学会杯”全国大学生电工数学建模竞赛/例2.罐头盒问题设计圆柱形罐头盒，使用料最省。假设：1.不考虑折边及铁皮厚度；2.底半径r，高h；3.容积为常数V。,.,8,建立最优化模型：（4）s.t.-subjectto(满足于):约束条件令模型（4）可写成与（1）类似的形式不考虑不等式约束时，模型（4）可用Lagrange乘子法求解,.,9,令求解方程组由r0,及（6）解得，代入（5）结论：高与直径相等时用料最省。问题扩展：侧面与底面厚度不同或造价不同，该如何设计？作业题：建立易拉罐的优化设计模型。,.,10,经典优化问题一般模型：a.无约束问题：其中的可省去；b.条件极值：最优化问题一般模型：,.,11,2.最优化问题实例：例4.生产计划问题某工厂有m种资源某一时段的数量分别为：可用来生产n种产品每生产一单位消耗为利润为。如何安排生产可获最大利润？设：计划生产单位建立线性规划模型LP（LinearProgramming）Maxc1x1+c2x2+cnxns.t.a11x1+a12x2+a1nxnb1am1x1+am2x2+amnxnbmx1,x2,xn0,.,12,令X=x1,x2,xnT;c=c1,c2,cnT;b=b1,b2,bnT;A=aijmxnLP：问题扩展a.若c1,c2,cn不是固定的，c是随机变量，平均值，协方差矩阵V。希望利润期望值最大且方差最小，建立多目标优化模型：,.,13,问题扩展b.风险投资问题（参考98全国建模赛题）将前面的产品换成投资项目，考虑投资Aj风险损失qj。建立多目标优化模型：化为多目标线性规划模型：,.,14,例5.数据拟合问题设某系统中变量x,y满足：y=f(x)已获得系统数据：(xi,yi),i=1,2,m确定f(x)的参数，例如：最优化模型：（最小二乘）其中决策变量为f(x)的参数,.,15,例6.指派问题（0-1规划）,.,16,例7.旅行商问题-TSP（组合优化）一商人欲到n个城市推销，城市i到城市j相距dij,求走遍所有城市的最短路。模型：,.,17,计算复杂性概念n个城市的旅行商问题-TSP，固定一个城市，采用枚举法需(n-1)!个枚举。枚举时城市数与计算时间的关系可以看出27个城市时枚举法已很费时，27个以上可采用启发式算法(heuristicalgrithm)，参见：5（邢文训，谢金星.现代优化计算方法.）问题扩展：多旅行商问题98全国建模赛题：B.灾情巡视路线,.,18,2000B题钢管订购和运输要铺设一条的输送天然气的主管道,如图一所示(见下页)。经筛选后可以生产这种主管道钢管的钢厂有。图中粗线表示铁路，单细线表示公路，双细线表示要铺设的管道(假设沿管道或者原来有公路，或者建有施工公路)，圆圈表示火车站，每段铁路、公路和管道旁的阿拉伯数字表示里程(单位km)。为方便计，1km主管道钢管称为1单位钢管。一个钢厂如果承担制造这种钢管，至少需要生产500个单位。钢厂在指定期限内能生产该钢管的最大数量为个单位，钢管出厂销价1单位钢管为万元，如下表：,.,19,钢管可由铁路、公路运往铺设地点（不只是运到点，而是管道全线）。（1）请制定一个主管道钢管的订购和运输计划，使总费用最小（给出总费用)。（2）请就（1）的模型分析：哪个钢厂钢管的销价的变化对购运计划和总费用影响最大，哪个钢厂钢管的产量的上限的变化对购运计划和总费用的影响最大，并给出相应的数字结果。（3）如果要铺设的管道不是一条线，而是一个树形图，铁路、公路和管道构成网络，请就这种更一般的情形给出一种解决办法，并对图二按（1）的要求给出模型和结果。,.,20,.,21,.,22,钢管订购和运输最优化模型,.,23,钢管订购和运输最优化模型,.,24,钢管订购和运输最优化模型,.,25,1998A题投资的收益和风险市场上有n种资产（如股票、债券、）Si(i=1,n)供投资者选择，某公司有数额为M的一笔相当大的资金可用作一个时期的投资。公司财务分析人员对这n种资产进行了评估，估算出在这一时期内购买Si的平均收益率为ri，并预测出购买Si的风险损失率为qi。考虑到投资越分散，总的风险越小，公司确定，当用这笔资金购买若干种资产时，总体风险可用所投资的Si中最大的一个风险来度量。购买Si要付交易费，费率为pi，并且当购买额不超过给定值ui时，交易费按购买ui计算（不买当然无须付费）。另外，假定同期银行存款利率是r0,且既无交易费又无风险。（r0=5%）,.,26,.,27,.,28,.,29,Matlab优化工具箱（Optimizationtoolbox）,attgoal：求解多目标优化问题.constr：求解约束非线性优化问题.fmin：求解标量非线性优化问题.fminu,fmins：求解无约束非线性优化问题.lp：求解线性规划问题.minmax：求解最小最大问题.qp：求解二次规划问题.seminf：求解半无限问题.conls：求解线性约束最小二乘最优解.curvefit：非线性数据拟合.leastsq：求解非线性最小二乘最优问题.nnls：求解非负约束最小二乘最优解,.,30,.,31,.,32,.,33,线性规划MATLAB程序,模型：MinZ=cTxS.t.Axbv1xv2X=lp(c,A,b,v1,v2,x0,ne,dis)v1,v2-x的下,上界X0-初始值ne-前ne个约束为等式约束dis-给出警告信息，如解无界或无可行解缺省时用占据其位置，程序将自动给出,.,34,无约束非线性规划MATLAB程序,模型：Minf（x）X=fminu(fun,x0,opt,grad,p1,p2)x,opt=fminu(fun,x0,opt,grad,p1,p2)fun-建立fun.m函数文件X0-初始值Opt-控制参数grad-建立grad.m函数文件计算梯度p1,p2-可传递到fun和grad中公用的参数（最多10个）缺省时用占据其位置，程序将自动给出,.,35,约束非线性规划MATLAB程序,模型：Minf（x）S.t.g（x）0X=constr(fun,x0,opt,v1,v2,grad,p1,p2)x,opt