钢管订购与运输建模论文

承 诺 书

我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.

我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。

我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。

我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。

我们参赛选择的题号是（从A/B/C/D中选择一项填写）： B 我们的参赛报名号为（如果赛区设置报名号的话）： 所属学校（请填写完整的全名）： 参赛队员 (打印并签名) ：1. 指导教师或指导教师组负责人 (打印并签名)：

日期： 2012 年 8 月 12 日

赛区评阅编号（由赛区组委会评阅前进行编号）：

2011高教社杯全国大学生数学建模竞赛

编 号 专 用 页

评 阅 人 评 分 备 注 赛区评阅编号（由赛区组委会评阅前进行编号）：

赛区评阅记录（可供赛区评阅时使用）：

全国统一编号（由赛区组委会送交全国前编号）：

全国评阅编号（由全国组委会评阅前进行编号）：

钢管订购和运输

摘要

本文要解决三个问题，其中问题二和问题三是建立在问题一的基础上的，所以我们首要的问题是解决问题一。而问题一是一个非线性的整数规划模型，我们需要写出总的最小花费的min函数以及约束条件。

首先，问题一的min函数比较复杂，我们可以分成三步进行：钢管的出厂花费，钢管的道路运输费用，钢管的铺设运输费用。而道路运输费用又可以分为铁路运输费用和公路运输费用。对上述函数分布求出其花费后求和即是最小花费的min函数。然后是列出约束条件，利用lingo求得问题一中的最小花费为：1278632万元。

在问题一的基础上，我们开始分析问题二中，各钢厂钢管的销售价格和产量上限改变对订购计划的影响。分别上调和下调各钢厂的销售价格一万元后，所得的最小花费与问题一中的最小花费进行比较，并对花费差价绝对值求和，比较各厂对

问题的重述

要铺设一条A1A2A15的输送天然气的主管道,经筛选后可以生产这种主

管道钢管的钢厂有S1,S2,S7。

一个钢厂如果承担制造这种钢管，至少需要生产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

钢管可由铁路、公路从钢厂运往铺设地点（不只是运到点A1,A2,,A15，而是管道全线）。1单位钢管公路运费为0.1万元每公里，铁路运费为一分段函数，具体如下： 301～351～401～451～501～601～701～801～901～里程≤300

350 400 450 500 600 700 800 900 1000 (km)

运价

20 23 26 29 32 37 44 50 55 60

(万元) 问题： （1）制定一个主管道钢管的订购和运输计划，使总费用最小（给出总费用)。

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

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

解决问题（1），我们可以直接得出A1A15从S1S7各厂的的订购数量和运输费用

的最优解，即最小花费的具体方案。解决问题（2），我们可以得出各个钢厂销售价格及产量上限的变化对购运计划的影响。解决问题（3），我们可以完成对树形管道的运购计划制定的推广。

模型的假设

1.假设沿管道或者原来有公路，或者建有施工公路;

2.在选择路线时仅考虑运输花费的多少而不考虑运输的路况等其他因素的影响； 3.在计算总费用时，仅考虑出厂及运输费用，不考虑其他费用； 4.在铺设运输时，每公里卸1单位的钢管，且假设到终点后才卸下；

5.钢厂因各种原因导致生产上限的变化时，变化幅度不超过本身的10%。

符号系统

符号

Si si Pi

Aj

说明

第i个钢厂，i1,2,7

7

7

第i个钢厂的最大产量，i1,2,第i个钢厂1单位钢管的出厂价格，i1,2,待铺设管道上的第j个节点，j1,2,15 铁路与公路第i个分界点，i1,2,17

bi

aij xij

Si钢厂至Aj节点1单位钢管的出厂运输费用，i1,2,Aj节点向Si钢厂订购的钢管数量，i1,2,7，j1,2,15

7，j1,2,15

Ajj1 Ajj1

dj nj W

Aj节点向左铺设的距离，j2,15 Aj节点向右铺设的距离，j1,2,14 Aj节点与Aj1节点的距离，j1,2,14 Aj节点向各钢厂订购的总数，j1,2,15

出厂道路运输铺设运输总花费

ti0or1,ti1时Si提供钢管，ti0时Si不提供钢管，i1,2,ti

 aij7 7，

树形图中Si钢厂至Aj节点1单位钢管的出厂运输费用，i1,2,j1,2,21

 xij树形图中Aj节点向Si钢厂订购的钢管数量，i1,2,节点Aj向节点Ak铺设的距离，j1,2,7，j1,2,21

21

Ajk

nj

W

21，k1,2,21

Aj节点向各钢厂订购的总数，j1,2,树形图出厂道路运输铺设运输总花费

模型的分析与求解

我们有三个问题需要解决，而第二个问题是建立在第一个问题解决的情况下，第三

个问题又是第一个问题的推广，所以解决第一个问题是解决所有问题的关键。

第一个问题需要我们找出钢管的最优订购及运输计划，使钢管铺设的花费最小。为简化分析，我们可以将铺设花费分成三部分：出厂费用（钢管销售价格），道路运输费用，铺设运输费用三部分。首先，我们分析1单位钢管的花费。

1单位钢管的出厂费用

我们可以直接从题中得到1单位钢管各钢厂的出厂费用，单位：万元。

表一 1单位钢管各钢厂的出厂费用 厂家Si 出厂价格pi

1单位钢管的道路运输费用

钢管的道路运输费用可以分为铁路运输费用和公路运输费用，而铁路运输费用为一分段函数，故和公路运输费用分别计算。

为分别计算铁路与公路的运输费用，我们增设公路与铁路分界点bi，共17个，具体分布见下图。

1 160

2 155

3 155

4 160

5 155

6 150

7 160

图一 铁路与公路分界点具体分布图

铁路运输的费用和运输距离有关，首先计算从Si到铁路与公路交点bj的最短路径。把上图的铁路路线视作图论中的图，首先给所有的节点进行标号，然后以节点之间的距离作为系数写出图对应的稀疏矩阵。通过调用matlab函数graphshortestpath()计算出各个钢厂到各个公路和铁路分界点的最短距离，计算最短距离使用Dijkstra算法。得到最短路径，最短路径结果详见附录。再将结果代入铁路运费的分段函数中，就可以得到对应的最小铁路运输费用，单位：万元。

表二 从Si到铁路与公路交点bj的最短路径所花费用

b1 S1 S2 S3 S4 S5 S6 S7 b2

b3

b4

b5

b6

b7

b8 b10

b9

b11

b12 b13

b14 b15

b16

b17

160 140 80 37 20 20 0 20 60 85 95 105 115 130 125 140 140 205 190 125 110 95 85 85 70 110 135 145 155 165 180 175 190 190 220 200 140 120 105 95 95 85 44 75 85 95 105 115 115 130 130 250 235 170 155 140 130 130 115 80 55 50 60 70 80 80 95 95 245 225 165 145 130 120 120 110 75 50 32 50 65 75 70 85 90 255 235 175 155 140 130 130 120 80 55 50 44 20 0 20 26 26 265 245 185 165 150 140 140 130 95 70 65 55 32 26 23 20 0 再考虑公路的运输费用，1单位钢管的最下铁路运输费用加上公路运输费用，用图表示成以下形式：以S1为例。

将公路长度量化成单位钢材的运输费用，加上各钢厂到公路铁路节点处最短路径费用，可得各钢厂到各节点的最少运费，用1单位钢管的道路运输费用表示。

计算最短最小费用的方法和计算最短路径的方法相同，把如上所示的运费图用稀疏矩阵表示，节点之间的价格作为系数。考虑到节点的重合情况（比如在上图中，钢厂S1和节点b7重合），我们约定其为两个节点，其间的运费规定为0。对于不直接相连的节点，在用矩阵表示的时候规定运费为无穷大（inf）。在输入到matlab函数

graphshortestpath()时，由于函数默认系数为零表示不相关的点，所以我们把得到的矩阵中所有的inf换成0，把所有的0换成eps（其值为2.22041016），计算出各个钢厂到各个节点的最小运费，最小运费的表格详见附录。

1单位钢管的订购道路运输费用

上述结果加上对应的销售价格可以得出购买和运输1单位钢管的最小费用。即得到1单位钢管从钢厂Si运输到Aj所需最小费用，如下表所示。 1单位钢管从出厂到铺设节点的最小花费表，单位：万元。

表三 1单位钢管从出厂到铺设节点的最小花费 S1 S2 S3 S4 S5 A1 330.7 370.7 385.7 420.7 410.7 A2 320.3 360.3 375.3 410.3 400.3 A3 300.2 345.2 355.2 395.2 380.2 A4 258.6 326.6 336.6 376.6 361.6 A5 198 266 276 316 301 A6 180.5 250.5 260.5 300.5 285.5 A7 163.1 241 251 291 276 A8 181.2 226.2 241.2 276.2 266.2 A9 224.2 269.2 203.2 244.2 234.2 A10 252 297 237 222 212 A11 256 301 241 211 188 A12 266 311 251 221 206 S6 S7 415.7

405.3 385.2 366.6 306 290.5 281 271.2 234.2 212 201 195 435.7 425.3 405.2 386.6 326 310.5 301 291.2 259.2 237 226 216 A13 A14 A15

281.2 288 302 326.2 333 347 266.2 273 287 236.2 243 257 226.2 228 242 176.2 161 178 198.2 186 162 1单位钢管从钢厂Si运输到节点Aj所需最小费用（包含出厂费用及道路运输费用）为aij，即是节点Aj向钢厂Si订购钢材出厂运输费的系数矩阵。钢管的出厂运输费用为

ai1j1715ijxij，及除铺设运输费用的其他费用之和。

各节点的铺设运输费用

将钢材运到各个节点后，我们最后考虑的就是把钢材运输到施工点进行铺设运输。而一个节点既可以往左铺设又可以往右铺设（端节点除外）。

节点Aj向左铺设的距离为Ajj1，向右铺设的距离为Ajj1，节点Aj从各个钢厂订购的总数为nj，则有njAjj1Ajj1。又AjAj1的距离为dj，则有Ajj1Aj1jdj。

从Aj向Aj1铺设的距离为Ajj1，则其铺设运费为：

(123Ajj1)0.1Ajj1(Ajj11)20

从Aj1向Aj铺设的距离为Aj1j，则其铺设运费为：

(123Aj1j)0.1Aj1j(Aj1j1)20

且有Ajj1Aj1jdj的关系。 那么钢管的铺设运输费用为：

Ajj1(Ajj11)Aj1j(Aj1j1)

2020j114总费用的计算

总费用包括出厂运输费及铺设运输费，总花费为：

A(A1)Aj1j(Aj1j1)Waijxijjj1jj1

2020i1j1j171514

又一个钢厂承担制造任务的最小量为500单位，而钢厂Si在指定期限内最大生产量为si，所以有约束500xijsi或者不承担xij0。综上，该问题可以转化为以下非

j1j11515线性规划模型：

A(A1)Aj1j(Aj1j1)minWaijxijjj1jj1

2020i1j1j1715147xijnjj1,2,3,15i11515500xijsiorxij0s..tj1j1xij0i1,2,,7j1,2,,15Ajj1Aj1jdjandAjj10andAj1j0

上述约束中，

500xijsiorxij0j1j11515在lingo的实际运用中比较困难，我们引入t，

i将上述约束简化成，

500tixijsitij115，t0or1。用lingo代码求出最小花费为

i1278632万元，具体的各厂运到个铺设点的结果如下，具体代码详见附录。

表四 各节点向钢厂的订购方案

S1 A1

S2 S3 S4 S5 S6 S7 A2 A3 A4 A5 A6 A7 A8 A9 A10 A11 A12 A13 A14 A15

总和

0 0 0 0 336 199 265 0 0 0 0 0 0 0 0 800 0 179 0 321 0 0 0 300 0 0 0 0 0 0 0 800 0 0 0 146 188 0 0 0 0 666 0 0 0 0 0 1000 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 509 0 92 0 0 0 0 350 415 0 0 0 0 1366 0 0 0 0 0 0 0 0 0 0 0 86 333 621 165 1205 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

各钢厂钢管销价的变化对购运计划的影响

针对问题二中销价对购运计划的影响，我们把每个钢厂的价格上调和降低一万元，求得结果与原来最小结果的差进行比较，运算的结果做成表格如图所示：

表五 各钢厂钢管销价的变化对购运计划 价格上涨一单位最小花费增幅 S1 S2 S3 S4 S5 S6 S7 800 S1 800 S2 1000 0 1008 价格下降一单位最小花费增幅 S3 S4 S5 -1000 0 -1369 两个增幅绝对值之和的平均值 S3 S4 S5 1000 0 1188.5 1203 S6 0 S7 -800 S1 -800 S2 -1563 S6 0 S7 800 800 1383 0 上表中，在改变相同价格的情况下，钢厂S6的销价变化对最小花费的结果影响最大。各钢厂钢管销价的变化对购运计划的影响

对于产量上限的分析，我们同上述销价方法一样，增加或减少原产量上限的10%，求得结果与原来最小结果的差进行比较，运算的结果做成表格如图所示：

表六 钢厂钢管销价的变化对购运计划的影响 生产上限增加10%最小花费增幅 S1 S2 S3 S4 S5 S6 S7 -8240 S1 -2800 S2 -2500 0 0 生产上限降低10%最小花费增幅 S3 S4 S5 2500 0 0 两个增幅绝对值之和的平均值 S3 S4 S5 2500 0 0 0 S6 0 S7 8240 S1 2800 S2 0 S6 0 S7 8240 2800 0 0 上表中，在生产上限改变相同幅度的情况下，钢厂S1的生产上限的变化对最小花费结果影响最大。

问题三树形图的推广

对于第三个问题,我们可以采用与第一个问题相同的方法。首先计算出钢厂到铁路与公路分界点（共18个，具体的标示详见附录。）的最短距离，然后再计算出1单位钢管从各钢厂到各节点（管道端点）的最小运输费用。

在第一问的基础上，计算铁路最短运输距离时，我们只需多加一个铁路与公路的分界点即可，计算最小运费的时候只需多添加6个节点。所以可以按照相同的方法利用matlab求解。

计算所得1单位钢管从Si运至bj的最短铁路运输费用，及1单位钢管从Si运至Aj的最少运输费用如下表所示，单位：万元

表六 1单位钢管从Si运至bj的最短铁路运输费用

b1 S1 S2 S3 S4 S5 S6 S7 b2

b3

b4

b5

b6

b7

b8 b10

b9

b11

b12 b13

b14 b15

b16

b18

b17

160 140 80 37 20 20 0 20 60 85 95 105 100 115 130 125 140 140 205 190 125 110 95 85 85 70 110 135 145 155 150 165 180 175 190 190 220 200 140 120 105 95 95 85 44 75 85 95 90 105 115 115 130 130 250 235 170 155 140 130 130 115 80 55 50 60 55 70 80 80 95 95 245 225 165 145 130 120 120 110 75 50 32 50 50 65 75 70 85 90 255 235 175 155 140 130 130 120 80 55 50 44 37 20 0 20 26 26 265 245 185 165 150 140 140 130 95 70 65 55 0 32 26 23 20 0 表七 1单位钢管从Si运至Aj的最少运输费用

A1

S1 S2 S3 S4 S5 S6 S7 A2 A3 A4 A5 A6 A7 A8 A9 A10 A11 A12 A13 A14 A15

A16

170.7 160.3 140.2 98.6 38 20.5 3.1 21.2 .2 92 96 106 121.2 121 142 60 215.7 205.3 190.2 171.6 111 95.5 86 71.2 114.2 142 146 156 171.2 171 192 110 230.7 220.3 200.2 181.6 121 105.5 96 86.2 48.2 82 86 96 111.2 111 132 44 260.7 250.3 235.2 216.6 156 140.5 131 116.2 84.2 62 51 61 76.2 76 97 80 255.7 245.3 225.2 206.6 146 130.5 121 111.2 79.2 57 33 51 .2 66 87 75 265.7 255.3 235.2 216.6 156 138.5 121.1 121.2 84.2 54 24 43 26.2 11 28 80 275.7 265.3 245.2 206.6 146 128.5 111.1 129.2 92 44 14 33 38.2 21 2 93.2

A17 A18 A19 A20 A21

95 100 105 115 110 145 150 155 165 160 85 90 95 105 100 50 55 60 70 65 32 45 50 58 55 23 10 42 20 0 13 0 32 32 10 表示节点Aj向钢厂Si订购的钢管数量，上表为1单位钢管的出厂运树形图中，xij表示，则钢管的出厂运输费用为aijxij。 输费用aiji1j1721最后考虑树形图的铺设运输费用，双向铺设的节点和问题一种的计算完全一样，三向铺设的点有A9，A11，A17三个节点，显然只要特殊考虑满足铺设要求即可。 所以钢管的铺设运输费用为：

Ajj1(Ajj11)Aj1j(Aj1j1)Ajj1(Ajj11)Aj1j(Aj1j1)A916(A9161)2020202020j1j17,19,20A(A916A(A1)A1117(A1)A1711(A1)A1719(A1)A1917(A1)1)916169169111717111719191720202020202014

xij，则有，钢管的总花费为： 再加上前面的钢管的出厂运输费aiji1j1721A(A1)Aj1j(Aj1j1)Ajj1(Ajj11)Aj1j(Aj1j1)xijjj1jj1Waij20202020i1j1j1j17,19,20A916A(A916A(A1)A1117(A1)A1711(A1)A1719(A1)(A9161)1)916169169111717111719202020202020A1917(A19171)2072114

最后我们得到树形图的非线性规划模型：

Ajj1(Ajj11)Aj1j(Aj1j1)Ajj1(Ajj11)Aj1j(Aj1j1)xijminWaij20202020i1j1j1j17,19,20A916A(A916A(A1)A1117(A1)A1711(A1)A1719(A1)(A9161)1)916169169111717111719202020202020A1917(A19171)2072114

7xijnjj1,2,3,21i12121500xijsiorxij0j1j1x0i1,2,,7j1,2,,21ijAjj1Aj1jdj(j1,2,14,17,19,20)d15A9,16A16,9d16A11,17A17,11dAA17,1919,1718Aj,j10Aj1,j0

参考文献 附录

附录一

最短路径的matlab求解程序（注：要在相应目录下运行。）： clear all; clc;

load tu_tielu_sparse.mat; S=[8 9 11 15 17 22 24];

B=[1 3 4 5 6 7 8 10 12 13 16 18 20 22 21 23 24]; dist_7=zeros(7,17); for i=1:7

[dist,path]=graphshortestpath(tu_tielu_sparse,S(i),B) dist_7(i,:)=dist; end

附录二

从Si到铁路与公路交点bj的最短路径 S1 S2 S3 S4 S5 A1 2902

2532

1302

521

215

A2 3900

3530

2300

1923

1617

A3 4110 3740 2510 2133 1827 A4 4800 4430 3200 2823 2517 A5 4660 4290 3060 2683 2377 A6 4820 4450 3220 2843 2537 A7 5070 4700 3470 3093 2787 A8 2902 2532 1302 521 215 A9 3900 3530 2300 1923 1617 A10 4110 3740 2510 2133 1827 A11 4800 4430 3200 2823 2517 A12 4660 4290 3060 2683 2377 A13 4820 4450 3220 2843 2537 A14 5070 4700 3470 3093 2787 A15

2902 2532 1302 521 215

附录三

最小道路运费的matlab函数（注：要在相应目录下运行。）： clear all; clc;

load expense_tielu; load yunshu_jiage;

expense_suoyou=zeros(7,15); for i=1:7

jiage(1,2:18)=expense_tielu(i,:); jiage(2:18,1)=expense_tielu(i,:)'; jiage_sparse=sparse(jiage); B = [19:1:33];

expense=graphshortestpath(jiage_sparse,1,B); expense_suoyou(i,:)=expense; end;

附录四

单位钢管从钢厂Si运输到Aj所需最小道路运输费用 S1 S2 S3 S4 S5 A1

170.7

215.7

230.7

260.7

255.7

S6 S7 20

0

1422

1402

1632 1612 2322 2302 2182 2162 2342 2322 2592 2572 20 0 1422 1402 1632 1612 2322 2302 2182 2162 2342 2322 2592 2572 20 0

S6 S7 265.7

275.7

A2 160.3 A3 140.2 A4 98.6 A5 38 A6 20.5 A7 3.1 A8 21.2 A9 .2 A10 92 A11 96 A12 106 A13 121.2 A14 128 A15 142

附录五

运算的lingo代码

model: sets:

205.3 190.2 171.6 111 95.5 86 71.2 114.2 142 146 156 171.2 178 192 220.3 200.2 181.6 121 105.5 96 86.2 48.2 82 86 96 111.2 118 132 250.3 235.2 216.6 156 140.5 131 116.2 84.2 62 51 61 76.2 83 97 245.3 225.2 206.6 146 130.5 121 111.2 79.2 57 33 51 71.2 73 87 255.3 235.2 216.6 156 140.5 131 121.2 84.2 62 51 45 26.2 11 28 265.3 245.2 226.6 166 150.5 141 131.2 99.2 77 66 56 38.2 26 2

gangchang/S1..S7/:s,t; pushedian/A1..A15/:y,z,d; links(gangchang,pushedian):a,x; endsets data:

s=800 800 1000 2000 2000 2000 3000; //表示每个钢厂生产的上限

d=104,301,750,606,194,205,201,680,480,300,220,210,420,500,0; //相邻铺设点之间的距离，最 后一个用0代替 a=330.7 320.3 300.2 258.6 198 180.5 163.1 181.2 224.2 252 256 266 281.2 288 302 370.7 360.3 345.2 326.6 266 250.5 241.0 226.2 269.2 297 301 311 326.2 333 347 385.7 375.3 355.2 336.6 276 260.5 251.0 241.2 203.2 237 241 251 266.2 273 287 420.7 410.3 395.2 376.6 316 300.5 291.0 276.2 244.2 222 211 221 236.2 243 257 410.7 400.3 380.2 361.6 301 285.5 276.0 266.2 234.2 212 188 206 226.2 228 242 415.7 405.3 385.2 366.6 306 290.5 281.0 271.2 234.2 212 201 195 176.2 161 178 435.7 425.3 405.2 386.6 326 310.5 301.0 291.2 259.2 237 226 216 198.2 186 162;

enddata

min=@sum(links(i,j):a(i,j)*x(i,j))+0.05*@sum(pushedian(j):y(j)^2+y(j)+z(j)^2+z(j)); //最小花费函数

@for(gangchang(i):@sum(pushedian(j):x(i,j))>=500*t(i); @sum(pushedian(j):x(i,j))<=s(i)*t(i);

@bin(t(i))); //每个钢厂生产钢的总量满足的条件 @for(pushedian(j):@sum(gangchang(i):x(i,j))=y(j)+z(j))

//y(j),z(j)相当于符号系统里的Ajj1和Ajj1 @for(pushedian(j)|j#NE#15:d(j)=z(j)+y(j+1)); z(15)=0;y(1)=0;

@for(gangchang(i):@for(pushedian(j):@gin(x(i,j)))); End