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

S S T 最优化方法最优化方法 哈尔滨工业大学 尚寿亭 建模 原理 算法 S S T 教材与参考教材与参考 1 吴祈宗 . 运筹学与最优化方法 . 北京：机械工业出版社， 2003.8 2 薛嘉庆 . 最优化原理与方法（修订版） . 北京：冶金工业 出版社， 1992.8 3 解可新，韩立兴，林友联 . 最优化方法 . 天津：天津大学 出版社， 1997.1 4 萧树铁，姜启源等 . 数学实验， 北京： 高等教育出版社， 1999.7 5 邢文训，谢金星 . 现代优化计算方法 . 北京：清华大学 出 版社， 1999.8 6 胡运权，运筹学基础及应用（第三版），哈尔滨工业 大学 出版社， 1998 S S T 参考网站参考网站 1 全国大学生数学建模竞赛 网： 2 美国：数学及其应用联合会网 站 ： /undergraduate/ 3 中国数学建模网站： / 4 “中国电机工程学会杯 ”全国大学生电工 数学建模竞赛网： / S S T 最优化方法最优化方法 实际问题与建模实际问题与建模 S S T 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 S S T 建模与求解 建立模型： 设：坐标系 xoy，铁路线在 ox- 轴上，点 A 位于坐标原点 o， 点 B位于（ 150， 20） ,点 C位于（ 150， 0） ,站 D选在 x 处，运 费为 f (x)。 模型： （ min-minimize） （ 1） 其中 ： 求解：应用导数求极值 令 ，即 （ 2） 由（ 2） S S T 移项后两边开方，解得： （ 3） 由（ 2）知 x = 165 为增根（ ） x = 135 为唯一驻点 答案：站 D 应设在距 钢厂 A 135km处。 问题扩展：问题扩展： 考虑筑路、建站、装卸等费用，如何建模？ 数学建模竞赛题： 道路改造项目中碎石运输的设计 相关网站： “中国电机工程学会杯 ”全国大学生电工数学建模竞赛 / 例 2. 罐头盒问题罐头盒问题 设计圆柱形罐头盒，使用料最省。 假设： 1.不考虑折边及铁皮厚度； 2.底半径 r，高 h； 3.容积为常数 V。 r h S S T 建立最优化模型： （ 4） s.t. - subject to (满足于 ): 约束条件 令 模型（ 4）可写成 与（ 1）类似的形式 不考虑不等式约束时，模型（ 4）可用 Lagrange乘子法求解 S S T 令 求解方程组 由 r 0,及（ 6）解得 ，代入（ 5） 结论：高与直径相等时用料最省。 问题扩展：问题扩展： 侧面与底面厚度不同或造价不同，该如何设计？ 作 业 题：建立易拉罐的优化设计模型。 S S T 经典优化问题一般模型： a.无约束问题： 其中的 可省去； b.条件极值： 最优化问题一般模型： S S T 2.最优化问题实例：最优化问题实例： 例例 4. 生产计划问题生产计划问题 某工厂有 m 种资源 某一时段的数量 分别为： 可用来生产 n 种产品 每生产一单位 消耗 为 利润为 。如何安排 生产可获最大利润？ 设：计划生产设：计划生产 单位单位 建立线性规划模型建立线性规划模型 LP（ Linear Programming） Max c1x1+ c2x2+ + cnxn s. t. a11 x1+ a12x2+ + a1nxnb1 am1 x1+ am2x2+ + amnxn bm x1, x2, , xn 0 S S T 令 X = x1, x2, , xn T ; c = c1, c2, , cn T ; b = b1, b2, , bn T ; A = aij mxn LP： 问题扩展问题扩展 a. 若 c1, c2, , cn 不是固定的， c 是随机变量， 平均值 ，协方差矩阵 V 。 希望利润期望值最大且方差最小，建立多目标优化模型： S S T 问题扩展问题扩展 b. 风险投资问题（参考 98全国建模赛题 ） 将前面的产品换成投资项目，考虑投资 Aj 风险损失 qj 。 建立多目标优化模型： 化为多目标线性规划模型： S S T 例例 5. 数据拟合问题数据拟合问题 设某系统中变量 x, y 满足： y = f (x) 已获得系统数据： ( xi , yi ) , i = 1, 2 , , m 确定 f (x) 的参数，例如： 最优化模型： （最小二乘） 其中决策变量为 f (x) 的参数 S S T 例例 6. 指派问题指派问题 （ 0-1规划规划 ） S S T 例例 7. 旅行商问题旅行商问题 -TSP（ 组合优化组合优化 ） 一商人欲到一商人欲到 n 个城市推销，个城市推销， 城市城市 i 到城市到城市 j 相距相距 dij , 求走遍所有城市的最短路。求走遍所有城市的最短路。 模型：模型： S S T 计算复杂性概念计算复杂性概念 n个城市的 旅行商问题 -TSP，固定一个城市，采用枚举法需 (n-1)! 个枚举。 枚举时城市数与计算时间的关系 可以看出 27个城市时枚举法已很费时， 27个以上可采用启发 式算法 (heuristic algrithm)，参见： 5 （邢文训，谢金星 . 现代优化计算方法 . ） 问题扩展问题扩展 ：多：多 旅行商问题旅行商问题 98全国建模赛题 ： B. 灾情巡视路线 城 市 数 24 25 26 27 28 29 30 31 计算时间 1s 24s 10min 4.3h 4.9d 136.5d 10.8a 325a S S T 2000B题 钢管订购和运输 要铺设一条的输送天然气的主管道 , 如图一所 示 (见下页 )。经筛选后可以生产这种主管道钢管 的钢厂有。图中粗线表示铁路，单细线表示公路 ，双细线表示要铺设的管道 (假设沿管道或者原来 有公路，或者建有施工公路 )，圆圈表示火车站， 每段铁路、公路和管道旁的阿拉伯数字表示里程 ( 单位 km)。 为方便计， 1km主管道钢管称为 1单位钢管。 一个钢厂如果承担制造这种钢管，至少需要生产 500个单位。钢厂在指定期限内能生产该钢管的 最大数量为个单位，钢管出厂销价 1单位钢管为万 元，如下表： S S T 钢管可由铁路、公路运往铺设地点（不只是运到 点，而是管道全线）。 （ 1）请制定一个主管道钢管的订购和运输计划， 使总费用最小（给出总费用 )。 （ 2）请就（ 1）的模型分析：哪个钢厂钢管的销 价的变化对购运计划和总费用影响最大，哪个钢 厂钢管的产量的上限的变化对购运计划和总费用 的影响最大，并给出相应的数字结果。 （ 3）如果要铺设的管道不是一条线，而是一个树 形图，铁路、公路和管道构成网络，请就这种更 一般的情形给出一种解决办法，并对图二按（ 1） 的要求给出模型和结果。 S S T A1 3 2 5 80 10 10 31 20 12 42 70 10 88 10 70 62 70 30 20 20 30 450 104 301 750 606 194 205 201 680 480 300 220 210 420 500 600 3060 195 202 720 690 520 170 690 462 160 320 160 110 290 1150 1100 1200 A2 A3 A4 A5 A6A11 A711A 11 A8A11 A911A 11 A10 A11 A12 A13 A14 A15 S1 S2 S3 S4 S5 S6 S7 图一 S S T A1 3 2 5 80 10 10 31 20 12 42 70 10 88 10 70 62 70 30 20 20 30 450 104 301 750 606 194 205 201 680 480 300 220 210 420 500 600 3060 195 202 720 690 520 170 690 462 160 320 160 110 290 1150 1100 1200 A19 130 190 260 100 A2 A3 A4 A5 A6 A7 A8A1 1 A9 A10 A11 A12 A13 A14 A15 S1 S2 S3 S4 S5 S6 S7 A16 A17 A18 A20 (A21) 图二 S S T 钢管订购和运输钢管订购和运输 最优化模型最优化模型 S S T 钢管订购和运输钢管订购和运输 最优化模型最优化模型 S S T 钢管订购和运输钢管订购和运输 最优化模型最优化模型 S S T 1998A题 投资的收益和风险 市场上有 n种资产（如股票、债券、 ） Si ( i=1,n) 供投资者选择，某公司有数额为 M的一 笔相当大的资金可用作一个时期的投资。公司财 务分析人员对这 n种资产进行了评估，估算出在这 一时期内购买 Si的平均收益率为 ri，并预测出购买 Si的风险损失率为 qi。考虑到投资越分散，总的风 险越小，公司确定，当用这笔资金购买若干种资 产时，总体风险可用所投资的 Si中最大的一个风 险来度量。 购买 Si要付交易费，费率为 pi，并且当购买额不超 过给定值 ui时，交易费按购买 ui计算（不买当然无 须付费）。另外，假定同期银行存款利率是 r0, 且 既无交易费又无风险。（ r0 =5%） S S T S S T S S T S S T Matlab优化工具箱 （ Optimization toolbox） attgoal： 求解多目标优化问题 . constr： 求解约束非线性优化问题 . fmin： 求解标量非线性优化问题 . fminu,fmins：求解无约束非线性优化问题 . lp： 求解线性规划问题 . minmax： 求解最小最大问题 . qp： 求解二次规划问题 . seminf： 求解半无限问题 . conls： 求解线性约束最小二乘最优解 . curvefit： 非线性数据拟合 . leastsq： 求解非线性最小二乘最优问题 . nnls： 求解非负约束最小二乘最优解 S S T S S T S S T S S T 线性规划 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 - 给出警告信息，如解无界或无可行解 缺省时 用 占据其位置，程序将自动给出 S S T 无约束非线性规划 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个） 缺省时 用 占据其位置，程序将自动给出 S S T 约束非线性规划 MATLAB程序 模型： Min f（ x） S.t. g（