数学建模资料-运筹学--优化建模.ppt

《数学建模资料-运筹学--优化建模.ppt》由会员分享，可在线阅读，更多相关《数学建模资料-运筹学--优化建模.ppt（35页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、最优化方法,哈尔滨工业大学 尚寿亭,建模原理算法,教材与参考 1 吴祈宗. 运筹学与最优化方法. 北京：机械工业出版社， 2003.8 2 薛嘉庆. 最优化原理与方法（修订版）. 北京：冶金工业 出版社，1992.8 3 解可新，韩立兴，林友联. 最优化方法. 天津：天津大学 出版社，1997.1 4 萧树铁，姜启源等. 数学实验，北京：高等教育出版社， 1999.7 5 邢文训，谢金星. 现代优化计算方法. 北京：清华大学出 版社，1999.8 6 胡运权，运筹学基础及应用（第三版），哈尔滨工业大学 出版社，1998,参考网站,1 全国大学生数学建模竞赛网： 2 美国：数学及其应用联合会网站

2、： 3 中国数学建模网站： 4 “中国电机工程学会杯”全国大学生电工数学建模竞赛网： http:/www.cseem.org/,最优化方法 实际问题与建模,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位于（

3、150，0）,站D选在 x 处，运费为 f (x)。 模型： （min-minimize） （1） 其中： 求解：应用导数求极值 令 ，即 （2） 由（2）,移项后两边开方，解得： （3） 由（2）知 x = 165 为增根（ ） x = 135 为唯一驻点 答案：站 D 应设在距钢厂 A 135km处。 问题扩展：考虑筑路、建站、装卸等费用，如何建模？ 数学建模竞赛题：道路改造项目中碎石运输的设计 相关网站： “中国电机工程学会杯”全国大学生电工数学建模竞赛 http:/www.cseem.org/ 例2. 罐头盒问题 设计圆柱形罐头盒，使用料最省。 假设：1.不考虑折边及铁皮厚度； 2.底

4、半径 r，高 h； 3.容积为常数V。,建立最优化模型： （4） s.t. - subject to (满足于): 约束条件 令 模型（4）可写成 与（1）类似的形式 不考虑不等式约束时，模型（4）可用Lagrange乘子法求解,令 求解方程组 由 r 0,及（6）解得 ，代入（5） 结论：高与直径相等时用料最省。 问题扩展：侧面与底面厚度不同或造价不同，该如何设计？ 作 业 题：建立易拉罐的优化设计模型。,经典优化问题一般模型： a.无约束问题： 其中的 可省去； b.条件极值： 最优化问题一般模型：,2.最优化问题实例： 例4. 生产计划问题 某工厂有 m 种资源 某一时段的数量 分别为：

5、 可用来生产 n 种产品 每生产一单位 消耗 为 利润为 。如何安排 生产可获最大利润？ 设：计划生产 单位 建立线性规划模型 LP（Linear Programming） 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 mxn LP： 问题扩展 a. 若 c1, c2, , cn 不是固定的，c 是随机变量，

6、 平均值 ，协方差矩阵 V 。 希望利润期望值最大且方差最小，建立多目标优化模型：,问题扩展 b. 风险投资问题（参考98全国建模赛题） 将前面的产品换成投资项目，考虑投资 Aj 风险损失qj 。 建立多目标优化模型： 化为多目标线性规划模型：,例5. 数据拟合问题 设某系统中变量 x, y 满足： y = f (x) 已获得系统数据： ( xi , yi ) , i = 1, 2 , , m 确定 f (x) 的参数，例如： 最优化模型： （最小二乘） 其中决策变量为f (x) 的参数,例6. 指派问题（0-1规划）,例7. 旅行商问题-TSP（组合优化） 一商人欲到 n 个城市推销， 城市

7、 i 到城市 j 相距 dij , 求走遍所有城市的最短路。 模型：,计算复杂性概念 n个城市的旅行商问题-TSP，固定一个城市，采用枚举法需 (n-1)! 个枚举。 枚举时城市数与计算时间的关系 可以看出27个城市时枚举法已很费时，27个以上可采用启发式算法(heuristic algrithm)，参见： 5 （邢文训，谢金星. 现代优化计算方法. ） 问题扩展 ：多旅行商问题 98全国建模赛题 ： B. 灾情巡视路线,2000B题 钢管订购和运输 要铺设一条的输送天然气的主管道, 如图一所示(见下页)。经筛选后可以生产这种主管道钢管的钢厂有。图中粗线表示铁路，单细线表示公路，双细线表示要铺

8、设的管道(假设沿管道或者原来有公路，或者建有施工公路)，圆圈表示火车站，每段铁路、公路和管道旁的阿拉伯数字表示里程(单位km)。 为方便计，1km主管道钢管称为1单位钢管。 一个钢厂如果承担制造这种钢管，至少需要生产500个单位。钢厂在指定期限内能生产该钢管的最大数量为个单位，钢管出厂销价1单位钢管为万元，如下表：,钢管可由铁路、公路运往铺设地点（不只是运到点，而是管道全线）。 （1）请制定一个主管道钢管的订购和运输计划，使总费用最小（给出总费用)。 （2）请就（1）的模型分析：哪个钢厂钢管的销价的变化对购运计划和总费用影响最大，哪个钢厂钢管的产量的上限的变化对购运计划和总费用的影响最大，并给

9、出相应的数字结果。 （3）如果要铺设的管道不是一条线，而是一个树形图，铁路、公路和管道构成网络，请就这种更一般的情形给出一种解决办法，并对图二按（1）的要求给出模型和结果。,钢管订购和运输最优化模型,钢管订购和运输最优化模型,钢管订购和运输最优化模型,1998A题 投资的收益和风险 市场上有n种资产（如股票、债券、）Si ( i=1,n) 供投资者选择，某公司有数额为M的一笔相当大的资金可用作一个时期的投资。公司财务分析人员对这n种资产进行了评估，估算出在这一时期内购买Si的平均收益率为ri，并预测出购买Si的风险损失率为qi。考虑到投资越分散，总的风险越小，公司确定，当用这笔资金购买若干种资

10、产时，总体风险可用所投资的Si中最大的一个风险来度量。 购买Si要付交易费，费率为pi，并且当购买额不超过给定值ui时，交易费按购买ui计算（不买当然无须付费）。另外，假定同期银行存款利率是r0, 且既无交易费又无风险。（ r0 =5%）,Matlab优化工具箱（Optimization toolbox）,attgoal： 求解多目标优化问题. constr： 求解约束非线性优化问题. fmin： 求解标量非线性优化问题. fminu,fmins：求解无约束非线性优化问题. lp： 求解线性规划问题. minmax： 求解最小最大问题. qp： 求解二次规划问题. seminf： 求解半无限问

11、题. conls： 求解线性约束最小二乘最优解. curvefit： 非线性数据拟合. leastsq： 求解非线性最小二乘最优问题. nnls： 求解非负约束最小二乘最优解,线性规划MATLAB程序,模型： Min Z = cTx S.t. Ax b v1 x v2 X=lp (c,A,b,v1,v2, x0,ne,dis) v1,v2- x 的下,上界 X0 - 初始值 ne - 前 ne 个约束为等式约束 dis - 给出警告信息，如解无界或无可行解 缺省时 用 占据其位置，程序将自动给出,无约束非线性规划MATLAB程序,模型： Min f（x） X=fminu (fun,x0,opt

12、,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） 0 X=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个） 缺省时 用 占据其位置，程序将自动给出,