数学建模优秀论文
钢管的订购和运输模型
周小云 崔新锋 荆璐
摘 要 本文讨论了钢管订购和运输最小费用问题。
针对问题一,以钢管订购和运输的总费用最小为目标函数,以厂家生产钢管数量的有限性及供需平衡为约束条件,建立非线性规划模型。采用Floyd算法求出铁路网和公路网各点间最短路线矩阵,利用Matlab软件计算得到最小运输费用矩阵cost(i,j),结合订购费用和铺设费用,使用Lingo软件对目标函数求解。
800,得到最优钢管订购方案为: 向厂家S1,S2,S3,S4,S5,S6,S7分别订购800,1000,0,1277.739,1293.26,0单位个钢管。最小的总费用为1281354万元。
针对问题二,在问题一的模型求解之后,对钢厂Si生产钢管的销价或其产量的上限进行变化并在此基础上继续运算,比较数据分析以上两个条件的变化对购运计划和总费用的影响程度,实则是对问题一规划模型的灵敏度分析。确定了当厂家S6的单位钢管销价变化时对总费用影响最大,厂家S7的单位钢管销价变化对购运计划影响最大。 厂家S1的钢管总产量上限变化对总费用影响最大,各厂家的钢管总产量上限变化对购运计划基本不产生影响。
针对问题三,与问题一不同之处在于问题三中的钢管铺设路线变成了树形,仍然采用问题一的建模思路,只是节点A9,A11,A17向三个方向铺设,对这三个节点另加讨论。用Lingo软件求解得到最优的钢管订购运输方案:向厂家S1,使总费用达到最小。 S2,S3,S4,S5,S6,S7分别订购与模型一相近数量的钢管,
关键词 非线性规划模型;Floyd算法;最小运输费用矩阵;Lingo软件
一.问题的重述
要铺设一条A1A2A15的输送天然气的主管道, 如图一所示(见附录图一)。经筛选后可以生产这种主管道钢管的钢厂有S1,S2,S7。为方便计,1km主管道钢管称为1单位钢管。
一个钢厂如果承担制造这种钢管,至少需要生产500个单位。钢厂Si在指定期限内能生产该钢管的最大数量为si个单位,钢管出厂销价1单位钢管为pi万元,如下表:
铁路运输费用1000km以上每增加1至100km运价增加5万元。
公路运输费用为1单位钢管每公里0.1万元(不足整公里部分按整公里计算)。
(1)制定一个主管道钢管的订购和运输计划,使总费用最小(给出总费用)。 (2)就(1)的模型分析:哪个钢厂钢管的销价的变化对购运计划和总费用影响最大,哪个钢厂钢管的产量的上限的变化对购运计划和总费用的影响最大,并给出相应的数字结果。
(3)如果要铺设的管道不是一条线,而是一个树形图,铁路、公路和管道构成网络,请就这种更一般的情形给出一种解决办法,并对图二(见附录图二)按(1)的要求给出模型和结果。
二.问题分析
在题中给定的各段钢管需求量,各厂生产钢管数量的上下限以及公路,铁路运输费用的前提下建立关于总费用最小的优化模型。
针对问题一,铺设管道总费用包括三部分,分别为:订购费用,运输费用,铺设费用。要使三者费用之和达到最小,必须选择最优的订购方案和运输路线。从厂家提供的管道数量的有界性,铺设节点对管道数量的使用必须达到供求平衡,从某一节点向右铺设管道长度与下一节点向左铺设的长度必须恰好等于这两节点之间的距离,在这些约束条件下建立关于铺设管道总费用最小为目标函数的非线性规划模型,再利用Lingo编程求出总费用的最小值以及向每一厂商订购钢管的具体数量。
针对问题二,在问题一的模型求解之后,对钢厂Si生产钢管的销价或其产量的上限进行变化并在此基础上继续运算,对比数据,分析以上两种变化对购运计划和总费用的影响程度,这一过程实则是对问题一规划模型进行的灵敏度分析。
针对问题三,当铺设管道不是一条直线,而是树形管道铺设图时,铺设管道总费用仍然由订购费用,运输费用,铺设费用三部分组成,且由厂家到铺设节点最优路线选择并未改变,只是铺设过程中对于节点A9,A11,A17不再只是向左右铺设而是向三个方向铺设。所以其它两部分费用计算方法仍采用模型一的思路,只是对节点A9,A11,A17分开讨论。
三.基本假设
1. 假设运到Aj的钢管,只能铺设Aj1到Aj1之间的天然气输送管道。否则,总2. 3. 4. 5. 6.
可以调节方案,使得路线最短;
将钢管每隔一公里沿着运送方向放置一公里所需的材料;
只考虑订购费,运输费和铺设费,不考虑铁路和公路的中转费,装卸费; 所需的钢管只能由这七个钢厂提供,即对于这七个钢厂而言或者不生产或者至少生产500个单位;
将每一单位的管道看成一个需求点,即向每一点运送钢管; 假设沿管道或者原来有公路,或者建有施工公路。
四.符号说明
5.1对于线形管道铺设最优的订购和运输计划
任意一钢厂Si的总产量是其向15个铺设节点运送钢管的数量之和xij,其
j115
总产量是有数量限制的,即不生产或者满足生产的上下限。所以得到以下关于产量的约束条件:
Qixij0[500,si]
j115
i1,27 (1)
运送到Aj的钢管,只能铺设Aj1到Aj1之间输送天然气的管道。为了节约资源每个厂家运送到Aj的钢管数量应该全部用于铺设管道,因此所有钢厂运送到节点Aj的钢管总数量xij必须等于Aj分别向左右铺设所需钢管数量之和。为此
i17
建立了供需平衡的约束条件:
x
i1
7
ij
zjyj
j1,215 (2)
由AjAj1的长度Dj与节点Aj向右、Aj1向左铺设的距离之和相等,且对节点A1与
A15并不存在左右铺设管道这种情况,由此可建立如下约束条件:
Djzjyj1
y10
z015
j1,214
(3)
在上述约束条件下,铺设钢管总费用可分为三部分,分别是订购钢管费用B,公路与铁路运输费用C,铺设费用E(节点Aj到铺设地点的运输费)。 订购费用B是指向七个厂家购买钢管时所支付总的原材料费用,其中厂家Si生产的钢管总数量为xij,它所获得的费用为pixij。故得订购钢管总的费用
j1
j1
15
15
为:
15
Bpixij (4)
i1j1
总的运输费用C是由公路运输费用与铁路运输费用组成。公路运输费用是距离的线性函数,而铁路运输费用是距离的分段函数,为非线性的,所以铁路费用不具有可加性。因此用cost(i,j)表示从厂商Si到节点Aj采用最短路线运送一个
7
单位钢管所需的运费。将运输路线分为铁路与公路利用Matlab程序和flody算法中邻接矩阵分别进行几次矩阵优化并进行整合后得出每一个厂商Si选择最优路线运输钢管到每一个节点Aj所需的最少费用:
Ccost(i,j)xij (5)
i1j17
15
对于节点Aj,它的铺设费用为向左,向右铺设费用的和,将该问题简化为每隔一公里放置一个单位的钢管,并且不考虑一公里之内从卸货地点到铺设地点的运费。只考虑向左铺设的情况,每单位钢管运输的距离成等差数列变化即
yj
因为公路计费方式是不足1,2,3yj所以总的运输距离为12yj(yj1)。
2
整公里按整公里计算,故对15个节点的铺设距离先取整进一再计算出总的铺设费用为:
0.115
E([yj2yjzj2zj]1) (6)2j1
由以上的分析讨论可建立关于钢管运输费用最小的非线性规划模型:
715715
0.115
minBCEpixijcost(i,j)xij([yj2yjzj2zj]1) (7)2j1i1j1i1j1
15
i1,27xij0[500,si]
j17
j1,215xijzjyj
i1s..t
Dzjyj1j1,214j
y10
z150x0,yj0,zj0ij
5.3对于树形管道铺设最优的订购和运输计划
问题三将问题一中的线形管道变成了树形管道,问题一的约束条件(1)没有改变。则问题三的产量约束条件为:
21
Qixij0[500,si]
j1
i1,27 (8)
除了节点A9,A11,A17其它节点供需平衡约束条件都与模型一类似,而对
于节点A9,A11,A17铺设管道时分三个方向,故有以下约束条件:
7
j9,11,17xijzjyj
1
i (9) 7
xzyvj9,11,17ijjjji1
对于节点A1,A15,A16,A18,A21只能朝一个方向铺设,且问题三相对于问题一新增节点铺设距离满足以下约束条件:
j1,214Djzjyj1
y10,z150,y210,y180,z160
(10)
vy42,vv10,yz[1**********]916
zy190,zy260,zy100
192020211719
钢管订购费用,运输费用与问题一类似分别为:
721
Bpixij (11)
i1j1
Ccost(i,j)xij (12)
i1j17
21
由铺设节点向多个方向铺设过程中,向左和向右铺设总运费为类似于模型
一,而对于节点A9,A11,A17考虑第三个方向铺设总费用,所以对于21个节点而言总的铺设费用为:
vi0.1210.122
+ E(yyzz)2(vi1) (13)jjjj2i9,11,17
2j1
由以上的分析讨论可建立关于铺设树形钢管订购及运输最小费用的非线性规划模型:
721
vi0.1210.122
min[pixijcost(i,j)xij](yyzz)(vi1) (14)jjjj
222i1j1j1i9,11,17
21
i1,27Qixij0[500,si]
j1
7
j9,11,17xijzjyj
i17
j9,11,17xijzjyjvj
i1j1,214 s..tDjzjyj1
y10,z150,y210,y180,z160
v9y1642,v17v1110,y17z18130zy190,zy260
1920
1719
z20y21100
zj0,yj0v0,x0
ijj
六.模型求解
6.1模型一的求解:
针对问题一中关于最小费用的非线性模型,使用Flody算法及Matlab软件计算出单位钢管从厂家Si到节点Aj最小的运输费用cost(i,j)。然后利用Lingo软件求解上述优化模型。具体求解步骤分为以下两部分: 1.最小运输费用计算
总体的最小运输费用cost(i,j)可以由公路最小运输费用与铁路最小运输费用求和得到,于是利用Flody算法,先建立关于铁路运输最短路径的矩阵T,再根据表二(1单位钢管的铁路运价)来编写计算铁路运费的程序得到铁路运输1单位钢管最小费矩阵T2,同理编程并得到公路运输1单位钢管最小费用矩阵R2(由于取整运算程序编写较为复杂,在此程序中我们将模型约束条件(6)予以简化),比较对应分量T2(i,j)与R2(i,j)的大小,最终建立单位钢管从厂家Si到节点Aj最小的运输费用cost(i,j)。(程序见附录)
cost(i,j)矩阵如下表所示(表三):
表三 单位钢管从Si运输到Aj的最小运输费用(单位:万元)
2.最优解计算:
应用Lingo软件对钢管运输最小费用的非线性规划模型进行求解得到具体铺设方法(表四)。
对于节点Aj,运送到此节点的钢管分别向左铺设yj个单位,向右铺设zj个单位,按下表所得到的数据来铺设天然气输送管道,可达到最优的铺设计划,此时所需费用最少。如节点A9可向左铺设159个单位的钢管,向右铺设505个单位的钢管。
表四 节点A的铺设方法
选定的厂家S1,S2,S3,S5,S6向各个节点运输钢管量只有满足下表时才可能达到费用最少。
表五 厂家向各节点运送钢管数量
Q1800.00,Q2800.00,Q31000.00,Q40 Q51277.739,Q61293.26,Q70
即分别向S1,S2,S3,S5,S6厂家订购800,800,1000,1277.739,1293.26单位个钢管。并未向S4和S7订购任何钢管。这样才能保证总的支付费用最小。 只有订购和运输按照以上提供方案来执行时,会使总费用最少为:1281354万元。
6.2模型三的求解:
对图二分析可知,在模型一的基础上新增了四条管道,并且把二条公路该修为管道,再求铁路最短矩阵时同模型一一样,只是在求公路最小矩阵时将被改的公路所属的矩阵元素去除,从而用Matlab软件及Flody算法得到新的最小费用矩阵(具体程序见附录),即表六:
表六 单位钢管从Si运输到Aj的最小运输费用(单位:万元)
的各项费用,再利用Lingo软件以订购运输铺设三者费用之和最小为目标函数,求出最小总费用。在此求解过程中基本与模型一类似,不同之处在于计算铺设费用时,此模型增加新的三分支节点,对此新增一个变量使原来的二维变量变为三维变量,再利用分类数学思想建立不同类别处节点的约束条件。
七.灵敏度分析
由问题分析知,问题二是对问题一的模型进行灵敏度分析,因此对每个厂家的单位钢管销售价和钢管总产量的上限分别进行调整,对比数据,然后分别判断哪个钢厂钢管的销价及钢管产量上限的变化对购运计划和总费用的影响最大。 7.1 单位钢管销售价变化的影响
厂家S6的单位钢管销价变化对总费用影响最大,厂家S2销价变化对总费用基本不产生影响。厂家S7的单位钢管销价变化对购运计划影响最大,而厂家S1的销价变化基本上不改变购运计划。
由上表可知,厂家S4,S5,S6,S7的钢管总产量上限变化对总费用没有影响。厂家S1的钢管总产量上限变化对总费用影响最大,厂家S2S3上限的变化对总费用有一定影响。 各厂家的钢管总产量上限变化对购运计划基本不产生影响。
八.模型的评价与推广
8.1模型的优缺点
1. 在问题一的模型中,计算目标函数时,将路径的选择分成两大部分处理,先将货物运到节点,再从节点向全线运输,将问题简化。
2. 在解决第一个问题的运输费用时,把铁路和公路分开计算,最后进行统一,简化了运算。
3.从节点向铺设点运输时,将问题简化为每隔一公里放置一单位的钢管,便于计算铺设费用。
4. 在分析问题一的灵敏度时,钢厂的销量和产量上限变化范围太小,结果的分
析有一定的局限性。
5. 本文的假设比较多,在实际生活中,要考虑中转费,装卸费。 8.2模型的推广
1.建立该模型的思想不仅可以用于钢管的运输铺设天然气管道,而且可以用于煤炭的运输来提供电力。
2. 由于我们在建立约束条件时要求从节点向其他方向运输时,相邻两节点运量加和恰好等于两点间线路距离,因此忽略了跨节点运输的情况,而这里面可能出现较之更优的方案。
参考文献
[1] 谢金星,薛毅,优化建模与LINGO软件,北京:清华大学出版社,2005 [2] 姜启源,数学模型(第三版),高等教育出版社,2003
[3] 李建平,大学计算机基础教程[M],北京:科学出版社,2006.
[4] 谢金星,薛毅.《优化建模与LINGO/LINGO软件》.北京:清华大学出版社,2005
附录
图中粗线表示铁路,单细线表示公路,双细线表示要铺设的管道(假设沿管道
7
7
或者原来有公路,或者建有施工公路),圆圈表示火车站,每段铁路、公路和管
道旁的阿拉伯数字表示里程(单位km)。
在模型建立阶段为了为了利用Flody算法,将图各节点进行标号,从而求出图一,图二的邻接矩阵。为以下编写程序做铺垫。