优化建模与LINGO第12章.ppt

《优化建模与LINGO第12章.ppt》由会员分享，可在线阅读，更多相关《优化建模与LINGO第12章.ppt（58页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、 优优 化化 建建 模模优化建模与LINGO第12章 Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life,there is hope。有生命必有希望。有生命必有希望 优优 化化 建建 模模简要提纲简要提纲 1.CUMCM-1995A:一个飞行管理问题一个飞行管理问题 2.CUMCM-2000B:钢管订购与运输钢管订购与运输3.CUMCM-2003B：露天矿生产的车辆安排：露天矿生产的车辆安排4.CUMCM-2000D:空洞探测空洞探测 优优 化化 建建 模模1995年全国大学生数学建模竞赛年全国大学生数学建模竞赛A题题一个飞行

2、管理问题一个飞行管理问题 优优 化化 建建 模模一个飞行管理问题在约10000m高空的某边长160km的正方形区域内,经常有若干架飞机作水平飞行,区域内每架飞机的位置和速度向量均由计算机记录其数据,以便进行飞行管理.当一架欲进入该区域的飞机到达边界区域边缘时,记录其数据后,要立即计算并判断是否会与其区域内的飞机发生碰撞.如果会碰撞,则应计算如何调整各架(包括新进入的)飞机飞行的方向角,以避免碰撞.现假设条件如下:1)不碰撞的标准为任意两架飞机的距离大于8km;2)飞机飞行方向角调整的幅度不应超过30度;3)所有飞机飞行速度均为每小时为800km;4)进入该区域的飞机在到达区域边缘时,与区域内飞

3、机的距离应在60km以上;5)最多考虑6架飞机;6)不必考虑飞机离开此区域后的状况;优优 化化 建建 模模请你对这个避免碰撞的飞行管理问题建立数学模型.列出计算步骤,对以下数据进行计算(方向角误差不超过0.01度),要求飞机飞行方向角调整的幅度尽量小.设该区域4个顶点坐标为(0,0),(160,0),(160,160),(0,160).记录数据为:飞机编号横坐标x纵坐标y方向角(度)1150140243285852363150155220.54145501595130150230新进入0052注:方向角指飞行方向与x轴正向的夹角 优优 化化 建建 模模两架飞机不碰撞的条件两架飞机不碰撞的条件（

4、0t Tij）Ti为第为第i架飞机飞出区域的时刻架飞机飞出区域的时刻不碰撞条件不碰撞条件初始位置时刻t飞机的位置两架飞机的距离（平方）优优 化化 建建 模模不必考虑在区域外的碰撞两架飞机都在区域中的时间具体来看，第i架飞机在区域内的时间飞机飞出区域的时刻飞机飞出区域的时刻 优优 化化 建建 模模整理：fij(t)的最小值(-bij2/4+cij)；此时其中：优优 化化 建建 模模不碰撞条件的等价表述不碰撞条件的等价表述 最后，优化模型为最后，优化模型为 fij(t)大于等于肯定成立fij(t)大于等于等价于fij(t)大于等于等价于 优优 化化 建建 模模LINGOLINGO求解求解程序程序e

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

6、模竞赛年全国大学生数学建模竞赛B题题钢管订购与运输钢管订购与运输 优优 化化 建建 模模问题描述问题描述 由钢管厂订购钢管，经铁由钢管厂订购钢管，经铁路、公路运输，铺设一条路、公路运输，铺设一条钢管管道钢管管道A1325801010312012427010881070627030202030450104301750606194205201680480300220210420500600306195202720690520170690462160320160110290115011001200A2A3A4A5A6A7A8A9A10A11A12A13A14A15S1S2S3S4S5S6S7管道铁路

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

8、？A1325801010312012427010881070627030202030450104301750606194205201680480300220210420500600306195202720690520170690462160320160110290115011001200A2A3A4A5A6A7A8A9A10A11A12A13A14A15S1S2S3S4S5S6S7A16130A17A18A19A20A21190260100（3）讨论管道为树形图的情形）讨论管道为树形图的情形 优优 化化 建建 模模问题问题1的基本模型和解法的基本模型和解法总费用最小的优化问题总费用：订购，运输

9、（由各厂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+1之和等于AjAj+1段的长度ljyj zjAj-1AjAj+1 优优 化化 建建 模模基本模型基本模型由Aj向AjAj-1段铺设的运量为1+yj=yj(yj+1)/2由Aj向AjAj+1段铺设的运量为1+zj=zj(zj

10、+1)/2二次规划?优优 化化 建建 模模求解步骤求解步骤1）求由Si至Aj的最小购运费用路线及最小费用cij难点：公路运费是里程的线性函数，而铁路运费是里程的分段阶跃函数，故总运费不具可加性。因而计算最短路常用的Dijkstra算法、Floyd算法失效。A17010881070627030202030300220210420500170690462160320160110290A10A11A12A13A14A15S4S5S6S7需要对铁路网和公路网进行预处理，才能使用常用算需要对铁路网和公路网进行预处理，才能使用常用算法，得到最小购运费用路线。法，得到最小购运费用路线。-至少求至少求3次最短

11、路次最短路如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之间距离的临时标号，即从节点之间距离的临时标号，即从节点i到到j但不允许经过其他节点但不允许经过其

12、他节点k，k+1，,n时的最短距离时的最短距离 优优 化化 建建 模模实际上只有S4和S7需要分解成子问题求解每个子问题是标准的二次规划，决策变量为xij,yj,zj,不超过135个。优优 化化 建建 模模fi表示钢厂表示钢厂i是否使用；是否使用；xij是从钢厂是从钢厂i运到节点运到节点j的钢管量的钢管量yj是从节点是从节点j向左铺设的钢管量；向左铺设的钢管量；zj是向右铺设的钢管量是向右铺设的钢管量c)比较好的方法：引入比较好的方法：引入0-10-1变量变量LINDO/LINGO得到的结果比得到的结果比matlab得到的好得到的好exam1202d.lg4yj zjAj 优优 化化 建建 模

13、模问题问题2:分析对购运计划和总费用影响分析对购运计划和总费用影响(哪个钢厂销价变哪个钢厂销价变化影响最大；哪个钢厂产量上限变化影响最大化影响最大；哪个钢厂产量上限变化影响最大)规划问题的灵敏度分析问题问题3：管道为树形图管道为树形图701088107062300220210170690462160320160A10A11A12S4S5S6130A17A18A19A20190260100(jk)是连接Aj,Ak的边，E是树形图的边集，ljk是(jk)的长度，yjk是由Aj沿(jk)铺设的钢管数量 优优 化化 建建 模模2003年全国大学生数学建模竞赛年全国大学生数学建模竞赛B题题露天矿生产的车

14、辆安排露天矿生产的车辆安排 优优 化化 建建 模模露天矿里铲位已分成矿石和岩石露天矿里铲位已分成矿石和岩石:平均铁含量不低于平均铁含量不低于25%的为矿石，否则为岩石。每个铲位的矿石、岩石数的为矿石，否则为岩石。每个铲位的矿石、岩石数量，以及矿石的平均铁含量（称为品位）都是已知的。量，以及矿石的平均铁含量（称为品位）都是已知的。每个铲位至多安置一台电铲，电铲平均装车时间每个铲位至多安置一台电铲，电铲平均装车时间5分钟分钟卡车在等待时所耗费的能量也是相当可观的，原则上在卡车在等待时所耗费的能量也是相当可观的，原则上在安排时安排时不应发生卡车等待不应发生卡车等待的情况。的情况。露天矿生产的车辆安排

15、露天矿生产的车辆安排矿石卸点需要的铁含量要求都为矿石卸点需要的铁含量要求都为29.5%1%(品位限制）品位限制），搭配量在一个班次（，搭配量在一个班次（8小时）内满足品位限制即可。小时）内满足品位限制即可。卸点在一个班次内不变。卡车载重量为卸点在一个班次内不变。卡车载重量为154吨，平均时吨，平均时速速28km,平均卸车时间为平均卸车时间为3分钟。分钟。问题：出动几台电铲，分别在哪些铲位上；出动几辆问题：出动几台电铲，分别在哪些铲位上；出动几辆卡车，分别在哪些路线上各运输多少次卡车，分别在哪些路线上各运输多少次?优优 化化 建建 模模平面示意图 优优 化化 建建 模模问题数据问题数据 距离铲位

16、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.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矿石量0951051001051101251051301

17、35125岩石量125110135105115135105115135125铁含量30%28%29%32%31%33%32%31%33%31%优优 化化 建建 模模问题分析问题分析 与典型的运输问题明显有以下不同：与典型的运输问题明显有以下不同：1.这是运输矿石与岩石两种物资的问题；这是运输矿石与岩石两种物资的问题；2.属于产量大于销量的不平衡运输问题；属于产量大于销量的不平衡运输问题；3.为了完成品位约束，矿石要搭配运输；为了完成品位约束，矿石要搭配运输；4.产地、销地均有单位时间的流量限制；产地、销地均有单位时间的流量限制；5.运输车辆只有一种，每次满载运输，运输车辆只有一种，每次满载运输

18、，154吨吨/车次；车次；6.铲位数多于铲车数意味着要最优的选择不多于铲位数多于铲车数意味着要最优的选择不多于7个个产地作为最后结果中的产地；产地作为最后结果中的产地；7.最后求出各条路线上的派出车辆数及安排。最后求出各条路线上的派出车辆数及安排。近似处理：近似处理：先求出产位、卸点每条线路上的运输量先求出产位、卸点每条线路上的运输量(MIP模型模型)然后求出各条路线上的派出车辆数及安排然后求出各条路线上的派出车辆数及安排 优优 化化 建建 模模模型假设模型假设卡车在一个班次中不应发生等待或熄火后再启动卡车在一个班次中不应发生等待或熄火后再启动的情况；的情况；在铲位或卸点处由两条路线以上造成的

19、冲突问题在铲位或卸点处由两条路线以上造成的冲突问题面前，我们认为只要平均时间能完成任务，就认面前，我们认为只要平均时间能完成任务，就认为不冲突。我们不排时地进行讨论；为不冲突。我们不排时地进行讨论；空载与重载的速度都是空载与重载的速度都是28km/h，耗油相差很大；，耗油相差很大；卡车可提前退出系统，等等。卡车可提前退出系统，等等。如理解为严格不等待，难以用数学规划模型来解如理解为严格不等待，难以用数学规划模型来解 个别参数队找到了可行解个别参数队找到了可行解（略）（略）优优 化化 建建 模模符号符号xij：从：从i铲位到铲位到j号卸点的石料运量号卸点的石料运量（车）（车）单位：单位：吨；吨；

20、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 吨吨

21、cki：i号铲位的铁矿石储量号铲位的铁矿石储量 万吨万吨cyi：i号铲位的岩石储量号铲位的岩石储量 万吨万吨fi:描述第描述第i号铲位是否使用的号铲位是否使用的0-1变量，取变量，取1为使用；为使用；0为关闭。为关闭。(近似近似)优优 化化 建建 模模优化模型（1）道路能力道路能力(卡车数卡车数)约束约束（2）电铲能力约束（3）卸点能力约束（4）铲位储量约束（5）产量任务约束（6）铁含量约束（7）电铲数量约束（8）整数约束.xij为非负整数fi 为0-1整数 优优 化化 建建 模模计算结果（计算结果（LINGOLINGO软件）软件）铲位1铲位2铲位3铲位4铲位5铲位6铲位7铲位8铲位9铲位10

22、矿漏131354541111倒42424343岩场70701515岩漏81814343倒13132 27070铲位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 优优 化化 建建 模模计算结果（派车）计算结果（派车）铲位1铲位2铲位3铲位4铲位5铲位6铲位7铲位8

23、铲位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辆）限制（其实上面的模型也辆）限制（其实上面的模型也应该有）应该

24、有）优优 化化 建建 模模2000年全国大学生数学建模竞赛年全国大学生数学建模竞赛D题题空洞探测空洞探测 优优 化化 建建 模模山体隧道坝体等的某些内部结构可用弹性波测量来确定。简化问题可叙述为，一块均匀介质构成的矩形平板内有一些充满空气的空洞。在平板的两个邻边分别等距地设置若干波源，在他们的对边对等地安放同样多的接收器，记录弹性波由每个波源到达对边上每个接收器的时间。根据弹性波在介质和在空气中不同的传播速度来确定板内空洞的位置 优优 化化 建建 模模具体问题：一块240(米)240(米)的平板ABCD，在AB边等距地设置7个波源Pi(i=1,7),在CD边等距地设置7个接收器Qj(j=1,7

25、),记录由Pi发出的弹性波到达Qj的时间tij(秒);在AD边等距地设置7个波源Ri(i=1,7),在BC边等距地设置7个接收器Sj(j=1,7),记录由Ri发出的弹性波到达Sj的时间ij(秒)。已知弹性波在介质和空气中的传播速度分别为2880(米/秒)和320(米/秒),且弹性波沿板边缘的传播速度与在介质中的传播速度相同 优优 化化 建建 模模P2Q4R3S6 优优 化化 建建 模模TP=(tij)tijQ1Q2Q3Q4Q5Q6Q7P1.0611.0895.1996.2032.4181.4923.5646P2.0989.0592.4413.4318.4770.5242.3805P3.3052

26、.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 优优 化化 建建 模模TR=(ij)ijS1S2S3S4S5S6S7R1.0645.0602.0813.3516.3867.4314.5721R2.0753.0700.2852.4341.3491.4800.4980R3.3456.3205.

27、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 优优 化化 建建 模模要求：(1)确定该平面内空洞的位置。(2)只根据Pi发出的弹性波到达Qj的时间tij能确定空洞的位置吗？讨论在同样能够确定空洞位置的前提下，减少波源和接收器的方法。优优 化化 建建 模模分析:弹性波沿平板边缘的理论传播时间t=240

28、/2880=0.0833(秒)弹性波沿平板边缘的实际传播时间t11=.0611,t77=.1042,11=.0645,77=.0583题目中已假设“弹性波沿板边缘的传播速度与在介质中的传播速度相同”观测数据的最大绝对误差为d=0.025秒.可以认为，可以认为，0.025*360=9(米）以下的空洞是探米）以下的空洞是探测不出的测不出的 优优 化化 建建 模模假设1.观测数据有测量误差。观测数据除测量误差外是可靠的。2.波在传播过程中沿直线单向传播，且不考虑波的反射、折射以及干涉等现象。3.空气密度和介质密度都均匀 优优 化化 建建 模模4.“弹性波”在传播过程中没有能量损失。其波速仅与介质有关

29、，且在同一均匀介质中波速不变。弹性波沿板边缘的传播速度与在介质中的传播速度相同。5.假设平板可划分化为网格，空洞定位于每个网格单元内,空洞大小大致相同.优优 化化 建建 模模波线与网格交线长度的计算波线与网格交线长度的计算(k,l)记波源记波源Pi与接收器与接收器Qj 决定的决定的波线与每个单元（波线与每个单元（k，l）的交线长度为的交线长度为bijkl i=j 时时123456654321 优优 化化 建建 模模波线与网格交线长度的计算波线与网格交线长度的计算 PiQj 决定的直线方程：决定的直线方程：(j-i）y=6(x-40(i-1)i=j 以外的情况以外的情况单元单元(k,l)左边缘直

30、线方程左边缘直线方程 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(

31、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=6(x-40(i-1)i

32、=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)由相似三角形关系由相似三角形关

33、系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）

34、之间的距离）之间的距离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!Thank you very much!