钢管订购和运输求解(1)

《钢管订购和运输求解(1)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、钢管订购和运输1、问题描述：2000网易杯全国大学生数学建模竞赛题目B题钢管订购和运输A13258010103120124270108810706270302020304501043017506061942052016804803002202104205006003060195202720690520170690462160320160110290115011001200A2A3A4A5A6A11A711A11A8A11A911A11A10A11A12A13A14A15S1S2S3S4S5S6S7图一要铺设一条

2、的输送天然气的主管道,如图一所示(见下页)。经筛选后可以生产这种主管道钢管的钢厂有。图中粗线表示铁路，单细线表示公路，双细线表示要铺设的管道(假设沿管道或者原来有公路，或者建有施工公路)，圆圈表示火车站，每段铁路、公路和管道旁的阿拉伯数字表示里程(单位km)。为方便计，1km主管道钢管称为1单位钢管。一个钢厂如果承担制造这种钢管，至少需要生产500个单位。钢厂在指定期限内能生产该钢管的最大数量为个单位，钢管出厂销价1单位钢管为万元，如下表：123456780080010002000200020003000160

3、1551551601551501601单位钢管的铁路运价如下表：里程(km)≤300301～350351～400401～450451～500运价(万元)2023262932里程(km)501～600601～700701～800801～900901～1000运价(万元)3744505560注：1000km以上每增加1至100km运价增加5万元。公路运输费用为1单位钢管每公里0.1万元（不足整公里部分按整公里计算）。钢管可由铁路、公路运往铺设地点（不只是运到点，而是管道全线）。（1）请制定一个主管道钢管的订购和运

4、输计划，使总费用最小（给出总费用)。（2）请就（1）的模型分析：哪个钢厂钢管的销价的变化对购运计划和总费用影响最大，哪个钢厂钢管的产量的上限的变化对购运计划和总费用的影响最大，并给出相应的数字结果。A13258010103120124270108810706270302020304501043017506061942052016804803002202104205006003060195202720690520170690462160320160110290115011001200A19130190260100

5、A2A3A4A5A6A7A8A11A9A10A11A12A13A14A15S1S2S3S4S5S6S7A16A17A18A20(A21)图二（3）如果要铺设的管道不是一条线，而是一个树形图，铁路、公路和管道构成网络，请就这种更一般的情形给出一种解决办法，并对图二按（1）的要求给出模型和结果。2、运费矩阵的计算模型问题分析：我们只考虑本题第一问的求解。首先，所有钢管必须要运到天然气主管道铺设线上的节点，然后才能向左或右铺设，因此，必须求出从每个钢管厂(记为i=1,……,7)到每个节点(记为j=1,……,15)的每

6、单位钢管最小运费Cij（不妨称为运费矩阵）及其对应的运输方式和线路。因为题目中没有给出装卸成本，我们简单假设总是采用最经济的运输方式，虽然这个铺设在实际中可能不太接近现实，也就是说，在运输过程中需要多次装卸也是允许的（如铁路转公路，再转铁路，等等）。自然的想法是运输路线应该是走最短路径，但由于有两种运输和计价方式（铁路和公路），公路运输费用为1单位钢管每公里0.1万元（不足整公里部分按整公里计算），运费是路程的线性函数；然而，铁路运费要通过运输里程查表得到，是一个阶梯函数。这两种计价方式混合在一起，使得我们不能

7、直接在整个铁路、公路混合的运输网络上计算最短路径作为运输路线，但可以分析分别在铁路、公路网上技计算最短路径，然后换算成相应的费用；最后在整个网络上以两个子网上相应的运费为权，再求一次最短路问题，就可以把它们统一成一个标准的运费矩阵。铁路子网络：假设铁路运输线应该是走最短路径，而且采用连续路径计价方式一定优于分段计价方式（其实题中数据并不符合这一规定。例如题中650km的运价为44万元，而分成300km和350km两段计价只需要43万元，这种情况不太符合实际，可能是每题时选择数据的疏忽，我们不过多考虑这种情况）。

8、这时，我们可以把铁路运输子网独立出来，在这个网络上计算任意两个节点i，j之间的最短路径长度dij1，然后按照这个最短路长度查铁路运价表得到最小费用Cij1。在无向网络上求任意两点之间最短路径算法很多，尤其对本题这种弧上的权（距离）全为正数的情况，存在相对比较的算法。例如，求任意两点之间最短路径的Floyd-Warshall算法是（可参阅网络优化的有关书籍）（24）这实际上是一种标号算法