《数学建模竞赛中的部分优化问题.pptx》由会员分享，可在线阅读，更多相关《数学建模竞赛中的部分优化问题.pptx（57页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、简要提纲 1.CUMCM-1995A:一个飞行管理问题2.CUMCM-2000B:钢管订购与运输3.CUMCM-2003B：露天矿生产的车辆安排4.CUMCM-2000D:空洞探测第1页/共57页1995年全国大学生数学建模竞赛A题 一 个 飞 行 管 理 问 题 第2页/共57页一个飞行管理问题在约10000m高空的某边长160km的正方形区域内,经常有若干架飞机作水平飞行,区域内每架飞机的位置和速度向量均由计算机记录其数据,以便进行飞行管理.当一架欲进入该区域的飞机到达边界区域边缘时,记录其数据后,要立即计算并判断是否会与其区域内的飞机发生碰撞.如果会碰撞,则应计算如何调整各架(包括新进入
2、的)飞机飞行的方向角,以避免碰撞.现假设条件如下:1)不碰撞的标准为任意两架飞机的距离大于8km;2)飞机飞行方向角调整的幅度不应超过30度;3)所有飞机飞行速度均为每小时为800km;4)进入该区域的飞机在到达区域边缘时,与区域内飞机的距离应在60km以上;5)最多考虑6架飞机;6)不必考虑飞机离开此区域后的状况;第3页/共57页请你对这个避免碰撞的飞行管理问题建立数学模型.列出计算步骤,对以下数据进行计算(方向角误差不超过0.01度),要求飞机飞行方向角调整的幅度尽量小.设该区域4个顶点坐标为(0,0),(160,0),(160,160),(0,160).记录数据为:飞机编号横坐标x纵坐标
3、y方向角(度)1150140243285852363150155220.54145501595130150230新进入0052注:方向角指飞行方向与x轴正向的夹角第4页/共57页两架飞机不碰撞的条件（0t Tij）Ti为第i架飞机飞出区域的时刻不碰撞条件初始位置时刻t飞机的位置两架飞机的距离（平方）第5页/共57页不必考虑在区域外的碰撞两架飞机都在区域中的时间具体来看，第i架飞机在区域内的时间飞机飞出区域的时刻第6页/共57页整理：fij(t)的最小值(-bij2/4+cij)；此时其中：第7页/共57页不碰撞条件的等价表述最后，优化模型为fij(t)大于等于肯定成立fij(t)大于等于等价于
4、fij(t)大于等于等价于第8页/共57页LINGO求解程序exam1201a.lg4一个简化的数学模型任何一架飞机在区域中停留最长时间放松到任两架飞机在这段时间不碰撞甚至放松到任两架飞机永远不碰撞第9页/共57页其他目标调整后的方向角总的调整量最小最大调整量最小初始位置与方向角第10页/共57页基于相对运动观点的模型第11页/共57页基于相对运动观点的模型第12页/共57页于是数学规划模型第13页/共57页LINGO求解程序exam1201b.lg4注意：应先计算出初始时刻的ij第14页/共57页2000年全国大学生数学建模竞赛B题 钢 管 订 购 与 运 输 第15页/共57页问题描述 由
5、钢管厂订购钢管，经铁路、公路运输，铺设一条钢管管道A1325801010312012427010881070627030202030450104301750606194205201680480300220210420500600306195202720690520170690462160320160110290115011001200A2A3A4A5A6A7A8A9A10A11A12A13A14A15S1S2S3S4S5S6S7管道铁路公路S1S7钢管厂火车站450里程（km)（沿管道建有公路）第16页/共57页钢厂的产量和销价（1单位钢管=1km管道钢管）钢厂产量的下限：500单位钢管1单位
6、钢管的铁路运价1000km以上每增加1至100km运价增加5万元1单位钢管的公路运价：0.1万元/km（不足整公里部分按整公里计）第17页/共57页（1）制定钢管的订购和运输计划，使总费用最小.（2）分析对购运计划和总费用影响：哪个钢厂钢管销价的变化影响最大；哪个钢厂钢管产量上限的变化影响最大？A1325801010312012427010881070627030202030450104301750606194205201680480300220210420500600306195202720690520170690462160320160110290115011001200A2A3A4A5A
7、6A7A8A9A10A11A12A13A14A15S1S2S3S4S5S6S7A16130A17A18A19A20A21190260100（3）讨论管道为树形图的情形第18页/共57页问题1的基本模型和解法总费用最小的优化问题总费用：订购，运输（由各厂Si经铁路、公路至各点Aj,i=1,7;j=1,15），铺设管道AjAj+1（j=1,14)由Si至Aj的最小购运费用路线及最小费用cij由Si至Aj的最优运量xij由Aj向AjAj-1段铺设的长度yj及向AjAj+1段铺设的长度zj最优购运计划约束条件钢厂产量约束：上限和下限（如果生产的话）运量约束：xij对i求和等于zj 加yj；zj与 yj
8、+1之和等于AjAj+1段的长度ljyjzjAj-1AjAj+1第19页/共57页基本模型由Aj向AjAj-1段铺设的运量为1+yj=yj(yj+1)/2由Aj向AjAj+1段铺设的运量为1+zj=zj(zj+1)/2二次规划?第20页/共57页求解步骤1）求由Si至Aj的最小购运费用路线及最小费用cij难点：公路运费是里程的线性函数，而铁路运费是里程的分段阶跃函数，故总运费不具可加性。因而计算最短路常用的Dijkstra算法、Floyd算法失效。A17010881070627030202030300220210420500170690462160320160110290A10A11A12A1
9、3A14A15S4S5S6S7需要对铁路网和公路网进行预处理，才能使用常用算法，得到最小购运费用路线。-至少求3次最短路如S7至A10的最小费用路线先铁路1130km，再公路70km,运费为77（万元）先公路（经A15）40km,再铁路1100km，再公路70km,运费为76（万元）第21页/共57页任意两点之间最短路的Floyd-Warshall算法1）求由Si至Aj的最小购运费用路线及最小费用cijA13次最短路的LINGO程序：Exam1202a.lg4Exam1202b.lg4Exam1202c.lg4uij(k)是任意两个节点i，j之间距离的临时标号，即从节点i到j但不允许经过其他节
10、点k，k+1，,n时的最短距离第22页/共57页实际上只有S4和S7需要分解成子问题求解每个子问题是标准的二次规划，决策变量为xij,yj,zj,不超过135个。第23页/共57页fi表示钢厂i是否使用；xij是从钢厂i运到节点j的钢管量yj是从节点j向左铺设的钢管量；zj是向右铺设的钢管量c)比较好的方法：引入0-1变量LINDO/LINGO得到的结果比matlab得到的好exam1202d.lg4yjzjAj第24页/共57页问题2:分析对购运计划和总费用影响(哪个钢厂销价变化影响最大；哪个钢厂产量上限变化影响最大)规划问题的灵敏度分析问题3：管道为树形图70108810706230022
11、0210170690462160320160A10A11A12S4S5S6130A17A18A19A20190260100(jk)是连接Aj,Ak的边，E是树形图的边集，ljk是(jk)的长度，yjk是由Aj沿(jk)铺设的钢管数量第25页/共57页2003年全国大学生数学建模竞赛B题 露 天 矿 生 产 的 车 辆 安 排第26页/共57页露天矿里铲位已分成矿石和岩石:平均铁含量不低于25%的为矿石，否则为岩石。每个铲位的矿石、岩石数量，以及矿石的平均铁含量（称为品位）都是已知的。每个铲位至多安置一台电铲，电铲平均装车时间5分钟卡车在等待时所耗费的能量也是相当可观的，原则上在安排时不应发生卡
12、车等待的情况。露天矿生产的车辆安排矿石卸点需要的铁含量要求都为29.5%1%(品位限制），搭配量在一个班次（8小时）内满足品位限制即可。卸点在一个班次内不变。卡车载重量为154吨，平均时速28km,平均卸车时间为3分钟。问题：出动几台电铲，分别在哪些铲位上；出动几辆卡车，分别在哪些路线上各运输多少次?第27页/共57页平面示意图平面示意图第28页/共57页问题数据 距离铲位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.
13、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%第29页/共57页问题分析 与典型的运输问题明显有以下不同：1.这是运输矿石与岩石
14、两种物资的问题；2.属于产量大于销量的不平衡运输问题；3.为了完成品位约束，矿石要搭配运输；4.产地、销地均有单位时间的流量限制；5.运输车辆只有一种，每次满载运输，154吨/车次；6.铲位数多于铲车数意味着要最优的选择不多于7个产地作为最后结果中的产地；7.最后求出各条路线上的派出车辆数及安排。近似处理：先求出产位、卸点每条线路上的运输量(MIP模型)然后求出各条路线上的派出车辆数及安排第30页/共57页模型假设模型假设卡车在一个班次中不应发生等待或熄火后再启动的情况；在铲位或卸点处由两条路线以上造成的冲突问题面前，我们认为只要平均时间能完成任务，就认为不冲突。我们不排时地进行讨论；空载与重
15、载的速度都是28km/h，耗油相差很大；卡车可提前退出系统，等等。如理解为严格不等待，难以用数学规划模型来解 个别参数队找到了可行解（略）第31页/共57页符号符号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)*10
16、000 吨cki：i号铲位的铁矿石储量 万吨cyi：i号铲位的岩石储量 万吨fi:描述第i号铲位是否使用的0-1变量，取1为使用；0为关闭。(近似)第32页/共57页优化模型优化模型（1）道路能力(卡车数)约束（2）电铲能力约束（3）卸点能力约束（4）铲位储量约束（5）产量任务约束（6）铁含量约束（7）电铲数量约束（8）整数约束.xij为非负整数fi 为0-1整数第33页/共57页计算结果（计算结果（LINGOLINGO软件）软件）铲位1铲位2铲位3铲位4铲位5铲位6铲位7铲位8铲位9铲位10矿漏131354541111倒42424343岩场70701515岩漏81814343倒13132 2
17、7070铲位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.489exam1203.lg4注:LINGO8.0本来是可以得到最优解的，但有些 LINGO8.0可能出现系统错误,可能是系统BUG第34页/共57页计算结果（派车）计算结果（派车）铲位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处各放置一台电铲。一
18、共使用了13辆卡车；总运量为85628.62吨公里；岩石产量为32186吨；矿石产量为38192吨。此外：6辆联合派车（方案略）第35页/共57页最大化产量最大化产量结论：（略）目标函数变化此外：车辆数量（20辆）限制（其实上面的模型也应该有）第36页/共57页2000年全国大学生数学建模竞赛D题 空 洞 探 测第37页/共57页山体隧道坝体等的某些内部结构可用弹性波测量来确定。简化问题可叙述为，一块均匀介质构成的矩形平板内有一些充满空气的空洞。在平板的两个邻边分别等距地设置若干波源，在他们的对边对等地安放同样多的接收器，记录弹性波由每个波源到达对边上每个接收器的时间。根据弹性波在介质和在空气
19、中不同的传播速度来确定板内空洞的位置第38页/共57页具体问题：一块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(米/秒),且弹性波沿板边缘的传播速度与在介质中的传播速度相同第39页/共57页P2Q4R3S6第40页/共57页TP=(tij)tijQ1
20、Q2Q3Q4Q5Q6Q7P1.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.1768.1810P6.3807.3177.2364.3064.2217.0939.1031P7.4311.3397.3566.1954.0760.0688.1042第41页/共57页TR=(ij)ijS1S2S3S4S5S
21、6S7R1.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.1017R5.3165.2509.3214.3256.0904.1874.2130R6.2749.3891.5895.3016.2058.0841.0706R7.4434.4919.3904.0786.0709.0914.0583第42页/共57页要求：(1)确定该平面内空洞的位置。(2)只根据Pi发出的
22、弹性波到达Qj的时间tij能确定空洞的位置吗？讨论在同样能够确定空洞位置的前提下，减少波源和接收器的方法。第43页/共57页分析:弹性波沿平板边缘的理论传播时间t=240/2880=0.0833(秒)弹性波沿平板边缘的实际传播时间t11=.0611,t77=.1042,11=.0645,77=.0583题目中已假设“弹性波沿板边缘的传播速度与在介质中的传播速度相同”观测数据的最大绝对误差为d=0.025秒.可以认为，0.025*360=9(米）以下的空洞是探测不出的第44页/共57页假设假设1.观测数据有测量误差。观测数据除测量误差外是可靠的。2.波在传播过程中沿直线单向传播，且不考虑波的反射
23、、折射以及干涉等现象。3.空气密度和介质密度都均匀第45页/共57页4.“弹性波”在传播过程中没有能量损失。其波速仅与介质有关，且在同一均匀介质中波速不变。弹性波沿板边缘的传播速度与在介质中的传播速度相同。5.假设平板可划分化为网格，空洞定位于每个网格单元内,空洞大小大致相同.第46页/共57页波线与网格交线长度的计算波线与网格交线长度的计算 (k,l)记波源Pi与接收器Qj 决定的波线与每个单元（k，l）的交线长度为bijkl i=j 时123456654321第47页/共57页波线与网格交线长度的计算波线与网格交线长度的计算 PiQj 决定的直线方程：(j-i）y=6(x-40(i-1)i
24、=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)第48页/共57页波线与网格交线长度的计算波线与网格交线长度的计算 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)第49页/共57页波线与网格交线长度的计算波线与网格交线长度
25、的计算 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)第50页/共57页波线与网格交线长度的计算波线与网格交线长度的计算 PiQj 决定的直线方程：(j-i）y=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)第51页/共57页波线与网
26、格交线长度的计算波线与网格交线长度的计算 交线在y轴的投影长度(交点条件最多只有2个成立)i=j 以外的情况dyijkl=max(y1ijkl,y2ijkl,y3ijkl,y4ijkl)-min(y1ijkl,y2ijkl,y3ijkl,y4ijkl)由相似三角形关系QjABCDPiRiSjPjdyijkl(k,l)bijklEFGbijkl=aij dyijkl/240i=j 也成立第52页/共57页波线与网格交线长度的计算波线与网格交线长度的计算 由对称性，RiSj与单元(k,l)的交线长度ci,j,k,l=bj,i,l,7-k计算程序：exam1204a.lg4(结果存入Excel文件备用)第53页/共57页参量、变量：xkl：单元(k,l)是否为空洞(1：是；0：否)aij：波源Pi与接收器Qj （同样，Ri与Sj）之间的距离pij经过介质的长度,qij经过空气的长度tij(同样 ij):传播时间观测值优化模型（拟合回归）第54页/共57页若没有误差：tij=pij/v1+qij/v2优化模型（拟合回归）同理：模型：第55页/共57页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第56页/共57页感谢您的观看！第57页/共57页