钢管的订购和运输问题.docx
《钢管的订购和运输问题.docx》由会员分享，可在线阅读，更多相关《钢管的订购和运输问题.docx（48页珍藏版）》请在冰点文库上搜索。
钢管的订购和运输问题
钢管的订购和运输问题
长安大学杨剑浩陈晓渭程牧刚
本文针对钢管订购和运输的一般特点和要求，建立了两个遵循题目要求的非
线性规划模型。
在给定钢管需求量，运输方式及价格，厂家生产量上下线，运输路线图等条件下，非线性规划模型和图论的最短路算法，从而得到线最优的钢管订购运输方案，是成本达到最小。
对于问题一，我们选取了钢管订购和运输的总费用最小作为模型的目标函数，用floyd算法分别求出铁路最短路矩阵和公路最短路矩阵，利用费用转化公
式，得到两个矩阵的最小费用，将两者综合求得总体最小运输费用矩阵C（i,j）。
然后用lingo求解得到最优的钢管订购运输方案。
对于问题二，我们根据要求改变钢厂钢管的销价和钢厂钢管的产量上限，然
后用lingo求解，观察得到的图表，对改变以上两个条件后总运费及方案受到的影响进行分析。
考虑到问题三与问题一很相似，不同之处在于问题三中的钢管铺设路线变成了树形，因此我们仍然采用问题一的建模思路，对于特殊之处进行修改。
采用图
论中的floyd算法，求得总体最小运输费用矩阵C（i,j）。
然后用lingo求解得到最优的钢管订购运输方案。
对问题一模型的求解得到最优钢管订购运输方案为：
总费用=1278632万元
每家厂家的生产量:
S1
S2
S3
S4
S5
S6
S7
800.0000
800.0000
1000.000
0
1297.428
1273.572
0
对问题二求解得：
厂家s5和厂家s6的单位钢管销售价发生变化时，对方案中总运费的影响最
大。
厂家si的钢管总产量上限变化对总费用影响最大。
对问题三的模型求解得到最优钢管订购运输方案为:
总费用=1403233万元。
每家厂家的生产量:
S1
S2
S3
S4
S5
S6
S7
800.0000
800.0000
1000.000
0
1303.000
2000.000
0
关键词：
floyd算法非线性规划模型总体最小运输费用矩阵
一、问题重述
要铺设一条输送天然气的主管道。
经筛选后可以生产这种主管道钢管的钢厂有七家。
图中粗线表示铁路，单细线表示公路，双细线表示要铺设的管道（假设
沿管道或者原来有公路，或者建有施工公路），圆圈表示火车站，每段铁路、公路和管道旁的阿拉伯数字表示里程（单位km）。
为方便计，1km主管道钢管称为1单位钢管。
一个钢厂如果承担制造这种钢管，至少需要生产500个单位。
每个钢厂在指定期限内能生产该钢管的最大数量和钢管出厂销售1单位钢管价格均已给出。
1000km以上每增加1至100km运价增加5万元。
公路运输费用为1单位钢管每公里0.1万元（不足整公里部分按整公里计算）。
钢管可由铁路、公路运往铺设地点（不只是运到点，而是管道全线）。
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
（1）请制定一个主管道钢管的订购和运输计划，使总费用最小（给出总费用）。
（2）请就
（1）的模型分析：
哪个钢厂钢管的销价的变化对购运计划和总费用影响最大，哪个钢厂钢管的产量的上限的变化对购运计划和总费用的影响最
大，并给出相应的数字结果。
（3）如果要铺设的管道不是一条线，而是一个树形图，铁路、公路和管道
构成网络，请就这种更一般的情形给出一种解决办法，并对图二按
（1）的要求
给出模型和结果。
2.1基本符号说明
、基本符号说明与基本假设
S，线段未占用N:
表示该线段是否被占用，N=*
1线段已占用L.）
2.2基本假设
1）假设沿管道或者原来有公路，或者建有施工公路。
2）所有钢管由七个产地供应。
3）钢管在运输过程中不考虑途中运输磨损，即运输的钢管都可用
4）运输过程中不考虑铁路，公路转换时的搬运费用。
5）题目所给数据可靠性高。
三、问题分析和基本思路
3.1问题分析和建模思路
该问题是一个比较明显的优化问题，其中主要包含两部分的优化选择：
一个是运输路线的选择，另一个是产销地的选择。
其中运输路线的选择是本题的关键，不妨将本题看作是一个运费最少的路线选择问题。
由于运输问题中需要考虑单位运价，运输量，运输距离，运输方式等一些因素的影响，而其中运价已经在题目中间接地给出，运价和选择的运输方式以及运输距离，运输量有关。
因此，我们需要考虑解决的因素就变为三个：
运输方式，运输距离和运输量。
因而在建立模型时没有必要考虑所有因素，只需抓住这三个关键因素，进行合理的假设和建模。
建立模型对钢管的运输和订购问题进行定量安排，就是从当前实际的钢管产量和铺设情况出发，选择恰当的订购运输方案，提出合理的订购运输要求和假定，应用科学的方法，预测出该方案需要花费的总资金，使总资金尽量达到最小，降低钢管铺设的成本。
（一）问题1的分析
问题一属于运输类求最短路的问题，题目中给出了七个钢管生产厂，十五个钢管铺设节点以及五十四条可直接连通路线。
我们希望找到一种方案，使从七个钢管厂中的某几个进行钢管生产，然后从该厂开始运输，选取运输路线和十五个节点中的一部分，使在满足题目铺设要求的前提下，取得最小的运输购买费用。
由于题目中说明：
钢管可由铁路、公路运往铺设地点（不只是运到点，而是管道全线）。
因此，当钢管运输到节点后，仍然需要考虑节点到全线的运输方法，我们采用从节点向两个方向运输的方式。
在两次路线选择中分别取最小费用路线，然后将两者结合起来，求的最终路线和订购方案。
因此，我们建立零一规划模型，对问题进行求解。
（二）问题2的分析
问题二是讨论钢厂钢管的销价的变化和钢厂钢管的产量的上限的变化对购运计划和总费用的影响，同时判别哪家钢厂在这两方面发生的变化对购运计划和总费用的影响最大，其实际上是对问题一中的模型进行灵敏度分析，使得钢管销售价和钢管生产上限在发生变化时，能够利用原有模型进行判断，是否需要对购运计划进行修改，以满足新情况下的最优。
由此，我们通过对厂家i的单位钢管销价和厂家i的最大生产量的数值调整，利用lingo功能求的不同情况下的运输方案，对各方案结果进行比照，得出结论。
（三）问题3的分析
问题三是对问题一的扩展，将线性管道铺设改为树形管道铺设图。
我们仍然采取问题一的建立模型的思路，对其中第一部分：
由生产厂家运往铺设节点的线路选择模型保留，对第二部分：
由节点向铺设全程运输模型进行改变，将从节点向两边运输改为在某些节点处向三个方向运输，以满足问题三的要求。
仍然建
立零一规划模型，对问题求解。
同时，对问题三进行钢厂钢管的销价的变化和钢厂钢管的产量的上限的变化对购运计划和总费用的影响的灵敏度分析。
4.模型的建立
4.1模型准备
由于本题中所给的路线比较多，又分为三种，一种是铁路，一种是公路，还有一种是需要铺设的管道线。
因此，为了方便叙述和运算，我们对问题一中每段路进行标号，标号内容如下：
1.线段i=1,2,……,14：
AA2，A2A3，……，A14A15编号；
2.线段i=15,16,……,31：
其他公路线段编号；
3.线段i=32,33,……,54:
铁路编号。
4.
同时，对问题一所给图中的每一个节点进行标号，标号如图所示：
25^
对问题三中每一段路进行标号，标号内容如下：
1.线段i=1,2,,20：
AiA2，A2A3，，A20A21编号;
2.线段i=15,16,……,29：
其他公路线段编号；
3.线段i=30,33,……,52：
铁路编号。
对问题三所给图中的每一个节点进行标号，由于问题三中节点数没有改变,因此标号仍如上图所示：
第一部分：
问题1模型的建立
4.2约束条件的确定
在对钢管订购和运输问题的若干要素进行统一规定后，下面来分析题目中已
知的或隐含的可能约束条件：
（1）.生产厂家个数限制
题目中共有能生产钢管的厂家七家，得生产厂家个数限制：
7
'mi一7
i4
（2）.每个厂家的生产量限制
由题目可知，钢厂i如果承担制造这种钢管，至少需要生产500个单位，同时，每个钢厂在指定期限内能生产该钢管的最大数量和钢管出厂销售1单位钢管价格均可由题目中的表查出。
因此，得到钢管生产量限制：
bmij二Xj二smj
（3）.产销平衡限制
为了节约成本，提高钢管利用率，每个厂家所生产的钢管数量应该全部用于铺设管线。
因此，得到每个厂家的钢管产销平衡限制：
15
'Yj风
（4）.管道铺设限制对于每个卸点来说：
该点向左铺设的管道长
j二
+临近另一点向右铺设的管道长=两点间距离用dj表示对点j来讲，该点到下一卸点的距离，
注意到问题一所给出的图中，在A和Al5两点处，A无需向左运输，Al5无需向右运输，因此对这两处做单独限制：
=0，h=0
为了保证钢管的充分利用，我们要求运到节点a的钢管全部用完，贝U得到约束
条件:
7
Y・=w-t-
J'ijvvjLj
iA
（5）.非负性限制
为了保证模型的解符合实际，具有实际意义，要求从厂家i运往卸点j的钢管量，从卸点Aj往左运的钢管量和从卸点A往右运的钢管量均大于零。
Yj-°，Wj-°，tj-°
4.3目标函数的确定
由题目可知，该问题主要目标是取得运输费用和订购费用总和最小，因此，我们决定将钢管的订购成本和运输成本作为两个目标函数，对其中的运输成本根
据题目要求进行进一步的细化，通过约束条件对目标函数的限制，进行求解，以期得到较为满意的结果。
（1）.钢管的订购费用函数
本题中钢管的订购费用主要由各厂家钢管的销售价来决定，而厂家销售额又是取决于厂家i的实际生产量和厂家i的单位钢管运价。
因此，我们得到问题一中的钢管的订购费用函数：
7
[XiPi
i-1
（2）.钢管的运输费用函数
本题目中对于钢管的运输费用函数的建立有一定的难度，由于题目中要求钢管的运输不只是运到点，而是管道全线，而在选定路线时，我们并不知道每次将钢管运到管道铺设全线的哪一个地方，因此，为了模型建立的方便，我们将该
函数分为两个部分：
a.由钢管生产厂运到钢管铺设节点；b.由铺设节点从左右两个方向向铺设线路运输。
a.由钢管生产厂运到钢管铺设节点
问题一中共有七个钢管生产厂家，十五个管道铺设节点，我们用N表示该线
段是否被占用，用零一规划进行区分，N=丿，若线段占用，贝UN=1,否则N=0,
3154
D表示线段里程数。
由此推的：
a'，DiN为钢管运输中的公路花费，QiDiNi为
i=15^32
钢管运输中的铁路花费。
对两个表达式再次进行处理，应用图论中的最短路原理，将铁路最短路矩阵和公路最短路矩阵，统一成总最小费用矩阵。
我们用Cij表示
从厂家i运往卸点j的最小运输费用，用Yij表示从厂家i运往卸点j的钢管量，
3154
将a7DiNiDiNi进行转化，则该部分的运输费用函数为：
i±5i=32
715
'、CjYij
\±j±
b.由铺设节点从左右两个方向向铺设线路运输
进行完第一部运输过程后，我们将钢管运到了各个节点，下面考虑第二部运输过程节点运输。
对于每个卸点，我们令它可以向左右两个方向进行运输，其中，设从卸点Aj
向左调运的钢管量为tj,则向右调运的钢管量为Wj，不妨先考虑向左调运的情况。
考虑一个节点向左调运时的情况，可能会出现多种调运需求，如需要调运1
个单位钢管，2个单位钢管，3个单位钢管....tj个单位钢管，由于一单位钢管
t（t+1）
等同于运距一公里，则调运总距离为1+2+3+....+tj=-^-^，单位距离公路运
一一t•（t•+1）一
费为a，则一个节点向左调运的总运费表示为：
a-!
—1。
再考虑向右调运的情
况，与向左调运类似，从一个卸点Aj开始向右铺设的费用同理可表示为:
aWj（Wj1）。
则十五个节点向左的总运费为：
jm2
向右的总运费为:
aJWjWj1
所以钢管的运输费用函数可表示为:
综合以上两点，又由于我们的目的是要求总费用成本最低，因此得到问题一的目标函数为：
ij=1j珀iWjW
4.4规划模型
综上所述，我们得到一个非线性规划模型，如下:
乞mi兰7
i4
bmi^Xi^smi
15
无Yj；
j4
<
Wj5=dj
7
S.T
为Yj二Wj+tj
iA
W15=0,右=0
mi=°°r1
Yij“Wj"tj=°
第二部分：
问题3模型的建立
4.5约束条件的确定
问题三与问题一非常类似，其主要区别在于问题三中将线性的管道铺设线变成了树形的铺设线路，多增加了几个节点。
因此，我们仿照问题一中的思路，找出问题三的约束条件。
在问题三的约束条件中，前三个条件与问题一的相同，没有改变，这里不再赘述，唯一有变化的是约束四。
管道铺设限制：
对于每个卸点（a9，a11，a17除外）来说：
该点向左铺设的管道长+临近另一点向右铺设的管道长二两点间距离
用dj表示对点j来讲，该点到下一卸点的距离，
Wjtj厂dj
注意到问题三所给出的图中，在a，a，a21,A18处，A,A18无需向左运
输，a15,a21无需向右运输，因此对这四处做单独限制：
W15=°，t^0，t18=0，W21=0
由图可知，在点a16,A18,A21处，只能向一个方向运输，为了提高利用率，得到以下约束：
W20t21=100，W16二0
为了保证钢管的充分利用，我们要求运到节点a的钢管全部用完，其中，在
a9,a11，a17三点处可以向三个方向运输，则得到约束条件:
（5）.非负性限制
为了保证模型的解符合实际，具有实际意义，要求从厂家i运往卸点j的钢管量，从卸点Aj往左运的钢管量，从卸点Aj往右运的钢管量以及向第三方向运量均大于零。
Yij-0，Wj-0，tj-0，|m-°
4.6目标函数的确定
我们将钢管的订购成本和运输成本作为两个目标函数，对其中的运输成本根据题目要求进行进一步的细化，通过约束条件对目标函数的限制，进行求解，以期得到较为满意的结果。
（1）.钢管的订购费用函数
本题中钢管的订购费用主要由各厂家钢管的销售价来决定，而厂家销售额又是取决于厂家i的实际生产量和厂家i的单位钢管运价。
因此，我们得到问题一中的钢管的订购费用函数：
7
打XiPi
（3）.钢管的运输费用函数
本题目中对于钢管的运输费用函数的建立有一定的难度，由于题目中要求钢管的运输不只是运到点，而是管道全线，而在选定路线时，我们并不知道每次将钢管运到管道铺设全线的哪一个地方，因此，为了模型建立的方便，我们将该
函数分为两个部分：
a.由钢管生产厂运到钢管铺设节点；b.由铺设节点从一个或多个方向向铺设线路运输。
a.由钢管生产厂运到钢管铺设节点
我们用Cij表示从厂家i运往卸点j的最小运输费用，用Yij表示从厂家i运往卸点j的钢管量，则该部分的运输费用函数为：
721
''CijYij
b.由铺设节点从一个或多个方向向铺设线路运输
对于某些卸点，我们令它可以向左右两个方向进行运输，其运费函数关系式与问题一相同。
节点向左的总运费为：
向右的总运费为:
WjWj1
av
ja2
与问题一不同的是，问题三中某些节点可以向三个方向运，由问题一中的求单方
向运费的思路可知，问题三中的这几个节点运费可以表示为
aJ9（l^^+lii（li^^\）^li7（li^1）
■|222
4.7规划模型
从而问题三的模型为：
WjWj1+
2
72121t•t121
minCjYj+*翠+'
i生j吕j总2j吕
al9l91.I11I111.I17I171
222
7
为mi兰7
i壬
bmi-Xsmi
21
三Yi=Xi
j壬
7
送Yij=Wj+tj+|m，|m=°（jH1,17）
i=1
S.T」Wj+t^dj
|9+ti6=42，ti7+wi8=13°，Wi7+ti9=19°
|i1+|i7"O'Ww+|2°=26°，W2°+t21"0°
Wi6二°，Wi5=°，W21=°，ti=°，ti8=°mi=°°r1
5.模型的求解
第一部分：
问题一中模型的求解
5.1总体最小运输费用矩阵的求解
在求解模型之前，先对总体最小运输费用矩阵进行确定，把线段的选择具体
到各S点到各A点的路线的选择。
1.用floyd算法分别求出铁路最短路矩阵T和公路最短路矩阵R
2.用费用转化公式获得铁路最小费用矩阵T2和公路最小费用矩阵R2
3.将两者综合，取值min={T2（i,j）,R2（i,j）}，求得总体最小运输费用矩阵
C（i,j）
总体最小运输费用矩阵C（i,j）如下所示：
A1
A2
A3
A4
A5
A6
A7
A8
A9
A10
A11
A12
A13
A14
A15
170
160
140
98.
20.
21.
64.
121.
S1
.7
.3
.2
6
38
5
3.1
2
2
92
96
106
2
128
142
215
r205I
190
171
95.
71.
114
171.
S2
.7
.3
.2
.6
111
5
86
2
.2
142
146
156
2
178
192
230
220
200
181
121
105
96
86.
48.
82
86
96
111.
118
132
S3
.7
.3
.2
.6
.5
2
2
2
260
250
235
216
156
140
131
116
84.
62
51
61
76.2
83
97
S4
.7
.3
.2
.6
.5
.2
2
255
245
225
206
146
130
121
111
79.
57
33
51
71.2
73
87
S5
.7
.3）
.2
.6
.5
.2
2
265
255
235
216
156
140
131
121
84.
62
51
45
26.2
11
28
S6
.7
.3
.2
.6
.5
.2
2
275
265
245
226
166
150
141
131
99.
76
66
56
38.2
26
2
S7
.7
.3
.2
.6
.5
.2
2
5.2模型求解
从上表可看出，从各S点到各A点共有7*15=105条路线，从中选择路线组合形成最优方案，用lingo求解得最优方案。
问题一的模型求解结果：
综上所述，问题一的钢管订购及运输的最优方案为：
总费用=1278632万元每家厂家的生产量：
S1
S2
S3
S4
S5
S6
S7
800.0000
800.0000
1000.000
0
1297.428
1273.572
0
从每个厂家到每个卸点运送的钢铁管数量:
丫（1,
150.7
183.7
107.0
丫（1,
丫（1,
200丫（1,
265.5丫（2,
179丫（2,
4）
632
368
599
5）
6）
7）
2）
3）
213.9
79.00
157.0
99.90
丫（2,
0丫（2,
丫（2,
300丫（3,
丫（3,
丫（3,
401
735
827
992
4）
5）
8）
3）
4）
5）
321.9
160.1
117.9丫（5,
282.4丫（5,
丫（3,
664丫（5,
丫（5,
丫（5,
415
327
54
13210）
27511）
9）
3）
4）
5）
丫（6,
68.57丫（6,
”丫（6,
丫（6,
“丫（6,
86
333
621
165
10）
24612）
13）
14）
15）
第二部分：
问题二的求解
由问题分析知，问题二是对问题一的模型进行灵敏度分析，因此，在解决问题二时，我们对每个厂家的单位钢管销售价和钢管总产量上限分别进行调整，对比数据，然后判断影响的大小。
5.3单位钢管销售价变化的影响
p增
加
p初
值
总费用
总费用增长
s1
s2
s3
s4
s5
s6
s
7
128.
12530
80
80
1298.7
1272.2
-20%
-2.00%
1000
0
0
0
32
0
0
89
11
144.
12658
80
80
P1298.2
1272.7
-10%
-1.00%
1000
0
0
0
32
0
0
04
96
p
168.
12850
80
80
1297.0
1273.9
5%
0.50%
1000
0
0
1
0
32
0
0
25
75
176.
12914
80
80
1296.5
1274.4
10%
1.00%
1000
0
0
0
32
0
0
16
84
192.
13042
80
80
p1294.9
1276.0
20%
2.00%
1000
0
升级会员 