单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,1,问题的提出,一、已知某露天矿的基本情况与要求,二、一个班次的生产计划的内容和原则,三、解决问题,1,、铲位：,有,10,个爆破生成的石料堆，每堆称为一个铲位，每个铲位已预先根据铁含量将石料分成矿石和岩石。一般来说，平均铁含量不低于,25%,的为,矿石,，否则为,岩石,。每个铲位的矿石、岩石数量，以及矿石的平均铁含量（即品位）都是已知的。,2,、铲车：,现有铲车,7,台,，每个铲位至多能安置一台电铲，电铲的平均装车时间为,5,分钟,。,3,、卸点：,卸货地点的简称，从保护国家资源的角度及矿山的经济效益考虑，应该尽量把矿石按矿石卸点需要的铁含量（假设要求都为,29.5%,1%,，称为品位限制）搭配起来送到卸点，搭配的量在一个班次（,8,小时,）内满足品位限制即可。从长远看，卸点可以移动，但一个班次内不变。,名称,矿石漏,倒装场,1,倒装场,2,岩石漏,岩场,吨数（万吨）,1.2,1.3,1.3,1.9,1.3,4,、卡车：,现有,卡车,20,辆,，卡车的平均卸车时间为,3,分钟,。所用卡车载重量为,154,吨,，平均时速,28km/h,。卡车的耗油量很大，每个班次每台车消耗近,1,吨柴油。发动机点火时需要消耗相当多的电瓶能量，故一个班次中只在开始工作时点火一次。卡车在等待时所耗费的能量也是相当可观的，原则上在安排时,不发生卡车等待,的情况。电铲和卸点都不能同时为两辆及两辆以上卡车服务。卡车每次都是,满载运输,。,back,5,、车道：,每个铲位到每个卸点的道路都是专用的宽,60,的双向车道，不会出现堵车现象，每段道路的里程都是已知的,back,1,、内容：,出动几台电铲，分别在哪些铲位上；出动几辆卡车，分别在哪些路线上各运输多少次,2,、要求：,一个合格的计划要在卡车不等待条件下满足产量和质量（品位）要求。,3,、原则：,应该考虑下面两条原则之一。,总运量（,吨公里,）最小，同时出动最少的卡车，从而运输成本最小；,利用现有车辆运输，获得最大的产量（岩石产量,优先,；在产量相同的情况下，取总运量,最小,的解）。,1,、问题一：,满足要求，依据原则一建立数学模型，并给出一个班次生产计划的快速算法、具体的生产计划、相应的总运量及岩石和矿石产量；,2,、问题二：,满足要求，依据原则二建立数学模型，并给出一个班次生产计划的快速算法、具体的生产计划、相应的总运量及岩石和矿石产量。,2,问题的分析,变量说明,M,卡车总数,(20,辆,)V,卡车行驶速度,(28,公里,)L,卡车载重量,(154,吨,)T,一个班次的总时间,(8,小时,)Ta,电铲的平均装车时间,(5,分钟,)Tb,卡车的平均卸车时间,(3,分钟,)i,卸点编号,(5,个,分别为矿石漏,倒装场,1,倒装场,2,岩石漏,岩场,前,3,个用于卸矿石,后,2,个卸岩石,),j,铲位编号,(10,个,)Dij,卸点,i,与铲位,j,之间的距离,Ni,卸点,i,的产量要求,Qaj,铲位,j,的矿石数量,Qbj,铲位,i,的岩石数量,Pj,铲位,j,的矿石平均铁含量,Kij,一辆卡车一个班次内在卸点,i,与铲位,j,之间可往返的次数,Xij,卸点,i,与铲位,j,之间需要安排的车次数,3,模型的建立,第,1,阶段,:,采用贪心法按距离,产量,品位等要求依次取得最优,次优等若干较优的铲位,获得一些铲位的组合方案,.,第,2,阶段,:,对这些组合进行线性规划,:,以车次为变量,根据不同目标建立目标函数,根据产量等条件限制建立约束方程,然后求整数解,在这些解中取最优者,.,第,3,阶段,:,根据每条路线上的车次数再次利用贪心法进行具体的车辆安排,.,第,1,阶段,铲车安排,基于分析,首先得到铲车安排方法共有种,如果直接计算,120,种组合,耗时太多,通过分析,最优解只可能存在于一些较优的组合中,可以采用贪心法获得这些组合,.,贪心法的,思想是,:,每次选择当前最优的点,如不满足条件,再选择次优点,以此类推,.,通过分析知,卡车应先选择距离卸点最近的铲位,才能以最小的运量获得足够的产量,若此铲位不能满足产量要求,再取次近的铲位,若不能达到品位要求,还需要选择可以平衡品位的点,.,如图所示铲车安排方法为,4,种,.1 2 3 4 9 10,（,5 6 7 8,）,铲位,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,矿石量,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,15,1,35,1,05,1,15,1,35,1,25,铁含量,30%,28%,29%,32%,31%,33%,32%,31%,33%,31%,第,2,阶段,线性规划求解车次,目标,1,：,对四种铲位方法依次进行线性规划求解得,1,，,2,，,3,，,4,，,8,，,9,，,10,七个铲位最优；,总运量,85628,吨公里,8,6,万吨公里；,总产量,70378,吨,7,0,万吨；,矿石产量,38192,吨,3,8,万吨；,岩石产量,32186,吨,3,2,万吨；,出动,7,台铲车；,变量,Xij,如下表所示：,图表,1,铲位,1,铲位,2,铲位,3,铲位,4,铲位,5,铲位,6,铲位,7,铲位,8,铲位,9,铲,10,矿石漏,0 13 0 0 0 0 0 54 0 11,倒装场,1 0 42 0 43 0 0 0 0 0 0,岩 场,0 0 0 0 0 0 0 0 70 15,岩石漏,81 0 43 0 0 0 0 0 0 0,倒装场,2 0 13 2 0 0 0 0 0 0 70,2.,针对目标,2,建立模型,目标,2,与目标,1,的主要区别是目标函数不同,其约束方程相同,只须改变目标函数即可,.,目标函数产量,约束方程,:(,同目标,1),如有多组解满足最大产量,依题目要求取,即岩石产量优先，如果岩石产量相同取总运量最小的解,.,目标,2,：,对四种铲位方法依次进行线性规划求解得,1,，,2,，,3,，,4,，,8,，,9,，,10,七个铲位最优；,总产量,103488,吨,10,3,万吨；,总运量,146791,吨公里,14,7,万吨公里；,矿石产量,54308,吨,5,4,万吨；,岩石产量,49280,吨,4,9,万吨,出动,7,台铲车；,变量,Xij,如下表：,铲位,1,铲位,2,铲位,3,铲位,4,铲位,5,铲位,6,铲位,7,铲位,8,铲位,9,铲位,10,矿石漏,0,0,36,0,0,0,0,28,16,0,倒装场,1,24,68,0,68,0,0,0,0,0,0,岩场,0,0,0,0,0,0,0,0,80,69,岩石漏,72,28,32,28,0,0,0,0,0,0,倒装场,2,0,0,23,0,0,0,0,57,0,27,图表,2,第,3,阶段,车辆安排（,以目标,1,为例,）,选取最优解中每条路线的车次,即可为每辆卡车安排行驶路线及运输次数,.,由可知共需要多少卡车,.,可再次采用贪心法,使每辆卡车发挥最大工效,先安排国家路线的卡车,然后安排改变路线的卡车,.,以目标一最优解为例,具体说明卡车的安排方法,:,由 求得需要,13,辆卡车,图表,1,为每条路线上的车次,通过,Xij/Kij,，使固定运行的卡车尽可能地往返于卸点和铲位之间，求出每条路线上固定运行的卡车数，见表,固定运行的卡车共,7,辆，其它,6,辆车需要改变工作路线。此时每条线上剩余的车次见表,在改变路线的,6,辆车中：,第一辆：在,1,2,线路运输,13,次，剩余时间,T-13(Ta+Tb+2D,12,V)=87,分钟，可以继续在,1-8,线路运输,87,(Ta+Tb+2D,18,/V)=5,次。剩余时间极小，忽略，此时,18,线路剩余车次,25-5=20,。,第二辆：在,18,线路运输,20,次，剩余时间,T,一,2 0(Ta+Tb+2D,18,/V)=157,分钟,可以继续在,110,线路运输,157,(Ta+Tb+2D,110,V)=11,次。剩余时间极小，忽略，此时,第三辆至第六辆的安排方法同上。,按上述方法，即贪心法计算剩余时间，即可得到具体的卡车安排安排,如下表,（以目标,2,为例）,以目标,2,最优解为例,具体说明卡车的安排方法,:,图表,2,为每条路线上的车次,解法如目标一；,由 求得需要,20,辆卡车具体的卡车安排方法见下表,编号 路线 运输次数,1,矿石漏 一 铲位,3 18,2,矿石漏 一 铲位,3 18,3,倒装场,1,一 铲位,2 39,4,倒装场,1,一 铲住,4 37,5,倒装场,2,一 铲位,3 20,6,倒装场,2,一 铲位,8 32,7,岩石漏 一 铲位,1 44,8,岩场 一 铲位,9 38,9,岩场 一 铲位,9 38,1 0,岩场 一 铲位,1 0 45,11,矿石漏 一 铲位,8 28,11,矿石漏 一 铲位,9 2,12,矿石漏 一 铲住,9 14,12,倒装场,1,一铲位,1 20,13,倒装场,1,一 铲位,1 4,1 3,倒装场,1,一 铲位,2 29,13,倒装场,1,一 铲位,4 4,14,倒装场,1,一 铲位,4 27,14,倒装场,2,一 铲住,3 5,15,倒装场,2,一 铲住,3 3,15,倒装场,2,一 铲位,8 25,15,倒装场,2,一 铲住,l 0 3,16,倒装场,2,一 铲位,1 0 24,16,岩石漏 一 铲位,1 22,17,岩石漏 一 铲位,1 6,17,岩石漏 一 铲位,2 26,18,岩石漏 一 铲位,2 2,18,岩石漏 一 铲位,3 32,18,岩石漏 一 铲住,4 1,19,岩石漏 一 铲位,4 27,19,岩场 一 铲位,8 2,20,岩场 一 铲位,8 9,20,岩场 一 铲位,9 4,20,岩场 一 铲位,1 0 24,