2000年数学建模B题钢管订购和运输

钢管订购和运输

摘要

本文根据问题的条件和要求，建立两个模型，两个模型均为单目标非线性规划模

型，并通过求解这两个模型，完整地解决了问题。

由于铁路运输费用函数具有不可加性，不能直接应用现有的最短路算法来求解铁路和公路交通网中任意两点间最小费用路问题。本文采用了一种分步递推算法，巧妙解决了这一问题。

在单目标非线性规划模型中，将管道铺设分为两个过程。先将钢管从钢管厂运到管道与道路交叉口，再从交叉口铺设到管道线上。这样，总的运输费用就化为两个过程的运输费用之和。本模型是以总费用为目标函数的非线性规划模型，利用Lingo 软件，求出问题一的最优解为1278632万元。

对于问题二通过对模型1的灵敏度分析，确定了S5钢厂的销价的变化对购运计划和总费用的影响最大，确定S1钢厂的生产上限的变化对物运计划和总费用的影响最大。 问题三模型的建立原理和问题一的相同，利用Lingo 软件，求得最优解为1407149万元.

关键词：Floyd算法 单目标非线性规划 灵敏度分析

1

问题重述

有7个生产厂，可以生产输送天然气主管道的钢管S1,S2,?S7。要沿着

A1?A2???A15的主管道铺设, 如题图一所示。图中粗线表示铁路，单细线表示公路，双细线表示要铺设的管道(假设沿管道或者原来有公路，或者建有施工公路)，圆圈表示火车站，每段铁路、公路和管道旁的阿拉伯数字表示里程(单位km)。为方便计，1km主管道钢管称为1单位钢管。

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

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

里程(km) 运价(万元)

里程(km) 运价(万元) 501～600 37 601～700 44 701～800 50 801～900 901～1000 55 60 ≤300 20 301～350 23 351～400 26 401～450 29 451～500 32 1000km以上每增加1至100km运价增加5万元。

公路运输费用为1单位钢管每公里0.1万元（不足整公里部分按整公里计算）。 钢管可由铁路、公路运往铺设地点（不只线）。

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

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

2

A1,A2,?,A15是运到点，而是管道全

问题分析

问题一，首先，所有钢管必须运到天然气主管道铺设路线上的节点

A1?A2???A15，然后才能向左或右铺设。必须求出每个钢管厂S1,S2,?S7到每

个节点A1?A2???A15的每单位钢管的最小运输费用。

对最小运费的求解，我们采用Floyd算法,先求出铁路网上钢管厂到铁路上任意两点Vi，同理用Floyd 算Vj的最短路线的长度Lij,用matlab求得Lij对应的铁路单位运费Dij；法求出公路网上的任意两点Vj，Vk 的最短公路路线的长度Ljk，结果乘以0.1得到公路运费D1jk。Cik?min(Dij?D1jk)，j表示所有运输中转点，于是就得到从某钢厂到某铺设点运输单位钢管的最少运输费用。（具体算法及程序见附录）

每个铺设点分别向y,z两个方向展开，通过Lingo编程求出最小铺设费用。运输费用加上购买费用再加上铺设费用就是我们所要求的总费用。

问题二，通过问题一里面Lingo编程运行得出的结果，分析哪个钢厂钢管的销价的变化对购运计划和总费用影响最大，哪个钢厂钢管的产量的上限的变化对购运计划和总费用的影响最大。

问题三，利用同问题一一样的方法，从而可求出某钢厂到某某铺设点运输单位钢管的最少运输费用。（具体算法及程序见附录）

模型的假设与符号说明

1) 基本假设:

○1要铺设的管道侧有公路，可运送所需钢管。

○2钢管在运输中由铁路运转为公路运时不计中转（换车）费用； ○3所需钢管均由Si(i?1,...,7) 钢厂提供； ④假设运送的钢管路途中没有损耗。 2) 符号说明:

Si: 钢厂Si的最大生产能力;

3

pi: 钢厂Si 的出厂钢管单位价格(单位: 万元) ;

d: 公路上一单位钢管的每公里运费(d = 0. 1 万元) ;

e: 铁路上一单位钢管的运费(分段函数见表1) ;

cijbj: 1 单位钢管从钢厂Si运到Aj的最小费用(单位: 万元) ; : 从

Aj 到

Aj?1之间的距离(单位: 千米) ;

xij: 钢厂Si运到

Aj的钢管数;

yj: 运到Zj：运到

AjAj地的钢管向左铺设的数目; 地的钢管向右铺设的数目;

?1，钢厂Si提供钢管；?t0，钢厂Si不提供钢管； i: =?

W : 所求钢管订购、运输的总费用(单位: 万元) ;

模型的建立与求解

问题一的模型：

针对题图一，我们采用Floyd算法，用matlab编程求出单位钢管从Si运输到最小运输费用，具体数据如下表1：

表1 单位钢管从Si运输到

A1A2A3A4A5A6A7A8A9A10A11A12A13A14A15S1 170.7160.3140.298.638.020.53.121.264.292.096.0106.0121.2128.0142.0S2215.7205.3190.2171.6111.095.586.071.2114.2142.0146.0156.0171.2178.0192.0Aj的

Aj的最小运输费用（单位：万元）

S4260.7250.3235.2216.6156.0140.5131.0116.284.262.051.061.076.283.097.0S5255.7245.3225.2206.6146.0130.5121.0111.279.257.033.051.071.273.087.0S6265.7255.3235.2216.6156.0140.5131.0121.284.262.051.045.026.211.028.0S7275.7265.3245.2226.6166.0150.5141.0131.299.277.066.056.038.226.02.0 S3230.7220.3200.2181.6121.0105.596.086.248.282.086.096.0111.2118.0132.0对表1的数据进行分析，我们得到一个非线性规划模型：

4

目标函数是总费用W , 它包含三项: 钢管出厂总价Q , 运输费P , 及铺设费T. 即

W = Q + P + T

Q???pi?xiji?1j?1715其中 ，

P???cij?xiji?1j?1715 ，

铺设费T可以如下来确定：

1?d?2?...?d?yj?d用为d?Aj开始从左右两个方向铺设，yj与zj单位长钢管的费与d(1?zj)zj2(1?yj)yj2

故 T?d?j?115??1?yj?yj?1?zj?zj???? 22??????1?yj?yj?1?zj?zj???? 22????目标函数为：

minW???pi?xij???cij?xij?d?i?1j?1i?1j?1j?171571515约束条件为:

500?ti??xij?si?tij?115① 生产能力的限制:

(t ，(i?1,...,7) i?0或1)

15) ② 运到Aj的钢管用完: ?xij?yj?zj，(j?1,...,i?1714) ③Aj与Aj-1之间的钢管: zj?yj?1?bj，(j?1,...,15) ④ 变量非负性限制:xij?0,yj?0,zj?0, (i?1,...,7,j?1,...,⑤ 运到模型一

Aj的钢管整数限制:

xij?N

minW???pi?xij???cij?xij?d?i?1j?1i?1j?1j?171571515??1?yj?yj?1?zj?zj???? 22????s.t.

500?ti??xij?si?tij?115

(t ，(i?1,...,7) i?0或1)

5

15) ?xij?yj?zj，(j?1,...,i?1714) zj?yj?1?bj，(j?1,..., y1=0 , z15=0

15) xij?0,yj?0,zj?0, (i?1,...,7,j?1,...,ti=0或1 (i=1,..,7) d=0.05;

根据模型二编写Lingo程序，程序运行后，得到最优最小费用为W?1282142万元。

问题二的模型

对模型1的灵敏度分析

（1）确定哪个钢厂的销价的变化对购运计划和总费用的影响最大

我们假设该钢厂的销价变化在?10%pi万元以内，这是较为合理的，将目标函数的w表示为pi的函数：

w=f（p1,p2,...,p7),?w??f?p1.?p1??f?p2.?p2?...? ?f?p7.?p7因此在销价的变化量相同时，

?f越大，则pi的变化对w的变化影响越大。 ?pi?f?2000单位是最大的，所以S6的销价变化 ?p6由模型Obj1计算得到的数据可以知道

对购运计算和总费用的影响最大，我们可以通过简单的分析来证明：由于S6提供的数量最 大，销价只要很小变化的，就会引起总费用的很大变化，同时，当价格越来越高，由于P6和

?x6ji?115互为消长的关系，当S6越来越小，它在总需求中占的份额减少，影响减弱，S6下降的速度也将放慢。

除了销价的升高，我们还必须考虑销价的降低，此时应尽量满足提供量最少的点S5，当价格越来越低，由互为消长的关系，S5点的提供量将增加，它在总需求中占的份额增加，影响增强，对于S5上升的速度将放慢。

2）确定哪个钢厂的生产上限的变化对物运计划和总费用的影响最大

由于S1是A1到A8的最优首选，因此若S1与其他Si同时扩大相同的?S容量，则S1 会更优，所以推断S1应为影响最大者。由最小费用矩阵C可以知道，Ai(i=1,…,8)所需的 钢管量最好都能由S1提供，则此时S1达到最大需求量，在模型Obj1的条件下，S1为2536

6

单位，而S1的上限为800单位，考虑到实际钢厂的投入与产出，在很短的时期内生产要达

到原来的3倍，不符合实际意义，所以考虑S1在10%范围内变化。同理对于A0点，最优为S3全部提供，即S3应提供634单位，对于A12,A13,A14,A15,由S6全部提供为最优，即S6应提供1205单位，A11,A10由S5全部提供为最优，即S5应提供796单位。

利用计算机模拟，得到5个供货钢厂分别扩建1%，2%，4%，6%，8%，10%时的成本的增长率，见表 。可以看出，相同的?S下A1产生的增长率最大，符合上述分析。一旦工厂扩建范围超过最大需求量，则不再会使目标函数优化，则此时增长率为0。即是上图中S5,S6的情况。而对于S1，一旦S1>2536,则其增长率也为0。（S1的数字结果见表 2 ）

△表2 某个Si在变化?S的情况下目标函数减小量及减小的比率 △s S1 △z (万元) 872 1744 3488 5232 6976 8720 S2 S3 S5 S6 ?z z(%) 0.068 0.136 0.272 0.408 0.544 0.685 △z （万元) 328 656 1312 1968 2624 3280 ?z z(%) 0.025 0.051 0.102 0.153 0.204 0.256 △z （万元) 310 620 1240 1860 2480 3100 ?z z(%) 0.024 0.048 0.096 0.145 0.193 0.242 △z (万元) 0 0 0 0 0 0 ?z z(%) 0 0 0 0 0 0 △z (万元) 0 0 0 0 0 0 ?z z(%) 0 0 0 0 0 0 1% 2% 4% 6% 8% 10%

问题三的模型

题图二为树形图，采用Floyd算法，用matlab编程求出单位钢管从Si运输到最小运输费用，具体数据如下表2：

表2 单位钢管从Si运输到

A1A2A3A4A5A6A7A8A9A10A11A12A13A14A15S1 170.7160.3140.298.638.020.53.121.264.292.096.0106.0121.2128.0142.0S2215.7205.3190.2171.6111.095.586.071.2114.2142.0146.0156.0171.2178.0192.0Aj的

Aj的最小运输费用 （单位：万元）

S3230.7220.3200.2181.6121.0105.596.086.248.282.086.096.0111.2118.0132.0S4260.7250.3235.2216.6156.0140.5131.0116.284.262.051.061.076.283.097.0S5255.7245.3225.2206.6146.0130.5121.0111.279.257.033.051.071.273.087.0S6265.7255.3235.2216.6156.0140.5131.0121.284.262.051.045.026.211.028.0S7275.7265.3245.2226.6166.0150.5141.0131.299.277.066.056.038.226.02.0 ，

Rj由于树形图的出现，则某些管道处会出现多支路。 则模型一中模型的

7

Lj不

再适用，此时可考虑多增加一些支路变量，并增加约束，在目标函数中增加相应的铺设费。 目标函数：

minW???pi?xij???cij?xij?

i?1j?1ji?1j?1721721?15d????j?2?1?y?y2j??j?114?1?z?zjj2m（）m11（m11?1）m17(m17?1)?9m9?1????222??

约束条件：

500?ti??xij?si?tij?1721① 生产能力的限制: ② 运到

(i?1,...,7)

(ti?0或1)

Aj且j?9,11,17) 的钢管用完:?xij?yj?zj (j?1,...,21i?1 ?xij?yj?zj?mj (j?9,11,17)

i?17③

Aj与

Aj?114) 之间的钢管:zj?yj?1?bj (j?1,...,m9?y16?42 m11?m17?10 y17?y18?130 z17?y19?190 z19?y20?260 z20?y21?100

④ 变量非负性限制: xij?0,yj?0,zj?0,mj?0, (i?1,...,7,j?1,...,21) ⑤ 运到模型二

Aj的钢管整数限制:

xij?N

minW???pi?xij???cij?xij?

i?1j?1i?1j?1721721?15d????j?2?1?yj?yj2??j?114?1?zj?zj2m（）m11（m11?1）m17(m17?1)?9m9?1????222??

s.t.

500?ti??xij?si?ti(i?1,..,7)

j?1218

且j?9,11,17) ?xij?yj?zj (j?1,...,21i?17 ?xij?yj?zj?mj (j?9,11,17)

i?1714) zj?yj?1?bj (j?1,...,m9?y16?42 m11?m17?10 y17?y18?130 z17?y19?190 z19?y20?260 z20?y21?100 xij?0,yj?0,zj?0,mj?0, (i?1,...,7,j?1,...,21)

ti?0或1(i=1,..,7) d=0.05;

根据模型二编写Lingo程序，程序运行后，得到最优最小费用为W?1406330万元。

模型优缺点

1. 本文先从简单的角度着手建立模型，采用Floyd算法，简化运输网络。过程严谨，理论性强，逻辑严密，而且易于理解。

2. 在计算最短路径时，我们采用Floyd算法，相比与Dijkstra算法，减少了大量的重复计算，提高了工作效率。

3. 本文大量运用了计算机程序，所有数据均由计算机处理，故误差由计算机精度产生，模型据有良好的稳定性。

参考文献：

[1] 谢金星,薛毅.《优化建模与LINGO/LINGO软件》.北京：清华大学出版社,2005 [2] 宗容,施继红,尉洪,李海燕.《数学实验与数学建模》.云南：云南大学出版社，2009 [3]陆维新，林皓，陈晓东，《订购与运输钢管的最优方案》.成都：四川大学，610064

9

附录

附录1

Floyd算法函数在matlab下的M函数文件如下： function [D,path]=floyd(a) n=size(a,1);

D=a;path=zeros(n,n); for i=1:n for j=1:n if D(i,j)~=inf path(i,j)=j; end end end for k=1:n for i=1:n for j=1:n

if D(i,k)+D(k,j)

10

本文来源：https://www.bwwdw.com/article/xrwt.html