优化建模与LINGO第12章

优化建模与LINDO/LINGO软件第12章数学建模竞赛中的部分优化问题［原书相关信息］谢金星,薛毅编，清华大学出版社,2005年7月出版./~jxie/lindo简要提纲1.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方向角(度)1150140243285852363150155220.54145501595130150230新进入0052注:方向角指飞行方向与x轴正向的夹角两架飞机不碰撞的条件（0≤t≤Tij）

Ti为第i架飞机飞出区域的时刻不碰撞条件

初始位置

时刻t飞机的位置两架飞机的距离（平方）不必考虑在区域外的碰撞

两架飞机都在区域中的时间具体来看，第i架飞机在区域内的时间飞机飞出区域的时刻整理：

fij(t)的最小值(-bij2/4+cij)

；此时其中：

不碰撞条件的等价表述

最后，优化模型为

fij(t)大于等于０肯定成立fij(t)大于等于０等价于fij(t)大于等于０等价于LINGO求解程序exam1201a.lg4一个简化的数学模型任何一架飞机在区域中停留最长时间

放松到任两架飞机在这段时间不碰撞甚至放松到任两架飞机永远不碰撞其他目标调整后的方向角

总的调整量最小

最大调整量最小

初始位置与方向角基于相对运动观点的模型基于相对运动观点的模型于是

数学规划模型

LINGO求解程序exam1201b.lg4注意：应先计算出初始时刻的βij2000年全国大学生数学建模竞赛B题

钢管订购与运输

问题描述由钢管厂订购钢管，经铁路、公路运输，铺设一条钢管管道A1325801010312012427010881070627030202030450104301750606194205201680480300220210420500600306195202720690520170690462160320160110290115011001200A2A3A4A5A6A7A8A9A10A11A12A13A14A15S1S2S3S4S5S6S7管道铁路公路S1~S7钢管厂火车站450里程（km)（沿管道建有公路）钢厂的产量和销价（1单位钢管=1km管道钢管）钢厂产量的下限：500单位钢管1单位钢管的铁路运价1000km以上每增加1至100km运价增加5万元1单位钢管的公路运价：0.1万元/km（不足整公里部分按整公里计）（1）制定钢管的订购和运输计划，使总费用最小.（2）分析对购运计划和总费用影响：哪个钢厂钢管销价的变化影响最大；哪个钢厂钢管产量上限的变化影响最大？A1325801010312012427010881070627030202030450104301750606194205201680480300220210420500600306195202720690520170690462160320160110290115011001200A2A3A4A5A6A7A8A9A10A11A12A13A14A15S1S2S3S4S5S6S7A16130A17A18A19A20A21190260100（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最优购运计划约束条件钢厂产量约束：上限和下限（如果生产的话）运量约束：xij对i求和等于zj加yj；

zj与

yj+1之和等于AjAj+1段的长度ljyj

zjAj-1

Aj

Aj+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算法失效。A17010881070627030202030300220210420500170690462160320160110290A10A11A12A13A14A15S4S5S6S7需要对铁路网和公路网进行预处理，才能使用常用算法，得到最小购运费用路线。--至少求3次最短路如S7至A10的最小费用路线先铁路1130km，再公路70km,运费为77（万元）先公路（经A15）40km,再铁路1100km，再公路70km,运费为76（万元）任意两点之间最短路的Floyd-Warshall算法1）求由Si至Aj的最小购运费用路线及最小费用cij

A13次最短路的LINGO程序：Exam1202a.lg4Exam1202b.lg4Exam1202c.lg4uij(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得到的好exam1202d.lg4yj

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

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

矿石卸点需要的铁含量要求都为29.5%

1%(品位限制），搭配量在一个班次（8小时）内满足品位限制即可。卸点在一个班次内不变。卡车载重量为154吨，平均时速28km,平均卸车时间为3分钟。问题：出动几台电铲，分别在哪些铲位上；出动几辆卡车，分别在哪些路线上各运输多少次?平面示意图问题数据距离铲位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矿石量0．951．051．001．051．101．251．051．301．351．25岩石量1．251．101．351．051．151．351．051．151．351．25铁含量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）道路能力(卡车数)约束