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