钢管订购和运输的规划模型

钢管订购和运输的规划模型

陈丹妮

摘要：本文就天然气管道钢管的订购和运输问题，建立了使订购和运输总费用最小的优化模型.我们把计

算分为订货和铁路，公路费用的计算及管道上运输费用的计算两个部分.对第一部分的计算，我们采用了增减约束条件的方法，避免了求解一组多分支规划的繁重的计算.对第二部分的计算，我们综合各种可能情况作出比较，从而使计算简化，并求出了最优的钢管订购和运输计划.对于第二问，我们把每个钢厂的销价及生产上限在一定范围内浮动，观察比较得出钢厂S3钢管的销价的变化对购运计划和总费用影响最大，钢厂同样S1钢管的产量的上限的变化对购运计划和总费用的影响最大.在第三问中运用第一问的方法建立模型，求出了铁路，公路和管道构成网络时总费用最小的钢管订购和运输计划.

一 题的重述

要铺设一条A1A2...A15的输送天然气的主管道.经筛选后可以生产这种主管道钢管的钢厂有S1,S2,...,S7.连接钢厂Si（i=1,…,15）和Aj(j1,...,15)的有铁路和公路.沿管道或者原来有公路，或者建有施工公路.一个钢厂如果承担制造这种钢管，至少需要生产500个单位.已知钢厂Si在指定期限内能生产该钢管的最大数量，钢管出厂销价及1单位钢管的铁路运价和公路运输费.钢管不只是运到点A1,A2,...,A15, 而是管道全线.问如何制定一个主管道钢管的订购和运输计划，使总费用最小；哪个钢厂的销价变化对购运计划和总费用影响最大，哪个钢厂钢管的产量的上限的变化对可以计划和总费用的影响最大；如果要铺设的管道不是一条线，而是一个树形图，铁路，公路和管道构成网络，如何建立相应的模型和如何求解.

290 S3 S2 1200 690 720 202 1100 20 306115600 195 5 10 194 10 31 S1 12 42 70 480 10 S4 30 20 30 A15 500 A14 S7 20 160 70 S6 62 462 S5 10 220 690 170 520 88 1670 320 110 420 A13 210 A12 680 201 A8A9300 A11 A10 45A5 2 750 A4 606 3 A3 104 A2 301 A1 8A6205 A7图一 84

第一期（2002年10月） 韶关学院学生数学建模论文集 No.1 290 S3 S4 A18 3S7

160 320 A20 20 70 160 20 69S2 100 30 260 690 S6 70 130 (A21) A15 120170 11500 A19 72190 5288 62 A14 420 A16 A17 462 202 S5 10 A13 70 S1 1100 210 10 42 220 A12 212 480 195 300 A11 31 A10 30A9 680 10 201 A85 600 10 194 A6 205 A7 1150 450 80 二 本假设与符号约定

A5 606 750 2 A4 3 A3 104 A2 301 A1 图二 1) 1km主管道钢管称为1单位钢管； 2) 假设在钢厂Si的订购货量为xi个单位；

3) 对于图一，铁路和公路相交的车站从左到右分别记为t1,t2,...,t17；

4) 对于图二，铁路和公路相交的车站或者铁路和管道相交的车站从左到右分别记为

t1,t2,...t18；

5) 假设钢厂Si流经tj站的钢管量为xi,j个单位； 6) 假设Aj处的到货量为aj；

7) 假设1单位钢管从钢厂Si运到Aj的运价为ki,j；

8) 钢厂Si在指定期限内能生产该钢管的最大数量是Si个单位； 9) 钢管出厂销价1单位钢管为Pi万元；

10) 假设铁路运费是整段计算的（从货物上车到下车一次性收费），二不是分段计算； 11) 沿管道公路的运费计算与其他公路一致，且不考虑流量的问题.

三 问题的分析

从图上可以看出，各钢厂订购的钢管必先经铁路或公路运往主管道与公路的各节点Ai上再沿主管道进行运输和铺设.因此，我们可以把运输的总费用分为在非管道（铁路或公路）

85

No.1 韶关学院学生数学建模论文集 第一期（2002年10月） 上的运输费用和主管道上的运输费用两部分来计算.

对于非管道上的运输.由于钢厂承担制造钢管后至少生产500个单位，所以对于每一个钢厂来说，订购量要么为0，要么就大于或等于500个单位，这就构成一组2个的多分支线性规划问题，计算将非常复杂.但我们可以采用如下办法简化计算：对所有钢厂的产量先不设下限进行求解，若解出来的订购量都符合不小于500个单位的情况则为可行解，若解出来的订购量中有不为0的，但小于500个单位，则在约束条件中加进这个订购量的下限进行求解，直至得出符合条件的最优解.

对于管道上的钢管运输铺设的费用则比较复杂，钢管从一个Ai点出发，可以单纯沿管道公路进行运输，也可以一边运输一边铺设，要使运输费最优是类似一次规划的非线性规划问题，由于变量多，计算量大，因此要进行一定的简化.

我们现证明一重要结论：当管道上各节点的钢管量等于与节点相连接的两边管道总长度的一半时，管道上钢管的运输费最小.

设运价为y，运量为x,y是x的函数，并且有k6dy0.1（其中路程单位为km）.dx假设一段长为S的路程，量为x的钢管从其中一端点出发，y-x的关系如图所示： y y y kx ks kx

k(x-s) 0 x s x 0 s x 0 s x

xs xs 运费g即是图中阴影部分的面积.

当xs0so1ydyk[x2(sx)2]，

2s0当x=s时，gydyk(xs)dx当x>s时，gydy0s12kS， 21ks(2xs)， 2kk[2x2(sx)(1)](4x2s)，推出22s11s1x为稳定点.在[0,s]区间上，g(0)ks2,g(s)ks2,g()ks2,

22224s所以当x时，费用是最小的，由此方法我们计算出管线上的最小运输费t=61593.275万

2'容易看出，当x>s时，对g来求导有：g元.

四 模型的建立和求解

1,通过上面的分析，我们首先先令各钢厂订购的钢管运往各节点的铁（公）路运费和订

86

第一期（2002年10月） 韶关学院学生数学建模论文集 No.1 购费最优，然后我们把各钢厂订购的钢管分成17份分别运往与公路相连的火车站.由于铁路轨道成树状分布，所以这样的最优路线是确定的.通过对图一的分析，我们发现，

A8A9,A10A11,A13A14,A14A15 这四段管道路有这样的情况：1单位钢管从这些管

道路之一运过的运费，比从连结该管道路两端点的最短的公（铁）路线运过的运费要高.也就是说，与其将钢管经过这些管道路运输，不如发生“倒运”.因此，这些管道路左右两边的钢管存货应该要满足两边管道铺设的需要，而不应该经这四段管道路进行货物调送.根据前面的假设，我们列出如下以铁（公）路运费和订购费为目标函数的线性规划：

7177minfi,jxi,jpixi

i1kj1i117s.t

xi,jxi(i1,2,...,7)....(1) j17xi,ja2....(3) i17xi,3a4....(5) i17xi,5a6....(7) i17xi,8a8....(9) i17xi,10a10....(11) i17xi,12a12....(13) i17(xi,14xi,15)a14....(15) i18ai2361....(17) i210ai3521....(19) i213ai4251....(21) i214ai4671....(23) i2xisi....(25)

xi,xi,j0....(2)

7xi,2a3....(4)

i17xi,4a5....(6)

i17(xi,6xi,7)a7....(8) i17xi,9a9....(10)

i17xi,11a11....(12)

i17xi,13a13....(14)

i17(xi,16xi,17)a15....(16)

i115ai2130....(18)

i915ai1350....(20) i1115ai500....(22)

i147xi5171....(24)

i187

No.1 韶关学院学生数学建模论文集 第一期（2002年10月）

由于只对xi作非负时，计算出x7低于下界500，所以需另加约束条件

x7500....(26)

重新求解得：f=1015556,

x1800, x2800, x31000, x40, x51331, x6740, x7500.这

样，我们得到各节点的钢管量，然后一边运输一边铺设这些钢管，求出所需运费为 q=3609.05万元，所以这样的运输方案得到的总费用为m=1381965.05万元.

对于这个方案我们还要进行调整.由上面的讨论我们知道，当管道上各节点的钢管量刚好等于与节点相连接的两边管道总长度的一半时，在管道上的运输费用最小.我们把

（a1,a2,a3,a4,a5,a6,a7,a8,a9,a10,a11,a12,a13,a14,a15）＝

( 0, 254.5, 525.5, 678, 400, 199.5, 203, 440.5, 580, 390, 260, 215, 315, 460,

250 ) 作为约束

条件加进上述规划中，解得m’=13066563万元，可见这样的运输方案更优.我们可以再考虑把各钢厂的钢管运到各节点后，再通过运输调整到运输最小时分钢量分布.调整的运输费用为

zi215hj115i,jai,j.

其中hi,j是1单位钢管从Ai到Aj沿管线运输的价格，ai,j是从Ai到Aj沿管线的钢管运输量. 因此我们又得到如下规划

minFfzt 其中，fi17kj117i,jxi,jpixi

i17s.t （加上一规划约束条件中的（1）至（16）及（25））

ai11515i,152

525.5 400 203

ai115i,2202.5 678

ai115i,3ai115i,4ai115i,5ai11515i,6199.5 440.5

ai1i,7ai1i,8ai115i,9580

ai11515i,10390

ai115i,11260

ai1i,12215

88

第一期（2002年10月） 韶关学院学生数学建模论文集 No.1 15ai1i,13315

ai115i,14460

ai115i,15250

用Maple软件解得：

F=1203697.575,

x1800, x2800, x31000, x40, x51181, x60, x7500

经过比较，我们认为这个订购和运输的方案是最优的.由此可得详细的订运方案如下： （1）7个钢厂的订购量分别为

x1800,x2800,x31000,x40,x51181,x60,x7500.

（2）钢厂S1的钢管分3批运输，第一批197个单位运往A5，第二批400个单位运到A6，第三批203个单位直接沿公路运到A7.钢厂S2的钢管分两批运输，第一批359.5个单位运往另一批经t8运到A8.钢厂S5的钢管也分两批运输，第一批420个单位经t8, t7,t6, t5, t4 A4，

运到A4，另一批580个单位经t9运往A9.钢厂S5的钢管分六批运输，第一批45个单位运往第三批61个单位运往A5，第四批199.5个单位经t6运到A7，A3,第二批166个单位运往A4，

第五批390单位运到A10，第六批260个单位运往A11.钢厂S6的钢管分三批运输，第一批115个单位往A12，第二批315个单位往A13，第三批420个单位直接沿公路运往A14.钢厂S7的钢管全部直接运到A15.

2，根据我们建立的模型，保持其它条件不变，令各个钢厂的钢管销价pi上浮或下降5％，可得到总费用的变化幅度和运购计划的变化情况，如下表： 项目 最小值 p1上调5% 1209827 下调5% 下调5% 下调5% 下调5% 下调5% 1197297 1197497 1195947 1203697 1208322 P2上调5% 12097 P3上调5% 1211447 P4上调5% 1203697 P5上调5% 1208322 x1 x2 x3 变幅 00（0.53%） 800 800 1000 -00（0.5%） 800 800 1000 6199（0.5%） 800 800 1000 6200（5.2%） 800 800 1000 7749（6.4%） 800 800 1000 -7750（6.4%） 800 800 1000 0 0 800 800 1000 800 800 1000 x4 0 0 0 0 0 0 0 0 0 0 x5 1181 1181 791 1181 1181 791 790 1181 200 200 x6 0 0 1280 0 0 1280 1280 0 1871 1871 x7 500 500 500 500 500 500 500 500 500 500

4625（3.8%） 800 800 1000 4625（3.8%） 800 800 1000

No.1 韶关学院学生数学建模论文集 第一期（2002年10月）

P6上调5% 1210372 下调5% 下调5% 1210372 1199697 P7上调5% 1207697 6675（5.5%） 800 800 1000 6675（5.5%） 800 800 1000 4000（3.3%） 800 800 1000 -4000（3.3%） 800 800 1000 0 0 0 0 1181 1181 791 1181 0 0 1280 0 500 500 500 500 从上表比较可得，钢厂Si的钢管销价的变化对总费用及购运计划影响最大.

用同样的方法，保持其他条件不变，令各个钢厂钢管产量的上限上浮或下降10%，得

出总费用和购运计划的变化情况： 项目 S1上调10% S2上调10% S3上调10% S5上调10% S6上调10% S7上调10% 最小值 变幅 X1 X2 800 800 880 720 800 800 800 800 800 800 800 800 X3 X4 X5 1101 1261 1101 1261 1081 1281 791 1181 1181 791 1181 1181 X6 0 0 0 0 0 0 1280 0 0 1280 0 0 X7 500 500 500 500 500 500 500 500 500 500 500 500 1195457 -8240(0.69%) 880 720 1000 0 1000 0 1000 0 1000 0 1100 0 900 0 下调10% 1211937 8240(0.68%) 1200497 -3200(0.27%) 800 800 800 800 800 800 800 800 800 800 下调10% 12067 3200(0.27%) 1201197 2500(0.21%) 下调10% 1206197 2500(0.21%) 1203697 0 1000 0 1000 0 1000 0 1000 0 1000 0 1000 0 下调10% 1203697 0 1203697 0 下调10% 1203697 0 1203697 0 下调10% 1203697 0 同样由上表可得出，钢厂S1的钢管产量的上限的变化对总费用及购运计划的影响最大. 3、如图二，要铺设的管道不是一条线，而是一个树形图，铁路、公路和管道构成网络.管道运输最优时各个Ai的存钢量为

La1,a2,a3,a4,a5,a6,a7,a8,a9,a10,a11,a12,a13,a14,a15,a16,a17,a18,a19,a20,a210,254.5,525.5,678,400,199.5,203,440.5,0,390,0,215,315,460,250,622,430,65,225,180,50

对于A19,A20,A21这三个兼为火（汽）车中转站的点，我们把它们一分为二看待.以A19为例，一方面看成t19,A12的货物由此经过，一方面看成A19，其钢管量为与之相连接的两段管道总长度的一半，并且钢管直接从它运到主管道.根据第一问的做法，先把Ai的钢管量预置成L的数量值，这样沿主管道的运输费用就能降到最低，在此基础上对各钢厂的定货量及其分流方式进行调配.然后，使用第一问的方法列

90

第一期（2002年10月） 韶关学院学生数学建模论文集 No.1 出线性规划如下：

minfki,jxi,jpixii1j1i17177s.t.xi,jxii1,2,...,7xi,xi,j0j121

xi177i,1a2　　　　　　　　　　　　　xi,2a3

i17xi17i,3a4　　　　　　　　　　　　　xi,4a5

i177xi17i,5a6　　　　　　　　　　　　　(xi,6xi,7)a7

i17xi17i,8a8　　　　　　　　　　　　　xi,9a16

i1xi17i,10a10　　　　　　　　　　　　xi,11a17

i177xi17i,12a18　　　　　　　　　　　　xi,13a12

i17xi17i,14a13　　　　　　　　　　　　(xi,17xi,18)a15

i17(xi17i,15xi,16)a14　　　　　　　　　xi,19a19

i17xi17i,20a20　　　　　　　　　　　　xi,21a21

i1xi1i5903　　　　　　　　　　　xisi

初次求解结果，0x7500，因此我们加入约束条件x7500，再次求解：

f1450357,x1800,x2800,x31000,x40,x51543,x61260,x7500

.475（万元）最小费用 mfe1518014，其中e是当节点上的钢管量取自中

的数值时，仿照问题一中的计算方法所得出的管道上的运输费用，e677.475万元.

五 模型的优缺点分析及其推广

91

No.1 韶关学院学生数学建模论文集 第一期（2002年10月） 我们建立的模型具有较强的可行性和可操作性，并且具有相当的实际意义.虽然我们未能对多个分支规划组逐个进行求解从而得出最优解，但我们对模型进行了适当的近似简化处理，减少了计算量和计算难度，最后得出可行解.我们建立模型的方法和思想对其它类似题材也适用，在建筑运输方面适用性较强，并可以推广到社会生活中相关的多个领域中去.对于类似的问题，对模型的决策性因素加以具体对 照分析即可.

参考文献：

[1]程里文，吴江，张玉林，运筹学模型与方法教程，清华大学出版社，北京，2000

[2]L.库珀，U.N勃哈特，L.J勒布朗（美），运筹学模型概论，上海科学技术出版社，上海，1987 [3]刘宝碇，赵瑞清，随机规划与模糊规划，清华大学出版社，北京，1998

[4]李世奇，杜慧琴，Maple计算机代数系统应用及程序设计，重庆大学出版社，1999.

（文章编辑：黄绮玲\\颜学友） 接83页

Dij A1 A2 A3 A4 A5 A6 A7 A8 A9 A10 A11 A12 A13 A14 A15 A16 A17 A18 A19 A20 A21 S1 0 160.3 140.2 98.6 38 20.5 3.1 21.2 .2 92 96 106 121.2 128 142 60 95 100 105 115 125 S2 S3 S4 S5 S6 0 0 0 0 0 205.3 220.3 250.3 245.3 255.3 190.2 200.2 235.2 225.2 235.2 171.6 181.6 216.6 206.6 216.6 111 121 156 146 156 95.5 105.5 140.5 130.5 140.5 88.1 98.1 133.1 123.1 133.1 71.2 86.2 116.2 111.2 121.2 114.2 48.2 84.2 79.2 84.2 142 82 62 57 57 146 86 51 33 51 156 96 61 51 61 171.2 111.2 76.2 71.2 26.2 178 118 83 73 11 192 132 97 87 28 110 44 80 75 80 145 85 50 32 47 150 90 55 50 33 155 95 60 50 36 165 105 70 65 10 175 115 80 75 0 (表2：从厂家Si运1单位钢管往Aj的最小路费)（图2） S7 0 265.3 245.3 226.6 166 150.5 143.1 131.2 99.2 77 66 71 38.2 26 2 95 65 50 55 32 26

92