优化建模与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轴正向的夹角优化建模两架飞机不碰撞的条件222)()()(tjttjtijyyxxtrii,sin,cos00iitiitivtyyvtxxi064)()(2trtfijij（0≤t≤Tij）Ti为第i架飞机飞出区域的时刻不碰撞条件000),,(iiiyxiii0初始位置时刻t飞机的位置两架飞机的距离（平方）优化建模),min(jiijTTT00000000000000000000tan,223tan,23,sin,tan,23tan,2,cos,tan,2tan,20,sin,tan,223tan,20,cosiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiixDyorxyifvyxyorxyDifvxxyDorxDyDifvxDxDyorxDyDifvxDT不必考虑在区域外的碰撞两架飞机都在区域中的时间具体来看，第i架飞机在区域内的时间飞机飞出区域的时刻优化建模.)(2ijijijijijczbztf整理：fij(t)的最小值(-bij2/4+cij)；此时其中：.2sin4*jiijijvbt优化建模不碰撞条件的等价表述最后，优化模型为0*ijt若fij(t)大于等于０肯定成立ijijTt*若fij(t)大于等于０等价于0)(ijijTfijijTt*0若fij(t)大于等于０等价于0)(*ijtfij,042ijijcb优化建模LINGO求解程序exam1201a.lg4283.0800/2160/2maxvDT一个简化的数学模型任何一架飞机在区域中停留最长时间放松到任两架飞机在这段时间不碰撞甚至放松到任两架飞机永远不碰撞优化建模000),,(iiiyxiii0.61iiMin其他目标调整后的方向角总的调整量最小||max6,...,1iiMin最大调整量最小初始位置与方向角优化建模基于相对运动观点的模型优化建模))22sin(),22(cos(2sin2)2cos,2sin(2sin2)2cos2sin,2sin2sin(2)sinsin,coscos(jijijijijijijijijijiijijvvvvvvvvvijijr基于相对运动观点的模型,8sin1ijijr优化建模于是.6,,1,30,,6,,1,,)(..21612ijijitsMiniijjiijii数学规划模型优化建模LINGO求解程序exam1201b.lg4注意：应先计算出初始时刻的βij优化建模2000年全国大学生数学建模竞赛B题钢管订购与运输优化建模问题描述由钢管厂订购钢管，经铁路、公路运输，铺设一条钢管管道1521AAAA1325801010312012427010881070627030202030450104301750606194205201680480300220210420500600306195202720690520170690462160320160110290115011001200A2A3A4A5A6A7A8A9A10A11A12A13A14A15S1S2S3S4S5S6S7管道铁路公路S1~S7钢管厂火车站450里程（km)（沿管道建有公路）优化建模钢厂i1234567产量上限is80080010002000200020003000销价ip（万元）160155155160155150160钢厂的产量和销价（1单位钢管=1km管道钢管）钢厂产量的下限：500单位钢管里程(km)≤300301～350351～400401～450451～500运价(万元)2023262932里程(km)501～600601～700701～800801～900901～1000运价(万元)37445055601单位钢管的铁路运价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段的长度ljyjzjAj-1AjAj+1优化建模基本模型由Aj向AjAj-1段铺设的运量为1+…+yj=yj(yj+1)/2由Aj向AjAj+1段铺设的运量为1+…+zj=zj(zj+1)/2)6(0,0)5(15,,2,1,7,,2,10,0,0)4(14,,2,1)3(15,,2,1)2(7,,2,1],500[}0{..)1())1()1((21.0min15117115171151151zyjiyzxjlyzjyzxisxtsyyzzxcjjijjjjjjiijijijijjjjjjijij二次规划?优化建模求解步骤1）求由Si至Aj的最小购运费用路线及最小费用cij难点：公路运费是里程的线性函数，而铁路运费是里程的分段阶跃函数，故总运费不具可加性。因而计算最短路常用的Dijkstra算法、Floyd算法失效。A17010881070627030202030300220210420500170690462160320160110290A10A11A12A13A14A15S4S5S6S7需要对铁路网和公路网进行预处理，才能使用常用算法，得到最小购运费用路线。--至少求3次最短路如S7至A10的最小费用路线先铁路1130km，再公路70km,运费为77（万元）先公路（经A15）40km,再铁路1100km，再公路70km,运费为76（万元）优化建模任意两点之间最短路的Floyd-Warshall算法1）求由Si至Aj的最小购运费用路线及最小费用cijA13次最短路的LINGO程序：Exam1202a.lg4Exam1202b.lg4Exam1202c.lg4.,,1,,},,min{,,,0)()()()1()1()1(nkjiuuuujiwuukkjkikkijkijijijiiuij(k)是任意两个节点i，j之间距离的临时标号，即从节点i到j但不允许经过其他节点k，k+1，…,n时的最短距离优化建模的处理约束条件)7,,2,1(],500[}0{)2151isxijij问题求解。，分解为上述形式的子的那些求解，再对解中满足先松弛为ixisxbjijijij5000)7,1(0)151151个子问题共和分解为71511512)7,1(5000)isxxaijijjij实际上只有S4和S7需要分解成子问题求解每个子问题是标准的二次规划，决策变量为xij,yj,zj,不超过135个。0,0,,,,,0..)(05.0min1511711512151271151zyzyxlyzzyxsxtsyyzzxcjjijjjjjijijjiijjjjjjijijij优化建模fi表示钢厂i是否使用；xij是从钢厂i运到节点j的钢管量yj是从节点j向左铺设的钢管量；zj是向右铺设的钢管量c)比较好的方法：引入0-1变量.7,...,1,1,0,0.14,...,1.15,...,1,.7,...,1,500..])1()1[(21.0)(151171151151,ifzyjbzyjzyxifSxftszzyyxcpMinijjjjjiijiijijijjjjjjiijiji•LINDO/LINGO得到的结果比matlab得到的好exam1202d.lg4yjzjAj优化建模问题2:分析对购运计划和总费用影响(哪个钢厂销价变化影响最大；哪个钢厂产量上限变化影响最大)规划问题的灵敏度分析问题3：管道为树形图701088107062300220210170690462160320160A10A11A12S4S5S6130A17A18A19A20190260100,0,,,,]},500[,0{..)(05.0min71)(2112211)(71211jkijjkkjjkijkEjkijjiijjkjkjEjkijijijyxbyyyxsxtsyyxc(jk)是连接Aj,Ak的边，E是树形图的边集，ljk是(jk)的长度，yjk是由Aj沿(jk)铺设的钢管数量优化建模2003年全国大学生数学建模竞赛B题露天矿生产的车辆安排优化建模露天矿里铲位已分成矿石和岩石:平均铁含量不低