资源描述
单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,建模实例与求解,建模实例与求解,最短路问题,飞行管理问题,下料问题,露天矿的运输问题,钢管运输问题,最短路问题,定义 是由 点出发至终点 的最短路程，由最优化原理可得,这是一个函数方程，用,LINGO,可以方便的解决。,最短路问题,最短路问题LINGO源程序(),计算的部分结果为：,Feasible solution found at iteration: 0,Variable Value,P( 1, 3) 0.000000,在约10,000米高空的某边长160公里的正方形区域内, 经常有若干架,飞机作水平飞行。区域内每架飞机的位置和速度均由计算机记录其,数据，以便进行飞行管理。当一架欲进入该区域的飞机到达区域边,缘, 记录其数据后，要立即计算并判断是否会与区域内的飞机发生,碰撞。如果会碰撞，则应计算如何调整各架(包括新进入的)飞机飞,行方向角，以避免碰撞。现假定条件如下:,1),不碰撞的标准为任意两架飞机的距离大于,8,公里,;,2),飞机飞行方向角调整的幅度不应超过,30,度,;,3),所有飞机飞行速度均为每小时,800,公里,;,4),进入该区域的飞机在到达区域边缘时,与区域内飞机的距离应在,60,公里以上,;,5),最多需考虑,6,架飞机,;,6),不必考虑飞机离开此区域后的状况。,请你对这个避免碰撞的飞行管理问题建立数学模型，列出计算步,骤，对以下数据进行计算,(,方向角误差不超过,度,),，要求飞机飞,行方向角调整的幅度尽量小。设该区域,4,个顶点的座标为,(0,0),，,(160,0),，,(160,160),，,(0,160),。记录数据为,:,飞行管理问题,飞机编号,横座标x,纵座标y,方向角(度),1,150,140,243,2,85,85,236,3,150,155,220.5,4,145,50,159,5,130,150,230,新进入,0,0,52,注: 方向角指飞行方向与x轴正向的夹角。试根据,实际应用背景对你的模型进行评价与推广。,飞行管理问题,模型及求解,模型的建立,飞行管理问题,飞行管理问题,飞行管理问题,飞行管理问题,模型求解,ij,=,max,，这实际上强化了问题的要求，即考虑了有些飞机可能已经飞出区域，但仍不允许两架飞机的距离小于Km,这个简化的模型可以输入LINGO软件演示：,结果：,飞行管理问题,问题1. 如何下料最节省 ?,钢管下料,问题2. 客户增加需求：,原料钢管:每根,19,米,4,米,50,根,6,米,20,根,8,米,15,根,客户需求,节省的标准是什么？,由于采用不同切割模式太多，会增加生产和管理成本，规定切割模式不能超过3种。如何下料最节省？,5,米,10,根,按照客户需要在一根原料钢管上安排切割的一种组合。,切割模式,余料1米,4,米,1,根,6,米,1,根,8米1根,余料3米,4米1根,6米1根,6米1根,合理切割模式的余料应小于客户需要钢管的最小尺寸,余料3米,8米1根,8米1根,钢管下料,为满足客户需要，按照哪些种合理模式，每种模式切割多少根原料钢管，最为节省？,合理切割模式,2. 所用原料钢管总根数最少,模式,4米钢管根数,6米钢管根数,8米钢管根数,余料(米),1,4,0,0,3,2,3,1,0,1,3,2,0,1,3,4,1,2,0,3,5,1,1,1,1,6,0,3,0,1,7,0,0,2,3,钢管下料问题1,两种标准,1. 原料钢管剩余总余量最小,x,i,按第,i,种模式切割的原料钢管根数(,i,=,1,2,7,),约束,满足需求,决策变量,目标1（总余量）,按模式,2,切割,12,根,按模式,5,切割,15,根，余料,27,米,模,式,4米,根数,6米,根数,8米,根数,余,料,1,4,0,0,3,2,3,1,0,1,3,2,0,1,3,4,1,2,0,3,5,1,1,1,1,6,0,3,0,1,7,0,0,2,3,需,求,50,20,15,最优解：,x,2,=12,x,5,=15,其余为0；,最优值：,27,整数约束：,x,i,为整数,当余料没有用处时，,通常以总根数最少为目标,目标,2（总根数）,钢管下料问题1,约束条件不变,最优解：,x,2,=15,x,5,=5,x,7,=5,其余为0；,最优值：,25。,x,i,为整数,按模式2切割15根，按模式5切割5根，按模式7切割5根，共25根，余料35米,虽余料增加8米，但减少了2根,与,目标,1的结果“共切割27根，余料27米” 相比,钢管下料问题2,对大规模问题，用模型的约束条件界定合理模式,增加一种需求：,5,米,10,根；切割,模式不超过3种。,现有4种,需求：,4,米,50,根，,5,米,10,根，,6,米,20,根，,8,米,15,根，用枚举法确定合理切割模式，过于复杂。,决策变量,x,i,按第,i,种模式切割的原料钢管根数(,i,=,1,2,3,),r,1,i,r,2,i,r,3,i,r,4,i, 第,i,种切割模式下，每根原料钢管生产4米、5米、6米和8米长的钢管的数量,满足需求,模式合理：每根余料不超过3米,整数非线性规划模型,钢管下料问题2,目标函数（,总根数）,约束条件,整数约束：,x,i,r,1,i,r,2,i,r,3,i,r,4,i,(,i,=,1,2,3,),为整数,增加约束，缩小可行域，便于求解,原料钢管总根数下界：,特殊生产计划：对每根原料钢管,模式1：切割成4根4米钢管，需13根；,模式2：切割成1根5米和2根6米钢管，需10根；,模式3：切割成2根8米钢管，需8根。,原料钢管总根数上界：31,模式排列顺序可任定,钢管下料问题2,需求：,4,米,50,根，,5,米,10,根，,6,米,20,根，,8,米,15,根,每根原料钢管长19米,LINGO求解整数非线性规划模型,Local optimal solution found at iteration: 12211,Variable Value Reduced Cost,R22 1.000000 0.000000 R23 0.000000 0.000000 R31 1.000000 0.000000 R32 1.000000 0.000000 R33 0.000000 0.000000 R41 0.000000 0.000000 R42 0.000000 0.000000 R43 2.000000 0.000000,模式1：每根原料钢管切割成2根4米、1根5米和1根6米钢管，共10根；(书上模式1与模式2相反了),模式2：每根原料钢管切割成3根4米和1根6米钢管，共10根；,模式3：每根原料钢管切割成2根8米钢管，共8根。,原料钢管总根数为28根。,演示；,露天矿里铲位已分成矿石和岩石: 平均铁含量不低于25%的为矿石，否则为岩石。每个铲位的矿石、岩石数量，以及矿石的平均铁含量（称为品位）都是已知的。每个铲位至多安置一台电铲，电铲平均装车时间5分钟,卡车在等待时所耗费的能量也是相当可观的，原则上在安排时不应发生卡车等待的情况。,露天矿生产的车辆安排(CUMCM-2003B),矿石卸点需要的铁含量要求都为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.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,矿石量,095,105,100,105,110,125,105,130,135,125,岩石量,125,110,135,105,115,135,105,115,135,125,铁含量,30%,28%,29%,32%,31%,33%,32%,31%,33%,31%,问题分析,与典型的运输问题明显有以下不同：,这是运输矿石与岩石两种物资的问题；,属于产量大于销量的不平衡运输问题；,为了完成品位约束，矿石要搭配运输；,产地、销地均有单位时间的流量限制；,运输车辆只有一种，每次满载运输，,154,吨,/,车次；,铲位数多于铲车数意味着要最优的选择不多于,7,个产地作为最后结果中的产地；,最后求出各条路线上的派出车辆数及安排。,近似处理：,先求出产位、卸点每条线路上的运输量,(MIP,模型,),然后求出各条路线上的派出车辆数及安排,模型假设,卡车在一个班次中不应发生等待或熄火后再启动的情况；,在铲位或卸点处由两条路线以上造成的冲突问题面前，我们认为只要平均时间能完成任务，就认为不冲突。我们不排时地进行讨论；,空载与重载的速度都是28km/h，耗油相差很大；,卡车可提前退出系统，等等。,如理解为严格不等待，难以用数学规划模型来解,个别参数队找到了可行解 （略）,符号,x,ij,：从i铲位到j号卸点的石料运量 （车） 单位： 吨；,c,ij,：从i号铲位到j号卸点的距离 公里；,T,ij,:从i号铲位到号j卸点路线上运行一个周期平均时间 分；,A,ij,：从号铲位到号卸点最多能同时运行的卡车数 辆；,B,ij,：从号铲位到号卸点路线上一辆车最多可运行的次数 次；,p,i,：i号铲位的矿石铁含量 p=(30,28,29,32,31,33,32,31,33,31) %,q,j,: j号卸点任务需求，q=(1.2,1.3,1.3,1.9,1.3)*10000 吨,ck,i,：i号铲位的铁矿石储量 万吨,cy,i,：i号铲位的岩石储量 万吨,f,i,:描述第i号铲位是否使用的0-1变量，取1为使用；0为关闭。,(近似),优化模型,（1）,道路能力(卡车数)约束,（2）电铲能力约束,（3）卸点能力约束,（4）铲位储量约束,（5）产量任务约束,（6）铁含量约束,（7）电铲数量约束,（8）整数约束,.,x,ij,为非负整数,f,i,为0-1整数,计算结果（LINGO软件）,铲位1,铲位2,铲位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.489,cumcm2003b1.lg4,计算结果（派车）,铲位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处各放置一台电铲。,一共使用了13辆卡车；总运量为85628.62吨公里；,岩石产量为32186吨；矿石产量为38192吨。,此外：6辆联合派车（方案略）,最大化产量,结论：,（略）,目标函数变化,此外：车辆数量（20辆）限制（其实上面的模型也应该有）,钢管运输问题（CUMCM-2000B),要铺设一条,的输送天然气的主管道, 如图所示(见下页)。经筛选后可以生产这种主管道钢管的钢厂有,表示公路，双细线表示要铺设的管道(假设沿,管道或者原来有公路，或者建有施工公路)，,圆圈表示火车站，每段铁路、公路和管道旁,的阿拉伯数字表示里程(单位km)。,为方便计，1km主管道钢管称为1单位钢管。,图中粗线表示铁路，单细线,A,1,3,2,5,80,10,10,31,20,12,42,70,10,88,10,70,62,70,30,20,20,30,450,104,301,750,606,194,205,201,680,480,300,220,210,420,500,600,3060,195,202,720,690,520,170,690,462,160,320,160,110,290,1150,1100,1200,A,2,A,3,A,4,A,5,A,6,A,7,A,8,A,9,A,10,A,11,A,12,A,13,A,14,A,15,S,1,S,2,S,3,S,4,S,5,S,6,S,7,铁路运价表,里程,300,301350,351400,401450,451500,运价,20,23,26,29,32,钢管运输问题（CUMCM-2000B),钢管运输问题（CUMCM-2000B),一个钢厂如果承担制造这种钢管，至少需要生产500,个单位。钢厂,在指定期限内能生产该钢管的最大,个单位，钢管出厂销价1单位钢管为,万元，如下表：,数量为,1,2,3,4,5,6,7,800,800,1000,2000,2000,2000,3000,160,155,155,160,155,150,160,1单位钢管的铁路运价如下表：,钢管运输问题（CUMCM-2000B),里程(km),300,301350,351400,401450,451500,运价(万元),20,23,26,29,32,里程(km),501600,601700,701,800,801,900,900,1000,运价(万元),37,44,50,55,60,1000km以上每增加1至100km运价增加5万元。,钢管运输问题（CUMCM-2000B),公路运输费用为1单位钢管每公里0.1万元（不足整公里部分按整,公里计算）。钢管可由铁路、公路运往铺设地点（不只是运到点,，而是管道全线）。,(1),请制定一个主管道钢管的订购和运输计划，使总费用最小,（给出总费用,),。,(2),请就（,1,）的模型分析：哪个钢厂钢管的销价的变化对购,运计划和总费用影响最大，哪个钢厂钢管的产量的上限的变化,对购运计划和总费用的影响最大，并给出相应的数字结果。,(3),如果要铺设的管道不是一条线，而是一个树形图，铁路、,公路和管道构成网络，请就这种更一般的情形给出一种解决办,法，并对图二按（,1,）的要求给出模型和结果。,钢管运输问题（CUMCM-2000B),常用解法: 二次规划,先计算最小运费矩阵,两种运输方式（铁路公路）混合最短路问题,是普通最短路问题的变种，需要自己设计算法,钢管运输问题（CUMCM-2000B),钢管运输问题（CUMCM-2000B),运输矩阵的计算模型,问题分析,铁路子网络,钢管运输问题（CUMCM-2000B),钢管运输问题（CUMCM-2000B),对图中的节点编号（除已经编号的节点S,1,-S,7,、A1-A15外，再增加编号B1-B17，）如下图：,LINGO程序为：,钢管运输问题,公路子网络,类似的，可以假设公路运输路线应该走最短路径，把,公路运输子网络独立出来，在这里网络上计算任意两,个节点,i,，,j,之间的最短长度，然后按照这个最短路长度,（因为公路运输费用为单位钢管每公里,.,万元）,此时，,LINGO,模型为：,钢管运输问题,购运费用矩阵,在上面的基础上，就可以将以上两个子网络（需要完全看,成两个完全子图）组合成一个网络，每条弧上相应的运费,钢管运输问题,算法采用Floyd-Warshall，LINGO程序为：,CUMCM-2000B-c.lg4,混合费用C,ij,为：,f,i,表示钢厂,i,是否使用；,x,ij,是从钢厂,i,运到节点,j,的钢管量,y,j,是从节点,j,向左铺设的钢管量；,z,j,是向右铺设的钢管量,钢管运输问题（CUMCM-2000B),LINDO/LINGO,得到的结果比,matlab,得到的好,CUMCM-2000B-d.lg4,其他优化赛题,空洞探测问题,钻井布局问题,抢渡长江问题,等等,俞雪永于2006.5.1 制作,谢谢大家！,
展开阅读全文