优化建模与LINGOppt课件第12章数学建模竞赛中的部分优化问题.ppt

《优化建模与LINGOppt课件第12章数学建模竞赛中的部分优化问题.ppt》由会员分享，可在线阅读，更多相关《优化建模与LINGOppt课件第12章数学建模竞赛中的部分优化问题.ppt（58页珍藏版）》请在三一办公上搜索。

1、优化建模与LINDO/LINGO软件第12章数学建模竞赛中的部分优化问题,原书相关信息谢金星, 薛毅编，清华大学出版社, 2005年7月出版.http:/,简要提纲,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,注意：应先计算出初始时刻的ij,

5、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 Exam1202

8、c.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个产地作为最后结果中的产地；最后求出各条路线上的派出车辆数及安排。,近似处理：先求出产位、卸点每条线路上的运输量(MIP模型)然后求出各条路线上

11、的派出车辆数及安排,模型假设,卡车在一个班次中不应发生等待或熄火后再启动的情况；在铲位或卸点处由两条路线以上造成的冲突问题面前，我们认为只要平均时间能完成任务，就认为不冲突。我们不排时地进行讨论；空载与重载的速度都是28km/h，耗油相差很大；卡车可提前退出系统，等等。,如理解为严格不等待，难以用数学规划模型来解 个别参数队找到了可行解 （略）,符号,xij ：从i铲位到j号卸点的石料运量 （车） 单位： 吨；cij ：从i号铲位到j号卸点的距离 公里；Tij :从i号铲位到号j卸点路线上运行一个周期平均时间 分；Aij ：从号铲位到号卸点最多能同时运行的卡车数 辆；Bij ：从号铲位到号卸点

12、路线上一辆车最多可运行的次数 次；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软件）,注

13、: 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), 记录由 Ri 发出的弹性波到达 Sj 的时间 ij(秒)。 已知弹性波在介质和空气中的传播速度分别为28

15、80(米/秒)和320(米/秒), 且弹性波沿板边缘的传播速度与在介质中的传播速度相同,P2,Q4,R3,S6,TP=(tij),tij Q1 Q2 Q3 Q4 Q5 Q6 Q7P1 .0611 .0895 .1996 .2032 .4181 .4923 .5646P2 .0989 .0592 .4413 .4318 .4770 .5242 .3805P3 .3052 .4131 .0598 .4153 .4156 .3563 .1919P4 .3221 .4453 .4040 .0738 .1789 .0740 .2122P5 .3490 .4529 .2263 .1917 .0839 .1

16、768 .1810P6 .3807 .3177 .2364 .3064 .2217 .0939 .1031P7 .4311 .3397 .3566 .1954 .0760 .0688 .1042,TR=(ij),ij S1 S2 S3 S4 S5 S6 S7R1 .0645 .0602 .0813 .3516 .3867 .4314 .5721R2 .0753 .0700 .2852 .4341 .3491 .4800 .4980R3 .3456 .3205 .0974 .4093 .4240 .4540 .3112R4 .3655 .3289 .4247 .1007 .3249 .2134

17、.1017R5 .3165 .2509 .3214 .3256 .0904 .1874 .2130R6 .2749 .3891 .5895 .3016 .2058 .0841 .0706R7 .4434 .4919 .3904 .0786 .0709 .0914 .0583,要求：(1) 确定该平面内空洞的位置。(2) 只根据Pi发出的弹性波到达Qj的时间tij 能确定空洞的位置吗？讨论在同样能够确定空洞位置的前提下，减少波源和接收器的方法。,分析: 弹性波沿平板边缘的理论传播时间 t=240/2880=0.0833(秒) 弹性波沿平板边缘的实际传播时间 t11=.0611, t77=.104

18、2, 11=.0645, 77=.0583 题目中已假设“弹性波沿板边缘的传播速度与在介质中的传播速度相同”观测数据的最大绝对误差为d=0.025秒.可以认为，0.025*360 =9(米）以下的空洞是探测不出的,假设,1. 观测数据有测量误差。观测数据除测量误差外是可靠的。2. 波在传播过程中沿直线单向传播，且不考虑波的反射、折射以及干涉等现象。3.空气密度和介质密度都均匀,4.“弹性波”在传播过程中没有能量损失。其波速仅与介质有关，且在同一均匀介质中波速不变。弹性波沿板边缘的传播速度与在介质中的传播速度相同。5.假设平板可划分化为网格，空洞定位于每个网格单元内,空洞大小大致相同.,波线与网

19、格交线长度的计算,(k,l),记波源Pi与接收器Qj 决定的波线与每个单元（k，l）的交线长度为bijkl,i=j 时,1,2,3,4,5,6,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 以

20、外的情况,单元(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)下边缘直线方程 y = 40(l-1),波线与单元(k,l)下边缘对应交点的y坐标为 y3ijkl = 40(l-1)， 其中 0 6(i-k)-(i-j)(l-1) 6,(k,l),波线与网格交线长度的计算,PiQj 决定的直线方程：(j - i）y

21、 = 6(x-40(i-1),i=j 以外的情况,单元(k,l)上边缘直线方程 y = 40l,波线与单元(k,l)上边缘对应交点的y坐标为 y4ijkl = 40l， 其中 0 6(i-k)-(i-j)l 6,(k,l),波线与网格交线长度的计算,交线在y轴的投影长度(交点条件最多只有2个成立),i=j 以外的情况,dyijkl= max(y1ijkl ,y2ijkl,y3ijkl,y4ijkl) - min(y1ijkl ,y2ijkl,y3ijkl,y4ijkl),由相似三角形关系,bijkl = aij dyijkl / 240,i=j 也成立,波线与网格交线长度的计算,由对称性，Ri

22、Sj与单元(k,l)的交线长度,ci,j,k,l= bj,i,l,7-k,计算程序：exam1204a.lg4(结果存入Excel文件备用),参量、变量：xkl：单元(k,l)是否为空洞(1：是；0：否)aij：波源Pi与接收器Qj （同样，Ri与Sj）之间的距离pij经过介质的长度, qij经过空气的长度tij (同样 ij): 传播时间观测值,优化模型（拟合回归）,若没有误差：tij =pij /v1+qij/v2,优化模型（拟合回归）,同理：,模型：,LINGO计算结果,Exam1204b.lg4,空洞X( P2, Q2) 1X( P2, Q3) 1X( P2, Q5) 1X( P3, Q2) 1X( P3, Q3) 1X( P3, Q4) 1X( P4, Q4) 1X( P5, Q3) 1,自己练习，或课上布置,布置作业内容,Thank you very much!,