数学建模案例分析管道运输与订购优化模型CAI

钢管订购和运输优化模型

要铺设一条A1A2A15的输送天然气的主管道, 如图1所示(见反面).经筛选后可以生产这种主管道钢管的钢厂有S1,S2,,S7.图中粗线表示铁

路，单细线表示公路，双细线表示要铺设的管道(假设沿管道或者原来有公路，或者建有施工公路)，圆圈表示火车站，每段铁路、公路和管道旁的阿拉伯数字表示里程(单位：km).

为方便计，1km主管道钢管称为1单位钢管.

一个钢厂如果承担制造这种钢管，至少需要生产500个单位.钢厂Si在指定期限内能生产该钢管的最大数量为si个单位，钢管出厂销价1单位钢管为pi万元，如下表：

i si 1 800 160 2 800 155 3 1000 155 4 2000 160 5 2000 155 6 2000 150 7 3000 160 pi 1单位钢管的铁路运价如下表：

里程(km) 运价(万元) 里程(km) 运价(万元) 1000km以上每增加1至100km运价增加5万元.

公路运输费用为1单位钢管每千米0.1万元（不足整千米部分按整千米计算）. 钢管可由铁路、公路运往铺设地点（不只是运到点A1,A2,,A15，而是管道全线）.

501～600 601～700 701～800 37 44 50 801～900 55 901～1000 60 ≤300 20 301～350 23 351～400 26 401～450 29 451～500 32 案例分析 1

数学建模

问题：

（1）请制定一个主管道钢管的订购和运输计划，使总费用最小（给出总费用). 思考题：

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

（3）如果要铺设的管道不是一条线，而是一个树形图，铁路、公路和管道构成网络，请就这种更一般的情形给出一种解决办法，并对图2按（1）的要求给出模型和结果.

290 S3 S2 690 1200 720 202 1100 20 195 3061150 600 10 5 194 A6 10 31 201 A8A7S1 12 42 70 10 170 520 88 462 S5 10 220 S4 320 160 70 30 70 62 S6 110 420 A14 A15 500 20 30 S7 20 690 160 A13 210 A12 480 680 A9A10 300 A11 450 80 205 A5 606 750 2 A4 3 A3 301 104 A2 A1 图1

案例分析 2

数学建模

290 S3 S2 690 1200 720 A16 202 1100 20 195 3061150 600 10 5 194 A6 A5 606 10 31 S1 12 42 170 520 88 S4 A18 160 130 320 160 A20 100 70 260 190 462 10 A19 62 70 30 S6 (A21) 110 420 30 S7 20 690 20 A15

500 A14 A17 70 S5 10 220 A13 210 A12 480 A9 A10 680 300 A11 201 A8205 A7 450 80 2 750 A 4A3 301 A2 图2 3 104 A1

一、 基本假设

1． 沿铺设的主管道以有公路或者有施工公路. 2． 在主管道上，每千米卸1单位的钢管.

3． 公路运输费用为1单位钢管每千米0.1万元（不足整千米部分按整千米计算） 4． 在计算总费用时，只考虑运输费和购买钢管的费用，而不考虑其他费用. 5． 在计算钢厂的产量对购运计划影响时，只考虑钢厂的产量足够满足需要的情况，

即钢厂的产量不受限制.

6． 假设钢管在铁路运输路程超过1000km时，铁路每增加1至100km，1单位钢管

案例分析 3

数学建模

的运价增加5万元.

二、符号说明：

Si：第i个钢厂； i1,2,,7 si：第i个钢厂的最大产量； i1,2,,7 Aj：输送管道（主管道）上的第j个点； j1,2,,15

pi：第i个钢厂1单位钢管的销价； i1,2,,7

xij：钢厂Si向点Aj运输的钢管量； i1,2,,7 j1,2,,15

tj：在点Aj与点Aj1之间的公路上，运输点Aj向点Aj1方向铺设的钢管量；

j1,2,3,,14(t10)

aij：1单位钢管从钢厂Si运到结点Aj的最少总费用，即公路运费﹑铁路运费和

钢管销价之和； i1,2,,7 j1,2,,15

bj：与点Aj相连的公路和铁路的相交点； j2,3,,15

Aj.j1：相邻点Aj与Aj1之间的距离； j1,2,,14

三、模型的建立与求解

问题一：讨论如何调整主管道钢管的订购和运输方案使总费用最小

由题意可知，钢管从钢厂Si到运输结点Aj的费用aij包括钢管的销价﹑钢管的铁路运输费用和钢管的公路运输费用.在费用aij最小时，对钢管的订购和运输进行分配，可得出本问题的最佳方案.

1. 求钢管从钢厂Si运到运输点Aj的最小费用

1）将图1转换为一系列以单位钢管的运输费用为权的赋权图.

案例分析 4

数学建模

由于钢管从钢厂Si运到运输点Aj要通过铁路和公路运输，而铁路运输费用是分段函数，与全程运输总距离有关.又由于钢厂Si直接与铁路相连，所以可先求出钢厂Si到铁路与公路相交点bj的最短路径.如图3

图3 铁路网络图

依据钢管的铁路运价表，算出钢厂Si到铁路与公路相交点bj的最小铁路运输费用，并把费用作为边权赋给从钢厂Si到bj的边.再将与bj相连的公路、运输点Ai及其与之相连的要铺设管道的线路（也是公路）添加到图上，根据单位钢管在公路上的运价规定，得出每一段公路的运费，并把此费用作为边权赋给相应的边.以S1为例得图4.

案例分析 5

数学建模

图4 钢管从钢厂S1运到各运输点

Aj的铁路运输与公路运输费用权值图

2）计算单位钢管从S1到Aj的最少运输费用

根据图4，借助图论软件包中求最短路的方法求出单位钢管从S1到Aj的最少运输费用依次为：170.7，160.3，140.2，98.6，38，20.5，3.1，21.2，64.2，92，96，106，121.2，128，142（单位：万元）.加上单位钢管的销售价pi，得出从钢厂S1购买单位钢管运输到点Aj的最小费用a1j依次为：330.3，320.3，300.2，258.6，198，180.5，163.1，181.2，224.2，252，256，266，281.2，288，302（单位：万元）.

同理，可用同样的方法求出钢厂S2﹑S3﹑S4﹑S5﹑S6﹑S7到点Aj的最小费用，从而得出钢厂到点的最小总费用（单位：万元）为：

表1 Si到点Aj最小费用

A2 A3 A4 A5 A6 A7 A8 A9 A10 A11 A12 A13 A14 A15 S1 320.3 300.2 258.6 198 180.5 163 181.2 224.2 252 256 266 281.2 288 302 S2 360.3 345.2 326.6 266 250.5 241 226.2 269.2 297 301 311 326.2 333 347 S3 375.3 355.2 336.6 276 260.5 251 241.2 203.2 237 241 251 266.2 273 287 S4 410.3 395.2 376.6 316 300.5 291 276.2 244.2 222 211 221 236.2 243 257 S5 400.3 380.2 361.6 301 285.5 276 266.2 234.2 212 188 206 226.2 228 242 S6 405.3 385.2 366.6 306 290.5 281 271.2 234.2 212 201 195 176.2 161 178 案例分析 6

数学建模

S7 425.3 405.2 386.6 326 310.5 301 291.2 259.2 237 226 216 198.2 186 162 2. 建立模型

运输总费用可分为两部分：

运输总费用=钢厂到各点的运输费用+铺设费用.

运输费用：若运输点Aj向钢厂Si订购xij单位钢管，则钢管从钢厂Si运到运输点Aj所需的费用为aijxij.由于钢管运到A1必须经过A2，所以可不考虑A1，那么所有钢管从各钢厂运到各运输点上的总费用为：

157xaijj2i1ij.

铺设费用：当钢管从钢厂Si运到点Aj后，钢管就要向运输点Aj的两边AjAj1段和Aj1Aj段运输（铺设）管道.设Aj向AjAj1段铺设的管道长度为yj，则Aj向

AjAj1段的运输费用为0.1(12yj)（万元）；由于相邻运输点

20Aj与Aj1之间的距离为Aj.j1，那么Aj1向AjAj1段铺设的管道长为Aj.j1tj，

tjtj1所对应的铺设费用为用为：

Aj.j1tj1Aj.j1tjAj.j1tjtj120j1147（万元）.所以，主管道上的铺设费

20tj1Aj.j1tj 20 总费用为：fi1Aj.j1tj1Aj.j1tjtjtj1xijaij2020j2j11514 又因为一个钢厂如果承担制造钢管任务，至少需要生产500个单位，钢厂Si在指定期限内最大生产量为si个单位，故500问题可建立如下的非线性规划模型：

xj215ijsi 或xij0 因此本

j215minf(j114tj(tj1)20(Aj.j1tj)(Aj.j11tj)20xijaijj2i11577xijnj j2,3,,15i11515500xs 或x0s.t. ijiijj2j2xij0 i1,,7,j2,,150tjAj.j1案例分析

7

数学建模

3. 模型求解：

由于MATLAB不能直接处理约束条件：500先将此条件改为

xj215ijsi或xij0，我们可

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

minf(j114tj(tj1)20(Aj.j1tj)(Aj.j11tj)20xijaijj2i11577xijnj j2,3,,15i115xs s.t.ij ij2xij0 i1,,7,j2,,150tjAj.j1 用MATLAB求解，分析结果后发现购运方案中钢厂S7的生产量不足500单位，下面我们采用不让钢厂S7生产和要求钢厂S7的产量不小于500个单位两种方法计算：

1）不让钢厂S7生产

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

计算结果：f2 1279664 （万元） （此时每个钢厂的产量都满足条件）. 比较这两种情况，得最优解为， minfmin(f1,f2)f1=1278632（万元） 具体的购运计划如表2：

表2 问题一的订购和调运方案

订购量 A2 S1 S2 S3 S4 S5 S6 S7 800 800 1000 0 1015 1556 0 0 179 139 0 0 0 0 A3 201 11 11 0 358 0 0 A4 133 14 186 0 242 0 0 A5 200 295 0 0 0 0 0 A6 266 0 0 0 0 0 0 A7 0 0 0 0 0 0 0 A8 0 300 664 0 0 0 0 A9 0 0 0 0 0 0 0 A10 0 0 0 0 0 0 0 A11 0 0 0 0 415 351 0 A12 0 0 0 0 0 86 0 A13 0 0 0 0 0 333 0 A14 0 0 0 0 0 621 0 A15 0 0 0 0 0 165 0 案例分析 8

数学建模

案例分析9