数学建模竞赛中的部分优化问题.ppt

优 化 建 模 优化建模与LINDO/LINGO软件 数学建模竞赛中的部分优化问题 优 化 建 模 简要提纲 1. CUMCM-1995A: 一个飞行管理问题 2. CUMCM-2000B: 钢管订购与运输 3. CUMCM-2003B：露天矿生产的车辆安排 4. CUMCM-2000D: 空洞探测 优 化 建 模 1995年全国大学生数学建模竞赛A题 一个飞行管理问题 优 化 建 模 一个飞行管理问题 在约10000m高空的某边长160km的正方形区域内,经常有若干架 飞机作水平飞行,区域内每架飞机的位置和速度向量均由计算机 记录其数据,以便进行飞行管理.当一架欲进入该区域的飞机到达 边界区域边缘时, 记录其数据后,要立即 计算并判断是否会与其 区域内的飞机发生碰撞.如果会碰撞 ,则应计算如何调整各架(包 括新进入的)飞机飞行的方向角,以避免碰撞.现假设条件如下: 1) 不碰撞的标准为任意两架飞机的距离大于8km; 2)飞机飞行方向角调整的幅度不应超过30度; 3)所有飞机飞行速度均为每小时为800km; 4)进入该区域的飞机在到达区域边缘时,与区域内飞机的距 离应在 60km以上; 5)最多考虑6架飞机; 6)不必考虑飞机离开此区域后的状况; 优 化 建 模 请你对这个避免碰撞的飞行管理问题建立数学模型.列出计算步骤, 对以下数据进行计算(方向角误差不超过0.01度),要求飞机飞行方向 角调整的幅度尽量小 . 设该区域4个顶点坐标为(0,0),(160,0),(160,160),(0,160).记录数据为: 飞机编号 横坐标x 纵坐标y 方向角(度) 1 150 140 243 2 85 85 236 3 150 155 220.5 4 145 50 159 5 130 150 230 新进入 0 0 52 注: 方向角指飞行方向与x轴正向的夹角 优 化 建 模 两架飞机不碰撞的条件 （0 t Tij） Ti为第i架飞机飞出区域的时刻 不碰撞条件 初始位置 时刻t飞机的位置 两架飞机的距离（平方） 优 化 建 模 不必考虑在区域外的碰撞 两架飞机都在区域中的时间 具体来看，第i架飞机在区域内的时间 飞机飞出区域的时刻 优 化 建 模 整理： fij(t)的最小值 (- bij2 / 4 + cij ) ；此时 其中： 优 化 建 模 不碰撞条件的等价表述 最后，优化模型为 fij(t) 大于等于肯定成立 fij(t) 大于等于等价于 fij(t) 大于等于等价于 优 化 建 模 LINGO求解 程序exam1201a.lg4 一个简化的数学模型 任何一架飞机在区域中停留最长时间 放松到任两架飞机在这段时间不碰撞 甚至放松到任两架飞机永远不碰撞 优 化 建 模 其他目标 调整后的方向角 总的调整量最小 最大调整量最小 初始位置与方向角 优 化 建 模 基于相对运动观点的模型 优 化 建 模 基于相对运动观点的模型 优 化 建 模 于是 数学规划模型 优 化 建 模 LINGO求解 程序exam1201b.lg4 注意：应先计算出初始时刻的ij 优 化 建 模 2000年全国大学生数学建模竞赛B题 钢管订购与运输 优 化 建 模 问题描述 由钢管厂订购钢管，经铁 路、公路运输，铺设一条 钢管管道 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 306 195 202 720 690 520 170 690 462 160 320 160 110 290 1150 1100 1200 A2 A3 A4 A5 A6 A7 A8 A9 A10 A11 A12 A13 A14 A15 S1 S2 S3 S4 S5 S6 S7 管道 铁路 公路 S1S7 钢管厂 火车站 450 里程（km) （沿管道建有公路） 优 化 建 模 钢厂的产量和销价（1单位钢管=1km管道钢管） 钢厂产量的下限：500单位钢管 1单位钢管的铁路运价 1000km以上每增加1至100km运价增加5万元 1单位钢管的公路运价：0.1万元/km（不足整公里部分按整公里计） 优 化 建 模 （1）制定钢管的订购和运输计划，使总费用最小. （2）分析对购运计划和总费用影响：哪个钢厂钢管销价的 变化影响最大；哪个钢厂钢管产量上限的变化影响最大？ 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 306 195 202 720 690 520 170 690 462 160 320 160 110 290 1150 1100 1200 A2 A3 A4 A5 A6 A7 A8 A9 A10 A11 A12 A13 A14 A15 S1 S2 S3 S4 S5 S6 S7 A16 130 A17 A18 A19 A20 A21 190 260 100 （3）讨论管道为树形图的情形 优 化 建 模 问题1的基本模型和解法总费用最小的优化问题 总费用：订购，运输（由各厂Si经铁路、公路至各点Aj, i=1,7; j=1, 15 ），铺设管道Aj Aj+1 （j=1, 14) 由Si至Aj的最小购运费用路线及最小费用cij 由Si至Aj的最优运量xij 由Aj向Aj Aj-1段铺设的长度yj及向Aj Aj+1段铺设的长度zj 最优购运计划 约束 条件 钢厂产量约束：上限和下限（如果生产的话） 运量约束：xij对i求和等于zj 加yj； zj与 yj+1之和等于Aj Aj+1段的长度lj yj zj Aj-1 Aj Aj+1 优 化 建 模 基本模型 由Aj向Aj Aj-1段铺设的运量为 1+ +yj= yj( yj+1)/2 由Aj向Aj Aj+1段铺设的运量为 1+ +zj= zj( zj+1)/2 二次规划? 优 化 建 模 求解步骤 1）求由Si至Aj的最小购运费用路线及最小费用cij 难点：公路运费是里程的线性函数，而铁路运费是里 程的分段阶跃函数，故总运费不具可加性。因而计算 最短路常用的Dijkstra算法、Floyd算法失效。 A1 70 10 88 10 70 62 70 30 20 20 30 300 220 210 420 500 170 690 462 160 320 160 110 290 A10 A11 A12 A13 A14 A15 S4 S5 S6 S7 需要对铁路网和公路网进行预处理，才能使用常用 算法，得到最小购运费用路线。- 至少求3次最短路 如S7至A10的最小费用路线 先铁路1130km，再公路 70km, 运费为77（万元） 先公路（经A15）40km, 再 铁路1100km，再公路 70km, 运费为76（万元） 优 化 建 模 任意两点之间最短路的Floyd-Warshall算法 1）求由Si至Aj的最小购运费用路线及最小费用cij A1 3次最短路的LINGO程序： Exam1202a.lg4 Exam1202b.lg4 Exam1202c.lg4 uij(k) 是任意两个节点i，j之间距离的临时标号，即从节点i 到j但不允许经过其他节点k，k+1，, n时的最短距离 优 化 建 模 实际上只有S4和S7需要分解成子问题求解 每个子问题是标准 的二次规划，决策 变量为xij,yj,zj, 不超 过135个 。 优 化 建 模 fi表示钢厂i是否使用；xij是从钢厂i运到节点j的钢管量 yj是从节点j向左铺设的钢管量；zj是向右铺设的钢管量 c) 比较好的方法：引入0-1变量 LINDO/LINGO 得到的结果比 matlab得到的好 exam1202d.lg4 yj zj Aj 优 化 建 模 问题2: 分析对购运计划和总费用影响(哪个钢厂销价变 化影响最大；哪个钢厂产量上限变化影响最大) 规划问题的灵敏度分析 问题3：管道为树形图 70 10 88 10 70 62 300 220 210 170 690 462 160 320 160 A10 A11 A12 S4 S5 S6 130 A17 A18 A19 A20 190 260 100 (jk)是连接Aj,Ak的边，E是树形图的边集， ljk是 (jk)的长度， yjk是由Aj沿(jk)铺设的钢管数量 优 化 建 模 2003年全国大学生数学建模竞赛B题 露天矿生产的车辆安排 优 化 建 模 露天矿里铲位已分成矿石和岩石: 平均铁含量不低于 25%的为矿石，否则为岩石。每个铲位的矿石、岩石数 量，以及矿石的平均铁含量（称为品位）都是已知的。 每个铲位至多安置一台电铲，电铲平均装车时间5分钟 卡车在等待时所耗费的能量也是相当可观的，原则上 在安排时不应发生卡车等待的情况。 露天矿生产的车辆安排 矿石卸点需要的铁含量要求都为29.5%1%(品位限制） ，搭配量在一个班次（8小时）内满足品位限制即可。 卸点在一个班次内不变。卡车载重量为154吨，平均时 速28km,平均卸车时间为3分钟。 问题：出动几台电铲，分别在哪些铲位上；出动几辆 卡车，分别在哪些路线上各运输多少次 ? 优 化 建 模 平面示意图 优 化 建 模 问题数据 距离铲位1铲位2铲位3铲位 4 铲位5铲位6铲位7铲位8铲位9铲位10 矿石漏5.265.194.214.002.952.742.461.900.641.27 倒装1.900.991.901.131.272.251.482.043.093.51 岩场5.895.615.614.563.513.652.462.461.060.57 岩石漏0.641.761.271.832.742.604.213.725.056.10 倒装4.423.863.723.162.252.810.781.621.270.50 铲位1铲位2铲位3铲位 4 铲位5铲位6铲位7铲位8铲位9铲位10 矿石量 095105100105110125105130135125 岩石量 125110135105115135105115135125 铁含量30%28%29%32%31%33%32%31%33%31% 优 化 建 模 问题分析 与典型的运输问题明显有以下不同： 1. 这是运输矿石与岩石两种物资的问题； 2. 属于产量大于销量的不平衡运输问题； 3. 为了完成品位约束，矿石要搭配运输； 4. 产地、销地均有单位时间的流量限制； 5. 运输车辆只有一种，每次满载运输，154吨/车次； 6. 铲位数多于铲车数意味着要最优的选择不多于7个 产地作为最后结果中的产地； 7. 最后求出各条路线上的派出车辆数及安排。 近似处理： 先求出产位、卸点每条线路上的运输量(MIP模型) 然后求出各条路线上的派出车辆数及安排 优 化 建 模 模型假设 卡车在一个班次中不应发生等待或熄火后再启动 的情况； 在铲位或卸点处由两条路线以上造成的冲突问题 面前，我们认为只要平均时间能完成任务，就认 为不冲突。我们不排时地进行讨论； 空载与重载的速度都是28km/h，耗油相差很大； 卡车可提前退出系统，等等。 如理解为严格不等待，难以用数学规划模型来解 个别参数队找到了可行解 （略） 优 化 建 模 符号 xij ：从i铲位到j号卸点的石料运量 （车） 单位： 吨； cij ：从i号铲位到j号卸点的距离 公里； Tij :从i号铲位到号j卸点路线上运行一个周期平均时间 分； Aij ：从号铲位到号卸点最多能同时运行的卡车数 辆； Bij ：从号铲位到号卸点路线上一辆车最多可运行的次数 次； pi：i号铲位的矿石铁含量 p=(30,28,29,32,31,33,32,31,33,31) % qj : j号卸点任务需求，q=(1.2,1.3,1.3,1.9,1.3)*10000 吨 cki ：i号铲位的铁矿石储量 万吨 cyi ：i号铲位的岩石储量 万吨 fi :描述第i号铲位是否使用的0-1变量，取1为使用；0为关闭。 (近似 ) 优 化 建 模 优化模型 （1）道路能力(卡车数)约束 （2）电铲能力约束 （3）卸点能力约束 （4）铲位储量约束 （5）产量任务约束 （6）铁含量约束 （7）电铲数量约束 （8）整数约束 . xij为非负整数 fi 为0-1整数 优 化 建 模 计算结果（LINGO软件） 铲位 1 铲位2铲位3铲位4铲位5铲位 6 铲位7铲位8铲位9铲位10 矿漏135411 倒4243 岩场7015 岩漏8143 倒13270 铲位1铲位2铲位3铲位4铲位5铲位6铲位7铲位8铲位9铲位10 矿石漏 0.8671.8620.314 倒场 1.0771.162 岩场 1.8920.326 岩石漏 1.8411.229 倒场 0.6840.11.489 exam1203.lg4 注: LINGO8.0本来是可以得到最优解的，但有些 LINGO8.0可能出现系统错误, 可能是系统BUG 优 化 建 模 计算结果（派车） 铲位1铲位2铲位3铲位4铲位5铲位6铲位7铲位8铲位9铲位10 矿石漏 1 (2 9) 倒场 1 (3 9) 1 (3 7) 岩场 1 (3 7) 岩石漏 1(44)1 (3 5) 倒场 1 (4 7) 结论： 铲位1、2、3、4、8、9、10处各放置一台电铲。 一共使用了13辆卡车；总运量为85628.62吨公里； 岩石产量为32186吨；矿石产量为38192吨。 此外：6辆联合派车（方案略） 优 化 建 模 最大化产量 结论： （略） 目标函数变化 此外：车辆数量（20辆）限制（其实上面的模型也 应该有） 优 化 建 模 2000年全国大学生数学建模竞赛D题 空洞探测 优 化 建 模 山体隧道坝体等的某些内部结构可用弹性波 测量来确定。简化问题可叙述为， 一块均匀介质构成的矩形平板内有一些充满 空气的空洞。 在平板的两个邻边分别等距地设置若干波源 ，在他们的对边对等地安放同样多的接收 器，记录弹性波由每个波源到达对边上每 个接收器的时间。 根据弹性波在介质和在空气中不同的传播速 度来确定板内空洞的位置 优 化 建 模 具体问题： 一块240(米)240(米)的平板ABCD， 在AB 边等距地设置7个波源Pi (i=1,7),在 CD 边 等距地设置7个接收器Qj (j=1,7), 记录由 Pi 发出 的弹性波到达 Qj 的时间 tij(秒) ; 在AD 边等距地设置7个波源 Ri (i=1,7),在 BC 边 等距地设置7个接收器Sj (j=1,7), 记录由 Ri 发出 的弹性波到达 Sj 的时间 ij(秒)。 已知弹性波在介质和空气中的传播速度分别为 2880(米/秒)和320(米/秒), 且弹性波沿板边缘的传播速度与在介质中的传播速 度相同 优 化 建 模 P2 Q4 R3 S6 优 化 建 模 TP=(tij) tij Q1 Q2 Q3 Q4 Q5 Q6 Q7 P1 .0611 .0895 .1996 .2032 .4181 .4923 .5646 P2 .0989 .0592 .4413 .4318 .4770 .5242 .3805 P3 .3052 .4131 .0598 .4153 .4156 .3563 .1919 P4 .3221 .4453 .4040 .0738 .1789 .0740 .2122 P5 .3490 .4529 .2263 .1917 .0839 .1768 .1810 P6 .3807 .3177 .2364 .3064 .2217 .0939 .1031 P7 .4311 .3397 .3566 .1954 .0760 .0688 .1042 优 化 建 模 TR=(ij) ij S1 S2 S3 S4 S5 S6 S7 R1 .0645 .0602 .0813 .3516 .3867 .4314 .5721 R2 .0753 .0700 .2852 .4341 .3491 .4800 .4980 R3 .3456 .3205 .0974 .4093 .4240 .4540 .3112 R4 .3655 .3289 .4247 .1007 .3249 .2134 .1017 R5 .3165 .2509 .3214 .3256 .0904 .1874 .2130 R6 .2749 .3891 .5895 .3016 .2058 .0841 .0706 R7 .4434 .4919 .3904 .0786 .0709 .0914 .0583 优 化 建 模 要求： (1) 确定该平面内空洞的位置。 (2) 只根据Pi发出的弹性波到达Qj的时间tij 能确定空洞的位置吗？讨论在同样能够 确定空洞位置的前提下，减少波源和接 收器的方法。 优 化 建 模 分析: 弹性波沿平板边缘的理论传播时间 t=240/2880=0.0833(秒) 弹性波沿平板边缘的实际传播时间 t11=.0611, t77=.1042, 11=.0645, 77=.0583 题目中已假设“弹性波沿板边缘的传播速度与 在介质中的传播速度相同” 观测数据的最大绝对误差为d=0.025秒. 可以认为，0.025*360 =9(米）以下的空洞是探 测不出的 优 化 建 模 假设 1. 观测数据有测量误差。观测数据 除测量误差外是可靠的。 2. 波在传播过程中沿直线单向传播 ，且不考虑波的反射、折射以及干 涉等现象。 3.空气密度和介质密度都均匀 优 化 建 模 4.“弹性波”在传播过程中没有能量损失。 其波速仅与介质有关，且在同一均匀介 质中波速不变。弹性波沿板边缘的传播 速度与在介质中的传播速度相同。 5.假设平板可划分化为网格，空洞定位于 每个网格单元内,空洞大小大致相同. 优 化 建 模 波线与网格交线长度的计算 (k,l) 记波源Pi与接收器Qj 决定的 波线与每个单元（k，l） 的交线长度为bijkl i=j 时 123456 6 5 4 3 2 1 优 化 建 模 波线与网格交线长度的计算 PiQj 决定的直线方程： (j - i）y = 6(x-40(i-1) i=j 以外的情况 单元(k,l)左边缘直线方程 x = 40(k-1) 波线与单元(k,l)左边缘对应交点的y坐标为 y1ijkl = 240(k-i)/(j-i)， 其中 l-1 6(k-i)/(j-i) l (k,l) 优 化 建 模 波线与网格交线长度的计算 PiQj 决定的直线方程： (j - i）y = 6(x-40(i-1) i=j 以外的情况 单元(k,l)右边缘直线方程 x = 40k 波线与单元(k,l)右边缘对应交点的y坐标为 y2ijkl = 240(k+1-i)/(j-i)， 其中 l-1 6(k+1-i)/(j-i) l (k,l) 优 化 建 模 波线与网格交线长度的计算 PiQj 决定的直线方程： (j - i）y = 6(x-40(i-1) i=j 以外的情况 单元(k,l)