钢管订购和运输问题.docx

钢管订购和运输问题
摘要：我们利用Floyd算法求出铁路网和公路网各点间最短路线，然后转化成最少运输，去掉了铁路和公路的性质，使运输网络变成一张供需运输价格表，然后建立了一个以总费用为目标函数的非线性规划模型，利用Lingo 软件，求出问题一的最优解为1278632万元。通过对问题一中lingo运行结果的分析，我们得出S5钢厂钢管的销价的变化对购运计划和总费用影响最大，S1钢厂钢管的产量的上限的变化对购运计划和总费用的影响最大。问题三模型的建立原理和问题一的相同，利用Lingo 软件，求得最优解为1407149万元.
关键词：非线性方程组 Floyd 算法 灵敏度

1. 问题重述
要铺设一条的输送天然气的主管道, 如图一所示(见下页)。经筛选后可以生产这种主管道钢管的钢厂有。图中粗线表示铁路，单细线表示公路，双细线表示要铺设的管道(假设沿管道或者原来有公路，或者建有施工公路)，圆圈表示火车站，每段铁路、公路和管道旁的阿拉伯数字表示里程(单位km)。
为方便计，1km主管道钢管称为1单位钢管。
一个钢厂如果承担制造这种钢管，至少需要生产500个单位。钢厂在指定期限内能生产该钢管的最大数量为个单位，钢管出厂销价1单位钢管为万元，如下表：

1
2
3
4
5
6
7

800
800
1000
2000
2000
2000
3000

160
155
155
160
155
150
160

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

里程(km)
≤300
301～350
351～400
401～450
451～500
运价(万元)
20
23
26
29
32

里程(km)
501～600
601～700
701～800
801～900
901～1000
运价(万元)
37
44
50
55
60

1000km以上每增加1至100km运价增加5万元。
公路运输费用为1单位钢管每公里0.1万元（不足整公里部分按整公里计算）。
钢管可由铁路、公路运往铺设地点（不只是运到点，而是管道全线）。
（1）请制定一个主管道钢管的订购和运输计划，使总费用最小（给出总费用)。
（2）请就（1）的模型分析：哪个钢厂钢管的销价的变化对购运计划和总费用影响最大，哪个钢厂钢管的产量的上限的变化对购运计划和总费用的影响最大，并给出相应的数字结果。
（3）如果要铺设的管道不是一条线，而是一个树形图，铁路、公路和管道构成网络，请就这种更一般的情形给出一种解决办法，并对图二按（1）的要求给出模型和结果。

2. 模型假设
（1） 只考虑订购费用和运输费用，不考虑装卸等其它费用。
（2） 在运输和铺设过程中无能量损耗。
（3） 钢管单价与订购量、订购次数、订购日期无关。
（4） 沿管道或者原来有公路或者建有施工公路。
3.符号说明
: 钢厂的最大生产能力;
: 钢厂 的出厂钢管单位价格(单位: 万元) ;
: 公路上一单位钢管的每公里运费( = 0. 1 万元) ;
：铁路网上两点间的单位钢管最少运输费用；
：题图一公路网上两点间的单位钢管最少运输费用；
：题图二公路网上两点间的单位钢管最少运输费用；
: 铁路上一单位钢管的运费 ;
: 1 单位钢管从钢厂运到的最小费用(单位: 万元) ;
: 从 到之间的距离(单位: 千米) ;

4. 问题分析
(一) 问题1的分析
问题一属于运输类求最短路的问题。 题目要求七个钢厂生产的钢管运输到十五个铺设点，又由于运输的时候，运输费用不是简单的路程长短决定的，因此要先考虑最短的运输到铺设点的最小费用，我们的模型建立目标函数，建立起约束条件，运用
(二) 问题2的分析
问题二是对问题一中的模型进行灵敏度分析。是讨论钢厂钢管的销价的变化和钢厂钢管的产量的上限的变化对购运计划和总费用的影响，同时判别哪家钢厂在这两方面发生的变化对购运计划和总费用的影响最大，使得钢管销售价和钢管生产上限在发生变化时，能够利用原有模型进行判断，是否需要对购运计划进行修改，以满足新情况下的最优。
(三) 问题3的分析
问题三是对问题一的一个扩展。如铺设的管道是一个树形图，铁路、公路和管道构成网络对于题图二，我们可以延用问题一里面的思想，在题图一的基础上多几条铺设路段，即多几个函数。

对最小运费的求解，我们采用Floyd算法。先求出铁路网上钢管厂到铁路上任意两点，的最短路线的长度,用matlab求得对应的铁路单位运费；同理用Floyd 算法求出公路网上的任意两点， 的最短公路路线的长度，结果乘以0.1得到公路运费。，j表示所有运输中转点，于是就得到从某钢厂到某铺设点运输单位钢管的最少运输费用。
每个铺设点分别向两个方向展开，通过Lingo编程求出最小铺设费用。运输费用加上购买费用再加上铺设费用就是我们所要求的总费用。
问题二，通过问题一里面Lingo编程运行得出的结果，分析哪个钢厂钢管的销价的变化对购运计划和总费用影响最大，哪个钢厂钢管的产量的上限的变化对购运计划和总费用的影响最大。
问题三，如铺设的管道是一个树形图，铁路、公路和管道构成网络对于题图二，我们可以延用问题一里面的思想，在题图一的基础上多几条铺设路段，9，11，17节点的铺设方向变为 三个方向，其他不变。
5. 模型的建立与求解
针对题图一，我们采用Floyd算法，用matlab编程求出单位钢管从运输到的最小运输费用，具体数据如下表1：
表1 单位钢管从运输到的最小运输费用（单位：万元）

对表1的数据进行分析，我们得到一个非线性规划模型：
目标函数是总费用W , 它包含三项: 钢管出厂总价Q , 运输费P , 及铺设费T. 即
W = Q + P + T
其中 ， ，

约束条件为:
① 生产能力的限制:
② 运到的钢管用完:
③ 与之间的钢管:
④ 变量非负性限制: ,
⑤ 运到的钢管整数限制:
运用数学软件Lingo编程求解
最优最小费用万元
问题二的模型
通过分析问题一中关于销价的约束，Lingo运行后得到的结果得

影子价格表示在最优解下“资源”增加一个单位时“效益”的增量，即每个钢厂销售价格每减少一万元，对总费用的影响。从表中数据分析，S5钢厂钢管的销价的变化对购运计划和总费用的影响最大。
通过分析问题一中关于产量的约束，Lingo运行后得到的结果得

分析表中数据，得S1钢厂钢管的产量上限的变化对购运计划和总费用的影响最大。
问题三的模型
题图二为树形图，采用Floyd算法，用matlab编程求出单位钢管从运输到的最小运输费用，具体数据如下表2：
表2 单位钢管从运输到的最小运输费用 （单位：万元）

由于树形图的出现，则某些管道处会出现多支路。 则模型一中模型的 ，不再适用，此时可考虑多增加一些支路变量，并增加约束，在目标函数中增加相应的铺设费。
目标函数：

约束条件：
① 生产能力的限制:
② 运到的钢管用完:

③ 与之间的钢管:

④ 变量非负性限制: ,
⑤ 运到的钢管整数限制:
运用数学软件Lingo编程求出
最优最小费用万元
6. 模型评价与推广

此模型是针对钢管订购运输问题的处理方案,其中主要方面在于运输路径的选择，模型中将路径的选择分成两大部分处理，先将货物运到节点，再从节点向全线运输。同时，在解决第一个问题时，把铁路和公路分开计算，最后进行统一，简化了运算。但模型也存在一些不足之处，在对铁路运费矩阵和公路运费矩阵进行统一时，取的还是相对近似值。另外，由于我们在建立约束条件时要求从节点向其他方向运输时，相邻两节点运量加和恰好等于两点间线路距离，因此忽略了跨节点运输的情况，而这里面可能出现较之更优的方案。
在解决本题时，我们主要采用的是通过点来表示线路的，同时应用图论中的floyd算法解决最短路径问题。在生活中，求最短路径的问题常常会碰到，我们可以对模型稍加修改，使之符合问题的条件，进而进行求解。

参考文献：
【1】周品 赵新芬，MATLAB数学建模与仿真，北京：国防工业出版社，2009.4
【2】谭永基 蔡志杰，数学模型，上海：复旦大学出版社，2011.1
【3】谢金星,薛毅.《优化建模与LINGO/LINGO软件》.北京：清华大学出版社,2005
【4】 宗容,施继红,尉洪,李海燕.《数学实验与数学建模》.云南：云南大学出版社，2009

附录：用matlab建立Floyd函数的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)<D(i,j)
D(i,j)=D(i,k)+D(k,j);
path(i,j)=path(i,k);
end
end
end
end

问题一：
1) 用Floyd算法求铁路最短距离， 以7个钢管厂和17个中转点建立初始距离矩阵，对于任意两点之间的距离，如果两点之间有铁路直接连接， 其值为两点间铁路的距离；如果两点之间没有铁路直接连接，则其值为inf。
2) 用Floyd算法求公路最短距离，以15个铺设节点、17个中转点和S1、S6、S7三个钢管厂建立初始距离矩阵，对于任意两点之间的距离，如果两点之间有公路直接连接， 其值为两点间公路的距离；如果两点之间没有公路直接连接，则其值为inf。
3) 用Floyd算法求铁路和公路最少费用，编程如下：
%距离转换为费用的程序

D1=D1*0.1; %把公路最短距离换算成公路最少费用
for k=1:300
m1(k)={k};
end
for k=1:50
m2(k)={300+k};
m3(k)={350+k};
m4(k)={400+k};
m5(k)={450+k};
end
for k=1:100
m6(k)={500+k};
m7(k)={600+k};
m8(k)={700+k};
m9(k)={800+k};
m0(k)={900+k};
end
for i=1:24
for j=1:24 %把铁路最短距离换算成铁路最少费用
switch D(i,j)
case 0
D(i,j)=0;
case m1
D(i,j)=20;
case m2
D(i,j)=23;
case m3
D(i,j)=26;
case m4
D(i,j)=29;
case m5
D(i,j)=32;
case m6
D(i,j)=37;
case m7
D(i,j)=44;
case m8
D(i,j)=50;
case m9
D(i,j)=55;
case m0
D(i,j)=60;
otherwise
D(i,j)=ceil((D(i,j)-1000)/100)*5+60;
end
end
end

%c矩阵表示七个钢管生产厂到十五个铺设节点之间的距离，先把它们都设成20000（任意一个钢管厂到任意一个铺设节点之间的距离不会超过20000），然后用 for 循环求出最小值
c=[20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000;
20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000;
20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000;
20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000;
20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000;
20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000;
20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000];

for i=1:7 %7个钢管生产厂
for k=1:15 %15个铺设节点
for j=8:24 %7个钢管生产厂和17个中转点，i=1，表示第一个钢管生产厂，j=8，表示第一个中转点
if c(i,k)>D(i,j)+D1(k,j+8)
c(i,k)=D(i,j)+D1(k,j+8);
%对于所有中转点，在铁路网和公路网上的下标相差8
end
end
end
end
for i=1:7
for k=1:15
if c(i,k)>D(i,1)+D1(k,33)
c(i,k)=D(i,1)+D1(k,33);
%33代表第一个钢管生产厂S1点
end
if c(i,k)>D(i,6)+D1(k,34)
c(i,k)=D(i,6)+D1(k,34);
%34代表第六个钢管生产厂S6点
end
if c(i,k)>D(i,7)+D1(k,35)
c(i,k)=D(i,7)+D1(k,35);
%35代表第七个钢管生产厂S7点
end
end
%因为S1,S6,S7这三个钢管厂有公路直接连接到铺设节点，所以把这三个点单独处理
end

运行结果如下：

问题一用Lingo软件求解的编程：
model:
sets:
supply/S1..S7/:p,s,t;
need/A1..A15/:L,R,b;
links(supply,need):c,x;
endsets
data:

s=800 800 1000 2000 2000 2000 3000;
b=104,301,750,606,194,205,201,680,480,300,220,210,420,500,;
c=170.7 160.3 140.2 98.6 38.0 20.5 3.1 21.2 64.2 92.0 96.0 106.0 121.2 128.0 142.0
215.7 205.3 190.2 171.6 111.0 95.5 86.0 71.2 114.2 142.0 146.0 156.0 171.2 178.0 192.0
230.7 220.3 200.2 181.6 121.0 105.5 96.0 86.2 48.2 82.0 86.0 96.0 111.2 118.0 132.0
260.7 250.3 235.2 216.6 156.0 140.5 131.0 116.2 84.2 62.0 51.0 61.0 76.2 83.0 97.0
255.7 245.3 225.2 206.6 146.0 130.5 121.0 111.2 79.2 57.0 33.0 51.0 71.2 73.0 87.0
265.7 255.3 235.2 216.6 156.0 140.5 131.0 121.2 84.2 62.0 51.0 45.0 26.2 11.0 28.0
275.7 265.3 245.2 226.6 166.0 150.5 141.0 131.2 99.2 77.0 66.0 56.0 38.2 26.0 2.0;
enddata
min=@sum(links(i,j):(p(i)+c(i,j))*x(i,j))+0.05*@sum(need(j):L(j)^2+L(j)+R(j)^2+R(j));
@for(supply(i):@sum(need(j):x(i,j))>=500*t(i));
@for(supply(i):@sum(need(j):x(i,j))<=s(i)*t(i));
@for(supply(i):@bin(t(i)));
@for(need(j):@sum(supply(i):x(i,j))=L(j)+R(j));
@for(need(j)|j#NE#15:b(j)=R(j)+L(j+1));
R(15)=0;L(1)=0;
@gin(@sum(links(i,j):x(i,j)));
p(1)=160;p(2)=155;p(3)=155;p(4)=160;p(5)=155;p(6)=150;p(7)=160;
end
问题三
（1） 用Floyd算法求铁路最短距离，matlab编程与问题一相同
（2） 用Floyd算法求公路最短距离，以21个铺设节点和14个中转点建立初始距离矩阵，D2矩阵的意义与前面D矩阵相似
（3） 再次调用距离转费用程序，求出铁路和公路最少费用

%h矩阵表示七个钢管生产厂到21个铺设节点之间的距离，先把它们都设成20000（任意一个钢管厂到任意一个铺设节点之间的距离不会超过20000），然后用 for 循环求出最小值
h=[20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000;
20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000;
20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000;
20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000;
20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000;
20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000;
20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000];

for i=1:7
m=1;
for k=[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,24,27,28,29,30,34]
for j=8:24
if h(i,m)>D(i,j)+D2(k,j+8)
h(i,m)=D(i,j)+D2(k,j+8);
end

end
m=m+1;
end
end
for i=1:7
m=1;
for k=[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,24,27,28,29,30,34]
if h(i,m)>D(i,1)+D2(k,33)
h(i,m)=D(i,1)+D2(k,33);
end
if h(i,m)>D(i,6)+D2(k,34)
h(i,m)=D(i,6)+D2(k,34);
end
if h(i,m)>D(i,7)+D2(k,35)
h(i,m)=D(i,7)+D2(k,35);
end
m=m+1;
end
end

运行结果如下：

问题三用软件Lingo编程：
model:
sets:
supply/S1..S7/:p,s,t;
need/A1..A21/:L,R,Z,b;
links(supply,need):c,x;
endsets
data:
p=160 155 155 160 155 150 160;
s=800 800 1000 2000 2000 2000 3000;
b=104,301,750,606,194,205,201,680,480,300,220,210,420,500,,42,10,130,190,260,100;
c=170.7, 160.3, 140.2, 98.6, 38, 20.5, 3.1, 21.2, 64.2, 92, 96, 106, 121.2, 128, 142, 60, 95, 100, 105, 115, 125
215.7, 205.3, 190.2, 171.6, 111, 95.5, 86, 71.2, 114.2, 142, 146, 156, 171.2, 178, 192, 110, 145, 150, 155, 165, 175
230.7, 220.3, 200.2, 181.6, 121, 105.5, 96, 86.2, 48.2, 82, 86, 96, 111.2, 118, 132, 44, 85, 90, 95, 105, 115
260.7, 250.3, 235.2, 216.6, 156, 140.5, 131, 116.2, 84.2, 62, 51, 61, 76.2, 83, 97, 80, 50, 55, 60, 70, 80
255.7, 245.3, 225.2, 206.6, 146, 130.5, 121, 111.2, 79.2, 57, 33, 51, 71.2, 73, 87, 75, 32, 45, 50, 65, 75
265.7, 255.3, 235.2, 216.6, 156, 140.5, 131, 121.2, 84.2, 62, 51, 37, 16.2, 11, 28, 80, 50, 37, 36, 10, 0
275.7, 265.3, 245.2, 226.6, 166, 150.5, 141, 131.2, 99.2, 77, 64, 56, 38.2, 26, 2, 95, 63, 50, 55, 32, 26;
enddata
min=@sum(links(i,j):(p(i)+c(i,j))*x(i,j))+0.05*(@sum(need(j)|j#GE#2 #AND# j#LE#21 :L(j)^2+L(j))+@sum(need(j)|j#LE#14 :R(j)^2+R(j))+@sum(need(j)|j#EQ#9 #OR# j#EQ#11 #OR# j#EQ#17 :Z(j)^2+Z(j))+@sum(need(j)|j#EQ#17 #OR# j#EQ#19 #OR# j#EQ#20 :R(j)^2+R(j)));
@for(supply(i):@sum(need(j):x(i,j))>=500*t(i));
@for(supply(i):@sum(need(j):x(i,j))<=s(i)*t(i));
@for(supply(i):@bin(t(i)));
@for(need(j)|j#NE#9 #AND# j#NE#11 #AND# j#NE#17:Z(j)=0);
@for(need(j):@sum(supply(i):x(i,j))=L(j)+R(j)+Z(j));
@for(need(j)|j#LT#15:b(j)=R(j)+L(j+1));
b(16)=Z(9)+L(16);b(17)=Z(11)+Z(17);
b(18)=L(17)+L(18);b(19)=R(17)+L(19);
b(20)=R(19)+L(20);b(21)=R(20)+L(21);
@gin(@sum(links(i,j):x(i,j)));
end