第31卷第1期2001年1月数学的实践与认识MATHEMATICSINPRACTICEANDTHEORYVol131No11Jan.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.1×lij由此,我们就在Vi、Vj之间用一条等价的公路线来代替Vi、Vj间的最短铁路线.如果Vi、Vj之间原来就有公路,就选择新旧公路中较短的一条.这样,我们就把铁路运输网络转换成了公路运输网络.销价等价转换法则:按单位费用相等将任意钢厂的单位销价转换为公路单位运价.对于钢厂Si的销售单价pi,我们可以虚设一条公路线,连接钢厂Si及另一虚拟钢厂S′i,其长度为li,并且满足li=0.1×pi;从而将钢厂的销售单价转换成公路运输单价,而新钢厂S′i的销售价为0.将铁路和销价转换为公路的过程可以由计算机编程实现.通过上述的分析,我们可以将原问题...
