2003-露天生产的车辆安排--历年数学建模优秀论文大全

露天矿生产的车辆安排参赛队员：黄振（数理学院），黄际洲（软件学院）黄指导教师：龚鑫（软件学院）劬参赛单位：重庆大学参赛时间：2003年9月2528日露天矿生产的车辆安排模型[摘要]本文根据露天矿生产的车辆安排中“一个好的生产计划”的两条原则，分别建立了规划模型，成功地解决了露天矿中电动铲车及卡车调度问题。基于“一个好的生产计划”的第一条原则，作者建立了双目标规划模型Ⅰ。在求解的第一步中，作者暂未考虑总运量，只在出动卡车最少的目标下，用单纯形法得出出动卡车的最少数目，即卡车的下限；求解的第二步是在此下限和上限（现有卡车数）之间以总运量最小为目标逐个搜索，并选取运输成本最小的一组解作为最优解。作者用Mablab6.1编程实现了以上两个步骤，求解得到最优解：总运量为8.4829万吨公里；电铲数为7，分别安放在铲位1、2、3、4、8、9、10；卡车数为13，具体路线及趟数见论文第7、8页的表3、表4。值得一提的是，作者构造了一种新的算法---回代搜索的分步算法，很好地处理了该模型的约束条件较多并其非常复杂等难点，另外，作者创造性地提出了“时间四边形”的思想，成功地解决了同一条线路上卡车的等待问题。基于“一个好的生产计划”的第二条原则，考虑到岩石产量优先的条件，作者在目标函数中引入了优先权系数，建立了规划模型Ⅱ。在求解过程中，考虑到各露天矿具体的地理、经济环境不同和管理者对岩石产量的重视程度不同，作者把优先权系数从0.55到1之间按0.05的步长递增，利用单纯形法，用Mablab6.1编程求得了权系数取不同值时的安排表，结果见论文第8页。由于在目标函数中引入了优先权系数，露天矿生产的管理者可根据露天矿具体的地理、经济环境不同等因素改变优先权系数，从而得到符合管理者需要的最优生产计划，由此，该模型具有一定的实用性。最后,本文对卸点可移和卡车可转运的情况作了推广和改进。[关键词]双目标规划，回代搜索，单纯形法，优先权系数1问题重述如图1所示，某露天矿共有10个铲点、5个卸点。每个铲位旁边的数字从上到下分别表示矿石量、岩石量和矿石的平均铁含量，每个卸点旁边的数字分别表示一个班次的产量要求。且各矿石卸点对铁含量的要求为29.5%±1%。每个铲位与每个卸点都有一条车道，图中连线上的数字表示从铲位到卸点的车道距离。0.95铲点0.64卸点1.25铲位1岩石漏1.930%┋┋6.10岩场矿石漏1.31.2┋0.951.25铲位1031%0.50倒装场Ⅰ1.3倒装场Ⅱ1.3图1铲位和卸点有关参数示意图由于卡车发动机点火时需要消耗相当多的电瓶能量，所以一个班次只点火一次，且卡--1车在等待时消耗的能量相当可观，所以卡车在工作时原则上不能发生等待的情况。又已知每个铲位只能安排一台电铲，电铲的平均装车时间为5分钟，卡车平均卸载时间为3分钟且电铲和卸点都不能同时为两辆及两辆以上卡车服务。卡车载重量量为154吨，每次满载运输，不出现堵车现象。题目要求在所给的两条原则下分别为一个班次（8小时）的生产安排一个计划，内容包括：出动几台电铲，分别在哪些铲位上；出动几辆卡车，分别在哪些路线上各运输多少次。２假设1.假设运输过程中卡车不会出现堵车现象，路况理想，卡车以恒速行驶；2.假设电铲和卡车在一个班次内可以不停地工作，如中途不会出现机器故障等；3.假设卸点、电铲的位置固定；4.假设卡车在装卸时不会出现等待；5.假设卡车的路线可以不固定，当其在一条线上完成了任务之后可以到其他线上去帮助别的车辆运输，且这中间的行车时间不计。3符号说明mijnijdijAjBjcjMix从第j个铲点运到第i个卸点的石料量从第j个铲点到第i个卸点的车次数j铲点到i卸点的距离第j个铲点矿石产量第j个铲点岩石产量第j个铲点铁含量第i个卸点的产量投入使用的卡车辆数优先权重系数其中i1表示矿石漏；i2表示倒装场Ⅰ；i3表示岩场；i4表示岩石漏；i5表示倒装场Ⅱ。4模型的建立1.模型Ⅰ分析：原则1要求总运量最小，同时出动最少的卡车，从而使得运输成本最小，由此很容易想到建立一个双目标规划模型。具体过程如下：--2(mminz1(mijdij)mmc(表示时间限制：nij为从第j个铲点到第i个卸点的车次数，易知nij向上取整，即nij1)，那么来回nij趟装车和卸车时间总和为总运量就是每个铲位运往每个卸点的矿石或岩石的量乘以铲位到卸点的距离，要使得总运量最小，则m11d11m12d12...m1,10d1,10m21d21...m2,10d2,10...m51d51...m5,10d5,10最小，亦即510i1j1ijdij)最小，这就是双目标规划模型的第一个目标函数：510i1j1要使得卡车数量少，则第二个目标函数为：minz2x------（1）------(2)分析约束条件：对于每个卸点，都有一个产量要求，这也相当于是供需关系中的需求量。以矿石漏为例有：m11m21...m1,101.2。对各个卸点有：10j1ijMii1，2…5------(3)对各铲点的矿石产量，矿石漏、倒装场Ⅰ、倒装场Ⅱ的需求量之和不能大于其生产能力，则有：m1jm2jm5jAjj=1，2…10同样对于岩石产量有：m3jm4jBjj=1，2…10-------（4）由题目已知，从保护国家资源的角度及矿山的经济效益考虑，应该尽量把矿石按矿石卸点需要的铁含量（假设要求都为29.5%1%，称为品位限制）搭配起来送到卸点，搭配的量在一个班次（8小时）内满足品位限制即可。则所有运往矿石卸点i的铁的总量除以第i个卸点的产量应在29.5%1%范围内。有：28.5%10ijj1Mij30.5%i1,2,5--------（5）mij0.0154mijmij0.01540.0154--3nij。而运输时间应为2(2mmminz1(mijdij)mmc(2(其中nij510i1j1860510i1j1nijdij28（乘以2表示来回两趟）。x辆卡车最多工作8x小时，那么有：510i1j1nijdij28nij860)8x0----------（6）电铲的平均装车时间为5分钟，又由于电铲不能同时为两辆及两辆以上卡车服务，那么1小时内1台电铲最多装车12辆，则一个班次8小时内最多装车96辆。那么对于第j个矿点，如果安排电铲的话，运出的岩石和矿石量之和应小于96辆卡车满载这个最大量。亦即：5i1ij960.0154j=1，2…10-------（7）同样的道理，对于卸点来说有：10j1ij1600.0154i1，2…5-------（8）mij为从第j个铲点运到第i个卸点的石料量，是非负数。则：mij0i1，2…5，j=1，2…10-------（9）卡车数量范围为：0x20且x为整数由式（1）-----（10），得双目标线形规划模型如下：510i1j1minz2x-------（10）s．t．10j1ijMii=1,2…5m1jm2jm5jAjm3jm4jBjj=1,2…10j=1,2…1028.5%10ijj1Mij30.5%i1,2,5510i1j1nijdij28nij860)8x0mij)0.0154--4mmmaxz3(m3jm4j)(1)(m1jm2jm5j)mmaxz3(m3jm4j)(1)(m1jm2jm5j)mmc(2(其中nij5i110j1ijij960.01541600.0154j=1，2…10i1，2…50x20且x为整数mij0i1，2…5，j=1，2…102.模型Ⅱ原则2要求利用现有车辆运输，获得最大产量（岩石产量优先；在产量相同的情况下，取总运量最小的解）。那么我们在保证各卸点产量需求的基础上，按一定优先权尽可能多地运输岩石。于是，在运输的岩石的总量前加一个优先权系数，那么运输矿石的总量前系数为1。目标函数为：约束条件：1010j1j1-----（11）要保证各卸点产量需求，则模型Ⅰ中(3)式变为：10j1ijMi；另外，为了获得最大产量，必须用上所有的20辆卡车，则模型Ⅰ中(6)式x20。其他约束条件与模型Ⅰ相同。于是原则2下的模型为：1010j1j1s.t.10j1ijMii=1，2…5m1jm2jm5jAjm3jm4jBjj=1,2…10j=1,2…1028.5%10ijj1Mij30.5%i1,2,5510i1j1nijdij28nij860)8200mij)0.0154--5mmmmc(2(其中nijmm5i110j1ijij960.01541600.0154j=1,2…10i1，2…5mij05模型的求解i1，2…5，j=1，2…101.模型Ⅰ求解：模型Ⅰ是一个双目标规化问题，在众多约束条件下直接求解有一定的困难。考虑到此题目中卡车数量的约束性：安排的卡车数量为整数，且最大数量为20辆。那么我们采用回代搜索的分步算法：在暂不考虑总运量的条件下，单以卡车数量最少作为目标函数，这样把它转化为一个求解单目标规化的问题。该单目标模型如下：minz2xs.t.10j1ijMii=1,2…5m1jm2jm5jAjm3jm4jBjj=1,2…10j=1,2…1028.5%10ijj1Mij30.5%i1,2,5510i1j1nijdij28nij860)8x0mij)0.01545i110j1ijij960.01541600.0154j=1，2…10i1，2…50x20且x为整数mij0i1，2…5，j=1，2…10--6卡车数量（辆）1314┈20总运量（吨公里）8.48298.4829┈8.4829电铲数量（台）77┈7minz1(mijdij)mmc(2(其中nijmm用Matlab6.1编程（程序见附录B）求解出以上单目标模型的最优解，其结果为卡车辆数为12.494，显然，此时所得的辆数不为整数，这不符合实际情况，以下将进一步地改进。考虑到卡车的安排要完全满足约束条件，我们认为卡车的最小数量不得低于13辆，即卡车的数量可能为13到20辆。因此我们对卡车数量为13辆至20辆时进行回代，以总运量最小为目标逐一求解（其模型见下），并通过比较选取运输成本最小的一组解。在卡车数量一定的条件下求总运量最小的模型：510i1j1s.t.10j1ijMii=1,2…5m1jm2jm5jAjm3jm4jBjj=1,2…10j=1,2…1028.5%10ijj1Mij30.5%i1,2,5510i1j1nijdij28nij860)8x0mij)0.01545i110j1ijij960.01541600.0154j=1，2…10i1，2…50x20且x为整数mij0i1，2…5，j=1，2…10用Matl