2003年高教社杯全国大学生数学建模竞赛露天矿生产的车辆安排数学竞赛模型

1、露天矿生产的车辆安排数学竞赛模型摘 要：本文研究了露天矿生产的车辆安排的最优化问题。需要我们解决的问题主要分两问。第一问包含了两层要求：一是总运量（吨公里）最小，另一个是同时出动最少的卡车，从而使运输成本最小。第二问是利用现有车辆运输，获得最大的产量（岩石产量优先；在产量相同的情况下，取总运量最小的解）。这两问都是一个多目标函数的优化问题，所以我们利用“主要目标法”将多目标最优化问题转化为单目标最优化问题。第一问根据主要目标（总运量）列出主要目标函数，将次要目标最小卡车数转化为约束条件，然后逐步简化，将非线性规划转化为线性规划来求解。通过matlab软件编程解出最优解，此时的最优解我们取其近似

2、解。如果我们将模型转化为整数线性规划求解，则会导致问题求解的复杂化，而且题设要求我们给出一个班次生产计划的快速算法，因此，我们采取了近似求解的办法。我们将近似求解得的结果通过验证，发现能够满足题目的要求。所以我们认为，近似求解的方法是可行的。关键词：总运量最小 主要目标法 线性规划 近似求解一、 问题重述钢铁工业是国家工业的基础之一，铁矿是钢铁工业的主要原料基地。许多现代化铁矿是露天开采的，它的生产主要是由电铲装车、卡车运输来完成。提高这些大型设备的利用率是增加露天矿经济效益的首要任务。露天矿里有若干个爆破生成的石料堆，每堆称为一个铲位，每个铲位已预先根据铁含量将石料分成矿石和岩石。一般来说，

3、平均铁含量不低于25%的为矿石，否则为岩石。每个铲位的矿石、岩石数量，以及矿石的平均铁含量（称为品位）都是已知的。每个铲位至多能安置一台电铲，电铲的平均装车时间为5分钟。卸点有卸矿石的矿石漏、2个倒装场和卸岩石的岩石漏、岩场等，每个卸点都有各自的产量要求。从保护国家资源的角度及矿山的经济效益考虑，应该尽量把矿石按矿石卸点需要的铁含量（假设要求都为29.5%±1%，称为品位限制）搭配起来送到卸点，搭配的量在一个班次（8小时）内满足品位限制即可。从长远看，卸点可以移动，但一个班次内不变。卡车的平均卸车时间为3分钟。所用卡车载重量为154吨，平均时速28km/h。卡车的耗油量很大，每个班次

4、每台车消耗近1吨柴油。发动机点火时需要消耗相当多的电瓶能量，故一个班次中只在开始工作时点火一次。卡车在等待时所耗费的能量也是相当可观的，原则上在安排时不应发生卡车等待的情况。电铲和卸点都不能同时为两辆及两辆以上卡车服务。卡车每次都是满载运输。每个铲位到每个卸点的道路都是专用的宽60m的双向车道，不会出现堵车现象，每段道路的里程都是已知的。一个班次的生产计划应该包括以下内容：出动几台电铲，分别在哪些铲位上；出动几辆卡车，分别在哪些线路上各运输多少次（因为随机因素影响，装卸时间与运输时间都不精确，所以排时计划无效，只求出各条线路上的卡车数及安排即可）。一个合格的计划要在卡车不等待条件下满足产量和质

5、量（品位）要求，而一个好的计划还应该考虑下面两条原则之一：1、 总运量（吨公里）最小，同时出动最少的卡车，从而运输成本最小。2、 利用现有车辆运输，获得最大的产量（岩石产量优先；在产量相同的情况下，取总运量最小的解）。 请你就以上两条原则分别建立数学模型，并给出一个班次生产计划的快速算法。针对题中的实例，给出具体的生产计划、相应的总运量及岩石和矿石产量。二、 问题的分析1. 运输矿石与岩石两种物资；2. 产量大于销量的不平衡运输；3. 在品位约束下矿石要搭配运输；4. 产地,销地均有单位时间的流量限制；5. 铲位数多于铲车数意味着最优的选择不多于7个产地；6. 最后求出各条路线上的派出车辆数及

6、安排；运输问题对应着线性规划,以上第1,2,3,4条可通过变量设计,调整约束条件实现；第5条用线性模型实现的一种办法,是从120个整数规划中取最优的即得到最佳物流；对第6条由最佳物流算出各条路线上的最少派出车辆数(整数),再给出具体安排即完成全部计算。这是一个多目标规划,第一问的目标有两层：第一层是总运量(吨公里)最小,第二层是出动卡车数最少,从而实现运输成本最小。第二问的目标有:岩石产量最大；矿石产量最大；运量最小,三者的重要性应按此序。三、 合理的模型假设1. 卡车在一个班次中不应发生等待或熄火后再启动的情况； 2. 在铲位或卸点处因两条路线(及以上)造成的冲突时,只要平均时间能完成任 务

7、即可,不进行排时讨论；3. 空载与重载的速度都是28km/h,耗油相差却很大,因此总运量只考虑重载运量；4. 卡车可提前退出系统。符号的说明：从i号铲位到j号卸点的石料运量 吨从i号铲位到j号卸点的距离 公里 从i号铲位到j号卸点路线上运行一个周期平均所需时间 分 从i号铲位到j号卸点最多能同时运行的卡车数 辆 从i号铲位到j号卸点路线上一辆车最多可以运行的次数 次 i号铲位的矿石铁含量 % =(30,28,29,32,31,33,32,31,33,31) j号卸点任务需求 吨 =(1.2,1.3,1.3,1.9,1.3)*10000 i号铲位的铁矿石储量 万吨 i号铲位的岩石储量 万吨 描述

8、第i号铲位是否使用的0-1开关变量,取1为使用；取0为关闭。四、问题一模型的建立及求解求总运量最小的生产计划 （一）以总运量最小为目标函数求解最佳物流第一层规划。 目标函数：限制条件：(1)道路能力约束：一个电铲(卸点)不能同时为两辆卡车服务,一条路线上最多能同时运行的卡车数是有限制的。卡车从i号铲位到j号卸点运行一个周期平均所需时间为： （分）由于装车时间5分钟大于卸车时间3分钟,所以这条路线上在卡车不等待条件下最多能同时运行的卡车数为： 其中最后开始发车的一辆卡车一个班次中在这条路线上最多可以运行的次数为(其他卡车可能比此数多1次) 这里 是开始装车时最后一辆车的延时时间。一个班次中这条固

9、定路线上最多可能运行的总车次大约为:总吨数 （1）(2)电铲能力约束:一台电铲不能同时为两辆卡车服务,所以一台电铲在一个班次中的最大可能产量为：8×60/5×154(吨) 10 （2）(3)卸点能力约束:卸点的最大吞吐量为每小时60/3=20车次,于是一个卸点在一个班次中的最大可能产量为：8×20×154(吨) （3）(4)铲位储量约束:铲位的矿石和岩石产量都不能超过相应的储藏量。(5)产量任务约束:各卸点的产量不小于该卸点的任务要求.(6)铁含量约束:各矿石卸点的平均品位要求都在指定的范围内.(7)电铲数量约束:电铲数量约束无法用普通不等式表达,可以引

10、入10个01变量来标志各个铲位是否有产量.(8)卡车数量约束:不超过20辆.这样，我们可以得到的一种求解最佳物流的模型为目标函数 模型的求解利用matlab编程（具体程序见附录1）求解取近似值得出最优解为：一个班次中用7台铲车时总运量最小为：84829（吨）。相应的运输安排如下表1.1所示表1.1铲位1铲位2铲位3铲位4铲位5铲位6铲位7铲位8铲位9铲位10矿石漏 2000 8333 1667 倒装场1 6333 6667 岩场 10716 2284 岩石漏12500 6500 倒装场2 2167 10833 最佳物流相对应的各个路线上的最佳运输车次如下表1.2所示，派出的卡车总数为16辆。表

11、1.2 铲位1铲位2铲位3铲位4铲位5铲位6铲位7铲位8铲位9铲位10矿石漏 13 54 11 倒装场1 41 43 岩场 70 15 岩石漏81 42 倒装场2 14 70 （二）对最佳物流的结果进行派车第二层规划 这是组合优化中的一维背包模型，针对快速算法的要求，用启发式方法求近优解。 先用最佳物流修正bij，确定卡车一个班次中在这条路线上实际最多可以运行的次数，然后在以目标为出动总卡车数最少的各路线派车中，把各路线需要的卡车数 分成整数部分 和小数部分 ，进而可以分配任务让 辆车在i到j路线上，每辆往返运输bij次。为了最后实现第二层规划的目标，只需联合处理所有的 时把这些小数组合成最少

12、的整数卡车数。所需/总卡车数的下界显然是 。如果某种派车方案恰好派出y0辆车实现了所有的，则其即为第二层目标意义下近优解的最优方案。但由于有联合派车而总公里数不一定最小，故不一定为全局意义下的最佳方案。 出动卡车数最少，意味着出动的卡车利用率要最大。容易出现的一辆卡车为两个以上路线服务的联合派车，可分为两种情况：有共同铲位(或卸点)的联合派车(v字形或更复杂)；不同铲位且不同卸点之间的联合派车(z字形或四边形或更复杂).派车方案的空载路线应尽量安排在第一层规划的最佳物流路线内，即使有的超出也要保证超出的路程总和最小，这样才能实现重载路程最小且使卡车空载路程也最小。而情况的路线不会超出第一层规划

13、的最佳物流路线。只有情况才会有一部分不在第一层规划的最佳物流路线内。 问题：各路线都是小数的需车数，如何组合使总卡车数最少且如果出现情况时空载超出部分总和尽量小。 如果存在情况，则整体考虑情况形路线需要的卡车数相加的和，先确定和的整数部分的车数并对这些车分配任务(任务的形式为在哪条路线上运几趟，再在哪条路线上运几趟，等等).之后已无情况了，再对各个小数进行组合相加试探,在所有动用卡车数最少的情况中，选择超出第一层最佳物流路线的总和最小的，即为最后派车方案。再对这些车分配任务。由于属情况的为多数,故后面的组合搜索比较简单，常常只有一两个任务属情况。 根据最后派车方案,回代计算出各车辆在各路线的运

14、输次数.由于整数部分已分配完运输次数， bij取整计算出小数部分对应的具体运输次数。进一步计算出实际总运量与矿石和岩石的产量. 五、问题二模型的建立与求解求产量最大的生产计划以产量最大为目标求解最佳物流。根据题目的要求，先考虑岩石的产量最大，然后是矿石的产量最大，最后是总运量最小的顺序，我们给岩石与矿石的产量进行加权。假设岩石占总产量比例的2/3，矿石占总产量比例的1/3。所建立的假设与问题一的相同。建立的模型如下： 目标函数： 模型的求解利用matlab编程（具体程序见附录2）求解取近似值得出最优解为：附录11、1程序data1.m(数据处理)1、2程序f1.m(主函数)1、3程序qiuji

15、e.m(求解程序)1、1、1程序data.mclearclcglobal a b c ck cy q pc=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.01 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

16、.50; % 铲位到卸点距离 p=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 % 各铲位岩石含量 0.30 0.28 0.29 0.32 0.31 0.33 0.32 0.31 0.33 0.31; % 各铲位铁矿石品位 t=c.*2./28.*60+8; % 铲位到卸点运行周期a=fix(t/5); % 铲位到卸点同时运行卡车数b=fix(480-(a-1)*5)./t); % 铲位到卸点一辆车可运行次数q=1.2

17、1.3 1.3 1.9 1.3*10000; % 卸点吞吐量ck=p(1,:)*10000; % 各铲位铁矿石含量cy=p(2,:)*10000; % 各铲位岩石含量p=p(3,:)*100; % 各铲位铁矿石品位1、1、2程序f1.mfunction fval=f1(f)global a b c ck cy q pclcc(1:50)=c; % 目标函数 a=zeros(47,50); %afor i=1:10 a(i,5*i-4:5*i)=1;endfor i=1:5 a(i+10,i:5:45+i)=1;endfor i=1:10 a(i+15,i*5-4,i*5-3,i*5)=1;en

18、dfor i=1:10 a(i+25,i*5-2,i*5-1)=1;endfor i=1:5 a(i+35,i:5:45+i)=-1;enda(41,1:5:46)=p-30.5;a(42,2:5:47)=p-30.5;a(43,5:5:50)=p-30.5;a(44,1:5:46)=28.5-p;a(45,2:5:47)=28.5-p;a(46,5:5:50)=28.5-p;bb(1:50)=b;a(47,:)=1./(154*bb); b=0;0;b(1:10)=f'*8*60/5*154;b(11:15)=8*20*154;b(16:25)=ck'b(26:35)=cy'b(36:40)=-q