当前位置：文档库 › 数学建模B题解答

数学建模B题解答

数学建模B题解答 IMB standardization office【IMB 5AB- IMBK 08- IMB 2C】

钢管订购和运输

摘要：本文建立了一个运输问题的最优化模型。

通过分析题图一，我们利用Floyd 算法求出铁路网和公路网各点间最短路线，然后转化成最少运输，去掉了铁路和公路的性质，使运输网络变成一张供需运输价格表，然后建立了一个以总费用为目标函数的非线性规划模型，利用Lingo 软件，求出问题一的最优解为1278632万元

通过对问题一中lingo 运行结果的分析，我们得出S5钢厂钢管的销价的变化对购运计划和总费用影响最大，S1钢厂钢管的产量的上限的变化对购运计划和总费用的影响最大。

问题三模型的建立原理和问题一的相同，利用Lingo 软件，求得最优解为

1407149万元.

关键词：Floyd 算法，非线性规划，0-1规划

一问题重述

有7个生产厂，可以生产输送天然气主管道的钢管

721,,S S S 。要沿着

1521A A A →→→ 的主管道铺设, 如题图一所示。图中粗线表示铁路，单细线表示

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

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

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

里程(km) ≤300 301～350 351～400 401～450 451～500

运价(万元) 20 23 26 29

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

1000km 以上每增加1至100km 运价增加5万元。

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

线）。

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

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

二问题分析

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

1521A A A →→→ ，然后才能向左或右铺设。必须求出每个钢管厂721,,S S S 到每个节点1521A A A →→→ 的每单位钢管的最小运输费用。

对最小运费的求解，我们采用Floyd 算法。先求出铁路网上钢管厂到铁路上任意两点i V ，j V 的最短路线的长度ij L ,用matlab 求得ij L 对应的铁路单位运费ij D ；同理用Floyd 算法求出公路网上的任意两点j V ，k V 的最短公路路线的长度jk L ，结果乘

1521,,,A A A

以得到公路运费jk D 1。)1min(jk ij ik D D C +=，j 表示所有运输中转点，于是就得到从某钢厂到某铺设点运输单位钢管的最少运输费用。

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

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

问题三，如铺设的管道是一个树形图，铁路、公路和管道构成网络对于题图二，我们可以延用问题一里面的思想，在题图一的基础上多几条铺设路段，9，11，17节点的铺设方向变为Z L R ,, 三个方向，其他不变。

三模型的假设与符号说明

1) 基本假设:

○

1钢管在运输中由铁路运转为公路运时不计中转费用； ○

2所需钢管均由)7,...,1(=i S i 钢厂提供； ○

3假设运送的钢管路途中没有损耗。 ○

4把“钢厂钢管的销价和产量上限变化对总费用和运购计划的影响”理解为在最优解附近的微小变化对总费用和运购计划的影响。销价最小变化是1万元，产量上限的最小变化是1个单位。

○

5沿管道或者原来有公路或者建有施工公路。 ○

6一个钢管厂如果承担制造钢管，至少要生产500个单位。 ○

7公路运输费用为1单位钢管每公里万元，不足整公里按整公里计算。

2) 符号说明1:

i S : 钢厂i S 的最大生产能力;

i p : 钢厂i S 的出厂钢管单位价格(单位: 万元) ;

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

ij D ：铁路网上两点间的单位钢管最少运输费用； jk D 1：题图一公路网上两点间的单位钢管最少运输费用；

jk D 2：题图二公路网上两点间的单位钢管最少运输费用；

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

ij c : 1 单位钢管从钢厂i S 运到j A 的最小费用(单位: 万元) ;

j b : 从j A 到1+j A 之间的距离(单位: 千米) ;

ij x : 钢厂i S 运到j A 的钢管数;

j L : 运到j A 地的钢管向左铺设的数目;

j R : 运到j A 地的钢管向右铺设的数目;

j Z ：运到j A 地的钢管向第三个方向铺设的数目;

i t : =??

?不提供钢管；

，钢厂提供钢管；，钢厂i i S 0S 1

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

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

四模型的建立与求解

问题一的模型：

针对题图一，我们采用Floyd 算法，用matlab 编程求出单位钢管从i S 运输到j

A 的最小运输费用，具体数据如下表1：

表1 单位钢管从i S 运输到j A 的最小运输费用（单位：万元）

对表1的数据进行分析，我们得到一个非线性规划模型：

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

W = Q + P + T

其中 ij i j i x p Q ?=∑∑==71151

， ij i j ij x c P ?=∑∑==7115

， ()()??

??+++=∑=212115

j j j j j R R L L d T 目标函数为： ()()

????++++?+?=∑∑∑∑∑=====2121min 15

115

1j j j j j ij i j ij ij i j i R R L L d x c x p W 约束条件为:

① 生产能力的限制: i i j ij i t s x t ?≤≤?∑=15

500 )7,...,

1(=i )10(或=i t

② 运到j A 的钢管用完: j i j ij R L x +=∑=7

)15,...,

1(=j ③ j A 与1j +A 之间的钢管: j j b L R =++1j )14,...,

1(=j ④ 变量非负性限制: 0,0,0≥≥≥j

R L x j ij , )15,...,1,7,...,

1(==j i ⑤ 运到j A 的钢管整数限制: N x ij ∈ 运用数学软件Lingo 编程求解最优最小费用1278632.=W 万元问题二的模型

通过分析问题一中关于销价的约束，Lingo 运行后得到的结果得

影子价格表示在最优解下“资源”增加一个单位时“效益”的增量，即每个钢厂销售价格每减少一万元，对总费用的影响。从表中数据分析，S5钢厂钢管的销价的变化对购运计划和总费用的影响最大。

通过分析问题一中关于产量的约束，Lingo 运行后得到的结果得

分析表中数据，得S1钢厂钢管的产量上限的变化对购运计划和总费用的影响最大。

问题三的模型

题图二为树形图，采用Floyd 算法，用matlab 编程求出单位钢管从i S 运输到j

A 的最小运输费用，具体数据如下表2：

表2 单位钢管从i S 运输到j A 的最小运输费用（单位：万元）

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

L ，

R 不再适用，此时可考虑多增加一些支路变量，并增加约束，在目标函数中增加相

应的铺设费。

目标函数：约束条件：

① 生产能力的限制: i i j ij i t s x t ?≤≤?∑=21

1500 )7,...,1(=i )10(或=i t

② 运到j A 的钢管用完: j i j ij R L x +=∑=7

)17,11,921,...,1(≠=j j 且

③ j A 与1j +A 之间的钢管: j j b L R =++1j )14,...,

1(=j ④ 变量非负性限制: 0,0,0,0≥≥≥≥j j Z R L x j ij , )21,...,1,7,...,1(==j i ⑤ 运到j A 的钢管整数限制: N x ij ∈

运用数学软件Lingo 编程求出最优最小费用1407149.=*W 万元

五模型优缺点

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

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

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

参考文献：

[1] 谢金星,薛毅.《优化建模与LINGO/LINGO 软件》.北京：清华大学出版社,2005 [2] 宗容,施继红,尉洪,李海燕.《数学实验与数学建模》.云南：云南大学出版社，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)

问题一：

用Floyd 算法求铁路最短距离，以7个钢管厂和17个中转点建立初始距离矩阵

()

*24ij D ，对于任意两点

之间的距离，如果两点之间有铁路直接连接，其值为两点间铁路的距离；如果两点之间没有铁路直接连接，则其值为inf 。 2)

用Floyd 算法求公路最短距离，以15个铺设节点、17个中转点和S1、S6、S7三个钢管厂建立初始距离矩阵

()

35*351ij D ，对于任意两点之间的距离，如果两点之间有公路直接连接，其值为两点间公路的距离；如

果两点之间没有公路直接连接，则其值为inf 。 3)

用Floyd 算法求铁路和公路最少费用，编程如下：

%距离转换为费用的程序

D1=D1*; %把公路最短距离换算成公路最少费用 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];

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

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= ;

enddata

min =@sum (links(i,j):(p(i)+c(i,j))*x(i,j))+*@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个中转点建立初始距离矩阵

()

35*352ij D ，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]; 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

m=m+1;

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

运行结果如下：

问题三用软件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=, , , , 38, , , , , 92, 96, 106, , 128, 142, 60, 95, 100, 105, 115, 125

, , , , 111, , 86, , , 142, 146, 156, , 178, 192, 110, 145, 150, 155, 165, 175

, , , , 121, , 96, , , 82, 86, 96, , 118, 132, 44, 85, 90, 95, 105, 115

, , , , 156, , 131, , , 62, 51, 61, , 83, 97, 80, 50, 55, 60, 70, 80

, , , , 146, , 121, , , 57, 33, 51, , 73, 87, 75, 32, 45, 50, 65, 75

, , , , 156, , 131, , , 62, 51, 37, , 11, 28, 80, 50, 37, 36, 10, 0

, , , , 166, , 141, , , 77, 64, 56, , 26, 2, 95, 63, 50, 55, 32, 26;

enddata

min=@sum(links(i,j):(p(i)+c(i,j))*x(i,j))+*(@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#E

Q#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