基于Floyd算法的钢管运输最优化模型.docx
《基于Floyd算法的钢管运输最优化模型.docx》由会员分享，可在线阅读，更多相关《基于Floyd算法的钢管运输最优化模型.docx（13页珍藏版）》请在冰点文库上搜索。
基于Floyd算法的钢管运输最优化模型
2011高教社杯全国大学生数学建模竞赛
承诺书
我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.
我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。
我们知道，抄袭别人的成果是违反竞赛规则的,如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。
我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。
如有违反竞赛规则的行为，我们将受到严肃处理。
我们参赛选择的题号是（从A/B/C/D中选择一项填写）：
我们的参赛报名号为（如果赛区设置报名号的话）：
10
所属学校（请填写完整的全名）：
参赛队员（打印并签名）：
1.肖柳青
2.程祺
3.赵育兴
指导教师或指导教师组负责人（打印并签名）：
日期：
2012年8月12日
赛区评阅编号（由赛区组委会评阅前进行编号）：
2011高教社杯全国大学生数学建模竞赛
编号专用页
赛区评阅编号（由赛区组委会评阅前进行编号）：
赛区评阅记录（可供赛区评阅时使用）：
评
阅
人
评
分
备
注
全国统一编号（由赛区组委会送交全国前编号）：
全国评阅编号（由全国组委会评阅前进行编号）：
题目：
基于Floyd算法的钢管运输最优化模型
摘要
为了在不太影响结果的前提下大幅降低思维难度，从实际情况出发，我们假设“运输钢管的时候先走铁路后走公路，最后沿钢管路线的公路运输”。
在此假设前提下，即可将原来复杂的问题分解为几个较为简单的问题，即“最少总费用=钢厂到中转站的铁路运输最少费用+中转站到节点（
）的公路运输最少费用+钢管购买和铺设的最少费用”。
在求解“钢厂到中转站的铁路运输最少费用”和“中转站到节点（
）的公路运输最少费用”的时候，我们采用Floyd算法，先求出铁路网上钢管厂到铁路上任意两点的最短路线的长度,用Matlab求得相应的铁路运费；同理用Floyd算法求出公路网上的任意两点的最短公路的长度，结果乘以0.1得到公路运费。
这样就得到从钢厂到铺设点运输钢管的最少费用。
根据前面所求的从钢厂到铺设点运输钢管的最少费用，每个铺设点分别向左右两边展开，用Lingo求出最小铺设费用。
运输费用加上购买费用再加上铺设费用就是总费用。
图一的最少费用是1278632万元。
经灵敏度分析7个钢厂的产量上限的影子价格，得1号厂的产量上限对结果影响最大。
再次分析钢厂销价的影子价格，得6厂的价格对结果影响最大。
与图一的模型相似，在建立图二模型时只需要在图一所建模型的基础上加几个约束条件，在Lingo中运行即可得到图二的最少费用是1429907万元。
不过此时所得“最少总费用”还不是“最终最少总费用”。
经参阅数篇相关论文，他们默认为如果乘铁路距离越长那么单位距离的的运费就越少。
实际上依据单位钢管的铁路运价表可知，当铁路长为601~650km或701~750km时，如果中间恰好有一中转站，那么就有可能经过中途转乘后反而比连续运输的费用要低。
例如A到C为625km，AC之间距A点290km处有一中转站B点，依据单位钢管的铁路运价表可知，直接从A到C的费用为44万元，而经过B点中转后的费用为43万元。
所以凡是没有考虑“中转后的费用可能比不中转的费用低”这中情况的都存在顶层思维上的错误。
为解决这种特殊情况，我们在建立图一模型的时候为了简化思维难度，同样采取先假设“铁路不中转时的费用最低”，得出在这一假设下的最优解后，判别所有连续铁路的路程是否在601~650km或701~750km的范围内。
如果都不在这两个范围内，那么原最优解即为最终的最优解，如果有一条或几条铁路的路程在此范围内，那么分别查看这段铁路之间是否有且只有一个中转站，而且此中转站恰好将该段铁路分为0~300km、301~350km或301~350km、351~400km，如果成立，那么将整段铁路划分为两段来计算运费，从而将其作为最终最优解，否则原最优解即为最终最优解。
关键词：
Floyd算法、非线性规划、运输规划
一问题重述
要铺设一条
的输送天然气的主管道,如图一所示（见下页）。
经筛选后可以生产这种主管道钢管的钢厂有
。
图中粗线表示铁路，单细线表示公路，双细线表示要铺设的管道（假设沿管道或者原来有公路，或者建有施工公路），圆圈表示火车站，每段铁路、公路和管道旁的阿拉伯数字表示里程（单位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）的要求给出模型和结果。
二模型假设
1.运输钢管的时候先走铁路再走公路，最后走沿着管道的公路。
（重要）
2.钢管在运输中由铁路运转为公路运时不计中转费用。
3.钢管单价与订购量、订购次数、订购日期无关。
4.将每一单位的管道所在地看成一个需求点，向一单位管道的所在地运输钢管即为
向一个点运输钢管。
5.所有管道的运输量都为整数
6.在铺设过程中，离路口0—1公里的这一公里管道的运输费用以1单位管道运行1公里记，而不考虑汽车到底将管道放在哪个位置，或者是汽车运一段，放一点的实际复杂过程。
显然我们的这种假设比较保守，能够保证计算出的运输费用满足实际使用，因而是一种合理安全的假设。
三符号说明
<1>目标变量（决策变量）：
表示总费用
子目标变量：
、
、
分别代表购买、运输、铺设费用
<2>因变量:
管道工厂的相关量：
表示厂i的管道出厂价，与程序中的price对应
表示厂i的生产量，与capacity对应
表示厂i的生产上限，对应limit
运输过程的相关量：
表示厂i到节点j的最省运输价格，对应cost
表示厂i运至节点j的运输量，对应volume
铺设过程的相关量：
表运至节点j的管道数量，对应demand
、
表示节点j向左向右铺设的长度
四问题分析和模型的建立
<1>模型一（图一）
为了在不太影响结果的前提下降低思维难度，我们假设运输钢管的时候先走铁路后走公路，最后沿钢管路线的公路运输。
依照实际情况，确实如此。
经参阅很多相关论文，他们默认为如果乘铁路距离越长那么单位距离的的运费就越少。
实际上依据单位钢管的铁路运价表可知，当铁路长为601~650km或701~750km时，如果中间恰好有一中转站，那么就有可能经过中途转乘后反而比连续运输的费用要低。
例如A到C为625km，AC之间距A点290km处有一中转站B点，依据单位钢管的铁路运价表可知，直接从A到C的费用为44万元，而经过B点中转后的费用为43万元。
所以凡是没有考虑“中转后的费用可能比不中转的费用低”这中情况的都存在思维上的漏洞，这也是导致难以从图一所建模型推广到图二的重要原因之一。
为了解决上段所述的特殊情况，我们在建立图一模型的时候为了简化思维难度，同样采取先假设“铁路不中转时的费用最低”，得出在这一假设下的最优解后，判别所有连续铁路的路程是否在601~650km或701~750km的范围内。
如果都不在这两个范围内，那么原最优解即为最终的最优解，如果有一条或几条铁路的路程在此范围内，那么分别查看这段铁路之间是否有且只有一个中转站，而且此中转站恰好将该段铁路分为0~300km、301~350km或301~350km、351~400km，如果成立，那么将整段铁路划分为两段来计算运费，从而将其作为最终最优解，否则原最优解即为最终最优解。
所有钢管必须运到天然气主管道铺设路线上的节点
，然后才能向两边铺设。
对最小运费的求解，我们采用Floyd算法。
先求出铁路网上钢管厂到铁路上任意两点的最短路线的长度,用Matlab求得相应的铁路运费；同理用Floyd算法求出公路网上的任意两点的最短公路的长度，结果乘以0.1得到公路运费。
于是就得到从钢厂到铺设点运输钢管的最少运费。
每个铺设点分别向左右两边展开，用Lingo求出最小铺设费用。
运输费用加上购买费用再加上铺设费用就是总费用。
（1）针对题图一，我们采用Floyd算法。
Floyd算法简介
算法基本思想：
假设求顶点Vi到Vj的最短路径。
弗洛伊德算法依次找从Vi到Vj，中间经过结点序号不大于0的最短路径，不大于1的最短路径，…直到中间顶点序号不大于n-1的最短路径，从中选取最小值，即为Vi到Vj的最短路径。
Floyd函数的M文件：
function[D,path]=floyd（a）
n=size（a,1）;
D=a;path=zeros（n,n）;
fori=1:
n
forj=1:
n
ifD（i,j）~=inf
path（i,j）=j;
end
end
end
fork=1:
n
fori=1:
n
forj=1:
n
ifD（i,k）+D（k,j）D（i,j）=D（i,k）+D（k,j）;
path（i,j）=path（i,k）;
end
end
end
end
我们对原图一进行了重新编号，参照（附录一图三）
我们用上述Floyd算法得到铁路距离矩阵（附录二），用Matlab（参见附录六）同时得到铁路运费矩阵（附录三），同理（参照附录一图四）得到公路距离矩阵（附录四），同时得到运费矩阵（附录五）。
或者可以运行“程序”文件夹中的Matlab程序亦可得到附录中的结果。
综合铁路运费矩阵和公路运费矩阵得到总运费矩阵，如下表。
运费
A1
A2
A3
A4
A5
A6
A7
A8
A9
A10
A11
A12
A13
A14
A15
S1
170.7
160.3
140.2
140
38
20.5
21
21.2
64.2
92
96
106
121.2
128
142
S2
215.7
205.3
190.2
185
111
95.5
86
71.2
114.2
142
146
156
171.2
178
192
S3
230.7
220.3
200.2
200
121
105.5
96
86.2
48.2
82
86
96
111.2
118
132
S4
260.7
250.3
235.2
230
156
140.5
131
116.2
84.2
62
51
61
76.2
83
97
S5
255.7
245.3
225.2
225
146
130.5
121
111.2
79.2
57
33
51
71.2
73
87
S6
265.7
255.3
235.2
235
156
140.5
131
121.2
84.2
62
51
45
26.2
23
28
S7
275.7
265.3
245.2
245
166
150.5
141
131.2
99.2
77
66
56
38.2
26
22
（2）用lingo求解线性优化问题：
根据前面所求的各工厂到各管道节点的最省运费，现在我们可以抽除运输的过程，将问题转化为常见的线性优化问题。
但是，与一般的最小运费问题不同的是，这里的最低费用包含了管道的购买费用、管道的运输费用，以及管道的铺设费用。
其实管道的铺设费用就是铺设过程中管道的运输费用，这里单独计算，使其结果更明晰。
我们仔细思考了实际情况，认为1单位的管道其实是一个比较大的运输量，所以我们理应将该问题连续性考虑，用积分表达式求解运费的总和，但是考虑到运算的复杂性，以及题目中的不足一公里以一公里记的提示，我们认为该问题完全允许以一单位管道为基本单位。
因为题目要求的也不是一个绝对精确的结果。
基于以上分析，我们开始建立模型。
[1]决策目标
Min
其中：
管道的购买费用：
管道的运输费用：
管道的铺设费用：
[2]约束条件：
或
+
=
[3]模型：
Min=
+
+
s.t.
或
+
=
代入求解：
运行“程序”文件夹中的“lingo1.lg4”。
运行结果如下所示：
Localoptimalsolutionfound.
Objectivevalue:
1278632.
Extendedsolversteps:
13
Totalsolveriterations:
3155
VariableValueReducedCost
WAYFEE399714.10.000000
PRODUCTFEE797725.00.000000
WORKFEE81192.500.000000
由运行结果，可知最优方案耗资仅为1278632万元
其中运输费用：
399714.1万元
购买管道费用：
797725.0万元
铺设费用：
81192.50万元
经检验，有连续铁路的路程在601~650km或701~750km的范围内，但是没有一个中转站，使得该中转站恰好将该段铁路分为0~300km、301~350km或301~350km、351~400km。
所以1278632万元为最终最优解。
[4]灵敏性分析（回答第二问）
<1>分析模型1，得1厂的生产上限影响最大，分析过程如下：
提取结果中对应的部分：
RowSlackorSurplusDualPrice
430.000000103.0000
450.00000035.00000
470.00000025.00000
490.0000000.000000
51985.00000.000000
53444.00000.000000
560.0000000.000000
上述7行分别代表7个工厂产量上限的影子价格，显然是厂1，即
的影子价格最大。
这表明1号厂的产量上限对结果影响最大。
而且，每增加一单位产量上限，可以节省103万元之多，远大于其余各厂。
显然，实际中应大力鼓励1厂扩大生产规模，这样不仅保证1厂不会生产滞销，而且为整个区域的管道建设可以节约大量成本，可谓是两全其美的好办法。
<2>再次分析模型1，得6厂的价格对结果影响最大，影子价格列出如下：
RowSlackorSurplusDualPrice
570.000000-800.0000
580.000000-800.0000
590.000000-1000.000
600.0000000.000000
610.000000-1015.000
620.000000-1556.000
630.0000000.000000
而且我们知道，6号厂每提高1万的售价，整个工程就要多消耗1556万之多，非常可怕。
但是相反，若能减小1万元售价，也会产生同样巨大的效益。
<2>模型二（图二）
与图一的模型相似，在建立图二模型时只需要在图一所建模型的基础上加以下几个约束条件即可在Lingo中运行得到最少费用。
①生产能力的限制:
②运到
的钢管用完:
③
与
之间的钢管:
④变量非负性限制:
⑤运到
的钢管整数限制:
特别注意！
只有在Lingo11.0版本上运行“程序”文件夹中的“lingo2.lg4”才能得出以下运行结果。
运行结果：
Localoptimalsolutionfound.
Objectivevalue:
1429907.
Objectivebound:
1429907.
Infeasibilities:
0.2910383E-10
Extendedsolversteps:
0
Totalsolveriterations:
154
即最少费用为1429907万元。
经检验，有连续铁路的路程在601~650km或701~750km的范围内，但是没有一个中转站，使得该中转站恰好将该段铁路分为0~300km、301~350km或301~350km、351~400km。
所以1429907万元为最终最优解。
五模型优缺点
由于提出针对图一的合理的假设（运输钢管的时候先走铁路后走公路，最后沿钢管路线的公路运输），所以不仅没有影响最优解而且大幅降低了思维难度，使得图一的最优解能较为容易地解出来。
但是，又是由于这一“苛刻”的假设，导致求解图二的最优解的时候不会得出真正的最优解，而是得到很接近“真正最优解”的“近似最优解”。
导致这一缺憾的根本原因是我们默认为“最短距离所支出费用等于真正最少费用”，但是实际上可能不是这样，所以我们没有建立普遍性的模型。
但是在最后结果相对误差不大的情况下，我们所建的模型不失为一种高效、可靠、简洁的模型。
六模型展望
在上文“模型优缺点”中已经阐明我们所建模型的缺憾之处，由于时间原因，我们没有建立一个完美的具有广义适用性的模型。
在我们心中，这个“完美”的模型所遵循的思路应当是运输费用决定运输路径和运输距离，例如：
“公路->铁路->公路->…->管道公路”的运输费用不一定比“铁路->公路->管道公路”的费用高。
七参考文献
[1]谢金星,薛毅.《优化建模与LINGO/LINGO软件》.北京：
清华大学出版社,2005
[2]王防修，周康，同小军。
《Floyd算法在公交线路优化中的作用》.第30卷第3期
升级会员 