露天矿生产车辆安排的算法分析与设计.doc

露天矿生产车辆安排的算法分析与设计 [摘要] 研究的是露天矿生产的车辆安排计划，利用最小的资源消耗取得理想的产量要求。全面分析了车辆安排问题的约束条件，构建了基于整数规划的车次安排算法，并对该算法进行了分析。采用两种方法贪心算法和整数规划模型，针对两个目标进行安排。 首先，采用贪心算法按距离、产量、品位等要求依次取得最优、次优 等若干较优的铲位，获得一些铲位的组合方案。其次，对这些组合进行整数规划以车次为变量，建立目标函数，根据产量等条件限制建立约束方程，然后求整数解，在这些解中取得最优者。最后，根据每条路线上的车次数在次利用贪心算法具体的车辆安排。 [关键词] 车辆安排；露天矿；整数规划，贪心算法，Matlab 6.0 The Analysed Designed Arrangement of Vehicles in Open Exploitation [Abstract] What is studied, utilize minimum resources to consume and make the ideal output to require. Analysed vehicle arrange restraint terms of issue , structure train number based on integer planning arrange for algorithms in an all-round way, and has analysed to this algorithm. Adopt two kinds of s --Plan models , arrange to two targets in greedy algorithm and integer First,Adopt greedy algorithm demand obtain optimum sequentially , time excellent according to distance , output , grade ,etc. - Wait for several more excellent shovel location, obtain the association scheme of some shovel location.Second, Carry on the integer to plan to these associations Regard train number as the variable, the function that set objectives, rcise restraint in setting up the equation of restraining according to such conditions as the output ,etc., then ask the integer to solve , obtain to the superior the most while solving in these. Finally,Count and utilize the concrete vehicle of greedy algorithm to arrange in time according to the train number on each route. [Key words] The vehicle arranges, Opencast Iron Mine, Integer programming, Greedy algorithm, Matlab 6.0 目录 第一章 绪论4 1.1研究背景4 1.2问题的提出4 第二章 问题的分析7 2.1基本的假设7 2.2基本符号说明7 2.3对问题的分析8 第三章 模型的建立11 3.1 运输成本最小的生产计划模型11 3.2利用现有车辆运输而获得最大的产量模型12 第四章 求解的准备15 4.1贪心算法简介15 4.2 Matlab简介16 第五章 模型的算法设计19 5.1模型1的算法设计19 5.2模型2的算法设计21 第六章 模型的求解结果22 6.1模型1的求解结果22 6.2模型1的求解结果24 第七章 模型优缺点的讨论26 7.1模型的优点26 7.2模型的缺点26 7.3模型的改进27 7.4模型的推广27 第八章 结论28 致谢29 参考文献30 附录31 第一章 绪论 1.1 研究背景 钢铁工业是国家工业的基础之一，铁矿是钢铁工业的主要原料基地。许多现代化铁矿是露天开采的，它的生产主要是由电动铲车（以下简称电铲）装车、电动轮自卸卡车（以下简称卡车）运输来完成。对露天矿的生产调度，可以划分成许多类型，但不论怎样最后都要牵涉到车辆的调度安排这样一个组合问题，因此都是没有好算法的NP完全NPC问题。各国根据一些露天矿的实际情况开发许多实用软件，但都没有公开它们的算法。我国仅有几个露天矿用上了智能化软件管理，水平还需要提高，应用面也需要扩大，矿业生产迫切需要这方面的成果。总之，深入研究这方面问题时很有实际意义的。 我们以国内某露天铁矿为背景，大幅度地简化了难度和去掉许多实际要求而编制的较理想的课题。特别是由于去掉了随机性，使得此题更接近露天矿生产的根本问题。 如果我们能够做出一个好的模型，并能给出一个合适的算法，就能最大限度的提高露天矿这些大型设备的利用率，将给露天采矿带来巨大的经济效益，给国家做出很大的贡献。 1.2 问题的提出 钢铁工业是国家工业的基础之一，铁矿是钢铁工业的主要原料基地。许多现代化铁矿是露天开采的，它的生产主要是由电动铲车（以下简称电铲）装车、电动轮自卸卡车（以下简称卡车）运输来完成。提高这些大型设备的利用率是增加露天矿经济效益的首要任务。 露天矿里有若干个爆破生成的石料堆，每堆称为一个铲位，每个铲位已预先根据铁含量将石料分成矿石和岩石。一般来说，平均铁含量不低于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 2.95 2.74 2.46 1.9 0.64 1.27 倒装场Ⅰ 1.9 0.99 1.9 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.6 4.21 3.72 5.05 6.1 倒装场Ⅱ 4.42 3.86 3.72 3.16 2.25 2.81 0.78 1.62 1.27 0.5 各铲位矿石、岩石数量万吨和矿石的平均铁含量如下表 铲位1 铲位2 铲位3 铲位4 铲位5 铲位6 铲位7 铲位8 铲位9 铲位10 矿石量 0.95 1.05 1 1.05 1.1 1.25 1.05 1.3 1.35 1.25 岩石量 1.25 1.1 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.卡车加油、司机吃饭与上厕所等休息时间忽略不计； 5.对所有卡车来说，一个班次的8小时是同一时刻开始的； 6.一卡车在一个班次内可以装矿石，也可以装岩石，但同一车次矿石与岩石不可以混装； 7.卡车运输可以转换线路。 2.2 基本符号说明 卡车总量（20辆）； 卡车行驶速度； 卡车的载重量； 一个班次的总时间； 电铲的平均装车时间； 卡车的平均卸车时间； 卸点的总数（5）； 铲点的总数（10）； 卸点编号（5个，分别为矿石漏、倒装场、倒装场、岩石漏、岩场，前3个用于卸矿石，后2个卸岩石）； 铲为编号（10个）； 卸点与铲位之间的距离； 从铲位到卸点来回所用的平均时间； 从号铲位到号卸点的石料运输次数； 铲点路线上在卡车不等待条件下最多能同时运行的卡车数； 卸点的产量要求； 总运量； 总产量； 铲位的矿石数量； 铲位的岩石数量； 表示卡车从铲位到卸点在一个计划内的最大运量，也就是一辆卡车在一个计划内只进行铲位到卸点的运输时能够完成的最大运量（车次）； 矿石数量转化成可运车数； 岩石数量转化成可运车数； 2.3 对问题的分析 从题目看，露天矿生产主要是运石料。它与典型的运输问题有以下不同。 1．这是运输矿石与岩石两种物资的问题； 2．属于产量大于销售的不平衡运输问题； 3．为了完成品位约束，矿石要搭配运输； 4．运输车辆只有一种，每次都是满载运输，车次； 5．不仅要求最佳物流，最后还要求出各条路线上的派出车辆数及安排。 每个运输问题对应着一个线性规划问题。以上不同点对它的影响不同，第1，2，3条可通过变量设计，调整约束条件实现；第4条整数要求将使其变为整数线性规划；为完成第5条由最佳物流算出各条路线上的最少派出车辆数再给出具体安排即完成全部计算。然而这是个实际问题，为了及时指挥生产，题中要求算法是快速算法，而整数规划的本质是NP完全NPC问题，短时间内计算至少50个变量的整数规划来说就不一定办得到。从另一个角度看，这是两个阶段的规划问题，第一个阶段是确定各条路线上运输石料的数量（车次），可以用整数规划建模；第二个阶段是规划各条线路上的派车方案，是一个组合优化问题。如果求最优解计算量较大，现成的各种算法都无能为力。于是问题可能变为找一个寻求近优解的近似解法，例如可用启发式方法求解。 可分析出问题的主要难点有 1． 处理在10个铲位选择7台点铲的问题。 2． 从铲位到的流量均为154吨的整数倍，即取为整数车车次。这题的核心是如何用近似算法求解NPC问题。整数规划的现有解法不是快速算法，无法保证在任何数据下都能在短时间内算完，应该想办法巧妙地设计算法和数学软件减少运行整数规划耗费地时间。 3. 模型中应有道路能力约束，否则原则二的结果不可能正确。 4. 派车问题本质为组合优化问题，如何快速得到最优解或近优解。 针对问题一的分析 该问题是在一定约束条件下的最优化问题。要求卡车满载运输，则必有一满足各卸点每班次产量要求的最小总运量，此总运量与车辆总数相对独立。建立一总运量最小为目标函数的整数规划模型。目标函数的解是每个铲位与其相对应的卸点之间载物卡车的运输次数。在满足总运量最小的前提下建立组合优化模型求解最少的卡车数。此后根据路线上的车流量，在考虑尽量避免等待的情况下确定各条路线的车流安排。 针对问题二的分析 该问题属于目标规划问题，可以采用目标法规划的模型求解，对于矿石产量最大，总产量最大，总运量最小按优先级排序。同时也可以把该问题看成多目标规划问题。 第三章 模型的建立 3.1 运输成本最小的生产计划模型 目标函数与约束条件的分析 （1）目标函数取为重载运输时的运量（吨公里）最小。 （2）道路能力约束一个电铲（卸点）不能同时为两辆卡车服务，所 以一条路线上最多能同时运行的卡车数是有限的。在号铲位和号卸点路线上运行一个周期平均所需时间（分）。由于装车时间5分钟大于卸车时间3分钟，所以可分析出这条路线上在卡车不等待条件下最多能同时运行的卡车数。 （3）电铲能力约束还是因为一台电铲不能同时位两辆卡车服务，所以一台电铲在一个班次中的最大可能产量为（车次）。 （4）卸点能力约束卸点的最大吞吐量为每一时60/320（车次），于是一个卸点在一个班次中的最大可能产量为8（车次）。 （5）铲位储量约束各铲位的矿石和岩石产量都不能超过相应的储藏量。 （6）产量任务约束各卸点的产量大于等于该卸点的任务要求。 （7）铁含量约束各矿石卸点的平均品位要求都在指定的范围内。 （8）整数约束问题作为整数规划模型时，为非负整数，表示运行的车次数。 （9）设备数量要求电铲数量和卡车数量不能超过现有设备数量。 这样我们可以得到最佳的模型1为 总运量目标函数 （1） 约束方程 则对应实例的模型1为 （2） 约束方程 3.2 利用现有车辆运输而获得最大的产量 下面在卡车不等待条件下利用现有车辆资源运输来获得最大的产量的模型。（岩石产量优先考虑，如果所得到的解产量相同，则取总运量最小 模型2与模型1的主要区别是目标函数不同，其约束方程相同，只需改变目标函数即可。 产量目标函数为 （3） 约束方程 对应的实例模型为 产量目标函数 （4） 约束方程 第四章 求解算法的预备知识 4.1 贪心算法简介 对与这个问题，要求算法是快速算法，而整数规划的本质是NP完全NPC问题，短时间内计算至少50个变量的整数规划来说就不一定办得到。为此，我们仔细的分析了这个问题，发现很有点像贪心算法的模型，于是我们便在贪心算法的基础上进行了改进，此点便是本设计最大的一个创新点，下面我先介绍一下贪心算法 贪心算法，顾名思义，就是总是做出在当前看来是最好的选择。也就是说贪心算法并不是从整体最优上加以考虑，它所做出的选择只是在某种意义上的局部最优选择。当然，我们希望贪心算法得到的最终结果也是整体最优的。在一些情况下，即使贪心算法不能得到整体最优解，但其最终结果却是最优解的很好近似解。 贪心算法通过一系列的选择来得到一个问题的解。它所作的每一个选择都是当前状态某种意义的最好选择，即贪心选择。希望通过每次所作的贪心选择导致最终结果是问题的一个最优解。这种启发式的策略虽然不能总奏效，然而在许多情况下确实能达到预期的目的。对一般的安排问题贪心算法就是能很好的解决。 贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。这是贪心算法可行的第一个最基本的要素，也是贪心算法与动态规划算法主要区别。在动态规划算法中，每步所做出的选择往往依赖于相关子问题的解。因而只有在解出相关子问题后，才能做出选择。而在贪心算法中，仅在当前状态下做出最好的选择，即局部最优选择。然后再去解作出这个选择后产生的相应的子问题。贪心算法所做出的贪心选择可以依赖于以往所作的选择，但绝不依赖于将来所做出的选择，也不依赖子问题的解。正是由于这种差别，动态规划算法通常以自底向上的方式解各子问题，而贪心算法则通常以自顶向下的方式进行，以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为一个规模更小的子问题。 对这个具体问题，因为它和活动安排问题一样，所以它也具有贪心选择性质。该问题作了贪心选择后，便简化为一个规模更小的类似子问题。然后，用数学归纳法证明，通过每一步作贪心选择，最终可得到问题的一个整体最优解。其中，证明贪心选择后的问题简化为规模更小的类似子问题的关键在于利用最优子结构性质。当一个问题的最优解包含着它的子问题的最优解时，称此问题具有最优子结构性质。问题所具有的这个性质是该问题可用动态规划算法或贪心算法求解的一个关键特征。 4.2 Matlab简介 为了求解，我们必须自己去编程解决，算法需要自己去想，结合前人的现有算法，我们加以借鉴，对算法进行了改进。但需求出答案，必须取求解，创造了算法，也必须加以实现，于是我们找到了Matlab,它具有良好的编程能力和强大的计算功能，现将其简介如下 MATLAB 语言的首创者 Cleve Moler 教授在数值分析，特别是在数值线性代数的领域中很有影响， 他参与编写了数值分析领域一些著名的著作和两个重要的 Fortran 程序 EISPACK 和LINPACK。他曾在密西根大学、斯坦福大学和新墨西哥大学任数学与计算机科学教授。1980 年前后，当时 的新墨西哥大学计算机系主任 Moler 教授在讲授线性代数课程时，发现了用其他高级语言编程极为不便，便构思并开发了 MATLAB MATrix LABoratory，即矩阵实验室, 这一软件利用了当时数值线性代数领域最高水平的 EISPACK 和 LINPACK 两大软件包中可靠的子程序，用 Fortran 语言编写了集命令翻译、科学计算于一身的一套交互式软件系统。 所谓交互式语言，是指人们给出一条命令，立即就可以得出该命令的结果。该语言无需像 C 和 Fortran 语言那样，首先要求使用者去编写源程序，然后对之进行编译、连接，最终形成可执行文件。这无疑会给使用者带来了极大的方便。早期的 MATLAB 是用 Fortran 语言编写的，只能作矩阵运算；绘图也只能用极其原始的方法，即用星号描点的形式画图；内部函数也只提供了几十个。但即使其当时的功能十分简单，当它作为免费软件出现以来，还是吸引了大批的使用者。 Cleve Moler 和 John Little 等人成立了一个名叫 The MathWorks 的公司，Cleve Moler 一直任该公司的首席科学家。该公司于 1984 年推出了第一个 MATLAB 的商业版本。 当时的 MATLAB 版本已经用 C 语言作了完全的改写，其后又增添了丰富多彩的图形图像处理、多媒体功能、符号运算和它与其他流行软件的接口功能，使得 MATLAB 的功能越来越强大。 The MathWorks 公司于 1992 年推出了具有划时代意义的 MATLAB 4.0 版本，并于 1993 年推出了其微机版, 可以配合 Microsoft Windows 一起使用， 使之应用范围越来越广。 1994 年推出的 4.2 版本扩充了 4.0 版本的功能，尤其在图形界面设计方面更提供了新的方法。 1997 年推出的 MATLAB 5.0 版允许了更多的数据结构，如单元数据、数据结构体、多维矩阵、对象与类等，使其成为一种更方便编程的语言。1999 年初推出的 MATLAB 5.3 版在很多方面又进一步改进了 MATLAB 语言的功能。 2000 年 10 月底推出了其全新的 MATLAB 6.0 正式版Release 12，在核心数值算法、界面设计、外部接口、应用桌面等诸多方面有了极大的改进。 虽然 MATLAB 语言是计算数学专家倡导并开发的，但其普及和发展离不开自动控制领域学者的贡献。甚至可以说，MATLAB 语言是自动控制领域学者和工程技术人员捧红的，因为在 MATLAB 语言的发展进程中，许多有代表性的成就和控制界的要求与贡献是分不开的。迄今为止，大多数工具箱也都是控制方面的。MATLAB 具有强大的数学运算能力、方便实用的绘图功能及语言的高度集成性，它在其他科学与工程领域的应用也是越来越广，并且有着更广阔的应用前景和无穷无尽的潜能。 子曰“工欲善其事，必先利其器”。如果有一种十分有效的工具能解决在教学与研究中遇到的问题，那么 MATLAB 语言正是这样的一种工具。它可以将使用者从繁琐、无谓的底层编程中解放出来，把有限的宝贵时间更多地花在解决问题中，这样无疑会提高工作效率。 目前，MATLAB 已经成为国际上最流行的科学与工程计算的软件工具，现在的 MATLAB 已经不仅仅是一个“矩阵实验室”了，它已经成为了一种具有广泛应用前景的全新的计算机高级编程语言了,有人称它为“第四代”计算机语言，它在国内外高校和研究部门正扮演着重要的角色。MATLAB 语言的功能也越来越强大，不断适应新的要求提出新的解决方法。可以预见，在科学运算、自动控制与科学绘图领域 MATLAB 语言将长期保持其独一无二的地位。 第五章 模型的算法设计 5.1 模型1的算法设计 说明按照距离最近原则运输，是显而易见节省资源（卡车耗油量）的较优算法。但是本课题中涉及到品位限制（矿石）的问题，因此只考虑距离肯定不是最优解；首先我们从距离着手，（运矿石时）再加上品位的限制，取车次与距离乘积最小者。 1、根据矩阵（各卸点到各产点的距离表）造一个距离矩阵； 矩阵（各铲点的矿石与岩石产量及矿石的品位） 根据矩阵造一个juli矩阵（50*3）第一列为（铲点到卸点）距离值，第二列为卸点标志，1表示矿石漏，2表示倒装场1，3表示岩场，4表示岩石漏，5表示倒装场2；第三列为铲点标志。110表示铲点 110； xie[78 85 85 124 85];//各卸点的需求量（车次） n1; for i15 for j110 julin,1ai,j; julin,2i; julin,3j; nn1; end end 把juli矩阵按第1列进行排序（按升序） SORTROWSjuli,1; 取juli矩阵第一个 Tempminjuli1,1; 取对应的卸点标志与铲点标志 。 Xhjuli1,2; Chjuli1,3; 根据Xh判断卸点是矿石卸点，岩石卸点 Case 1岩石。取Tempmin,看是否满足产量需求 if b2,Ch xie1,Xh b2,Chb2,Ch-xie1,Xh; aXh,110100; else 取次优点 即xie1,Xhxie1,Xh-b2,Ch; a34,Ch100; b2,Ch0; Tema1,110110； TemaminSORTROWSTema,2; Ch2Temamin1,1; if xie1,Xhb2,Ch2 xie1,Xh0; aXh,110100; else 重复取次优点步骤 Case2 矿石 取铲点Ch的品位 若大与30.5则按30.5配比，即尽量从最近距离运。从1，2，3中取一个铲点与其搭配。 取车次*距离的最小值。同理哪个铲点不足取其次优点。 算法模拟程序及注释见附录 5.2 模型2的算法设计 为使卡车在不等待条件下利用现有的车辆资源运输获得最大的产量，我们只要在满足模型中约束条件下，使 1、 运送岩石产量优先 按距离的最优值取运输多条最优组合的线路，每条线路车辆安排满，车辆数是按每条线路的距离决定的。如果铲位提前运完，则再选择次优的铲位安排车辆运输，以此下去，直到不满足约束条件为止。 2、 运送矿石 矿石运输先要满足模型1的要求，按模型1的求解算法得到一个临时结果，再补加总矿石的量。 补加原则由于矿石的运量要满足一定的品位要求，所以按照距离与车次的乘积最优值取运输多条最优组合的线路，每条线路车辆安排满，车辆数是按每条线路的距离决定的。如果铲位提前运完，则再选择次优的铲位安排车辆运输，以此下去，直到不满足约束条件为止。 第六章 模型的求解结果 卸点编号为1 矿石漏，2 倒装场I,3 倒装场II,4 岩场，5 岩石漏；矿石卸点的集合为，铲为集合为；岩石卸点集合， 铲为集合为。依据铲位和各卸点之间的平均走行时间得到卡车在一个计划内的平均最大运量如表5-1 铲位1 铲位2 铲位3 铲位4 铲位5 铲位6 铲位7 铲位8 铲位9 铲位10 矿石漏 15 15 18 19 23 24 25 29 44 35 倒装场Ⅰ 29 39 29 37 35 27 33 28 22 20 岩场 14 14 14 17 20 20 25 25 38 45 岩石漏 44 30 35 30 24 25 18 20 16 14 倒装场Ⅱ 17 19 20 22 27 23 42 32 35 47 表5-1 铲卸点最大运量一览表 将上表铲位矿石、岩石数量转化成可运车数（车次）、（车次）如下表5-2所示 铲位1 铲位2 铲位3 铲位4 铲位5 铲位6 铲位7 铲位8 铲位9 铲位10 61 68 64 68 71 81 68 84 87 81 81 71 87 68 74 87 68 74 87 81 30 28 29 32 31 33 32 31 33 31 表5-2铲位最大工供应能力 6.1 对第1个模型的求解结果 根据上面的算法，我们最后求出前面给出的整数规划模型可计算出最 优值为85628.62吨公里，共出动13辆卡车。 1、结果相对应的各个路线上的最佳运输车次 铲位1 铲位2 铲位3 铲位4 铲位5 铲位6 铲位7 铲位8 铲位9 铲位10 矿石漏 13 54 11 倒装场Ⅰ 42 43 岩场 70 15 岩石漏 81 43 倒装场Ⅱ 13 2 70 表5-3 最佳运输次数 2、固定路线派车（这些卡车在一个班次内一直在固定路线上运输）方案为 铲位1 铲位2 铲位3 铲位4 铲位8 铲位9 铲位10 矿石漏 129 倒装场Ⅰ 239 337 岩场 437 岩石漏 544 665 倒装场Ⅱ 747 表5-4 固定路线派车路线 表中括号内的数是卡车车号，后面是运的车次数，以下同。 3、联合派车方案为 铲位1 铲位2 铲位3 铲位4 铲位8 铲位9 铲位10 矿石漏 1113 1022113 106135 倒装场Ⅰ 123 126 岩场 933 951310 岩石漏 837 85133 倒装场Ⅱ 1213 121131 723 表5-5 联合派车方案 最后，得出结果为在铲位1、2、3、4、8、9、10处各放置一台电铲。 一共使用了13辆卡车；总运量为85628.62吨公里； 岩石产量为32186吨；矿石产量为38192吨。 6.2 对第2个模型的求解结果 根据上面的算法，我们的算出结果为总运量142385.3吨公里； 1、 结果相对应的各个路线上的最佳运输车次 铲位1 铲位2 铲位3 铲位4 铲位5 铲位6 铲位7 铲位8 铲位9 铲位10 矿石漏 38 24 18 倒装场Ⅰ 16 54 22 68 岩场 12 74 74 岩石漏 80 28 32 20 倒装场Ⅱ 14 4 60 22 表5-6 最佳运输次数 2、固定路线派车（这些卡车在一个班次内一直在固定路线上运输）方案为 铲位1 铲位2 铲位3 铲位4 铲位8 铲位9 铲位10 矿石漏 （3）（4）36 倒装场Ⅰ 239 337 岩场 7874 945 岩石漏 144 665 倒装场Ⅱ 631 747 表5-7固定路线派车路线 表中括号内的数是卡车车号，后面是运的车次数，以下同。 3、联合派车方案为 铲位1 铲位2 铲位3 铲位4 铲位8 铲位9 铲位10 矿石漏 151201 19142010 2018 倒装场Ⅰ 1051411 112 1413 1221481512 13121519 岩场 1912 933 185192 岩石漏 1036 1128 1232 1320 倒装场Ⅱ 1614 164 16 1 17 28 表5-8 联合派车方案 最后，得出结果为在铲位1、2、3、4、8、9、10处各放置一台电铲。 一共使用了20辆卡车；总运量为142385.3吨公里； 岩石产量为49280吨；矿石产量为52360吨； 第七章 模型优缺点的讨论 运用贪心法，可迅速求得铲车的可能位置，确定可能取得最优解的若干组合，大大减少了整数规划的计算次数。确定铲车位置后，列出规划方程，用Matlab软件进行编程求解，可迅速得到结果。对于一些特殊情况，如多数铲位的优劣程度接近时，采用贪心法无法准确地确定较优的铲位，此时需要进行线性规划的铲车安排方案数会大大增加，求解的时间会较长。在解线性规划问题时，需要考虑多解的情况，即多种方案均可取得最优解，此时需要根据题目要求（岩石产量优先、总运量最小、卡车数最少）取得 相应的最优解。 7.1 模型的优点 1.使用贪心算法、迅速确定了铲车的可能位置； 2.采用线性规划的思想，化整为零，使模型简化，大大减少了计算 复杂度； 3.充分利用了Matlab良好的编程能力和强大的计算功能； 4.充分利用了模型目标函数、约束条件的线性关系； 5.模型具有较好的通用性，能够适应同类问题的各种变化； 6.给出了快速算法，从而能够在较短的时间内制定出较优的生产计划。 7.2 模型的缺点