第12章数学建模竞赛中的部分优化问题分解

优 化 建 模,优化建模与LINDO/LINGO软件,第12章数学建模竞赛中的局部优化问题,原书相关信息,谢金星, 薛毅编，清华大学出版社, 2005年7月出版.,:/ 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,4 145 50 159,5 130 150 230,新进入 0 0 52,注: 方向角指飞行方向与x轴正向的夹角,两架飞机不碰撞的条件,0 t Tij,T,i,为第,i,架飞机飞出区域的时刻,不碰撞条件,初始位置,时刻t飞机的位置,两架飞机的距离平方,不必考虑在区域外的碰撞,两架飞机都在区域中的时间,具体来看，,第,i,架飞机在区域内的时间,飞机飞出区域的时刻,整理：,f,ij,(,t,)的最小值 (-,b,ij,2,/ 4 +,c,ij,),；此时,其中：,不碰撞条件的等价表述,最后，优化模型为,f,ij,(,t,)大于等于肯定成立,f,ij,(,t,)大于等于等价于,f,ij,(,t,)大于等于等价于,LINGO求解,一个简化的数学模型,任何一架飞机在区域中停留最长时间,放松到任两架飞机在这段时间不碰撞,甚至放松到任两架飞机永远不碰撞,其他目标,调整后的方向角,总的调整量最小,最大调整量最小,初始位置与方向角,基于相对运动观点的模型,基于相对运动观点的模型,于是,数学规划模型,LINGO求解,注意：应先计算出初始时刻的,ij,2000年全国大学生数学建模竞赛B题,钢管订购与运输,问题描述,由钢管厂订购钢管，经铁路、公路运输，铺设一条钢管管道,A,1,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,A,2,A,3,A,4,A,5,A,6,A,7,A,8,A,9,A,10,A,11,A,12,A,13,A,14,A,15,S,1,S,2,S,3,S,4,S,5,S,6,S,7,管道,铁路,公路,S1S7,钢管厂,火车站,450 里程（km),（沿管道建有公路）,钢厂的产量和销价1单位钢管=1km管道钢管,钢厂产量的下限：500单位钢管,1单位钢管的铁路运价,1000km以上每增加1至100km运价增加5万元,1单位钢管的公路运价：0.1万元/km缺乏整公里局部按整公里计,1制定钢管的订购和运输方案，使总费用最小.,2分析对购运方案和总费用影响：哪个钢厂钢管销价的变化影响最大；哪个钢厂钢管产量上限的变化影响最大？,A,1,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,A,2,A,3,A,4,A,5,A,6,A,7,A,8,A,9,A,10,A,11,A,12,A,13,A,14,A,15,S,1,S,2,S,3,S,4,S,5,S,6,S,7,A,16,130,A,17,A,18,A,19,A,20,A,21,190,260,100,3讨论管道为树形图的情形,问题1的根本模型和解法,总费用最小的优化问题,总费用：订购，运输由各厂Si经铁路、公路至各点Aj, i=1,7; j=1, 15 ，铺设管道Aj Aj+1 j=1, 14),由S,i,至A,j,的最小购运费用路线及最小费用,c,ij,由S,i,至A,j,的最优运量,x,ij,由A,j,向A,j,A,j-1,段铺设的长度,y,j,及,向A,j,A,j+1,段铺设的长度,z,j,最优购运方案,约束条件,钢厂产量约束：上限和下限如果生产的话,运量约束：xij对i求和等于zj 加yj；,zj与 yj+1之和等于Aj Aj+1段的长度lj,y,j,z,j,A,j-1,A,j,A,j+1,根本模型,由A,j,向A,j,A,j-1,段铺设的运量为 1+ +,y,j,= y,j,(,y,j,+1)/2,由A,j,向A,j,A,j+1,段铺设的运量为 1+ +,z,j,= z,j,(,z,j,+1)/2,二次规划?,求解步骤,1求由Si至Aj的最小购运费用路线及最小费用cij,难点：公路运费是里程的线性函数，而铁路运费是里程的分段阶跃函数，故总运费不具可加性。因而计算最短路常用的Dijkstra算法、Floyd算法失效。,A,1,70,10,88,10,70,62,70,30,20,20,30,300,220,210,420,500,170,690,462,160,320,160,110,290,A,10,A,11,A,12,A,13,A,14,A,15,S,4,S,5,S,6,S,7,需要对铁路网和公路网进展预处理，才能使用常用算法，得到最小购运费用路线。- 至少求3次最短路,如S,7,至A,10,的最小费用路线,先铁路1130km，再公路70km, 运费为77万元,先公路经A1540km, 再铁路1100km，再公路70km, 运费为76万元,任意两点之间最短路的Floyd-Warshall算法,1求由Si至Aj的最小购运费用路线及最小费用cij,A,1,3次最短路的LINGO程序：,u,ij,(k),是任意两个节点,i,，,j,之间距离的临时标号，即从节点,i,到,j,但不允许经过其他节点,k,，,k,+1，,n,时的最短距离,实际上只有S,4,和S,7,需要分解成子问题求解,每个子问题是标准的二次规划，决策变量为,x,ij,y,j,z,j,不超过135个 。,f,i,表示钢厂,i,是否使用；,x,ij,是从钢厂,i,运到节点,j,的钢管量,y,j,是从节点,j,向左铺设的钢管量；,z,j,是向右铺设的钢管量,c) 比较好的方法：引入0-1变量,LINDO/LINGO,得到的结果比,matlab,得到的好,exam1202d.lg4,y,j,z,j,A,j,问题2: 分析对购运方案和总费用影响(哪个钢厂销价变化影响最大；哪个钢厂产量上限变化影响最大),规划问题的灵敏度分析,问题3：,管道为树形图,70,10,88,10,70,62,300,220,210,170,690,462,160,320,160,A,10,A,11,A,12,S,4,S,5,S,6,130,A,17,A,18,A,19,A,20,190,260,100,(,jk,),是连接A,j,A,k,的边，E是树形图的边集，,l,jk,是(,jk,)的长度，,y,jk,是由A,j,沿(,jk,)铺设的钢管数量,2003年全国大学生数学建模竞赛B题,露天矿生产的车辆安排,露天矿里铲位已分成矿石和岩石: 平均铁含量不低于25%的为矿石，否那么为岩石。每个铲位的矿石、岩石数量，以及矿石的平均铁含量称为品位都是的。每个铲位至多安置一台电铲，电铲平均装车时间5分钟,卡车在等待时所消耗的能量也是相当可观的，原那么上在安排时不应发生卡车等待的情况。,露天矿生产的车辆安排,矿石卸点需要的铁含量要求都为29.5%1%(品位限制，搭配量在一个班次8小时内满足品位限制即可。卸点在一个班次内不变。卡车载重量为154吨，平均时速28km,平均卸车时间为3分钟。,问题：出动几台电铲，分别在哪些铲位上；出动几辆卡车，分别在哪些路线上各运输多少次 ?,平面示意图,问题数据,距离,铲位1,铲位,2,铲位3,铲位4,铲位5,铲位6,铲位7,铲位,8,铲位9,铲位10,矿石漏,5.26,5.19,4.21,4.00,2.95,2.74,2.46,1.90,0.64,1.27,倒装,1.90,0.99,1.90,1.13,1.27,2.25,1.48,2.04,3.09,3.51,岩场,5.89,5.61,5.61,4.56,3.51,3.65,2.46,2.46,1.06,0.57,岩石漏,0.64,1.76,1.27,1.83,2.74,2.60,4.21,3.72,5.05,6.10,倒装,4.42,3.86,3.72,3.16,2.25,2.81,0.78,1.62,1.27,0.50,铲位1,铲位2,铲位3,铲位4,铲位5,铲位6,铲位7,铲位,8,铲位9,铲位10,矿石量,095,105,100,105,110,125,105,130,135,125,岩石量,125,110,135,105,115,135,105,115,135,125,铁含量,30%,28%,29%,32%,31%,33%,32%,31%,33%,31%,问题分析,与典型的运输问题明显有以下不同：,这是运输矿石与岩石两种物资的问题；,属于产量大于销量的不平衡运输问题；,为了完成品位约束，矿石要搭配运输；,产地、销地均有单位时间的流量限制；,运输车辆只有一种，每次满载运输，,154,吨,/,车次；,铲位数多于铲车数意味着要最优的选择不多于,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整数约束,.,x,ij,为非负整数,f,i,为0-1整数,计算结果LINGO软件,铲位1,铲位2,铲位3,铲位4,铲位5,铲位6,铲位7,铲位8,铲位9,铲位10,矿漏,13,54,11,倒,42,43,岩场,70,15,岩漏,81,43,倒,13,2,70,铲位1,铲位2,铲位3,铲位4,铲位5,铲位6,铲位7,铲位8,铲位9,铲位,10,矿石漏,0.867,1.862,0.314,倒场,1.077,1.162,岩场,1.892,0.326,岩石漏,1.841,1.229,倒场,0.684,0.1,1.489,exam1203.lg4,注: LINGO8.0本来是可以得到最优解的，但有些,LINGO8.0可能出现系统错误, 可能是系统BUG,计算结果派车,铲位1,铲位2,铲位3,铲位4,铲位5,铲位6,铲位7,铲位8,铲位9,铲位,10,矿石漏,1 (29),倒场,1 (39),1 (37),岩场,1 (37),岩石漏,1(44),1 (35),倒场,1 (47),结论：,铲位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=(t,ij,),t,ij,Q,1,Q,2,Q,3,Q,4,Q,5,Q,6,Q,7,P,1,.,0611,.0895 .1996 .2032 .4181 .4923 .5646,P,2,.0989 .0592 .4413 .4318 .4770 .5242 .3805,P,3,.3052 .4131 .0598 .4153 .4156 .3563 .1919,P,4,.3221 .4453 .4040 .0738 .1789 .0740 .2122,P,5,.3490 .4529 .2263 .1917 .0839 .1768 .1810,P,6,.3807 .3177 .2364 .3064 .2217 .0939 .1031,P,7,.4311 .3397 .3566 .1954 .0760 .0688,.1042,TR=(,ij,),ij,S,1,S,2,S,3,S,4,S,5,S,6,S,7,R,1,.0645,.0602 .0813 .3516 .3867 .4314 .5721,R,2,.0753 .0700 .2852 .4341 .3491 .4800 .4980,R,3,.3456 .3205 .0974 .4093 .4240 .4540 .3112,R,4,.3655 .3289 .4247 .1007 .3249 .2134 .1017,R,5,.3165 .2509 .3214 .3256 .0904 .1874 .2130,R,6,.2749 .3891 .5895 .3016 .2058 .0841 .0706,R,7,.4434 .4919 .3904 .0786 .0709 .0914,.0583,要求：,(1) 确定该平面内空洞的位置。,(2) 只根据Pi发出的弹性波到达Qj的时间t,ij,能确定空洞的位置吗？讨论在同样能够确定空洞位置的前提下，减少波源和接收器的方法。,分析: 弹性波沿平板边缘的理论传播时间,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,时,1,2,3,4,5,6,6,5,4,3,2,1,波线与网格交线长度的计算,PiQj 决定的直线方程：,(j - iy = 6(x-40(i-1),i=j,以外的情况,单元(,k,l,)左边缘直线方程,x,= 40(,k,-1),波线与,单元(,k,l,)左边缘,对应交点的y坐标为,y,1,ijkl,= 240(k-i)/(j-i)， 其中 l-1 6(k-i)/(j-i) l,(,k,l,),波线与网格交线长度的计算,PiQj 决定的直线方程：,(j - iy = 6(x-40(i-1),i=j,以外的情况,单元(,k,l,)右边缘直线方程,x,= 40,k,波线与,单元(,k,l,)右边缘,对应交点的y坐标为,y,2,ijkl,= 240(k+,1,-i)/(j-i)， 其中 l-1 6(k+,1,-i)/(j-i) l,(,k,l,),波线与网格交线长度的计算,PiQj 决定的直线方程：,(j - iy = 6(x-40(i-1),i=j,以外的情况,单元(,k,l,)下边缘直线方程,y,= 40(,l-1),波线与,单元(,k,l,)下边缘,对应交点的y坐标为,y,3,ijkl,= 40(l-,1,)， 其中 0 6(i-k)-(i-j)(l-,1,) 6,(,k,l,),波线与网格交线长度的计算,PiQj 决定的直线方程：,(j - iy = 6(x-40(i-1),i=j,以外的情况,单元(,k,l,)上边缘直线方程,y,= 40,l,波线与,单元(,k,l,)上边缘,对应交点的y坐标为,y,4,ijkl,= 40l， 其中 0 6(i-k)-(i-j)l 6,(,k,l,),波线与网格交线长度的计算,交线在,y,轴的投影长度,(交点条件最多只有2个成立),i=j,以外的情况,dy,ijkl,= max(y,1,ijkl,y,2,ijkl,y,3,ijkl,y,4,ijkl,),- min(y,1,ijkl,y,2,ijkl,y,3,ijkl,y,4,ijkl,),由相似三角形关系,Q,j,A,B,C,D,P,i,R,i,S,j,P,j,dy,ijkl,(,k,l,),b,ijkl,E,F,G,b,ijkl,=,a,ij,dy,ijkl,/ 240,i=j,也成立,波线与网格交线长度的计算,由对称性，R,i,S,j,与单元(k,l)的交线长度,c,i,j,k,l,= b,j,i,l,7-k,(结果存入Excel文件备用),参量、变量：,xkl：单元(k,l)是否为空洞(1：是；0：否),aij：波源Pi与接收器Qj,同样，Ri与Sj之间的距离,pij经过介质的长度, qij经过空气的长度,tij (同样 ij): 传播时间观测值,优化模型拟合回归,假设没有误差：,tij =pij /v1+qij/v2,优化模型拟合回归,同理：,模型：,LINGO计算结果,空洞,X( P2, Q2) 1,X( P2, Q3) 1,X( P2, Q5) 1,X( P3, Q2) 1,X( P3, Q3) 1,X( P3, Q4) 1,X( P4, Q4) 1,X( P5, Q3) 1,自己练习，或课上布置,布置作业内容,Thank you very much!,