露天矿生产的车辆安排.doc

露天矿生产的车辆安排 摘 要 本文研究的是露天矿生产的车辆安排问题，核心问题是多目标优化问题，关键是将多目标优化转化为单目标优化求解。共建立了两个模型，采用了主要目标法、理想点法进行问题转化的快速算法。 针对原则一，我们建立了多目标优化模型即模型一，并用主要目标法、理想点法，巧妙地将多目标非线性问题转化为单目标线性规划问题求解，给出了一个快速解决问题的算法，可以求出在总运量最小同时出动车辆最少的目标下铲车和卡车的安排；得出了动用7辆铲车，14辆卡车，总运量8.56万吨公里的优化结果。具体数据见论文第14页。 针对原则二，我们建立了模型二，采用多次优化的方法，将多目标非线性优化问题转化为单目标线性规划，可以求出满足总产量最大的条件下，岩石产量优先和总运量最小的优化解；得到的解为7辆铲车20辆卡车，总产量9.3万吨，岩石产量5.48万吨，总运量12.35万吨公里的优化结果。具体数据见论文第15页。 在模型检验中采取计算卡车利用率的方法对模型进行检验，有运算量小、容易检验的特点，具有创新性。 一、 问题重述 钢铁工业是国家工业的基础之一，铁矿是钢铁工业的主要原料基地。许多现代化铁矿是露天开采的，它的生产主要是由电动铲车（以下简称电铲）装车、电动轮自卸卡车（以下简称卡车）运输来完成。提高这些大型设备的利用率是增加露天矿经济效益的首要任务。 露天矿里有若干个爆破生成的石料堆，每堆称为一个铲位，每个铲位已预先根据铁含量将石料分成矿石和岩石。一般来说，平均铁含量不低于25的为矿石，否则为岩石。每个铲位的矿石、岩石数量，以及矿石的平均铁含量（称为品位）都是已知的。每个铲位至多能安置一台电铲，电铲的平均装车时间为5分钟。 卸货地点（以下简称卸点）有卸矿石的矿石漏、2个铁路倒装场（以下简称倒装场）和卸岩石的岩石漏、岩场等，每个卸点都有各自的产量要求。从保护国家资源的角度及矿山的经济效益考虑，应该尽量把矿石按矿石卸点需要的铁含量（假设要求都为29.51，称为品位限制）搭配起来送到卸点，搭配的量在一个班次（8小时）内满足品位限制即可。从长远看，卸点可以移动，但一个班次内不变。卡车的平均卸车时间为3分钟。 所用卡车载重量为154吨，平均时速28。卡车的耗油量很大，每个班次每台车消耗近1吨柴油。发动机点火时需要消耗相当多的电瓶能量，故一个班次中只在开始工作时点火一次。卡车在等待时所耗费的能量也是相当可观的，原则上在安排时不应发生卡车等待的情况。电铲和卸点都不能同时为两辆及两辆以上卡车服务。卡车每次都是满载运输。 每个铲位到每个卸点的道路都是专用的宽60的双向车道，不会出现堵车现象，每段道路的里程都是已知的。 一个班次的生产计划应该包含以下内容出动几台电铲，分别在哪些铲位上；出动几辆卡车，分别在哪些路线上各运输多少次（因为随机因素影响，装卸时间与运输时间都不精确，所以排时计划无效，只求出各条路线上的卡车数及安排即可）。一个合格的计划要在卡车不等待条件下满足产量和质量（品位）要求，而一个好的计划还应该考虑下面两条原则之一 1.总运量（吨公里）最小，同时出动最少的卡车，从而运输成本最小； 2.利用现有车辆运输，获得最大的产量（岩石产量优先；在产量相同的情况下，取总运量最小的解）。 请你就两条原则分别建立数学模型，并给出一个班次生产计划的快速算法。针对下面的实例，给出具体的生产计划、相应的总运量及岩石和矿石产量。 某露天矿有铲位10个，卸点5个，现有铲车7台，卡车20辆。各卸点一个班次的产量要求矿石漏1.2万吨、倒装场Ⅰ1.3万吨、倒装场Ⅱ1.3万吨、岩石漏1.9万吨、岩场1.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 矿石量 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 二、实际问题的背景 钢铁工业是国家工业的基础之一，铁矿是钢铁工业的主要原料基地。许多现代化铁矿是露天开采的，它的生产主要是由电动铲车（以下简称电铲）装车、电动轮自卸卡车（以下简称卡车）运输来完成。如果能够最大限度的提高这些大型设备的利用率，将给露天采矿带来巨大的经济效益。 三、 问题分析 这是一个多目标的优化问题。要求我们考虑两条原则。第一条原则就是让我们决定从每个铲位运给各个卸点多少产量，才能使总的吨公里数和总的运输成本最小。目标函数有两个一、总运量最小；二、运输成本最小。约束条件可以考虑以下几点、铲位向卸点运送矿物量与铲位存贮量之间的关系；、卸点从铲位接收的矿物量与卸点要求量之间的关系；、矿石卸点对铁含量的品位限制；、铲车和卡车够用；、每辆卡车在一个班次内的工作时间不超过小时；、卡车在装车和卸车时均不发生等待；、铲位装车量的约束。若考虑上述完备的约束条件很难求解，考虑用主要目标法、理想点法将多目标非线性优化的问题转化成单目标线性规划的问题再求解。 第二条原则，就是让我们决定以获得最大的产量为首要目标，如何调配现有的所有车辆。如果有总产量相等的情况，找出岩石量占总产量比例最大的运输方案。若仍有两种或两种以上的运输方案存在，取总运量最小的一种。以获得最大产量为目标函数，考虑以下几点约束条件、铲位向卸点运送矿物量与铲位存贮量之间的关系；、卸点从铲位接收的矿物量与卸点要求量之间的关系；、矿石卸点对铁含量的品位限制；、取用所有的铲车和卡车；、每辆卡车在一个班次内的工作时间不超过小时；、卡车在装车和卸车时均不发生等待；、铲位装车量的约束。考虑用分层次优化的方法加以解决。 四、合理假设 为了简化模型，我们做如下假设 、在计算一个来回时间时，假定精确到小数点后两位就已经满足要求了。 、电铲和卸点都不能同时为两辆及两辆以上卡车服务。 、卡车每次都是满载运输。 、电铲装车时间取为分钟，卡车卸车时间取为分钟。 、每个铲位与每个卸点之间的道路不会出现堵车现象。 、排时计划无效，只求出各条路线上的卡车数及安排。 五、符号系统 ，，， 铲位编号，从到依次表示铲位，，铲位 ，，， 卸点编号,从到依次表示倒装场, 倒装场, 矿石漏，岩场和岩石漏。 铲地与卸点之间的卡车数。 辆卡车共跑了个来回（一个来回指卡车空车驶离卸点至返回卸点卸完货后）。 卡车跑一个来回所需时间 卡车时速公里/时 卡车载重量 吨 铲位的铲车数，为零时表示此处无铲车，为时表示此处有一辆铲车 铲位矿石的含铁量 铲位与卸点之间的距离 总运量 出动卡车数 铲位的矿石存贮量 铲位的岩石存贮量 卸点一个班次的产量要求 六、建立模型 模型一的建立 总运量 ， 出动卡车数 这就是所要求的目标函数。 各量之间所应满足的限制条件 （）供给约束、对每个来说，运到倒装场I, 倒装场II和矿石漏的矿石量少于或等于的矿石存贮量 （，，，） 、运到岩场和岩石漏的岩石量少于或等于的岩石存贮量 （，，，） （）需求约束对每个来说，从各个铲位运到的矿物量多于或等于的要求量 （，，，） （）品位约束保证矿石卸点的铁含量都为 （，，） （）工作时间约束保证每辆卡车在一个班次内的工作时间不超过小时 （）（，，，；，，） （）车辆约束保证现有的铲车和卡车够用 ， （）不等待约束、假设有一个铲位向任一个卸点发出一辆卡车后，经（小时），又向卸点发出一辆卡车。、与的距离分别为和。 设两辆车分别跑了个和个来回（一个班次内最多分别跑个和个来回）。为保证在铲位不发生因装车而造成的等待，应有 （，；，，，； 均在内取值）。 、假设有一个卸点向任一个铲位发出一辆卡车后，经（小时），又向铲位发出一辆卡车。、与的距离分别为和。 设两辆车分别跑了个和个来回（一个班次内最多分别跑个和个来回）。为保证在卸点不发生因卸车而造成的等待，应有 （，；，，，；均在内取值）。 推广 表示铲位向同一个卸点发出多辆卡车； 表示卸点向同一个铲位发出多辆卡车。 （）铲位装车量约束铲位的电铲装一次车用分钟，在一个班次（小时）内最多装（车） 根据分析，建立满足原则一矿物运输问题的 模型一 其中， 模型二的建立 虽然模型二与模型一是截然不同的两个模型，但模型一中的下列约束条件在模型二中仍然成立 、对每个来说，运到倒装场I, 倒装场II和矿石漏的矿石量少于或等于的矿石存贮量；同时，运到岩场和岩石漏的岩石量少于或等于的岩石存贮量。 、对每个来说，从各个铲位运到的矿物量多于或等于的要求量。 、矿石卸点的铁含量都为。 、每辆卡车在一个班次内的工作时间不超过小时。 、在铲位不发生因装车而造成的等待。 、在卸点不发生因卸车而造成的等待。 、铲位的电铲在一个班次（小时）内最多装车。 但首要目标变为获取最大总产量，取 为目标函数。 模型一中要求铲车数少于或等于和卡车数少于或等于的约束条件不再适用，应改为 铲车数为 卡车数为 （即利用现有全部车辆运输）。 还要考虑岩石产量优先和在产量相同的情况下，取总运量最小的下层目标 （1）即选取岩石量占总产量比例最大的运输方案 （）即选取总运量最小的运输方案 根据分析，建立满足原则二矿物运输问题的 模型二 第一层目标 第二层目标 第三层目标 其中， 七、模型求解 模型一的求解 首先由题给数据得到下列表格（为处理方便，将岩场与倒装场II的两行数据交换） 铲位到卸点的距离 铲点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 倒装场I 1.90 0.99 1.90 1.13 1.27 2.25 1.48 2.04 3.09 3.51 倒装场II 4.42 3.86 3.72 3.16 2.25 2.81 0.78 1.62 1.27 0.50 岩石漏 0.64 1.76 1.27 1.83 2.74 2.60 4.21 3.72 5.05 6.10 岩场 5.89 5.61 5.61 4.56 3.51 3.65 2.46 2.46 1.06 0.57 表一 一个班次内从铲位到卸点可以安排的车辆数为 铲点1 铲点2 铲点3 铲点4 铲点5 铲点6 铲点7 铲点8 铲点9 铲点10 矿石漏 6 6 5 5 4 3 3 3 2 2 倒装场I 3 2 3 2 2 3 2 3 4 4 倒装场II 5 4 4 4 3 4 2 2 2 2 岩石漏 2 3 2 3 3 3 5 4 5 6 岩场 6 6 6 5 4 4 3 3 2 2 表二 一个班次内一辆车从铲位到卸点可以跑的趟数 铲点1 铲点2 铲点3 铲点4 铲点5 铲点6 铲点7 铲点8 铲点9 铲点10 矿石漏 15 15 18 19 23 24 25 29 44 35 倒装场I 29 39 29 37 35 27 33 28 22 20 倒装场II 17 19 20 22 27 23 42 32 35 47 岩石漏 44 30 35 30 24 25 18 20 16 14 岩场 14 14 14 17 20 20 25 25 38 45 （表三） 一辆车从铲位到卸点跑一个来回所用的时间（分钟计） 铲位1 铲位2 铲位3 铲位4 铲位5 铲位6 铲位7 铲位8 铲位9 铲位10 矿石漏 30.5429 30.2429 26.0429 25.1429 20.6429 19.7429 18.5429 16.1429 10.7429 13.4429 倒装场I 16.1429 12.2429 16.1429 12.8429 13.4429 17.6429 14.3429 16.7429 21.2429 23.0429 倒装场II 33.2429 32.0429 32.0429 27.542 23.0429 23.6429 18.5429 18.5429 12.5429 10.4429 岩石漏 10.7429 15.5429 13.4429 15.8429 19.7429 19.1429 26.0429 23.9429 29.6429 34.1429 岩场 26.9429 24.5429 23.9429 21.5429 17.6429 20.0429 11.3429 14.9429 13.4429 10.1429 表四 一辆车从铲位到卸点一个班次内的运载能力 铲位1 铲位2 铲位3 铲位4 铲位5 铲位6 铲位7 铲位8 铲位9 铲位10 矿石漏 90 90 90 95 92 72 75 87 88 70 倒装场I 87 78 87 74 70 81 66 84 88 80 倒装场II 85 76 80 88 81 92 84 64 70 94 岩石漏 88 90 70 90 72 75 90 80 80 84 岩场 84 84 84 85 80 80 75 75 76 90 表五 通过对上述图表的分析，要形成一个可以对目标函数求解的快速算法，需要采用以下两种转化问题的方法 、主要目标法在满足基本产量和质量要求的前提下要使总运量最小，运送货物的量应基本接近产量需求；而货车在利用率高的情况下，货车使用的越多，总的公里数越大，因此首先考虑总运量的优化目标，将非线性约束转化为线性约束，将一个多目标优化的问题转化成单目标规划的问题求解。 此时求得总运量 8.56万吨公里 需使用铲车7辆，分别在铲位（1、2、3、4、8、9、10） 根据表三中铲位一辆车从铲位到卸点一个班次内的运载能力进行调度,将一个班次提前完成任务的卡车调度到路程相近的路线上工作，遵循以下原则 线路上运完额定车数后还能运送的车数为车，将这部分剩余运载能力调度到线路上（），能运载的车数为 （车） 可得一个班次计划共需要14辆卡车。 、理想点法 理想点的定义对于多目标决策问题（），如果决策者事先能够对每个目标给出一个目的值（或交目标值），使其满足 则称为理想点。[1] 本题中，根据问题的实际背景，目标的理想点取为，直接将作为约束条件，将一个多目标优化的问题转化成单目标规划的问题来解，无解；然后将作为约束条件，转化成单目标规划问题，有解，从而很快就得到一个班次计划共需要14辆卡车的解，该解也是满足目标。 模型二的求解 类似于模型一求解中的主要目标法，先不考虑岩石产量和总运量目标，得到单个目标为的线性规划问题，解该线性规划问题可以确定目标函数9.3（万吨）。将该等式作为约束条件置入线性规划中，目标函数变为，即考虑总产量一定条件下岩石产量较大的解；继而将该最大产量作为约束条件置入线性规划，目标函数变为即考虑总运量最小的解。 八、模型结果 模型一的结果 对于本题中所提供的数据，利用上节的快速算法我们可以得到模型一的结果如下列表格所示 需使用铲车7辆，分别在铲位（1、2、3、4、8、9、10）； 需使用14辆卡车，在各条线路上运输的趟数 铲位1 铲位2 铲位3 铲位4 铲位5 铲位6 铲位7 铲位8 铲位9 铲位10 矿石漏 0 13 0 0 0 0 0 52 0 13 倒装场I 0 40 0 45 0 0 0 0 0 0 倒装场II 0 15 0 0 0 0 0 0 0 68 岩石漏 81 0 43 0 0 0 0 0 0 0 岩场 0 0 0 0 0 0 0 0 70 15 各条线路上的卡车数 线路 车辆数 铲位1－岩石漏 2 铲位2－矿石漏 3 铲位2－倒装场II 铲位2－倒装场II 铲位4－倒装场I 3 铲位3－岩石漏 铲位8-矿石漏 2 铲位10-矿石漏 铲位10-倒装场II 2 铲位9-岩场 2 铲位10-岩场 总运量 8.56万吨公里 模型二的结果 对于模型二，利用现有车辆运输，以获得最大产量为首要问题，考虑了岩石产量优先；在产量相同的情况下，取总运量最小的条件。利用上节的算法我们可以得到模型二的结果如下列表格所示 需使用铲车7辆，分别在铲位（1、2、3、4、8、9、10）； 使用20辆卡车，在各条线路上运输的趟数 铲位1 铲位2 铲位3 铲位4 铲位5 铲位6 铲位7 铲位8 铲位9 铲位10 矿石漏 0 1 20 0 0 0 0 55 2 0 倒装场I 0 52 0 33 0 0 0 0 0 0 倒装场II 0 15 0 0 0 0 0 29 1 40 岩石漏 81 22 70 57 0 0 0 0 0 0 岩场 0 0 0 0 0 0 0 0 76 50 各条线路上的卡车数 线路 车辆数 铲位1－岩石漏 2 铲位2－矿石漏 2 铲位2－倒装场I 铲位2－倒装场II 1 铲位2－岩石漏 1 铲位3－矿石漏 1 铲位3－岩石漏 2 铲位4－倒装场I 1 铲位4－岩石漏 2 铲位8－矿石漏 2 铲位9－矿石漏 铲位8－倒装场II 1 铲位9－倒装场II 铲位10－倒装场II 3 铲位10-岩场 铲位9-岩场 2 总产量（万吨）；岩石产量（万吨） 总运量（万吨公里） 九、模型检验 引入卡车利用率的概念，通过较少的运算对模型一进行检验 卡车利用率定义设一个班次内辆卡车总运量的理论值为，实际求得的总运量为，卡车利用率为，有 。 其中，表示满足五个卸点总需求量的总车数。 越接近于所需的最少卡车数，卡车利用率越高，值越接近。 模型一求得的最小值为，吨公里， （吨公里）， 可以看出，在考虑相当多约束条件的情况下，辆卡车已经是最优解。 十、模型的优缺点 从建立模型的设想及实施过程，我们可以看出模型有如下优点及不足之处，优点 1、模型的目标函数简洁明了，安排出的生产计划能够满足多种生产要求。 2、采用了分层次优化的方法，能够较好地解决问题。 3、给出了快速算法，从而能够在较短的时间内制定出较优的生产计划。 4、较好的解决了将多目标非线性约束转化为单目标线性约束的问题。 缺点由于时间有限，解题时用到的某些数据为近似值，从而决定了结果只能是近似的。 十一、模型推广 根据原题重述和问题分析，可以联想到其它生产中与本文所讨论问题的类似情况，如救灾物资的配送问题，救灾物资从处在不同地的仓库运往多个救灾点，要考虑各救灾点不同救灾物质的搭配和现有车辆的分配，如何能最快地将一定量的救灾物资按一定比例送达救灾点，有极大的适用性。 参考文献 [1]蔡锁章，数学建模原理与方法，北京海洋出版社，2000。 [2]许波，MATLAB工程数学应用，北京清华大学出版社，2000。 附录计算源程序 include include include void read; void place; bool ask; bool needint,int; bool need2int,int,int; bool ask; void show; void place2; void outout; double distance[5][10];//距离 double oncetime[5][10];//一趟用时间分钟计 int times[5][10];//一条线路的班次要跑多少趟 int truck[5][10];//一条线路上可以安排多少车 double heaven[7][5][10];//一条线路上安排n辆车ntmp; distance[i][j]tmp; ptmp*120/288;//一趟时间分钟计 oncetime[i][j]p; times[i][j]480/p; kp/5;//一个线路上最多跑几趟车 truck[i][j]k; tmpk*times[i][j]; } couttmp; product[i][j]tmp; } } data.close; fori0;itruck[i][j]return 0;//满足等待条件 forint k0;k0t1;//使用铲车数 ifx[i][k]0tmp;//卸点i使用的铲位数 } ift17return 0;//铲车数不大于7 iftmp2return 0;//卸点i使用不超过两个铲位 t2heaven[x[0][j]][0][j]heaven[x[1][j]][1][j]heaven[x[2][j]][2][j]; ift2product[0][j]*10000return 0;//运量不超过产量 t2heaven[x[3][j]][3][j]heaven[x[4][j]][4][j]; ift2product[1][j]*10000return 0;//运量不超过产量 return 1; } bool need2int k,int i,int j { int t10,tmp0; double t20; ifall15return 0;//不大于卡车数 ifx[i][j]truck[i][j]return 0;//满足等待条件 forint s0;s0t1;//使用铲车数 ifx[k][s]0tmp;//卸点i使用的铲位数 } ift17return 0;//铲车数不大于7 iftmp2return 0;//卸点i使用不超过两个铲位 t2heaven[x[0][j]][0][j]heaven[x[1][j]][1][j]heaven[x[2][j]][2][j]; ift2product[0][j]*10000return 0;//运量不超过产量 t2heaven[x[3][j]][3][j]heaven[x[4][j]][4][j]; ift2product[1][j]*10000return 0;//运量不超过产量 return 1; } bool ask { int i,j;double t1,t2,tmp; fori0;i5;i { tmpt1t20; forj0;j10;j { tmpheaven[x[i][j]][i][j]; t1tmp; t2tmp*product[2][j]; } ift12//如果是矿石，要满足品位要求 { tmpt2/t1; iftmp0.305return 0; } } return 1; } void show { int i,j; fstream file; file.open“out.txt“,iosapp; file“lift“; fori0;i0file“1\t“;else file“0\t“; fileendl“trucks“all“\n“; fori0;i5;i { forj0;j10;j { filex[i][j]; } fileendl; } fileendl; file.close; } void place { int i,j; fori0;i3;i { forj0;j10;j { x[i][j]; all; lift[j]; ifneedi,j { ifask { show; } else { place; } } lift[j]--; all--; x[i][j]--; } } } 26