《【课件】优化模型及算法》由会员分享，可在线阅读，更多相关《【课件】优化模型及算法（48页珍藏版）》请在金锄头文库上搜索。
1、优化模型及算法 北京化工大学理学院数学系闫白鹭 1 2 UnloadingCommuterTrains 写作思路参数 敏感性分析 车厢数目 站台长度 确定优化模型的三大要素 目标函数 决策变量 约束条件用数学工具表示 会涉及到做一些合理的假设 求出结果后要做些定性定量分析 3 一个简单案例1995年全国大学生数学建模竞赛A题2000年全国大学生数学建模竞赛B题2015年全国研究生数学建模竞赛F题 4 一个简单案例 飞机的精确定位问题 5 0 y x VOR2x 629 y 375 309 00 1 30 864 3 2 0 飞机x y VOR1x 764 y 1393 161 20 0 80
2、VOR3x 1571 y 259 45 10 0 60 北 DMEx 155 y 987 飞机与监控台 图中坐标和测量距离的单位是 公里 例 飞机的精确定位问题 飞机的精确定位模型 飞机的精确定位模型 第1类模型 不考虑误差因素 超定方程组 非线性最小二乘 量纲不符 飞机的精确定位模型 第2类模型 考虑误差因素 作为硬约束 Minx Miny Maxx Maxy 以距离为约束 优化角度误差之和 或平方和 或以角度为约束 优化距离误差 非线性规划 仅部分考虑误差 角度与距离的 地位 不应不同 有人也可能会采用其他目标 如 误差非均匀分布 飞机的精确定位模型 误差一般服从什么分布 正态分布 不同的
3、量纲如何处理 无约束非线性最小二乘模型 归一化处理 飞机坐标 978 31 723 98 误差平方和0 6685 4 角度需要进行预处理 如利用Matlab的atan2函数 值域 pi pi 第3类模型 考虑误差因素 作为软约束 且归一化 1995年全国大学生数学建模竞赛A题 一个飞行管理问题 11 一个飞行管理问题 在约10000m高空的某边长160km的正方形区域内 经常有若干架飞机作水平飞行 区域内每架飞机的位置和速度向量均由计算机记录其数据 以便进行飞行管理 当一架欲进入该区域的飞机到达边界区域边缘时 记录其数据后 要立即计算并判断是否会与其区域内的飞机发生碰撞 如果会碰撞 则应计算如
4、何调整各架 包括新进入的 飞机飞行的方向角 以避免碰撞 现假设条件如下 1 不碰撞的标准为任意两架飞机的距离大于8km 2 飞机飞行方向角调整的幅度不应超过30度 3 所有飞机飞行速度均为每小时为800km 4 进入该区域的飞机在到达区域边缘时 与区域内飞机的距离应在60km以上 5 最多考虑6架飞机 6 不必考虑飞机离开此区域后的状况 12 请你对这个避免碰撞的飞行管理问题建立数学模型 列出计算步骤 对以下数据进行计算 方向角误差不超过0 01度 要求飞机飞行方向角调整的幅度尽量小 设该区域4个顶点坐标为 0 0 160 0 160 160 0 160 记录数据为 飞机编号横坐标x纵坐标y方
5、向角 度 1150140243285852363150155220 54145501595130150230新进入0052注 方向角指飞行方向与x轴正向的夹角 13 两架飞机不碰撞的条件 0 t Tij Ti为第i架飞机飞出区域的时刻 不碰撞条件 初始位置时刻t飞机的位置两架飞机的距离 平方 14 不必考虑在区域外的碰撞两架飞机都在区域中的时间 具体来看 第i架飞机在区域内的时间 飞机飞出区域的时刻 15 整理 fij t 的最小值 bij2 4 cij 此时 其中 16 不碰撞条件的等价表述 最后 优化模型为 fij t 大于等于 肯定成立 fij t 大于等于 等价于 fij t 大于等于
6、 等价于 17 2000年全国大学生数学建模竞赛B题 钢管订购与运输 18 问题描述 19 钢厂的产量和销价 1单位钢管 1km管道钢管 钢厂产量的下限 500单位钢管 1单位钢管的公路运价 0 1万元 km 不足整公里部分按整公里计 20 1 制定钢管的订购和运输计划 使总费用最小 2 分析对购运计划和总费用影响 哪个钢厂钢管销价的变化影响最大 哪个钢厂钢管产量上限的变化影响最大 3 讨论管道为树形图的情形 21 问题1的基本模型和解法 总费用最小的优化问题 总费用 订购 运输 由各厂Si经铁路 公路至各点Aj i 1 7 j 1 15 铺设管道AjAj 1 j 1 14 由Si至Aj的最小
7、购运费用路线及最小费用cij由Si至Aj的最优运量xij由Aj向AjAj 1段铺设的长度yj及向AjAj 1段铺设的长度zj 最优购运计划 约束条件 钢厂产量约束 上限和下限 如果生产的话 运量约束 xij对i求和等于zj加yj zj与yj 1之和等于AjAj 1段的长度lj yjzj Aj 1AjAj 1 22 基本模型 由Aj向AjAj 1段铺设的运量为1 yj yj yj 1 2由Aj向AjAj 1段铺设的运量为1 zj zj zj 1 2 二次规划 23 求解步骤 1 求由Si至Aj的最小购运费用路线及最小费用cij 难点 公路运费是里程的线性函数 而铁路运费是里程的分段阶跃函数 故总
8、运费不具可加性 因而计算最短路常用的Dijkstra算法 Floyd算法失效 A1 需要对铁路网和公路网进行预处理 才能使用常用算法 得到最小购运费用路线 至少求3次最短路 如S7至A10的最小费用路线 先铁路1130km 再公路70km 运费为77 万元 先公路 经A15 40km 再铁路1100km 再公路70km 运费为76 万元 24 任意两点之间最短路的Floyd Warshall算法 1 求由Si至Aj的最小购运费用路线及最小费用cij A1 uij k 是任意两个节点i j之间距离的临时标号 即从节点i到j但不允许经过其他节点k k 1 n时的最短距离 25 fi表示钢厂i是否使
9、用 xij是从钢厂i运到节点j的钢管量yj是从节点j向左铺设的钢管量 zj是向右铺设的钢管量 比较好的方法 引入0 1变量 yjzj Aj 26 论文中发现的主要问题 1 针对题目给的数据用凑的方法算出结果 没有解决这类问题的一般模型 2 局部最优 如将管道分为左右两段 分别寻求方案 如将问题分为购运和铺设两部分 分别寻优 会导致每段管道都从两端铺到中点 4 由Si至Aj的最小购运费用路线及最小费用cij不对 5 数字结果相差较大 如最小费用应127 5至128 2亿元 2015年全国研究生数学建模竞赛F题 旅游路线规划问题 28 附件1提供了国家旅游局公布的201个5A级景区名单 一位自驾游
10、爱好者拟按此景区名单制定旅游计划 该旅游爱好者每年有不超过30天的外出旅游时间 每年外出旅游的次数不超过4次 每次旅游的时间不超过15天 基于个人旅游偏好确定了在每个5A级景区最少的游览时间 见附件1 基于安全考虑 行车时间限定于每天7 00至19 00之间 每天开车时间不超过8小时 在每天的行程安排上 若安排全天游览则开车时间控制在3小时内 安排半天景点游览 开车时间控制在5小时内 在高速公路上的行车平均速度为90公里 小时 在普通公路上的行车平均速度为40公里 小时 该旅游爱好者计划在每一个省会城市至少停留24小时 以安排专门时间去游览城市特色建筑和体验当地风土人情 不安排景区浏览 景区开
11、放时间统一为8 00至18 00 请考虑下面问题 29 30 在行车线路的设计上采用高速优先的策略 即先通过高速公路到达与景区邻近的城市 再自驾到景区 附件1给出了各景区到相邻城市的道路和行车时间参考信息 附件2给出了国家高速公路相关信息 附件3给出了若干省会城市之间高速公路路网相关信息 请设计合适的方法 建立数学模型 以该旅游爱好者的常住地在西安市为例 规划设计旅游线路 试确定游遍201个5A级景区至少需要几年 给出每一次旅游的具体行程 每一天的出发地 行车时间 行车里程 游览景区 若有必要 其他更详细表达请另列附件 31 TSP问题 哈密顿圈 会发现直接游玩34个省级行政区时间远远超过15
12、天 因此势必需要分开游玩 即需要回到出发点重新出发 32 VRP问题 33 34 35 Matlab求解非线性规划MatlabGA算法工具箱MatlabPSO算法工具箱 36 37 例 s t 建立M文件fun4 m 定义目标函数 functionf fun4 x f exp x 1 4 x 1 2 2 x 2 2 4 x 1 x 2 2 x 2 1 建立M文件mycon m定义非线性约束 function g ceq mycon x g x 1 x 2 1 5 x 1 x 2 x 1 x 2 x 1 x 2 10 主程序youh3 m为 X0 1 1 A b Aeq 11 beq 0 vlb
13、 vub x fval fmincon fun4 x0 A b Aeq beq vlb vub mycon 试着求解ppt第10页的目标函数 MatlabGA算法工具箱 38 MatlabGA算法工具箱 39 MatlabGA算法工具箱 functionf GA demo x f1 4 x 1 3 4 x 1 x 2 2 x 2 2 42 x 1 14 f2 4 x 2 3 4 x 1 x 2 2 x 1 2 26 x 1 22 f f1 2 f2 2 40 MatlabGA算法工具箱 clearclcfitnessfcn GA demo 适应度函数句柄nvars 2 个体的变量数目optio
14、ns gaoptimset PopulationSize 100 EliteCount 10 CrossoverFraction 0 75 Generations 500 StallGenLimit 500 TolFun 1e 100 PlotFcns gaplotbestf gaplotbestindiv 参数设置 x best fval ga fitnessfcn nvars options 调用ga函数 41 MatlabGA算法工具箱 42 functionz test func in nn size in fork 1 nn 2 x k in k endnx nn 1 ny nn 2
15、 fori 1 nxrec fun 0 forj 1 ny 1rec fun rec fun 100 x i j 1 x i j 2 2 x i j 1 2 endz i rec fun end MatlabGA算法工具箱求解0 1规划 43 WW 120 背包的容量限制P 30 60 25 8 10 40 60 W 40 40 30 5 15 35 30 7种物品 背包问题 MatlabPSO算法工具箱 44 基于粒子群工具箱的函数优化算法 清空环境clearclc 参数初始化x range 50 50 参数x变化范围y range 50 50 参数y变化范围range x range y
16、range 参数变化范围 组成矩阵 Max V 0 2 range 2 range 1 最大速度取变化范围的10 20 n 2 待优化函数的维数 此例子中仅x y两个自变量 故为2PSOparams 25200024220 90 415001e 25250NaN00 粒子群寻优pso Trelea vectorized test func n Max V range 0 PSOparams 调用PSO核心模块 MatlabPSO算法工具箱 45 PSOparams 25200024220 90 415001e 25250NaN00 pso Trelea vectorized test func n Max V range 0 PSOparams 46 PSOparams 25200024220 90 415001e 25250NaN00 pso Trelea vectorized test func n Max V range 0 PSOparams 47 谢谢大家 48
