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

1、1露天矿车辆生产的安排刘 月 梁伟韬 黄 捷摘要我们小组在讨论后认为以第一个原则建立的数学模型基本上可以看作是一个线性优化模型。这个模型以产量要求，品位限制及不等待原则为限制条件，在此基础上求出最小的总运量及同时需出动的最少卡车数。我们以最小总运量为目标函数，列出的限制条件作为约束条件编写 Matlab 程序。大致的做法是:按题意，建立以铲位组合为变量的函数设为函数 1，计算在给定铲位组合下的最小运量。然后以随机抽取铲位组合的方法，利用函数 1，比较铲位组合改变前后运量大小来确定最小运量所对应的铲位组合。求得最小运量对应的铲位组合以后，确定每条线路的运送吨数，在八小时满负荷工作的前提下,确定所

2、需的最小车数，所余零头由若干辆车完成，所有车数合起来为所确定的最小车数，顺便给出车辆安排表。保证运量最小的铲位号是 1 2 8 3 9 4 10（铲位不按顺序的原因是我们在选铲位组合时是采用随机算法） ，最小运量是85217（单位：吨公里） ，至少需要 15 辆卡车。对于原则二的要求，同原则一类似，只是目标函数做了改动，并增加了一些限制条件。在产量要求最大情况下的铲位是 1 2 7 3 4 8 10，最大产量是 87355 吨，其中岩石产量为 49280 吨。2一 问题重述露天矿里有若干个铲位，每个铲位的石料已预先分为矿石和岩石。卸点有卸矿石的矿石漏，两个倒转场和卸岩石的岩石漏，岩场等，每个卸

3、点都有各自的产量要求。要求尽量把矿石按矿石卸点需要的铁含量（假设要求都为 29.5%1%）搭配起来送到卸点。每个铲位至多能安置一台电铲，电铲的平均装车时间为 5 分钟。卡车在卸点的平均卸车时间为 3 分钟。电铲和卸点都不能同时为两辆及两辆以上的卡车服务，而原则上在安排时不应发生卡车等待的情况。卡车每次都是满载运输。假设每个铲位到每个卸点的道路不会出现堵车现象，且每段道路的里程都是已知的。现要求安排一个班次的生产计划，包含以下内容：出动几台电铲，分别在哪些铲位上；出动几辆卡车，分别在哪些线路上各运输几次。在此基础上依照以下两原则之一：1. 总运量（吨公里）最小，同时出动最少的卡车，从而运输成本最

4、小；2. 利用现有车辆运输，获得最大的产量（岩石产量优先；在产量相同的情况下，取总运量最小的解） 。就两条原则分别建立数学模型，并给出一个班次生产计划的快速算法。针对下面实例，给出具体生产计划：某露天矿里有铲位 10 个，卸点 5 个，铲车 7 台，卡车 20 辆。各卸点一个班次（8小时）的产量要求：矿石漏 1.2 万吨，倒转场1.3 万吨，倒转场1.3 万吨，岩石漏1.9 万吨，岩场 1.3 万吨。二 模型的假设及符号说明模型假设：1. 只考虑一个班次，即铲车位置是固定的。2. 最大限度的利用大型设备。3. 每个铲位至多能安置一台电铲，电铲平均装车时间为 5 分钟。4. 每个矿石卸点需要的铁

5、含量都为 29.5%1%。5. 卸点在一个班次内不变，卡车的平均卸车时间为 3 分钟。6. 铲位到卸点之间的道路不会堵车，卡车每次都是满载运输。7. 卡车可在不同铲位运作以完成任务。符号说明：最小运量。T：距离矩阵， 中元素 表示第 j 个铲位到第 i 个卸点的距离。 AAij：铲位资源矩阵， 中元素 中的 表示第 个铲位上的某种含量，即矿石量，岩BBij j石量及铁含量中的某一种。：一个 的向量，元素 按照矿石漏，倒装场 ，岩场，岩石漏，倒装D15iD(1.5)3场 的顺序排列。：运出量矩阵， 中元素 表示从第 个铲位运到第 个卸点的石料数。这是一个XXijji未知数的矩阵。：时间矩阵， 表

6、示卡车在从 卸点到 卸点往返依次需要的时间。bijbji：是对 中元素乘上一个系数以后进行取整得到的矩阵，其中元素代表对应路线上c所能同时容纳的最大车数。三. 模型的分析，建立及求解首先给铲位按 1，2，3标号，对卸点同样进行标号。分别测出各个铲位与不同卸点间的距离。将这些数据列成二维表格（本题中此表格已给出） 。同时将个铲位的矿石，岩石及矿石铁含量列成二维表格。这样，我们得到两张表格：距离表格和数量表格。很直观的，我们把表格都看作矩阵，得到距离矩阵 A 和数量矩阵 B。A 中一个元素代表一个距离。一考虑原则一：按照生产计划的原则一，总运量 （单位：吨公里）应达到最小，同时出动的卡T车数要最少

7、。 由（1）各铲位向卸点运送的矿石与岩石量， （2）各铲位到每个卸点的T距离这两部分组成。距离通过测量容易得到，现在问题的关键是怎样确定铲位的石料运出量。我们知道，每个铲位的石料运往各个卸点，将卸点上来自不同铲点的石料列成二维表格，也就是一个矩阵，记作 X。显然，X 的维数同距离矩阵 A 的维数是保持一致的，也就是说，两个矩阵的元素是一一对应的。X 中一个位置上的元素，对应着 A 中相同的位置上的元素。反映在问题中，就是对应着铲位到卸点的每一条路线，都有一个相应的运量。这样，把每条路线上的石料运量（单位：吨公里）求和，就是一个班次内的运量。这样我们得到了目标函数：求这个最小运量 T。考虑到实际

8、情况中，由于硬件的限制，铲车的数量往往少于铲位的数量，总有铲位会闲置。所以我们只能选取铲位中的一些。这样又面临这样一个问题：不同的铲位选取会有不同的运量！我们把问题分两步做：首先在提高大型设备的利用率的前提下，按照铲车数目确定铲位组合与最小运量的函数关系式，随机或依据经验取定铲位，算出最小运量。然后，选取另一种铲位组合，算出这种铲位组合的最小运量，如此反复。所有铲位组合的最小运量中最小的那一个就是我们希望得到的。由排列组合原理知道，这种比较所有铲位组合的最小运量的方法根本不必要。我们采用了这样的方法：首先固定一个铲位组合 ，求出它1H的最小运量 ，然后用组合外的一个铲位替换掉这个组合中的一个铲

9、位，得到一个新1T组合 ，并将它相应的最小运量 同前一组合比较，如果 = ,则保持 不变，继续进行，如果出现连续多次 值不变，21HT则认为 值已经达到最小。在编制的程序中，我们设定如果值 20 次不变，即得到最小T4值及其相应得铲点组合。程序多次执行得到的结果相同！可以相信得到的组合是最优组合。现在针对给出的具体数据解答。题中给出的表格有两张。我们叫做表一，表二。表一是各铲位到各卸点的距离值。应于表格中数字的位置，把它写成矩阵的形式（参照表一）：5.26.194.20.952.74.6190.412703182.3.5.8.5.6.783.7.6.04.236.2.5.161A 相应的运出矩

10、阵： 114789022325622133334 445154758950XXXX 表二经过单位换算后，我们有（单位：吨）：90101021031212535535503%829%3%B 考虑到只有 7 部铲车，最大限度利用这些铲车，我们最多用到其中的 7 个铲位。这样，运出矩阵 。 111123456722333574 4155534672XXXXnnnnXXXXnnnn 这里 是选取铲位安放铲车的号码，它的元素是我们要求的铲位123467,运出量。按照 中选定的这 7 个铲位号，从矩阵 （表格二）中抽取相应位置上的列A向量，按原顺序组成新的路程矩阵路程矩阵 .这样我们分别得到了运出矩阵57

11、L与路程矩阵 。那么有下式：XL571ijijTX（1）上式是这个最优化问题的目标函数。但需要注意的是，这只是我们在随机选取七个铲位的情况下得到的一个运量。并不是期望得到的最小运量！（事实上，由排列组合原理很容易知道，抽取的方法有 120 种！换句话说，我们只是得到了所应当求出的120 个结果中的一个！） 。我们给出这个问题的函数及约束条件并进行解释。目标函数：571minijjXL5约束条件：1. 71ijijXD(1.5)i各个铲位运往同一个卸点的石料数量加总，即 ，应达到该卸点产量要求 。71ijjX i如运往矿石漏的石料总量应等于 1.2 万吨。2. ,1251XBjj17(.)jn一

12、个铲位运往矿石漏，倒装场 及倒装场 的矿石总量 ，不可能超125jjjX过该铲位的矿石产量 。1j3. ,342XBj17(.)n每个铲位运往岩场及岩石漏的岩石总量 不能超过该铲位的岩石产量 。34jjX2jB4. ,（ =15）70.2850.351DDiiji是关于铁含量的限制，即“品位”的限制。各铲位运往卸点的石料铁含量应该符合品位标准。 是铲位 上矿石的铁含量。运出石料的含铁量 按照题中给出3jBj 731ijjjiXBD的，必须在 之间。29.5%15. ，74801Xijcbj(1.5)i表明在卡车不等待的情况下，将每个铲位要运出的石料量都运完所要的时间应该不超过 480 分钟（8

13、 小时） 。 是 到 的距离，往返的路程为 卡车时速换算成（千米ijAj 2ijA/分） 。则时间 ，表示在这条线路上往返需要的时间，8 为装车卸车花的120ijijb时间。 是 铲点到 卸点这条路线上所能容纳的最大车辆数（是因为装车时/5ijijci间是 5 分钟） 。运用 ，得出最小运量。程序文件见所附磁盘中的 solution1 函数。Matlb6现在我们对原则一建立的模型（以下称作模型一）给出大致的排车计划，该计划并不精确，只是一种快速算法。先阐述一下我们的思路：由模型一求出的线性优化解以及已知的距离矩阵 ,返回得到这样两个矩阵（分别记为 和 ）： 中元素代表AMN每条线路在卡车不等待

14、的情况下所能容纳的最大卡车数， 中元素表示： 中元素为代表的卡车数完成相应线路运输任务所需要的单车平均运行时间。将 与 中Mij N对应元素相乘并除以 480，得到一个矩阵,记为 ， 中元素代表相应线路以 8 小时满Q负荷工作所需要的车数。这里的得到的车数不必为整数。我们把 中元素小数部分大Q于 0.2 的，向上取整；否则向下取整,这样又生成一个新矩阵，记为 。同时，把 中小数部分小于 0.2 的数在另一矩阵 中用 1 在相应的位置上标识出来，其余元素置 0。P这样得到排车矩阵 和 。 中元素表示相应线路上所派卡车数。再派若干辆车，每Q辆车负责 中每五个非零元素所代表线路的运输任务。至此得出一

15、个完整的排车计划。P具体程序见磁盘中的 schedul.m 文件二.考虑原则二：原则二要求最大产量，这也是一个优化问题。求解方法与 1 类似，只是目标函数已经改变。根据岩石产量优先原则，现在的目标是求出最大的岩石产量。同时，由于卡车数量的限制，约束条件也相应的增加了两条，即：完成任务的总车时有限制；卸点的最大产量应不超过卸点满负荷工作时的产量。下面给出它的目标函数及约束条件的数学表达式。目标函数： 34()jjjX新增约束条件：（2）(15)960ijijjibc2460ijX（3）表达式（2）左边表示完成任务的车时。表达式（3）表示卸点的产量不可能超过 24640 吨- 。15480/3其他

16、约束条件与模型一相同。具体程序见磁盘中的 solution2.m四解模模型一 计算机的运算结果： 7保证运量最小的铲位号是 1 2 8 3 9 4 10，最小运量是 85217（单位：吨公里）至少需要 15 辆卡车表一 （每条线上能同时跑的最大车数）：铲位 1 铲位 2 铲位 8 铲位 3 铲位 9 铲位 4 铲位 10矿石漏 6 6 3 5 2 5 2倒装场 1 3 2 3 3 4 2 4岩场 6 6 3 6 2 5 2岩石漏 2 3 4 2 5 3 6倒装场 2 5 4 2 4 2 4 2如：左上角的数字 6 表示从铲位一到矿石漏线路在卡车不等待情况下所能容纳的最大卡车数。以下表格意义相同

17、。表二（每条路线运送石料的吨数）：铲位 1 铲位 2 铲位 8 铲位 3 铲位 9 铲位 4 铲位 10矿石漏 0 2000 10000 0 0 0 0倒装场 1 0 6333 0 0 0 6667 0岩场 0 0 0 0 9365 0 3635岩石漏 12500 0 0 6500 0 0 0倒装场 2 0 2167 0 0 0 0 10833表三（每条线路完成石料运送需要的时间）：铲位 1 铲位 2 铲位 8 铲位 3 铲位 9 铲位 4 铲位 10矿石漏 0 66 350 0 0 0 0倒装场 1 0 252 0 0 0 278 0岩场 0 0 0 0 382 0 124岩石漏 436 0

18、 0 284 0 0 0倒装场 2 0 87 0 0 0 0 357表四（每条线路应派的车辆 Q ）：铲位 1 铲位 2 铲位 8 铲位 3 铲位 9 铲位 4 铲位 10矿石漏 0 1 2 0 0 0 0倒装场 1 0 1 0 0 0 1 0岩场 0 0 0 0 2 0 1岩石漏 2 0 0 1 0 0 0倒装场 2 0 1 0 0 0 0 2表五（表格中的 1 所占路线需要派车，即 P）：铲位 1 铲位 2 铲位 8 铲位 3 铲位 9 铲位 4 铲位 10矿石漏 0 0 1 0 0 0 0倒装场 1 0 1 0 0 0 1 0岩场 0 0 0 0 0 0 0岩石漏 0 0 0 1 0 0

19、 0倒装场 2 0 0 0 0 0 0 08模型二：在产量要求最大情况下的铲位是 1 2 7 3 4 8 10最大产量是 87355 吨，其中岩石产量为 49280 吨表六（各路线所运的岩石产量）：铲位 1 铲位 2 铲位 7 铲位 3 铲位 4 铲位 8 铲位 10矿石漏 1677 2496 1347 1865 1578 1686 1382倒装场 1 1975 2292 1420 2291 1591 1580 1871岩场 3670 2797 2853 4018 3432 3753 4114岩石漏 3988 3023 4451 2610 4109 2991 3466倒装场 2 1872 24

20、26 1531 1926 1618 1671 1971五模型推广如果我们把那张铲位卸点联起来，铲位同卸点看作点，点点间距离看作带权重的边，就是一张图。把运量看作均等，距离可以变化的话，就变成一个求最短距离的问题。譬如说在几个城市之间建造交通基础设施，如高速公路。以最大限度的节省资源及成本为前提，问题转化为：得到一个交通网，使这个交通网的总长度最小。这同样可以用与此题类似的方法来做。当然，考虑的约束条件会变。因为要考虑到地形，经济效益等。而经济效益不只是成本的问题，如果这些城市中有旅游胜地，她带来的经济收入可能会抵消掉花费成本，等等类似这样的一些问题。具体问题有不同的限制条件。六.优缺点分析1.

21、在我们作优化的时候，限制条件比较宽松。我们也尝试加入了其他的条件，譬如再要求卸点时间不冲突，但是得到的结果没有未加入前的好。我们对这种情况也进行了计算。结果是：铲位 10 铲位 5 铲位 4 铲位 9 铲位 8 铲位 1 铲位 3矿石漏 2123 1910 1153 3098 171 1130 2819倒装场 1 1251 1665 1555 1570 3061 1214 3108岩场 6353 1523 4 2456 1891 900 1487岩石漏 0 22 10996 32 2 7952 12倒装场 2 2981 2007 1197 1594 1863 1702 2060总运量达到 16

22、000 之多，接近原来方法的两倍。不但增加了生产成本，而且安排车辆也十分困难，虽然这种方法能在理论上保证车辆之间不冲突。但是实际运用要做到这一点几乎不可能。只能选择舍弃。2.车辆的安排方面，我们的方法在理论上不能保证车辆之间不会冲突。实际执行起来，极有可能发生等待。在我们看来，完全避免车辆的冲突是不可能的。在执行我们的方案时，要有一定的变通。至于具体怎么作，很遗憾我们还没有找到有效的方法。3.我们的程序执行速度比较快，执行磁盘中 schedul.m 程序（一般只需 2.5 秒左右）便能得出模型一中所有所求结论。而执行磁盘中 solution2.m 程序（一般只需 3秒左右）便能得出模型二中除排车计划外所有结论。9