管道订购与运输问题.pdf

第31卷第1期2001年1月数学的实践与认识MA THEMA T ICS I N PRACT ICE AND THEORYVol131No11Jan.2001管 道 订 购 与 运 输 问 题杨志江,李国欣,张敏指导老师:中国矿业大学数模教练组(中国矿业大学,江苏徐州221008)编者按:本文采用将待铺设管道按单位长度分解成n个需求点,建立运输模型的方法,避免了问题一和三的差别.模型切合原赛题要求,并针对原问题的规模,对算法作了一定的改进,得到了较好的结果.本刊予以摘要发表.摘要:本文在详细分析的基础上,通过合理假设并引入等价转换原则,将管道订购与运输问题转化为单一的公路运输问题.运用组合优化的思想和方法,给出了数学模型产量未定的运输模型.针对此模型,我们设计了“改进的最小元素法”和“改进的伏格尔法”,先求得了一个初始解,再通过“试探法”和“迭代法”进行调整优化,最后得出结果:对第一问,最小总费用为1279019万元;对第三问,最小总费用为1407383万元.1问题的重述(略)2基本假设(1)只考虑订购费用和运输费用,不考虑装卸等其它费用.(2)钢管单价与订购量、订购次数、订购日期无关.(3)订购计划是指对每个厂商的定货数量;运输方案是指具有如下属性的一批记录:管道区间,供应厂商,具体运输路线.(4)将每一单位的管道所在地看成一个需求点,向一单位管道的所在地运输钢管即为向一个点运输钢管.3符号说明m:钢厂总数.n:单位管道总数.Si:第i个钢厂.si:第i个钢厂的产量上限.pi:第i个钢厂单位钢管的销售价.Ai:管道线上第i个站点.di:管道线上第i个单位管道的位置.F:总费用.Cij:从钢厂Si(i=1,2,m)到点dj(j=1,2,n)的最低单位费用.4问题分析运输费用等价转换法则:按单位运费相等原则将任意两点间的最短铁路线转换为公路线.对于铁路线上的任意两点Vi、Vj,用Floyd算法找出两点间最短铁路路线的长度Lij,查铁路运价表求得Lij对应的铁路单位运费fij;又设与该段铁路等费用的公路长度为lij,则:fij=0.1lij由此,我们就在Vi、Vj之间用一条等价的公路线来代替Vi、Vj间的最短铁路线.如果Vi、Vj之间原来就有公路,就选择新旧公路中较短的一条.这样,我们就把铁路运输网络转换成了公路运输网络.销价等价转换法则:按单位费用相等将任意钢厂的单位销价转换为公路单位运价.对于钢厂Si的销售单价pi,我们可以虚设一条公路线,连接钢厂Si及另一虚拟钢厂Si,其长度为li,并且满足li=0.1pi;从而将钢厂的销售单价转换成公路运输单价,而新钢厂Si的销售价为0.将铁路和销价转换为公路的过程可以由计算机编程实现.通过上述的分析,我们可以将原问题化为一个相对简单的产量未定的运输问题,利用A1到A15之间的管道距离和钢厂和站点之间的公路距离建立一个产量未定的运输问题的模型.但是由于A1,A2,A15并不能代表所有的实际需求点(实际需求点是n个单位管道),因此,我们可以用Floyd算法进一步算出7个钢厂到所有实际的n个需求点(对于问题一,n=5171;对于问题三,n=5903)的最短路径,并由此得出一个具有7个供应点、n个需求点的产量未定的运输模型.5模型的建立产量未定的运输模型根据假设4,我们可以将每一单位的管道看成一个需求点,向一单位管道的所在地运输钢管即为向一个点运输钢管.对每个点,我们可以根据该点的位置和最短等价公路距离,求出各钢厂与该点之间最小单位运输费用Cij(销价已经归入运输费用之中了).设总共有m个供应点(钢厂),n个需求点,我们就可以得到一个产量未定的运输模型:有m个供应点、n个需求点,每个供应点的供应量ui0500,si;每个需求点需要1单位,运输单价矩阵为C,求使得总运输费用最小的运输方案.其数学规划模型:m inF=mi=1nj=1Cijxijs.t.nj=1xij0500,Sii=1,2,mmi=1xij=1j=1,2,nxij=0或1其中:C=C11?Cm1C12Cm2C1n?Cm n为单位费用矩阵X=x11?xm1x12xm2x1n?xm n为决策矩阵,也为0-1矩阵6模型的求解对于本题,上述01规划规模宏大,现有的一些算法不能胜任,我们必须具体问题具体06数学的实践与认识31卷分析,结合本题实际情况,寻找行之有效的算法.(1)初始方案的改进的最小元素法和改进的伏格尔法3改进的最小元素法改进的最小元素法又称为贪婪法或瞎子爬山法,它的宗旨是每一步都取当前的最优值.算法步骤为,对费用矩阵C作n次下列循环:C中找一个最小值Cij;令xij=1;C的第j列的所有数据改为+;如果nj=1xij=si,第i个供应点的供应量已达上限,将C的第i行数据全改为+;对于问题一和问题三,我们用贪婪法求得的最小总费用的初始分别为:128669211万元和141451512万元.3改进的伏格尔法改进的最小元素法确定的初始方案往往缺乏全局观念,即为了节省一处的费用,在其它处要花费更多.改进的伏格尔法的主要思想:一个目的地如果不能采用最小值供应(供应点供应不足),就必须考虑次小值供应,这里就存在一个差额.差额越大,在不能采用最小值时,损失越大.因此,改进的伏格尔法的宗旨是每一步对当前差值最大的点取当前最小值.算法的步骤为,对矩阵C做n次下列循环:指出每一行最小值与最大值之差最大的一行,第i行,找出该行的最小值为Cij;令xij=1;令C的第j列的数据为+;如果nj=1xij=si,第i个供应点供应量已达上限,令C的第i行的所有数据为+.对于问题一和问题三,我们用改进的伏格尔法求得方案的总费用分别为1279019万元和1407383万元.(2)调整优化调整优化是将一个离最优解很近的初始解调整到在调整算法下无法更优的程度.调整优化分两个部分,第一部分是用试探法对供应点的供应量进行优化.第二部分是用迭代法对供应点进行两两对调优化.3试探法调整优化实际供应量在500以下的供应点对每个实际供应量在500以下的供应点,只存在两种合理的优化方法:一种是将其供应量增加到500,另一种是将其供应量减少到0.试探法将分别试探进行下列两种优化:其一是先将供应点的供应量强行提升至500,使用改进的伏格尔法的优先顺序,从其它供应点负责供应的需求点抢夺一部分,再用对调法优化至无法更优,得出一个总费用F1;其二是先将该供应点的供应量调整为0,其原供应的需求点由其它钢厂用改进的伏格尔法的优先顺序补充,再用对调法优化至无法更优,得出一个总费用F2.那么,就应当采取总费用较小的方法.例如,对于第一问,按改进的伏格尔法获得的初始方案中,S7的用量仅为245,优化时,试探将其降为0和将其提升为500后的最优结果,分别为1279019万元和1280506万元,则161期杨志江等:管道订购与运输问题说明应将S7降为0.3用迭代法进行对调优化改进的伏格尔法给出的初始值虽然很接近最优值,但仍有不足之处,即可能存在两个需求点,调换供应点能使总费用更小,例如,需求点a和b的供应点是x和y,费用分别是C(x,a)和C(y,b),如果让y供应a,x供应b的话,费用将是C(y,a)和r(x,b),如果:C(y,a)+r(x,b)C(x,a)+C(y,b)则说明对调后总费用更低.因此,我们可以采用迭代法对任意两个需求点的供应点两两对调至无法更优.由于一共只有m=7个供应点,所以两两对调的可行方案一共有C27=21种,因此,两两对调供应点的方法是可行的,具体步骤如下:Step1对于任意两个供应点xi和xji=1,2,mj=1,2,mij1)找出所有由xi供应的需求点,构成点集A=a1,a2,c2)找出所有由xj供应的需求点,构成点集B=b1,b2,3)对A中所有点,如果改用xj来供应,将付出的代价构成向量A=a1,a1,4)对B中所有点,如果改用xi来供应,将付出的代价构成向量B=b1,b1,5)对A和B分别按升序排序.6)同时对A和B从前向后遍历,如果ai+bi(为一固定的较小值).如果有明显的进步,则再回Step1执行,否则结束优化.令人振奋的是,采用改进的最小元素法和改进的伏格尔法得到问题一的初始方案分别采用这种优化方案后,竟都达到了相同的最小费用:1279019万元.(3)结果(略)参考文献:1薛秀谦等编著.运筹学.中国矿业大学出版社,1998年.2赵新泽著.线性规划的新方法和应用.世界图书出版社,1996年.3王树禾著.图论极其算法.中国科学技术大学出版社,1990年.4LUCASW F著.离散与系统模型.国防科技大学出版社,1996年.The Order and Transportation of the Tube PipeYAN G Zhi2jiang,L I Guo2xin,ZHAN G M in(China U niversity ofM ining and Technology,Xuzhou221008)Abstract:In this paper,through the rational hypothesis,aswell as the principle of equivalenttransformation,the problem of order and transportation of tube pipe could be transformed tothat of the road transportation.By using the idea andmethod of combinatorialopti m ization,we26数学的实践与认识31卷