《优化建模与LINGO第12章 数学建模竞赛中的部分优化问题课件》由会员分享，可在线阅读，更多相关《优化建模与LINGO第12章 数学建模竞赛中的部分优化问题课件（58页珍藏版）》请在金锄头文库上搜索。
1、优化建模与LINDO/LINGO软件 第12章数学建模竞赛中的部分优化问题,原书相关信息 谢金星, 薛毅编，清华大学出版社, 2005年7月出版. ,简要提纲,1. CUMCM-1995A: 一个飞行管理问题 2. CUMCM-2000B: 钢管订购与运输 3. CUMCM-2003B：露天矿生产的车辆安排 4. CUMCM-2000D: 空洞探测,1995年全国大学生数学建模竞赛A题,一个飞行管理问题,一个飞行管理问题,在约10000m高空的某边长160km的正方形区域内,经常有若干架飞机作水平飞行,区域内每架飞机的位置和速度向量均由计算机记录其数据,以便进行飞行管理.当一架欲进入该区域的飞
2、机到达边界区域边缘时, 记录其数据后,要立即 计算并判断是否会与其区域内的飞机发生碰撞.如果会碰撞 ,则应计算如何调整各架(包括新进入的)飞机飞行的方向角,以避免碰撞.现假设条件如下: 1) 不碰撞的标准为任意两架飞机的距离大于8km; 2)飞机飞行方向角调整的幅度不应超过30度; 3)所有飞机飞行速度均为每小时为800km; 4)进入该区域的飞机在到达区域边缘时,与区域内飞机的距离应在 60km以上; 5)最多考虑6架飞机; 6)不必考虑飞机离开此区域后的状况;,请你对这个避免碰撞的飞行管理问题建立数学模型.列出计算步骤,对以下数据进行计算(方向角误差不超过0.01度),要求飞机飞行方向角调
3、整的幅度尽量小 . 设该区域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架飞机在区域内的时间,飞机飞出区域的
4、时刻,整理：,fij(t)的最小值 (- bij2 / 4 + cij ) ；此时,其中：,不碰撞条件的等价表述,最后，优化模型为,fij(t)大于等于肯定成立,fij(t)大于等于等价于,fij(t)大于等于等价于,LINGO求解,程序exam1201a.lg4,一个简化的数学模型 任何一架飞机在区域中停留最长时间,放松到任两架飞机在这段时间不碰撞 甚至放松到任两架飞机永远不碰撞,其他目标,调整后的方向角,总的调整量最小,最大调整量最小,初始位置与方向角,基于相对运动观点的模型,基于相对运动观点的模型,于是,数学规划模型,LINGO求解,程序exam1201b.lg4,注意：应先计算出初始时
5、刻的ij,2000年全国大学生数学建模竞赛B题,钢管订购与运输,问题描述,钢厂的产量和销价（1单位钢管=1km管道钢管）,钢厂产量的下限：500单位钢管,1单位钢管的公路运价：0.1万元/km（不足整公里部分按整公里计）,（1）制定钢管的订购和运输计划，使总费用最小.,（2）分析对购运计划和总费用影响：哪个钢厂钢管销价的变化影响最大；哪个钢厂钢管产量上限的变化影响最大？,（3）讨论管道为树形图的情形,问题1的基本模型和解法,总费用最小的优化问题,总费用：订购，运输（由各厂Si经铁路、公路至各点Aj, i=1,7; j=1, 15 ），铺设管道Aj Aj+1 （j=1, 14),由Si至Aj的最
6、小购运费用路线及最小费用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,难点：公路运费是里程的线
7、性函数，而铁路运费是里程的分段阶跃函数，故总运费不具可加性。因而计算最短路常用的Dijkstra算法、Floyd算法失效。,A1,需要对铁路网和公路网进行预处理，才能使用常用算法，得到最小购运费用路线。- 至少求3次最短路,如S7至A10的最小费用路线,先铁路1130km，再公路70km, 运费为77（万元）,先公路（经A15）40km, 再铁路1100km，再公路70km, 运费为76（万元）,任意两点之间最短路的Floyd-Warshall算法,1）求由Si至Aj的最小购运费用路线及最小费用cij,A1,3次最短路的LINGO程序： Exam1202a.lg4 Exam1202b.lg4
8、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得到的好,yj zj,Aj,问题2: 分析对购运计划和总费用影响(哪个钢厂销价变化影响最大；哪个钢厂产量上限变化影响最大),规划问题
9、的灵敏度分析,问题3：管道为树形图,(jk)是连接Aj,Ak的边，E是树形图的边集， ljk是(jk)的长度， yjk是由Aj沿(jk)铺设的钢管数量,2003年全国大学生数学建模竞赛B题,露天矿生产的车辆安排,露天矿里铲位已分成矿石和岩石: 平均铁含量不低于25%的为矿石，否则为岩石。每个铲位的矿石、岩石数量，以及矿石的平均铁含量（称为品位）都是已知的。每个铲位至多安置一台电铲，电铲平均装车时间5分钟,卡车在等待时所耗费的能量也是相当可观的，原则上在安排时不应发生卡车等待的情况。,露天矿生产的车辆安排,矿石卸点需要的铁含量要求都为29.5%1%(品位限制），搭配量在一个班次（8小时）内满足品
10、位限制即可。卸点在一个班次内不变。卡车载重量为154吨，平均时速28km,平均卸车时间为3分钟。,问题：出动几台电铲，分别在哪些铲位上；出动几辆卡车，分别在哪些路线上各运输多少次 ?,平面示意图,问题数据,问题分析,与典型的运输问题明显有以下不同： 这是运输矿石与岩石两种物资的问题； 属于产量大于销量的不平衡运输问题； 为了完成品位约束，矿石要搭配运输； 产地、销地均有单位时间的流量限制； 运输车辆只有一种，每次满载运输，154吨/车次； 铲位数多于铲车数意味着要最优的选择不多于7个产地作为最后结果中的产地； 最后求出各条路线上的派出车辆数及安排。,近似处理： 先求出产位、卸点每条线路上的运输
11、量(MIP模型) 然后求出各条路线上的派出车辆数及安排,模型假设,卡车在一个班次中不应发生等待或熄火后再启动的情况； 在铲位或卸点处由两条路线以上造成的冲突问题面前，我们认为只要平均时间能完成任务，就认为不冲突。我们不排时地进行讨论； 空载与重载的速度都是28km/h，耗油相差很大； 卡车可提前退出系统，等等。,如理解为严格不等待，难以用数学规划模型来解 个别参数队找到了可行解 （略）,符号,xij ：从i铲位到j号卸点的石料运量 （车） 单位： 吨； cij ：从i号铲位到j号卸点的距离 公里； Tij :从i号铲位到号j卸点路线上运行一个周期平均时间 分； Aij ：从号铲位到号卸点最多能
12、同时运行的卡车数 辆； 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）整数约
13、束,.,xij为非负整数 fi 为0-1整数,计算结果（LINGO软件）,注: LINGO8.0本来是可以得到最优解的，但有些 LINGO8.0可能出现系统错误, 可能是系统BUG,计算结果（派车）,结论： 铲位1、2、3、4、8、9、10处各放置一台电铲。 一共使用了13辆卡车；总运量为85628.62吨公里； 岩石产量为32186吨；矿石产量为38192吨。,此外：6辆联合派车（方案略）,最大化产量,结论： （略）,目标函数变化 此外：车辆数量（20辆）限制（其实上面的模型也应该有）,2000年全国大学生数学建模竞赛D题,空洞探测,山体隧道坝体等的某些内部结构可用弹性波测量来确定。简化问题
14、可叙述为， 一块均匀介质构成的矩形平板内有一些充满空气的空洞。 在平板的两个邻边分别等距地设置若干波源，在他们的对边对等地安放同样多的接收器，记录弹性波由每个波源到达对边上每个接收器的时间。 根据弹性波在介质和在空气中不同的传播速度来确定板内空洞的位置,具体问题： 一块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), 记录由 R
15、i 发出的弹性波到达 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
