钢管订购及运输.doc

钢管订购和运输

张伟 丁林阁 邓小涛 指导教师：数模组
海军航空工程学院

摘要 本模型研究了管道铺设过程中钢管的订购和运输问题，它通过图论和非线性规划的知识建立。模型使总费用达到最小，很好地解决了向哪个钢厂定货，定货多少，如何运输的问题，并且可以推广到更一般的网络。同时针对模型中涉及的变量多、求解复杂这一问题，我们对模型进行了适当的简化,大大减少了变量的个数,从而减少了计算量。
一、问题重述
要铺设一条的天然气主管道，可以生产这种主管道钢管的钢厂有七家。钢厂的位置，管道的铺设路线，以及从钢厂到铺设地的运输网络（运输网络包括沿管道的公路）均已知。每个钢厂的钢管价格及其生产能力不全一样，且一个钢厂若要生产这种钢管，至少需要生产500个单位（1千米钢管记为1个单位）。铁路的运价和公路的运价不一样。
要求在这种情况下，（1）制定一个钢管的订购和运输计划，使总费用最小，并给出总费用。(2)分析：哪个钢厂钢管的销价的变化对购运计划和总费用影响最大，哪个钢厂钢管的产量的上限的变化对购运计划和总费用的影响最大，给出相应的数字结果。(3)如果铺设的管道不是一条线，而是一个树形图，铁路、公路和管道构成网络，就这种更一般的情形给出一种解决办法，并对图二按（1）的要求给出模型和结果。
二、问题的假设
在问题所给条件成立的前提下，我们进一步作如下假设：
1. 假设公路运输费用不是整公里的按整公里计算是合理的。
2. 假设沿管道的公路（施工公路）运输费用也为每公里0.1万元（不足整公里部分按整公里计算）。
3. 假设不考虑铁路、公路及施工公路的运输能力限制。
4. 假设运输费用为单程运输的费用，即从出发点到目的地的单程费用，不考虑空车返回的费用。
5. 假设运输费用已包含装卸费用。
　 关于假设的一点说明：根据上述假设我们认为在铺设管道的过程中每隔一公里，卸下一单位钢管供工人铺设是合理的。
三、符号约定
：生产主管道钢管的钢厂 ；
：管道节点 ；
：从到铺设钢管的路段长度（单位：公里，）；
: 钢厂在指定期限内生产钢管的最大数量（单位：单位钢管）；
: 钢厂单位钢管的出厂价格（单位：万元）；
：从 钢厂运到的钢管数量（单位：单位钢管）；
：表示1单位钢管从 钢厂到的最小费用（单位：万元）；
：运到的钢管总数（单位：单位钢管）；
： 从往左铺设的钢管总数（单位：单位钢管），为的一部分；
： 从往右铺设的钢管总数（单位：单位钢管），这里；
其中
四、问题分析
本问题分两部分：一部分是图论中的最短路径的问题：确定1单位钢管从 钢厂到的最小费用；另一部分是非线性规划问题：求总的最小费用。具体如下：
首先，以钢厂、管道节点和火车站为顶点，铁路、公路（包括沿管道的原有公路和施工公路）为边，里程为权值，构成一个无向图。将处理为以运费为权值的完全图，用Floyd算法求出最短路经，从而确定从钢厂()到()单位钢管的最小费用（此费用包括单位钢管的价格费用和最小运输费用）。具体实现如下：
记单位钢管从钢厂()到()的最小运费为，那么最小费用，由于已知，所以确定就变成确定。在中让公路边的权值为无穷大，没边相连的结点之间加一条权值为无穷大的边，求出任两结点间最短的铁路长度，使变成完全图；同样在中让铁路边的权值为无穷大，没边相连的结点之间加一条权值为无穷大的边，求出任两结点间最短的公路长度，使变成完全图。按把和合成完全图，其中表示费用权值，而不是里程权值，函数表示1单位钢管由铁路运输每公里的运费，0.1表示1单位钢管由公路运输每公里的运费，由 求出到的最小费用。
然后解决从各个钢厂运到()的钢管总数量如何铺设问题。我们把分为从往左铺设的钢管总数和从往右铺设的钢管总数，从而很好的解决了此问题。且该方法可以很好的推广到问题的第（3）问中（见模型推广）。
最后建立以钢管的价格费用和运输费用（包括铺设过程中的运费）为最小的目标函数，用非线性规划求解。
五、模型的设计与求解
模型用到如下引理：
引理１．要将管道全程铺满且无重复铺设，和应满足。
引理２．分为和不影响目标函数全局最优性。
因为在确定从钢厂()到()单位钢管的最小费用时，运输网络已包含沿管道的公路（施工公路），所以很容易用反证法证明。
引理３．当从到的最短路不经过时，应满足；当从到的最短路不经过时，应满足。
假如大于，那么我们肯定可把（）这一部分理解为某个钢厂途经沿管道铺设线运往的钢管，且从该钢厂经到的路线是最小费用路线（本模型的最终结果也证明了这一点）。
1. 所有钢管从钢厂运到()的费用：

2. 铺设的运输费用为：

在处分别向左右铺设，按每走一公里卸下一单位钢管计算运费。从（）处向左运输（）单位钢管（其中），由等差数列得运费为；同理得从（）向右运输（）单位钢管（其中）的运费为。
3. 总费用的目标函数：

4. 模型的简化及求解
引理4. 对最优化问题：（），的一个最优解，如果满足，则 也是最优化问题
（） 的一个最优解。
在利用 Matlab 进行数值计算时，我们可以把约束条件 改写为
，
且 ，
利用上述条件计算时可以用隐枚举法，在 的条件下，使 从 变到 。
针对模型涉及变量过多、求解复杂，我们对模型做进一步简化。具体如下：利用消去中间变量，使得目标函数仅剩便于编程计算。消去步骤为以此类推即可。对于本问题，为了提高计算效率,应用引理4放松部分约数条件，求得一最优解，且满足放松的约束条件，所以为本模型的最优解。(程序见附录)
结果如下： 最小总费用是127.93亿元。
订购和运输方案：
钢管的订购计划 (单位:万元)

A1
A2
A3
A4
A5
A6
A7
A8
A9
A10
A11
A12
A13
A14
A15
总计
S1
0
0
0
139
196
203
262
0
0
0
0
0
0
0
0
800
S2
0
182
76
161
93
0
0
288
0
0
0
0
0
0
0
800
S3
0
0
232
4
87
0
0
0
677
0
0
0
0
0
0
1000
S4
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
S5
0
0
193
168
240
0
0
0
0
169
409
0
0
0
0
1179
S6
0
0
0
0
0
0
0
0
0
181
0
0
282
429
0
892
S7
0
0
0
0
0
0
0
0
0
0
0
90
50
0
360
500
总计
0
182
501
472
616
203
262
288
677
350
409
90
332
429
360
5171
主管道钢管的运输方案如下（见图一）括号内的数字为订购的钢管的数量,图上各顶点均用红色的数字标注
S1-22-21-20-A5-A4(139)
S1-22-21-20-A5(196)
S1-22-21-A6(203)
S1-A7(262)

S2-24-19-18-16-A2(182)
S2-24-19-18-17-A3(76)
S2-24-23-22-21-20-A5-A4(161)
S2-24-23-22-21-20-A5(93)
S2-24-A8(288)

S3-26-24-19-18-17-A3(232)
S3-26-24-23-22-21-20-A5-A4(4)
S3-26-24-23-22-21-20-A5(87)
S3-26-A9(677)

S5-30-29-28-26-24-19-18-17-A3(193)
S5-30-29-28-26-24-23-22-21-20-A5-A4(168)
S5-30-29-28-26-24-23-22-21-20-A5(240)
S5-30-29-28-A10(169)
S5-30-A11(409)

S6-37-35-33-29-28-A10(181)
S6-37-35-A13(282)
S6-A14(429)

S7-38-37-35-33-34-A12(90)
S7-38-37-35-A13(50)
S7-A15(360)

六、结果分析
为了研究哪个钢厂钢管价格的变化对结果的影响最大。我们以最优值点为基础，先暂时让某一个钢厂钢管的价格有规律的变动，其余钢厂钢管的价格不变，观察其对目标函数的影响。在Matlab下得到目标函数在最优值附近对七个钢厂钢管价格的敏感程度曲线图。经分析当价格变化较小时，钢厂S5的钢管价格变化对目标函数影响最大。当价格变化较大时，钢厂S6的钢管价格变化对目标函数影响最大，价格以万元变化，目标函数(单位：亿元)的变化如下：

-20
-10
-5
0
5
10
20
S1
126.30
127.14
127.54
127.93
128.34
128.74
129.54
S2
126.30
127.14
127.54
127.93
128.34
128.74
129.53
S3
125.93
126.94
127.44
127.93
128.44
128.94
129.93
S4
127.26
127.93
127.93
127.93
127.93
127.93
127.93
S5
125.08
126.55
127.32
127.93
128.41
128.58
128.68
S6
124.62
126.53
127.38
127.93
128.28
128.62
129.23
S7
126.93
127.44
127.69
127.93
128.19
128.44
128.93

在研究哪个钢厂产量的上限的变化对结果的影响最大。我们仍以最优值点为基础，先暂时让某一个钢厂产量有规律的变动，其余钢厂产量不变，观察其对目标函数的影响。经计算，向S4,S5,S6,S7订购的钢管数量远离的它们的生产上限，所以它们的上限的变化对结果影响很小，可以忽略。S1,S2,S3的生产上限变化对目标函数影响比较大。在Matlab下得到目标函数在最优值附近对3个钢厂产量的敏感程度曲线图。从图上可以看出S1在最优解附近对目标函数影响最大。产量每变化5单位钢管，目标函数(单位：亿元)的变化结果如下：

-10
-5
0
5
10
S1
128.04
127.99
127.93
127.88
127.83
S2
127.97
127.95
127.93
127.92
127.90
S3
127.96
127.95
127.93
127.92
127.91

七、模型的推广

如果要铺设的管道是一个树形图，不妨设它有个节点(管道交接点)，仍记为。设有个钢厂，仍记为。此时由于铺设的管道不是一条直线，而是一个树，和相连的节点有很多。所以不能对简单地分为左右两部分，我们记由铺往的钢管数量是，则总费用的目标函数为：

对此推广模型我们仍可采用模型一简化步骤中消去的类似方法消去。原理如下：
由于铺设的管道是一个树形图，所以个节点对应个边，对应个中间变量（因为每条边有两个中间变量）。有引理1.可得个独立的等式，即，再由可得个独立的等式，再剔去二者之间　这个多余的暗含等式，可得个独立的等式，所以 可由（即）表示，从而消去了中间变量。
对问题（3）的求解仅需令推广模型中的即可，结果为：亿元。
订购方案为： （单位：单位钢管）

s1
s2
s3
s4
s5
s6
s7
总计
A1
0
0
0
0
0
0
0
0
A2
0
178
0
0
0
0
0
178
A3
0
254
37
0
217
0
0
508
A4
159
33
131
0
146
0
0
469
A5
176
35
131
0
273
0
0
615
A6
200
0
0
0
0
0
0
200
A7
265
0
0
0
0
0
0
265
A8
0
300
0
0
0
0
0
300
A9
0
0
659
0
0
0
0
659
A10
0
0
0
0
0
362
0
362
A11
0
0
0
0
370
0
0
370
A12
0
0
0
0
0
116
0
116
A13
0
0
0
0
0
393
0
393
A14
0
0
0
0
0
237
129
366
A15
0
0
0
0
0
0
371
371
A16
0
0
42
0
0
0
0
42
A17
0
0
0
0
144
0
0
144
A18
0
0
0
0
0
85
0
85
A19
0
0
0
0
0
100
0
100
A20
0
0
0
0
0
260
0
260
A21
0
0
0
0
0
100
0
100
总计
800
800
1000
0
1150
1653
500
5903
运输方案为（见图二）：
S1→22→21→20→A5→A4(159)
S1→22→21→20→A5(176)
S1→22→21→A6(200)
S1→A7(265)
S2→24→19→18→16→A2(178)
S2→24→19→18→17→A3(254)
S2→24→S1→22→21→20→A5→A4(33)
S2→24→S1→22→21→20→A5(35)
S2→24→A8(300)

S3→26→24→19→18→17→A3(37)
S3→26→24→S1→22→21→20→A5→A4(131)
S3→26→24→S1→22→21→20→A5(131)
S3→26→A9(659)
S3→A16(42)

S5→30→29→28→26→24→19→18→17→A3(217)
S5→30→29→28→26→24→23→22→21→20→A5→A4(146)
S5→30→29→28→26→24→23→22→21→20→A5(273)
S5→A17→A11(370)
S5→A17(144)

S6→35→33→29→28→A10(362)
S6→35→A13→A12(116)
S6→35→A13(393)
S6→A14(237)
S6→35→A18(85)
S6→35→A18→A19(100)
S6→A20(260)
S6→A21(重合)(100)
S7→38→37→A14(129)
S7→A15(371)

八 模型评价
本模型首先应用图论知识，把整个网络变成完全图，利用 Floyd 算法求出图中任意两顶点之间的最短路径，即最小费用。再应用非线性规划求解，在求解过程中利用网络流量的平衡关系，减少了大量中间变量，降低了计算量。并对更一般的树形管道路线，给出了解决办法。模型求解速度快，对实际问题有一定的指导意义。　

参考文献
[1]《运筹学》教材编写组编，运筹学，清华大学出版社。
[2]苏海岛等著，C语言数值计算常用程序，警官教育出版社。
[3]杨洪编，图论常用算法选编，中国铁道出版社。
[4]袁亚湘、孙文瑜著，最优化理论与方法，科学出版社。

11