资源描述
B.露天矿生产的车辆安排问题 摘要： 本文通过对原有的对多目标规划模型进行线性和加权，使得多目标的规划问题转化为单目标非线性规划问题，另外在选定7个铲点的时候，通过对于数据的处理和论证，预先选定了5个铲点，而在剩下的5个铲点中搜索最优的2个铲点，大大简化了运算量。而且搜索出的10组数据是很离散化的，涵盖了各种不同的情况，说明我们的搜索算法是可行的，是可以搜索出最优解的。而且由于采用线性加权和算法，所以能比较好的反映出各个目标函数的重要程度。另外，我们对于矿石的品位精度对于总运量和卡车数的影响进行了研究，得出的结果虽然比问题一的最优结果在运输成本上差很多，但是对于对矿石的品位精度有较高要求的时候（比如矿石的价格比较高），这种算法还是给出了最优解的。 通过在计算机上运行 程序，分别得到了问题一，二的最优解。 问题一所选用的铲点为1，2，3，4，8，9，10，共用了7辆铲车，13辆卡车，总运量为87964.8吨公里。 问题二所选用的铲点为1，2，3，4，8，9，10，共用了7辆铲车，20辆卡车，总产量为103488吨，其中岩石产量为49280吨，总运量为148771.7吨公里。 在得出最优解的同时，我们还大致排出了卡车的调度计划。 问题的提出： 钢铁工业是国家工业的基础之一，铁矿是钢铁工业的主要原料基地。许多现代化铁矿是露天开采的，它的生产主要是由电动铲车（以下简称电铲）装车、电动轮自卸卡车（以下简称卡车）运输来完成。提高这些大型设备的利用率是增加露天矿经济效益的首要任务。 露天矿里有若干个爆破生成的石料堆，每堆称为一个铲位，每个铲位已预先根据铁含量将石料分成矿石和岩石。一般来说，平均铁含量不低于25%的为矿石，否则为岩石。每个铲位的矿石、岩石数量，以及矿石的平均铁含量（称为品位）都是已知的。每个铲位至多能安置一台电铲，电铲的平均装车时间为5分钟。 卸货地点（以下简称卸点）有卸矿石的矿石漏、2个铁路倒装场（以下简称倒装场）和卸岩石的岩石漏、岩场等，每个卸点都有各自的产量要求。从保护国家资源的角度及矿山的经济效益考虑，应该尽量把矿石按矿石卸点需要的铁含量（假设要求都为29.5% 1%，称为品位限制）搭配起来送到卸点，搭配的量在一个班次（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 矿石量 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% 模型的假设： 1 因为每个铲位到每个卸点的道路都是专用的宽60 的双向车道，所以不会出现堵车现象。 2 卡车每次都是满载运输的。 3 因为产量限制的数量级是 (吨)，而卡车满载的载重量为154吨，所以在运输结果中如果误差在10吨以内，我们认为是没有误差的。 4 在一个班次内的铲车固定在铲位，而且不进行移动。 5 因为随机因素影响，装卸时间与运输时间都不精确，所以我们在安排车次的时候忽略时间的影响。 本文所用的变量和符号： 点 岩场点 岩石漏点 矿石漏点 倒装场1点 倒装场210个铲点分别用1，2，3.10编号每个铲点的岩石量为 ，其中 每个铲点的矿石量为 ，其中 每个铲点的含铁量为 ，其中 用 表示 点到铲点 的距离，其中 比如：用 表示 点到铲点1的距离， 表示 点到铲点2的距离.以此类推。用 表示铲点 到 点卡车所跑的次数，其中 比如：用 表示卡车从铲点1到 点卡车所跑的次数， 表示卡车从铲点2到 点所跑的次数.以此类推。用 表示 所形成的矩阵。用 表示在一个班次内卡车从铲点运到卸点的岩石或矿石的总质量，其中 ， ，比如： 表示在一个班次内卡车从铲点1运到卸点 的岩石的总质量， 表示在一个班次内卡车从铲点1运到卸点 的矿石的总质量表示矿石卸点的实际品位，其中 表示在一个班次内所有汽车的总路程表示卸点的在一个班次内的实际产量，其中 表示卸点的在一个班次内的计划产量，其中 表示在理论上一个班次内所用卡车的总数表示铲车的台数表示第 辆汽车的工作时间。 问题的分析： 因为电铲和卸点都不能同时为两辆及两辆以上卡车服务，而且一个班次的工作时间是8个小时。电铲为卡车装车的时间为5分钟，所以一个铲点在8小时内不间断的装车，只能装 （车次）。卡车在卸点卸车时间为3分钟，所以一个卸点在8小时内不间断的接收卡车的卸车，只能接受 （车次）。 一个班次总运量（吨公里）的定义为总运量的定义应该是运量与路程的乘积，也就是 ， 。下面针对总运量的定义给出一个结论，并给予证明：结论：汽车在一个班次内的总运量应该近似的等于每辆汽车的满载量与总路程的1/2的乘积。 证明： ， 其中 ， ， 而一个班次内所有汽车的总路程 等于 每台车转换铲点的路程， ， ，实际上这段路程全部加起来不会超过10，对于我们的总路程是不会产生太大影响的，而且车在转换铲点的时候是空载，所以这部分实际上是没有运量的。所以 证明完毕。 所以要求一个班次内的总运量最小的问题，就可以转化为求一个班次内所有卡车的总路程最小的问题。 模型的建立： 根据题意,得出以下关于问题一的1多目标函数的最优化问题的原始数学模型:： ， 模型的转化： 在问题分析中我们已经给出证明 ， ，除此之外， 理论上所需要的卡车总数和在一个班次内卡车在每个铲位和每个卸点之间所走的路程 ，以及卡车在每个铲位和每个卸点之间所走的次数 有关。从时间的角度考虑，为了使车辆数最小，假定每辆车都工作了8小时，则这时的 ，其中 ， , 再由问题的分析，一个铲点在8小时内不间断的装车，只能装96车次。一个卸点在8小时内不间断的接收卡车的卸车，只能接受160车次。也就是说， ， 这个约束条件可以转化为以下两个约束条件： ， ； ， 。各矿石卸点的实际品位 ， ， 这个条件可以转化为矩阵 的非零列向量的个数小于等于7，又因为矩阵 中的每一个元素 （车次）都是大于等于0的，所以该条件可以转化为2矩阵 的列元素的和大于0的列数小于等于7。这样模型的目标函数和约束条件都可以化成以 为自变量的函数。则原始模型可以转化为以下形式：， 然后，再通过3线性加权和方法，对于目标函数 分别引入权系数 ，把这个多目标函数的最优化问题就转化成了关于单变量 的单目标函数 的最优化问题。 模型的求解及计算机实现： 铲位和卸点位置的二位示意图如下： 因为题目并没有要求我们考虑铲车的成本问题，所以在计算时我们先按照7台铲车全部被使用的时候开始计算的。 1 铲车位置的确定： 因为一共有10个矿点，铲车只有7台，显然做不到每个铲位都安排一辆铲车。所以铲车位置的确定就是很重要的，他们的确定很可能会影响最终的结果。从最简单的角度来看，在运输的时候，铲位如果距离卸点的距离越近那么所需的成本则最小。在选取铲位的时候，我们应该优先考虑那些距离卸点较近的铲位。这样我们就把距离5个卸点最近的点先确定，这样，共有1，2，9，10四个点。（其中铲位10距离岩场和倒装场2的距离在10个铲位中都是最小的）。另外，运矿石的时候，因为品位限制铁的最高含量为30.5%,而大部分铲位的铁含量基本都比30.5%大，只有1，2，3铲位的铁矿石的铁含量是低于这30.5%的，所以为了达到铁矿石的品位要求，应该尽可能的把这3个铲位都考虑进去。而且3铲位距离卸点的距离也比较近，所以我们认为有必要把这3这个铲位作为首选进入7个铲位之中。 这样我们就在7个铲位中率先确定了1，2，3，9，10这五个点，剩下的两个铲位由于距离各个卸点的距离都比较远，在选定的时候无法确定，所以应该在剩下的4，5，6，7，8这五个点中每次选择2个点，计算其总运量和需要的总车数，这样共会得到10组不同的数据，在进行比较以后，再选取最优的一组作为我们最终确定的铲位方案。 2权系数的确定：4权系数由试探和修正确定，我们发现当 的时候 ，所得到的结果最优，而且满足题里所给出的各种条件。当 取别的权值的时候，要么理论上的卡车数大于20或者品位不满足 的要求，要不就是达不到最优解。 对权的说明：两个权值 反映了对万吨公里数和卡车数的对总成本重要程度。也就是说我们在搜索的时候，卡车数是优先于万吨公里数的。当 的时候 ， 和 的比值约为1：10较符合实际。从实际的角度来讲，让较少的卡车多跑一些路程要比让较多的卡车少跑一些路程所需要的成本要少。 3搜索算法初值的确定：通过计算机模拟试验得出一个符合要求的初始值。 4铲位的搜索算法：每个铲位确定的时候，搜索每个铲位的在满足各个卸点的产量和品位的要求情况下，总运量最小的同时，总车数最小的方案。因为矿石的品位要求铁含量最高为30.5%，所以为了满足卸点的品位要求，从一个铲位向卸点运输显然是无法满足品位要求的。所以这就有必要从1，2，3这三个铲位也向矿石卸点运输，从而达到题目所要求的品位要求。在运矿石的时候，我们应该尽可能的从邻近的铲位向卸点运输，当达到一个品位所能允许的最大吨位的时候再靠1，2，3铲位的矿石来补足。所以为了能够找到最优解，我们尽可能的把满足每个矿石卸点所有的分配方案都计算出来。最后我们用5 优化函数 搜索了10组方案。如表一所示： 表一：以总运量和卡车数为目标函数搜索得到的结果 铲点总路程（千米）理论上的车辆数对理论上的车辆数取整倒装场1的品位（%）倒装场2的品位（%）矿石漏的品位（%）铲车数目4，51240.613.1381429.61230.25930.15474，61227.413.0631429.64730.30630.14364，71227.413.0631429.64730.30630.14364，81142.412.6661329.60030.39030.35175，61268.313.2621429.46430.11830.16565，71249.613.1451429.53630.19130.15475，81182.312.8621329.46430.25930.34676，71248.913.1421429.57130.32130.15466，81207.812.9751329.41230.40030.35177，81159.712.7441329.53330.42930.3517 在选定最优解的时候，我们发现，如果总路程和总车数稍微放大一点的话，那么就会剩下一辆铲车，因为题目并没有给我们铲车的成本数值，所以铲车的数目并不是选取最优解的决定因素。而且从实际的角度考虑，车的耗油量很大，每个班次每台车消耗近1吨柴油。发动机点火时需要消耗相当多的电瓶能量，故一个班次中只在开始工作时点火一次，所以卡车运行的成本应该比铲车运行的成本要高，所以我们应该选择总运量和总车数最小的解作为最优解。对于程序搜索结果的分析，通过表一我们可以看到，该算法是比较好的，因为它尽可能的搜索到了各种情况的点。也就是说，它所选取的点是比较离散的，能够更好的描绘对于各个点的选取在总成本中的重要性。最终我们选择了4，8点作为问题的最优点，也就是说7个铲点我们选择了1，2，3，4，8，9，10这7个铲点，选择这7个铲点得到总路程和理论上所需要的车次数都是最小的。至于实际能不能够达到，既需要我们对这个方案进行调度。因为随机因素影响，装卸时间与运输时间都不精确，所以排时计划无效，我们只求出了一个大概的时间分配方案。如表二所示： 表二：问题一最优解的卡车调度计划 工作时间 车辆号123456781B12 B1D23E2D24E2D25B36C37D48C8 C39C8B310A911A9A1012E10A1013 E10 C10 每条线路的运输车次所构成的矩阵 如表三：表三：问题一每个铲点到矿点的运输车次 铲点卸点铲点1铲点2铲点3铲点4铲点8铲点9铲点10A 岩场0 00007015B岩石漏810420000C矿石漏0025038014D倒装场1051034000E倒装场2017000067 总运量为87964.8吨公里，共需要13台卡车，7台铲车。 在计算机进行搜索的时候，我们发现如果把卸点矿石的品位也作为一个目标函数进行加权的话，也可以得到一系列的最优解。但是这组最优解除了矿石品位比表一中的数据更接近于29.5%,但是其余的数值（比如：总运量，卡车数）都远远大于表一中的数据。也就是说，为了使品位的精度控制更高，那么就要付出更多的运输成本。这与实际的吻合是相当好的。但是对于本题的要求，对于品位精度的控制没有那么严格的情况下，无疑表一中的数据是最好的。但是如果为了得到品位精度较高的矿石（矿石比较贵重，比一般的运输成本要高）的时候，这种算法就是比较有效的。问题二的数学模型： 针对问题二的数学模型和问题一的数学模型基本一样，只是目标函数有所改变。约束条件其中的卡车数由原来的小于等于20变成等于20。铲车数由原来的小于等于7变成等于7（为了达到最大产量）。所以问题二的数学模型为： 经过类似于模型一的变换，也可以将模型二转化为目标函数和约束条件都以 为自变量的函数。然后，再通过线性加权和的方法，对于目标函数 分别引入权系数 ，把这个多目标函数的最优化问题就转化成了关于单变量 的单目标函数 的最优化问题。在经过试探和修正，我们发现 的时候，能得到岩石产量的极大值的同时，总产量也尽可能的大，这样的结果是比较好的。其中岩石产量的极大值= （吨）由于模型一中我们的选择铲点的方案求出的结果很好，给予一中所论述的理由，我们在这里依然按照模型一中的选点规则进行选点。也就是说先确定1，2，3，9，10四个矿点，然后再对剩下的5个矿点每次取出两个矿点进行搜索，得到以下的表四： 表四：以总产量，岩石总产量和总运量为目标函数搜索得到的结果 选取的铲点 岩石和矿石的总产量（吨） 岩石的总产量（吨） 总路程（千米） 4，5 101486 49280 2018.5 4，6 98714 49280 2083.4 4，7 101948 49280 2013.0 4，8 103488 49280 1932.1 5，6 97804 49280 2109.0 5，7 103200 49280 2045.0 5，8 98319 49280 1978.2 6，7 100640 49280 2096.5 6，8 102200 49280 2040.2 7，8 102102 49280 2000.4 通过该表我们很容易得就找到了最优的铲点，依然是4，8，这两个铲点无论从总产量还是从总运量的角度来看都是最优的。所以问题二所选用的铲点为1，2，3，4，8，9，10，共用了7辆铲车，20辆卡车，总产量为103488吨，其中岩石产量为49280吨，总运量为148771.7吨公里。 以下是我们的调度大致计划，如表五所示： 表五：问题二最优解的卡车调度计划 工作时间 车辆号123456781B12D1E23B1A104A105B2C86B2C87D28D2C39C310C3D311D3D312E3D413E3D414 D415D4 E1016 A8E817 E818E8C9A919 A920 A9 每条线路的运输次数所构成的矩阵 如表六所示：表六：问题一每个铲点到矿点的运输车次 铲点卸点铲点1铲点2铲点3铲点4铲点8铲点9铲点10A 岩场0 000118861B岩石漏73283128000C矿石漏003903180D倒装场12360968000E倒装场20817054035 模型评估： 优点：我们所建立的模型通过对原有的对多目标规划模型进行线性和加权，使得多目标的规划问题转化为单目标非线性规划问题，另外在选定7个铲点的时候，通过对于数据的处理和论证，预先选定了5个铲点，而在剩下的5个铲点中搜索最优的2个铲点，大大简化了运算量。而且搜索出的10组数据是很离散化的，涵盖了各种不同的情况，说明我们的搜索算法是可行的，是可以搜索出最优解的。而且由于采用线性加权和算法，所以能比较好的反映出各个目标函数的重要程度。另外，我们对于矿石的品位精度对于总运量和卡车数的影响进行了研究，得出的结果虽然比问题一的最优结果在运输成本上差很多，但是对于对矿石的品位精度有较高要求的时候（比如矿石的价格比较高），这种算法还是给出了最优解的。 缺点：由于采用线性加权和的算法，导致合理的权值的确定是很麻烦的，需要经过多次的调试才能最终确定最后的权值。而且模型在计算中作了一些舍入和取整，不可避免的产生了一些误差，但是这些误差的是可以容忍的。 参考书目： 1 邢继祥 张春蕊等，最优控制应用基础，北京，科学出版社，2003年8月 2 北京大学数学系几何与代数教研室代数小组，高等代数，北京，高等教育出版社，1988年3月 3 胡达，多目标规划有效性理论，上海，上海科学技术出版社，1994年12月 4 郭晶， 辅助优化计算与设计，北京，电子工业出版社，2003年1月 5 萧树铁，数学实验，北京，高等教育出版社，1997年7月 附录： 源程序： %目标与约束函数的实现程序 function f,g=yunkuang(x)%x为自变量，f为优化目标，g为约束条件Dis=5.265.194.214.002.952.742.461.900.641.27; 1.900.991.901.131.272.251.482.043.093.51; 5.895.615.614.563.513.652.462.461.060.57; 0.641.761.271.832.742.604.213.725.056.10; 4.423.863.723.162.252.810.781.621.270.50 ; quan=2000,1000;hl=0.951.051.001.051.101.251.051.301.351.25; 1.251.101.351.051.151.351.051.151.351.25; 30 28 29 32 31 33 32 31 33 31;qudian=1 2 3 4 8 9 10;d=Dis(3 4 1 2 5,qudian);pin=hl(3,qudian);%f1为总路程函数f1=0;for i=1:5 for j=1:7 f1=x(i-1)*7+j)*d(i,j)+f1;endendtimes=0;for i=1:35 times=times+x(i);end%truck为卡车辆数truck=(f1*2/28+times*8/60)/8;for i=3:5 for j=1:7 pei(i-3)*7+j)=pin(j)*x(i-1)*7+j); endendfor i=1:3 peibi(i)=0; timestot(i)=0;endfor i=1:3 for j=1:7 timestot(i)=x(i+1)*7+j)+timestot(i);endendfor i=1:3 for j=1:7 peibi(i)=pei(i-1)*7+j)+peibi(i); end peibi(i)=peibi(i)/timestot(i);endcha=0;for i=1:3 cha=(peibi(i)-29.5)*(peibi(i)-29.5)+cha;endf=(f1+truck*quan(1)+cha*quan(2);for j=1:5 sumj(j)=0;endfor j=1:5 for i=1:7 sumj(j)=sumj(j)+x(j-1)*7+i)*154; endend%产量约束条件sumjx=1.3 1.9 1.2 1.3 1.3*1e+4;for i=1:5 g(i)=sumjx(i)-sumj(i);endfor i=1:7 sumi1(i)=0; sumi2(i)=0; sumi3(i)=0;endfor i=1:7 for j=1:2 sumi1(i)=sumi1(i)+x(j-1)*7+i)*154; endendfor i=1:7 for j=3:5 sumi2(i)=sumi2(i)+x(j-1)*7+i)*154; endendfor i=1:7 sumi3(i)=(sumi1(i)+sumi2(i)/154;endsumi2x=hl(1,qudian)*1e+4;sumi1x=hl(2,qudian)*1e+4;%岩石矿石的最大运量约束for i=1:7 g(i+5)=sumi1(i)-sumi1x(i); g(i+12)=sumi2(i)-sumi2x(i);end%铲车装车时间约束for i=1:7 g(19+i)=sumi3(i)-96;end%卸车时间约束for i=1:5 g(26+i)=sumj(i)/154-160;end%卡车辆数约束g(32)=truck-20; %优化执行程序 %x0为初始值x0=10 10 10 10 10 15 10 11 10 13 10 10 10 10 10 10 10 10 18 10 10. 12 13 10 10 10 10 10 10 10 12 10 10 10 13;op(13)=0;op(14)=4000;%v1为搜索下界v1=zeros(1,35);x,op=constr(yunkuang1,x0,op,v1);
展开阅读全文