数学建模-钢管订购和运输

一、问题重述和分析

要铺设一条A1A2A15的输送天然气的主管道，如图1所示,经筛选后可以生产这种主管道的钢厂有S1,S2,,S7. 图中粗线表示铁路，单细线表示公路，双细线表示要铺设的管道（假设沿管道或者原来有公路，或者建有施工公路），圆圈表示火车站，每段铁路、公路和管道旁的阿拉伯数字表示里程（单位km）.

290 S3 S2 1200 690 170 720 202 1100 20 195 306115600 10 5 194 10 31 S1 12 42 70 480 10 5288 462 S510 220 S4 1670 62 320 160 70 S6 11420 A1420 30 A15500 30 S7 2690 A13 210 A12 680 201 A8 A9A11 A10300 45A5 606 750 2 A4 3 A3 301 104 A2 A1 8A6205 A7

图1

为了方便，1km主管道称为1单位钢管. 一个钢厂如果承担制造这种钢管，至少

需要生产500个单位. 钢厂Si在指定期限内能生产该钢管的最大生产数量为si个单位，钢厂出厂销价为pi万元，如下表：

221

表1 i si pi 1 800 160 2 800 155 3 1000 155 4 2000 160 5 2000 155 6 2000 150 7 3000 160

1单位钢管的铁路运价如下表：

401~450 451~500 里程（km） 300 29 32 运价（万元） 20 801~900 901~1000 里程（km） 501~600 55 60 运价（万元） 37 1000km以上每增加1至100km运价增加5万元. 公路运输费用为1单位管道每公里0.1万元（不足整公里的按整公里计算）. 管道可由铁路、公路运往铺设地点（不只是运到点A1A2A15，而是管道全线）.

问题1. 制定一个主管道钢管的订购和运输计划，使总费用最小，并给出总费用. 问题2. 就（1）的模型进行分析：哪个钢厂钢管的销价的变化对购运计划和总费用影响最大，哪个钢厂钢管的产量的上限的变化对购运计划和总费用的影响最大，并给出相应的数字结果.

表2

301~350 351~400 23 26 601~700 701~800 44 50 二、基本假设

1． 在计算运费时，沿管道铺设路线上的公路与其它普通公路相同（1单位钢管每

公里0.1万元）；

2． 订购的钢管数量刚好等于需要铺设的钢管数量；

3． 管道可由铁路、公路、管道全线运往铺设地点（不只是运到点A1,A2,,A15）； 4． 模型只考虑钢管销价费用和钢管从钢管厂运送到铺设点的钢管运费，而不考虑

其它费用，如不计换车、转站的时间和费用，不计装卸费用等；

5． 不计运输时由于运输工具出现故障等意外事故引起工期延误造成损失； 6． 销售价和运输价不受市场价格变化的影响.

三、符号说明

Si ： si：

第i钢管厂

表示Si的最大生产能力

Aj： 表示需要铺设管道路径上的车站 xi j：

222

从所有Si运往Aj的钢管数

ci j：

表示单位钢管从Si地运往Aj地的最小费用 从Si订购钢管的单位价格

pi：

Q： 订购的所有钢管全部运到Aj(j1,2,,15)点的总运费 T： 当钢管从钢厂Si运到点Aj后，钢管向Aj的左右两边运输（铺设）

管道的运输费用

用于订购和运输的总费用

Z ：

yj： 运到Aj地向左铺设的数目 zj： 运到Aj地向右铺设的数目

d： 单位钢管1公里的公路运输费用

Aj, j1： 表示Aj和Aj1之间需要铺设的管道长度

四、模型的建立与求解

问题1.

1、 模型的建立

钢管的订购和运输方案是直接影响工程费用的主要原因，因此，选取费用最小的路线运送货物，合理的订购计划是决定该工程费用的重要因素，首先利用图论的方法，来确定从钢管生产厂家到施工结点的费用最小路线，然后建立工程费用的优化模型，从中优化出最佳购运方案.

对本问题而言，实际上是一个要求制定订购和运输计划，使总费用最小的优化问题. 本模型的总费用包括钢管的销价和运输总的费用. 首先，向某厂订购钢管，然后将在每个厂订购的钢管运往需要铺设的全路段. 欲解决本问题可以按以下方案进行思考：首先，需要确定将货物从i地运往j地的最优路线（费用最小）；然后，求出向每个钢管厂的订购计划，并确定出运输计划；最后计算将运往j地的钢管铺到各个管道上的运输费用，我们不妨假设运往以j为终点的钢管只铺到与j点相邻的两段管道上. 因此，本问题可以按以下步骤求解.

第一步：确定从i地到j地的最优路径，从而确定出单位钢管从i地运往j地的最小运费.

si(i1,2,7)表示钢管厂Si(i1,2,7)的最大生产能力，Aj(j1,2,,15)表

示需要铺设钢管路径上的车站. 假设从Si运往Aj的钢管用于铺设Aj点左右侧的钢管数为xi, j单位，单位产品从Si到Aj地的运费为Fi, j万元，用ci, j表示单位钢管从Si地

223

运往Aj地的最小费用，则：

cijminFij

第二步：建立从Si厂运送xi, j单位钢管到Aj点的运费的模型： 用Q表示订购的所有钢管全部运到Aj(j1,2,,15)点的总运费，则：

（1）

Qxi jci j；j1i1157（2）

第三步：将运到Aj处的钢管铺到相邻两段路上的运输费用

对于运到Aj的钢管，它向左运输的总量yj，它向左运输的总费用为：

yjd(yj1)d(yj2)d＝0.1(12同理它向右运输的总费用为

1d

； yj)0.05yjyj1（万元）

d(zj1)2zj＝0.05zjzj1

用T表示当钢管从钢厂Si运到点Aj后，钢管向Aj的左右两边运输（铺设）管道的运输费用，得

T0.051yjyj1zjzj

j115（3）

yj和zj之间存在的关系为

7xi jyjzj;(j1,2,,15) i1zyA;(j1,2,,14)j1j,j1j（4）

（Aj, j1表示Aj和Aj1之间需要铺设的管道长度）

第四步：建立订购费用的模型

设W表示订购管道的总费用，则可建立如下模型：

224

Wpixi, j

i1j1715（5）

又因为一个钢厂如果承担制造钢管任务，至少需要生产500个单位，钢厂Si在指定期限内最大生产量为si个单位，故500xj215ijsi 或xij0 ， 用Z表示订购和运输

j215的总费用，由（2）、（3）、（4）、（5），本问题可建立如下的非线性规划模型：

目标函数

minZWQT (picij)xij0.051yjyj1zjzj

i1j1j171515约束条件

7xi jyjzj;(j1,2,,15)i1zjyj1Aj,j1;(j1,2,,14)1515500xijsi或xij0;(i1,2,j2j2xij0 i1,,7,j2,,15 （6）

,7)其中Aj, j1表示Aj和Aj1之间需要铺设的管道长度.

2、模型的求解

（1）首先求解ci j 由于钢管从钢厂Si运到运输点Aj要通过铁路和公路运输，而铁路运输费用是分段函数，与全程运输总距离有关. 又由于钢厂Si直接与铁路相连，所以可先求出钢厂Si到铁路与公路相交点bj的最短路径. 依据钢管的铁路运价表，算出钢厂Si到铁路与公路相交点bj的最小铁路运输费用，并把费用作为边权赋给从钢厂Si到bj的边. 再将与bj相连的公路、运输点Ai及其与之相连的要铺设管道的线路（也是公路）添加到图上，根据单位钢管在公路上的运价规定，得出每一段公路的运费，并把此费用作为边权赋给相

应的边. 这样就转换为以单位钢管的运输费用为权的赋权图，再利用E.W.Dijkstra的最短路算法计算出一个单位钢管从钢厂运到工地的最少费用系数阵cij，MATLAB程序(略).

表3 表中对应的值为对应两点最优路径单位钢管运输费用 S1 S2 S3 S4 S5 S6 S7 225

A1 A2 A3 A4 A5 A6 A7 A8 A9 A10 A11 A12 A13 A14 A15

170.7 160.3 140.2 98.6 38 20.5 3.1 21.2 64.2 92 96 106 121.2 128 142 215.7 205.3 190.2 171.6 111 95.5 86 71.2 114.2 142 146 156 171.2 178 192 230.7 220.3 200.2 181.6 121 105.5 96 86.2 48.2 82 86 96 111.2 118 132 260.7 250.3 235.2 216.6 156 140.5 131 116.2 84.2 62 51 61 76.2 83 97 255.7 245.3 225.2 206.6 146 130.5 121 111.2 79.2 57 33 51 71.2 73 87 265.7 255.3 235.2 216.6 156 140.5 131 121.2 84.2 62 51 45 26.2 11 28 275.7 265.3 245.2 226.6 166 150.5 141 131.2 99.2 76 66 56 38.2 26 2 (2)根据以上结果, 继续求解非线性规划模型：

minZ (picij)xij0.051yjyj1zjzj

i1j1j1715157xi jyjzj;(j1,2,,15)i1zjyj1Aj,j1;(j1,2,,14)s.t1515500xijsi或xij0;(i1,2,j2j2xij0 i1,,7,j2,,15由于不能直接处理约束条件：500为

,7)xj215ijsi或xij0，我们可先将此条件改

j215xj215ijsi，得到如下模型：

minZ (picij)xij0.051yjyj1zjzj

i1j1j171515226

7xi jyjzj;(j1,2,,15)i1zjyj1Aj,j1;(j1,2,,14)s.t15xijsi;(i1,2,,7)j2xij0 i1,,7,j2,,15

用LINGO求解（程序略）. 分析结果后发现购运方案中钢厂S7的生产量不足500单位，下面我们采用不让钢厂S7生产和要求钢厂S7的产量不小于500个单位两种方法计算：

1）不让钢厂S7生产,程序略.

计算结果：Z11278632（万元）（此时每个钢厂的产量都满足条件）. 2）要求钢厂S7的产量不小于500个单位，程序略.

计算结果：Z21285281（万元） （此时每个钢厂的产量都满足条件）. 比较这两种情况，得最优解为，minZmin(Z1,Z2)Z1=1278632（万元）. 所以根据上述的模型，得运输总费用最小为1278632（万元）. 具体的购运计划和铺设方案如表4，表5.

表4 问题一的订购和调运方案 订购量 A2 A3 A4 A5 A6 A7 A8 A9 A10 A11 A12 A13 A14 A15 S1 S2 S3 S4 S5 S6 S7 800 800 1000 0 1015 1556 0 0 179 0 0 0 0 0 0 0 0 0 508 0 0 40 0 336 0 92 0 0 295 321 0 0 0 0 0 200 0 0 0 0 0 0 265 0 0 0 0 0 0 0 300 0 0 0 0 0 0 0 664 0 0 0 0 0 0 0 0 0 351 0 0 0 0 0 415 0 0 0 0 0 0 0 86 0 0 0 0 0 0 333 0 0 0 0 0 0 621 0 0 0 0 0 0 165 0 A1 A2 A3 A4 A5 A6 A7 A8 A9 A10 A11 A12

表5 问题一的铺设方案 y 0.000000 104.0000 226.0000 468.0000 606.0000 184.5000 189.5000 125.0000 505.0000 321.0000 270.0000 75.00000 z 0.000000 75.00000 282.0000 0.000000 9.500000 15.50000 76.00000 175.0000 159.0000 30.00000 145.0000 11.00000 227

A13 A14 A15 199.0000 286.0000 165.0000 134.0000 335.0000 0.000000 问题2. 针对问题一的求解模型，讨论钢厂钢管的销售价格变化对购运计划和总费用影响及钢厂钢管产量的上限变化对购运计划和总费用的影响．

定义 方案中运往各点Ai的运输量的变化量的绝对值之和称为运输方案变化量． 1、讨论钢厂钢管的销售价格变化对购运计划和总费用的影响

当钢厂钢管销售价格变化时，会对购运计划和总费用造成影响. 为了更好地观察每一个钢厂钢管销售价格所造成的影响，采用比较法，即每次只让一个钢厂钢管的销售价格发生相同的变化，其余钢厂钢管的销售价格不发生变化.

我们将各个钢厂单位钢管的销价分别增加1万元和减少1万元，借助LINGO软件得出相应的总费用、运输方案、订购方案变化情况如表6、表7所示

表6 各个钢厂单位钢管的销价分别增加1万元 运输方案变化订购方案变化钢厂 总费用 总费用变化量 量 量 S1 1279432 800 0 0 S2 1279432 800 0 0 S3 1279632 1000 0 0 S4 1278632 0 0 0 S5 1279639 1007 40 30 S6 1279834 1202 712 712 S7 1278632 0 0 0

表7 各个钢厂单位钢管的销价分别减少1万元 运输方案变化订购方案变化钢厂 总费用 总费用变化量 量 量 S1 1277832 800 0 0 S2 1277832 800 0 0 S3 1277632 1000 0 0 S4 1278632 0 0 0 S5 1277263 1369 712 712 S6 1277068 1564 40 30 S7 1278632 0 0 0 由上述表格观察分析可得： S6钢厂销价变化对总费用影响最大，S5,S6钢厂钢管的销价的变化对购运计划影响最大.

2、讨论钢厂钢管产量的上限的变化对购运计划和总费用的影响

同样采用比较法，即每次只让一个钢厂钢管产量的上限的发生相同的变化，其余钢厂钢管产量的上限不发生变化. 将各个钢厂的产量的上限分别增加100个单位和减少100个单位，分别计算，得到购运计划和总费用变化情况如表8、表9所示.

228

表8 各个钢厂钢管的产量的上限分别增加100个单位 钢厂 S1 S2 S3 S4 S5 S6 S7 总费用 1268332 1275132 1276132 1278632 1278632 1278632 1278632 总费用变化量 10300 3500 2500 0 0 0 0 运输方案变化量 218 404 1786 0 0 844 0 订购方案变化量 200 200 200 0 0 0 0

表9 各个钢厂钢管的产量的上限分别减少100个单位 钢厂 S1 S2 S3 S4 S5 S6 S7 总费用 1288932 1282132 1281132 1278632 1278632 1278632 1278632 总费用变化量 10300 3500 2500 0 0 0 0 运输方案变化量 260 1244 200 0 0 0 0 订购方案变化量 200 200 200 0 0 0 0 由上述表格观察分析可得：S1钢厂钢管的产量的上限的变化对总费用影响最大，购运计划影响较小.

五、模型的评价及改进

由于总费用由订购费用和运输费两部分组成，运输费又由一般线路上的运输费和铺设管道上的运输费组成. 利用求网络中最短路径的Dijkstra算法，进行改进得到新的算法，可对含多种权重计算方式的网络进行搜索，得出最小费用路径（最短路径），算出两点之间的最优路径，进而根据非线性规划，借助于Lingo软件求解即可求出相应的结果.

1．优点 1）本问题中运用了求网络中最短路径的Dijkstra算法的思想，进行改进和修改得到新的算法，可对含多种权重计算方式的网络进行搜索，算出两点之间的最优路径，计算结果准确，从而得出相应的购运单价的矩阵.

2）本问题构造出的模型算法较简单，也可以运用相应的其他编程软件来得到比较满意的结果.

3）本模型计算步骤清晰，借助于Lingo软件求解，可靠性较高. 2．缺点

1）由于题意中不考虑铁路公路间转运的中转费用，也不限制转运次数，因此在算法设计中存在着考虑不周全的缺限，如我们考虑是先通过铁路再通过公路到铺设点，但这不一定是最小费用路径，有可能先通过公路，然后经铁路再经公路运到铺设点，费用更少，这里没有理论证明.

229

2) 问题二要求根据问题一的分析,指出哪家钢厂销价的变化对购运计划和总费用影响最大，哪家钢厂钢管产量的上限的变化对购运计划和总费用的影响最大，并给出相应的数字结果. 这个问题属于规划问题的灵敏度分析，一般来说，应该对于销价的变化△p和产量上限的变化△s求出相应的总费用的变化△w，但要得到△w关于△p和△s的函数关系，几乎是不可能的，只对每个钢厂进行单独讨论.

3．模型改进

这个数学模型可以应用于西部开发中\"天然气东送”问题，当然，西部开发中\"天然气东送”问题远比我们的假设还要复杂的多，但无论如何，他们的本质一样，我们可将本问题运用于时间的变化等范围的推广. 本文还可以把问题1归结为网络最小费用流问题，建立了线性和非线性最小费用流模型，并运用相应的解法和分支定界法求解，简洁，层次分明.

参考文献：

[1] 甘应爱，田丰等等. 运筹学.清华大学出版社,北京,1994.

[2] 袁亚湘.孙文瑜著. 最优化理论与方法.科学出版社，北京，1997. [3] 徐俊明著. 图论及其应用.中国科学技术大学出版社，合肥，1997. [4] 赵静，但琦. 数学建模与数学实验[M].北京：高等教育出版社，2003.

习题1. 如果要铺设的管道不是一条线，而是一个树形图，铁路、公路和管道构成网络（图2），请就这种更一般的情形给出一种解决办法，制定一个主管道钢管的订购和运输计划，使总费用最小（给出总费用).

230

290 S3 S2 690 1200 720 170 520 S4 A18 160 320 160 A20 100 130 70 260 190 A19 70 30 S6 (A21) 110 30 S7 20 690 20 A15

500 88 62 A16 202 A17 420 462 S5 10 A13 1100 S1 42 70 10 20 220 210 A12 12 195 480 A11 30631 A9 A10 300 1150 680 5 10 201 A8600 450 10 194 A205 A7 80 6 2 750 A606 A5 4 3 104 301 A3 A2 A1

图2

A14 231