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

《数学建模竞赛中的部分优化问题.ppt》由会员分享，可在线阅读，更多相关《数学建模竞赛中的部分优化问题.ppt（57页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、 优 化 建 模优化建模与LINDO/LINGO软件数学建模竞赛中的部分优化问题 优 化 建 模简要提纲 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度),要求飞机飞行方向角调整的幅度尽量小.设该区域4个顶点坐标为(0,0),(160

3、,0),(160,160),(0,160).记录数据为:飞机编号横坐标x纵坐标y方向角(度)1150140243285852363150155220.54145501595130150230新进入0052注:方向角指飞行方向与x轴正向的夹角 优 化 建 模两架飞机不碰撞的条件（0t Tij）Ti为第i架飞机飞出区域的时刻不碰撞条件初始位置时刻t飞机的位置两架飞机的距离（平方）优 化 建 模不必考虑在区域外的碰撞两架飞机都在区域中的时间具体来看，第i架飞机在区域内的时间飞机飞出区域的时刻 优 化 建 模整理：fij(t)的最小值(-bij2/4+cij)；此时其中：优 化 建 模不碰撞条件的等价

4、表述 最后，优化模型为 fij(t)大于等于肯定成立fij(t)大于等于等价于fij(t)大于等于等价于 优 化 建 模LINGO求解程序exam1201a.lg4一个简化的数学模型任何一架飞机在区域中停留最长时间放松到任两架飞机在这段时间不碰撞甚至放松到任两架飞机永远不碰撞 优 化 建 模其他目标调整后的方向角总的调整量最小 最大调整量最小 初始位置与方向角 优 化 建 模基于相对运动观点的模型 优 化 建 模基于相对运动观点的模型 优 化 建 模于是数学规划模型 优 化 建 模LINGO求解程序exam1201b.lg4注意：应先计算出初始时刻的ij 优 化 建 模2000年全国大学生数学

5、建模竞赛B题钢管订购与运输 优 化 建 模问题描述 由钢管厂订购钢管，经铁路、公路运输，铺设一条钢管管道A1325801010312012427010881070627030202030450104301750606194205201680480300220210420500600306195202720690520170690462160320160110290115011001200A2A3A4A5A6A7A8A9A10A11A12A13A14A15S1S2S3S4S5S6S7管道铁路公路S1S7钢管厂火车站450里程（km)（沿管道建有公路）优 化 建 模钢厂的产量和销价（1单位钢管=1

6、km管道钢管）钢厂产量的下限：500单位钢管1单位钢管的铁路运价1000km以上每增加1至100km运价增加5万元1单位钢管的公路运价：0.1万元/km（不足整公里部分按整公里计）优 化 建 模（1）制定钢管的订购和运输计划，使总费用最小.（2）分析对购运计划和总费用影响：哪个钢厂钢管销价的变化影响最大；哪个钢厂钢管产量上限的变化影响最大？A13258010103120124270108810706270302020304501043017506061942052016804803002202104205006003061952027206905201706904621603201601102

7、90115011001200A2A3A4A5A6A7A8A9A10A11A12A13A14A15S1S2S3S4S5S6S7A16130A17A18A19A20A21190260100（3）讨论管道为树形图的情形 优 化 建 模问题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最优购运计划约束条件钢厂产量约束：上限和下限（如果生产的话）运量约束：

8、xij对i求和等于zj 加yj；zj与 yj+1之和等于AjAj+1段的长度ljyj zjAj-1AjAj+1 优 化 建 模基本模型由Aj向AjAj-1段铺设的运量为1+yj=yj(yj+1)/2由Aj向AjAj+1段铺设的运量为1+zj=zj(zj+1)/2二次规划?优 化 建 模求解步骤1）求由Si至Aj的最小购运费用路线及最小费用cij难点：公路运费是里程的线性函数，而铁路运费是里程的分段阶跃函数，故总运费不具可加性。因而计算最短路常用的Dijkstra算法、Floyd算法失效。A17010881070627030202030300220210420500170690462160320

9、160110290A10A11A12A13A14A15S4S5S6S7需要对铁路网和公路网进行预处理，才能使用常用算法，得到最小购运费用路线。-至少求3次最短路如S7至A10的最小费用路线先铁路1130km，再公路70km,运费为77（万元）先公路（经A15）40km,再铁路1100km，再公路70km,运费为76（万元）优 化 建 模任意两点之间最短路的Floyd-Warshall算法 1）求由Si至Aj的最小购运费用路线及最小费用cijA13次最短路的LINGO程序：Exam1202a.lg4 Exam1202b.lg4 Exam1202c.lg4uij(k)是任意两个节点i，j之间距离的

10、临时标号，即从节点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.lg4yj zjAj 优 化 建 模问题2:分析对购运计划和总费用影响(哪个钢厂销价变化影响最大；哪个钢厂产量上限变化影响最大)规划问题的灵敏度分析问题3：管道为树

11、形图701088107062300220210170690462160320160A10A11A12S4S5S6130A17A18A19A20190260100(jk)是连接Aj,Ak的边，E是树形图的边集，ljk是(jk)的长度，yjk是由Aj沿(jk)铺设的钢管数量 优 化 建 模2003年全国大学生数学建模竞赛B题露天矿生产的车辆安排 优 化 建 模露天矿里铲位已分成矿石和岩石:平均铁含量不低于25%的为矿石，否则为岩石。每个铲位的矿石、岩石数量，以及矿石的平均铁含量（称为品位）都是已知的。每个铲位至多安置一台电铲，电铲平均装车时间5分钟卡车在等待时所耗费的能量也是相当可观的，原则上在安

12、排时不应发生卡车等待的情况。露天矿生产的车辆安排矿石卸点需要的铁含量要求都为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

13、.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矿石量0 95 1 05 1 00 1 05 1 10 1 25 1 05 1 30 1 35 1 25岩石量1 25 1 10 1 35 1 05 1 1

14、5 1 35 1 05 1 15 1 35 1 25铁含量30%28%29%32%31%33%32%31%33%31%优 化 建 模问题分析 与典型的运输问题明显有以下不同：1.这是运输矿石与岩石两种物资的问题；2.属于产量大于销量的不平衡运输问题；3.为了完成品位约束，矿石要搭配运输；4.产地、销地均有单位时间的流量限制；5.运输车辆只有一种，每次满载运输，154吨/车次；6.铲位数多于铲车数意味着要最优的选择不多于7个产地作为最后结果中的产地；7.最后求出各条路线上的派出车辆数及安排。近似处理：先求出产位、卸点每条线路上的运输量(MIP模型)然后求出各条路线上的派出车辆数及安排 优 化 建

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

16、次数 次；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

17、铲位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.489exam1203.lg4注:LINGO8.0本来是可以得到最优解的，但有些 LINGO8.0可能出现系统错误,可能是系统BUG 优 化 建 模计算结果（派车）铲位1 铲位2 铲位3 铲位4 铲位5 铲位6 铲位7 铲位8 铲位

18、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题空洞探测 优 化 建 模山体隧道坝体等的某些内部结构可用弹性波测量来确定。简化问题可叙述为，一块均匀介质构成的矩形平板内有一些充满空气的空洞。在平板的两个邻

19、边分别等距地设置若干波源，在他们的对边对等地安放同样多的接收器，记录弹性波由每个波源到达对边上每个接收器的时间。根据弹性波在介质和在空气中不同的传播速度来确定板内空洞的位置 优 化 建 模具体问题：一块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(米/

20、秒),且弹性波沿板边缘的传播速度与在介质中的传播速度相同 优 化 建 模P2Q4R3S6 优 化 建 模TP=(tij)tijQ1Q2Q3Q4Q5Q6Q7P1.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.1031P

21、7.4311.3397.3566.1954.0760.0688.1042 优 化 建 模TR=(ij)ijS1S2S3S4S5S6S7R1.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.491

22、9.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(米）以下的空洞是探测不出的 优 化

23、 建 模假设1.观测数据有测量误差。观测数据除测量误差外是可靠的。2.波在传播过程中沿直线单向传播，且不考虑波的反射、折射以及干涉等现象。3.空气密度和介质密度都均匀 优 化 建 模4.“弹性波”在传播过程中没有能量损失。其波速仅与介质有关，且在同一均匀介质中波速不变。弹性波沿板边缘的传播速度与在介质中的传播速度相同。5.假设平板可划分化为网格，空洞定位于每个网格单元内,空洞大小大致相同.优 化 建 模波线与网格交线长度的计算(k,l)记波源Pi与接收器Qj 决定的波线与每个单元（k，l）的交线长度为bijkl i=j 时1 2 3 4 5 6654321 优 化 建 模波线与网格交线长度的计

24、算 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)优 化 建 模波

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)优 化 建 模波线与网格交线长度的计算 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)优 化 建 模波线与网格交线长度的

26、计算 交线在y轴的投影长度(交点条件最多只有2个成立)i=j 以外的情况dyijkl=max(y1ijkl,y2ijkl,y3ijkl,y4ijkl)-min(y1ijkl,y2ijkl,y3ijkl,y4ijkl)由相似三角形关系QjABCDPiRiSjPjdyijkl(k,l)bijklEFGbijkl=aij dyijkl/240 i=j 也成立 优 化 建 模波线与网格交线长度的计算 由对称性，RiSj与单元(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