露天矿生产车辆安排的优化模型.doc

露天矿生产车辆安排的优化模型数学与应用数学01级本科1班 祝文康指导老师：简国明 副教授1 问题的提出许多现代化铁矿是露天开采的,它的生产主要是由电动铲车（以下简称电铲）装车、电动轮自卸卡车（以下简称卡车）运输来完成.提高这些大型设备的利用率是增加露天矿经济效益的首要任务.现要制定一个班次的生产计划,一个班次的生产计划包含以下内容:出动几台电铲,分别在哪些铲位上;出动几辆卡车,分别在哪些路线上各运输多少次（因为随机因素影响,装卸时间与运输时间都不精确,所以排时计划无效,只求出各条路线上的卡车数及安排）.一个合格的计划要在卡车不等待条件下满足产量和质量（品位）要求,而一个好的计划还要考虑下面两条原则之一: 1.总运量（吨公里）最小,同时出动最少的卡车,从而运输成本最小;2.利用现有车辆运输,获得最大的产量（岩石产量优先;在产量相同的情况下,取总运量最小的解）.对以上两条原则分别建立数学模型,并给出一个班次生产计划的快速算法.针对给出的实例,给出具体的生产计划、相应的总运量及岩石和矿石产量.2 模型的假设2.1 卡车的往返平均速度相等,均为v=28km/h,一个班次内允许卡车在卸点、铲位分钟的等待时间,实际上可以通过卡车的调速来实现;2.2 铲车在一个班次内不移动,卸点在一个班次内也不移动;2.3 每个铲位均已预先根据铁含量将石料分成矿石和岩石;2.4 卡车在一个班次的出发地点为卸点;2.5 卡车可以允许有30秒的时间调节车速,使其不会出现等待的情况;2.6 电动铲车（电铲）、电动轮自卸卡车（卡车）在一个班次内可以不间断的工作;2.7 每个卸点所给定的各自产量是要求的最小值;2.8 在开始状态、结束状态,各电铲都在各自铲位上,电铲在一班次的开始状态就能为卡车服务、且卡车被安排到相应的铲位上.3 符号约定3.1 j: 铲位(j=1,2,p)；3.2 i: 卸点(i=1,2,q)；3.3 :第k个矿石卸点的产量要求；3.4 :第m个岩石卸点的产量要求(其中k+m=i)；3.5 w: 卡车满载时的载重量,w=154吨;3.6 : 卸点i到铲位j的距离（单位:km）, 距离矩阵为: = : 铲位j的矿石量: 铲位j的岩石量: 铲位j的矿石铁含量记3.7 : 平均装车时间(=5分钟);3.8 : 平均卸车时间(=3分钟)3.9 t: 一个班次工作的总时间(t=480分钟)3.10 : 从铲位j运输到卸点i的总车次（表示铲位不运输到卸点i）3.11 v:卡车平均时速(v=28km/h)3.12 :第i个卸点一个班次出动的总卡车数4 模型的建立通过对题目的分析,我们可得出对解此规划问题的数学模型的思路如下:运输数据合理假设简化问题数据搜索结论结论函数约束条件目标人工分析4.1 原则1的模型一原则1中总运量(吨公里)可看成是各铲位运往各卸点的车次与其之间的路程及车的载重之间的乘积:.卡车数是各卸点的一个班次内所有卡车的总运行时间与一辆卡车在一个班次内的总工作时间之比:即.每个铲位输出的矿石为:;输出岩石为: ;每个卸点的需求;运往各卸点的矿石的含铁量为:.根据问题中提出的生产计划要求,要使总运量最小,同时出动最少的卡车,即是如下双目标规划问题:目标函数:总运量:一个班次内所需的卡车数: st 点运量限制: i=1,k(1)矿石卸点运量限制: i=1,m(其中k+m=q) (2)搭配限制（品位要求）, i=1,2,k(3)铲位矿石限制: （i=1,2,p） (4) 铲位岩石限制: （i=1,2,p） 各卸点的卡车限制: (5) 铲车台数限制,其中 (6) 各铲位铲车的铲量限制: (7) 各卸点的产量限制: 线路最大承受卡车能力: (8)4.1.1目标函数说明:目标函数使总运量最小. 目标函数使在一个班次内出动的卡车数最小.4.1.2 约束条件说明:(1)对于i卸点,从铲位j到卸点一次运输时间为等于装车时间、卸车时间及卡车在卸点与铲位间运行所用的时间 (其中)则运行次所需的总时间为: 故卸点i的卡车数为(2) 运量限制:对于卸点I,所有铲位j(j=1.p)运到卸点i的总吨数必须要满足要卸点的产量要求. (3)各条线路上的卡车最大容量,即在一个班次内,在同一条线路上,原则上不等待的最多可运行卡车数量.如在题中给出的实例数据中,如铲位1到岩石漏的路程为0.64公里,往返一次加上装卸时间为:10.74分钟,当第一台卡车出发时,第二台铲车马上装车,装车需5分钟,考虑有多个铲点往同一个卸点运输时的情况,由于各铲点往返时间加等待时间,即运行周期不同,而又受随机因素影响,故排时计划无效,所以只考虑线路的承载能力.由于露天矿道路宽敞,实际生产中司机可以而且应观察是否还有其它车同时驶向卸点,离卸点近的司机自动将车开快,远的车降低车速,使之达到不等待的条件,于是只考虑其在铲点上最大等待时间内不相遇,超过了就会出现相遇情况,则计划不合理.4.2原则二的模型 原则二要求的总产量可看成所有出动的卡车运行的车次和.与模型一不同之处在于约束条件(3)对于卸点i,各个铲位运到卸点的矿石铁含量要满足品位要求,卸点i的总产量大于、等于它的产量要求.而总产量正是未知要求的.这使使模型二成为一个非线形规划.目标函数:总产量st(1) (2) (4) (5) (6) (7) (8) 同模型I搭配限制（品位要求）, i=1,2,k 4.2.1 目标函数说明:目标函数使总产量最大4.2.2 约束条件说明:除约束条件(3),其余条件都与模型相同.5 模型的求解5.1 模型一的求解本模型为双目标多约束的优化模型,很难求出全局最优解,所以我们将多目标规化化简为单目标规化,再根据生产计划的要求.仿真全部铲车和卡车的工作过程.求解思路如下:由于这一多目标规化模型的两个函数相矛盾的目标函数（在最大运量时,卡车数难以达到最小值）,因此我们引入一个权重系数, 利用线性加权法,将多目标规划问题转化为单目标规划问题,把这个多目标规划化成单目标规划,其表达式为: 目标函数: 约束条件与模型一的约束条件相同.5.1.1 模型一的快速算法目标函数与约束条件内的和各量都是已知可求的,将数据输入后,以总运量、出动的总卡车数为目标,用Maple的线性规划函数求解.根据运行后输出的总运量、总车数、各卸点与各铲位间的车次数,再有了各卸点与铲位、需要的车次数,则可以进行排车计划,如下.假设离卸点i,最近的铲位为j,如果此时从j向i运输的次数在一个班次内一辆卡车无法完成,两辆卡车则又可提早完工,事实上,在实际生产中的一条路线上,很难出现整数台卡车刚好完成任务就到下班时间的情况,将会有多条路线都会出现u台车不够,u+1台车又可超额完成.而合理的规划第u+1台车的路线安排又是非常重要的.例如,在一个班次的上班前,对第u+1台车的司机安排好,要求其在一个铲位运完要运的车次,就转到第二个铲位,可节省很多的运输成本.那么我们应先考虑铲位到卸点最近的路线.则使第u辆卡车在此铲位和卸点间工作一个班期,而u+1辆卡车完成次铲位的车次减去u台卡车一天的工作次数后,在卸点卸完货,就去服务要运往同一卸点的另一铲位.每一个点的是一个固定的数,第u+1台卡车则先不考虑,第u台车要先考虑铲位与卸点最近的路线,才去帮第二近的路线,以此类推,当在帮第x近的卸点卸完货要收工,又还没完成这个点的需要供给车次,就考虑第x+1的对第x近的线路则再多安排一台卡车运输,如果第x+1近的仍不行则考虑第x+2近的直到有满足其工作量的为止,按此方法可给出所要求的安排.5.2 模型二的快速算法 由于模型二为一个非线性规划,将已知数据输入后,我们在Maple中采用搜索法编程,在多组数据中求解搜索出此非线性规划的最优解,在满足总产量优先,再考虑岩石产量优先,最后是总运量优先这一多层目标下取最优解.这就需要对所求数据层层分析,先满足最上一层,再满足第二层,最后满足第三层,再将所求出的进行人工分析,排车计划与模型一所给出的方法相同.5.3对实例的求解5.3.1模型一的求解目标函数: 约束条件:与模型的限制条件相同.取,则求解(*)的最优解,即为原多目标规划问题的有效解:如下表:加权系数的值总运量卡车数0.184829.2312.490.284829.1512.490.384829.1712.490.484829.1312.490.584829.1512.490.684829.1912.490.784829.1812.490.884829.1512.490.984829.2312.49观察表中数据可得出=0.1与=0.9时总运量达到最大,取=0.1的数值进行计算,然而总运量的大小的变化都不大,而车次也没有变化,即权重系数在此影响不大,两项间的制约性不强.以附录中的数据为此实例求解的数据.以车数(整数)表示出各铲位的岩石、矿石及各个卸点的产量.即题表中所给数据整除其载重量154吨.因为题目要求卡车每次要满载,所以小数部分不再用一台卡车运输.可得以下数据:铲位12345678910矿石61686468718168848781岩石81718768748768748781卸点所用车次:矿石漏:78 倒装1:85 倒装2:85 岩石漏:124 岩场:85将数据代入模型1,用Maple运行可得出的矩阵,通过整和和人工分析,得出的数据:铲位1铲位2铲位3铲位4铲位5铲位6铲位7铲位8铲位9铲位10矿石漏0130000054 011倒装场041 044000000岩场000000007015岩石漏81 043 0000000倒装场014000000071铲车的数量为7辆,最小总运量:min X=85230吨公里,最小卡车数为:13辆.车辆安排如下图所示1 1 2 21 122 1 1 1.线路的一辆卡车运行了36次后,就调度到线.因此, 线路两部车分别运载了45,36次. 线路的两部车(有一部是支援的)分别运载了35,7(支援车的运载次数)次.2.线路的一辆卡车运行了2次后,就调度到线. 线路的车运载的次数分别为39,2次. 线路的两部车(有一部是支援的)运载的次数分别为23,20(支援车的运载次数).3.线路的一辆卡车运载完(15次)后,就到线去运载. 线路的车运载的次数是15次. 线路的两部车(有一部是支援的)的运载次数是41,29(支援车的运载次数).4.线路的一辆卡车运载了24次后，就到线去运载.在此之前 线路是没有卡车的. 线路的两部车(有一部是支援的)运载的次数分别是47,24次. 线路的一部车的运载次数是7次.5.线路的一部车的运载次数是13次.6.线路的两部车的运载次数分别是27,27次. 5.3.2模型二的求解目标函数: 总产量约束条件与模型二相同.MAPLE搜索求得的最优解,求得最优解如下:最大产量为94313吨,岩石产量为49280吨,矿石产量为45033吨,此时总运量为168908.各铲位与卸点间的的车辆安排如下表所示:铲位1的车铲位2的车铲位3的车铲位4的车铲位5的车铲位6的车铲位7的车铲位8的车铲位9的车铲位10的车矿石漏0300000100倒装场1110000000岩场0000000031岩石漏1112000000倒装场0020000101具体的车辆安排为: 从铲位8到卸点5间的车辆在完成任务后调度到铲位3到卸点5之间;从铲位10到卸点5的车辆在完成任务后调度到铲位3到卸点5;从铲位2到卸点2间的车辆在完成任务后调度到铲位1到卸点2之间;从铲位10到卸点3间的车辆在完成任务后调度到铲位9到卸点3之间;从铲位3到卸点4间的车辆在完成任务后调度到铲位4到卸点4之间.便完成了其车辆调度安排. 6 模型的评价本文对建立的两个基本模型逐步简化求解,将多目标规划利用主要目标法转化为单目标规划,非线性规划转化为线性规划,利用Maple软件的整数规划求解，模型简单,实用性强,容易编程实现求解.在建设模型的过程中,本人发现了一些在满足目标函数时引发的可能的更大的浪费.在解出某个铲位中,有可能会遇上的需求量只要很少的几车次,在这种情况下,如果仍然派一台铲车帮其运输,虽然达到了运量最小的条件,但又浪费了一台铲车在一个班次内剩下的应工作的时间.所以可以考虑去掉这些铲点以节省资源.也有一种情况可能会出现为达到卸点产量要求,而需多派一台车再运少数的几次,这时,如果减少这台车的安排,可节省资源.可设铲车调度的费用与卡车启动的费用和不够产量的费用及总运量转换的费用数值为一定值,衡量其利弊关系.从而决定出在一个班次中,经济效益先行,可求出在要派铲车和卡车的条件,即一个铲位要派铲车的车次数要超出一个次数范围,和要派卡车的的次数要超出一个次数的范围.7 致谢毕业论文写作完毕.回想起论文的写作过程，一直得到简国明副教授关心、支持和帮助.简国明副教授严谨的治学精神深深地影响着我，使自己的数学思想、方法变得严密和科学，综合素质得到一定的提高，使本人在成文过程中受益匪浅.在论文的选题、论证、撰写中得到简国明副主任的悉心指导， 提供或查找资料、解决疑难问题、修改论文，使本人的毕业论文能如期完成，这与简主任的悉心指导、教育分不开的.在此，本人特向简老师表示衷心的感谢.祝简老师身体健康、工作顺利、万事胜意！同时，也借此机会对曾经为本人的论文成文过程中提供帮助的陈晔、何荣坚同学和其他老师表示深深的谢意.祝老师们工作顺利、桃李满天下，也祝同学们学业有成.参考文献:1 程理民运筹学模型与方法教程M北京：清华大学出版社,19992 甘应爱运筹学M 北京：清华大学出版社,19983 马开平Maple高级应用和经典实例M北京：国防大学出版社,20024 胡达多目标规划有效性理论M上海上海科学技术出版社,19945 施光燕，董加礼最优化方法北京：高等教育出版社，19996 姜启源等数学模型(第三版) M北京：高等教育出版社,20037 胡显佑等线性经济模型极其数学方法M 北京：中国人民大学出版社8 尹泽明等精通MATLAB6M北京：清华大学出版社,20049 丁余良等露天矿生产的车辆安排工程数学学报，2003，第20卷(第七期):63-7510 姚恩瑜等数学规划与组合优化杭州：浙江大学出版社，2001附录:铲位和卸点位置的二维示意图如下,各铲位和各卸点之间的距离（公里）如下表:铲位1铲位2铲位3铲位4铲位5铲位6铲位7铲位8铲位9铲位10矿石漏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各铲位矿石、岩石数量(万吨)和矿石的平均铁含量如下表:铲位1铲位2铲位3铲位4铲位5铲位6铲位7铲位8铲位9铲位10矿石量095105100105110125105130135125岩石量125110135105115135105115135125铁含量30%28%29%32%31%33%32%31%33%31%附录一:restart;#清内存 with(linalg):#调入线性软件包 d:=matrix(5,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): x:=matrix(5,10,): b:=matrix(3,10,9500,10500,10000,10500,11000,12500,10500,13000,13500,12500, 12500,11000,13500,10500,11500,13500,10500,11500,13500,12500, 0.30,0.28,0.29,0.32,0.31,0.33 ,0.32,0.31,0.33,0.31) S:=154*(sum(sum(di,j*xi,j,j=1.10),i=1.5):#总运量 T:=sum(sum(8+120*di,j/28)*xi,j,j=1.10),i=1.5)/480:#卡车数 eq1:=sum(154*b3,j*x1,j/12000,j=1.10)=0.285:#品位限制 eq2:=sum(154*b3,j*x1,j/12000,j=1.10)=0.305: eq3:=sum(154*b3,j*x2,j/13000,j=1.10)=0.285: eq5:=sum(154*b3,j*x5,j/13000,j=1.10)=0.285: eq6:=sum(154*b3,j*x5,j/13000,j=1.10)=0.305: eq7:=(154*x1,1+154*x2,1+154*x5,1)=9500:#矿石输出量限制 eq8:=(154*x1,2+154*x2,2+154*x5,2)=10500: eq9:=(154*x1,3+154*x2,3+154*x5,3)=10000: eq10:=(154*x1,4+154*x2,4+154*x5,4)=b1,4: eq11:=(154*x1,5+154*x2,5+154*x5,5)=b1,5: eq12:=(154*x1,6+154*x2,6+154*x5,6)=b1,6: eq13:=(154*x1,7+154*x2,7+154*x5,7)=b1,7: eq14:=(154*x1,8+154*x2,8+154*x5,8)=b1,8: eq15:=(154*x1,9+154*x2,9+154*x5,9)=b1,9: eq16:=(154*x1,10+154*x2,10+154*x5,10)=b1,10: eq17:=(154*x3,1+154*x4,1)=b2,1: #岩石输出量限制 eq18:=(154*x3,2+154*x4,2)=b2,2: eq19:=(154*x3,3+154*x4,3)=b2,3: eq20:=(154*x3,4+154*x4,4)=b2,4: eq21:=(154*x3,5+154*x4,5)=b2,5: eq22:=(154*x3,6+154*x4,6)=b2,6: eq23:=(154*x3,7+154*x4,7)=b2,7: eq24:=(154*x3,8+154*x4,8)=b2,8: eq25:=(154*x3,9+154*x4,9)=b2,9: eq26:=(154*x3,10+154*x4,10)=1.2*104:#卸点需求量限制 eq28:=154*sum(x4,j,j=1.10)=1.9*104: eq29:=154*sum(x2,j,j=1.10)=1.3*104: eq30:=154*sum(x3,j,j=1.10)=1.3*104: eq31:=154*sum(x5,j,j=1.10)=1.3*104: eq32:=sum(xi,1,i=1.5)=96:#铲位约束 eq33:=sum(xi,2,i=1.5)=96: eq34:=sum(xi,3,i=1.5)=96: eq35:=sum(xi,4,i=1.5)=96: eq36:=sum(xi,5,i=1.5)=96: eq37:=sum(xi,6,i=1.5)=96: eq38:=sum(xi,7,i=1.5)=96: eq39:=sum(xi,8,i=1.5)=96: eq40:=sum(xi,9,i=1.5)=96: eq41:=sum(xi,10,i=1.5)=96: eq42:=sum(x1,j,j=1.10)=160:#卸点的约束 eq43:=sum(x2,j,j=1.10)=160: eq44:=sum(x3,j,j=1.10)=160: eq45:=sum(x4,j,j=1.10)=160: eq46:=sum(x5,j,j=1.10)=160: eq47:=T=0.285:eq2:=sum(154*b3,j*x1,j,j=1.10)/tmp1=0.305:eq3:=sum(154*b3,j*x2,j,j=1.10)/tmp2=0.285:eq5:=sum(154*b3,j*x5,j,j=1.10)/tmp2=0.285:eq6:=sum(154*b3,j*x5,j,j=1.10)/tmp2=.305:eq7:=T=20:eq8:=(154*x1,1+154*x2,1+154*x5,1)=b1,1:eq9:=(154*x1,2+154*x2,2+154*x5,2)=b1,2: #矿石输出量限制eq10:=(154*x1,3+154*x2,3+154*x5,3)=b1,3:eq11:=(154*x1,4+154*x2,4+154*x5,4)=b1,4:eq12:=(154*x1,5+154*x2,5+154*x5,5)=b1,5:eq13:=(154*x1,6+154*x2,6+154*x5,6)=b1,6:eq14:=(154*x1,7+154*x2,7+154*x5,7)=b1,7:eq15:=(154*x1,8+154*x2,8+154*x5,8)=b1,8:eq16:=(154*x1,9+154*x2,9+154*x5,9)=b1,9:eq17:=(154*x1,10+154*x2,10+154*x5,10)=b1,10:eq18:=(154*x3,1+154*x4,1)=b2,1: eq19:=(154*x3,2+154*x4,2)=b2,2: #岩石输出量限制eq20:=(154*x3,3+154*x4,3)=b2,3:eq21:=(154*x3,4+154*x4,4)=b2,4:eq22:=(154*x3,5+154*x4,5)=b2,5:eq23:=(154*x3,6+154*x4,6)=b2,6:eq24:=(154*x3,7+154*x4,7)=b2,7:eq25:=(154*x3,8+154*x4,8)=b2,8:eq26:=(154*x3,9+154*x4,9)=b2,9:eq27:=(154*x3,10+154*x4,10)=1.2*104:eq29:=154*sum(x4,j,j=1.10)=1.9*104: #卸点需求量限制eq30:=154*sum(x2,j,j=1.10)=1.3*104:eq31:=154*sum(x3,j,j=1.10)=1.3*104:eq32:=154*sum(x5,j,j=1.10)=1.3*104:eq33:=sum(xi,