钢管订购与运输问题

1钢管订购与运输问题摘要天然气管道的订购与运输是建设天然气基础设施的一项非常重要的工作，在理论上更蕴含了丰富的数学知识。本文通过建立数学模型，对钢管的订购和运输问题进行数学描述。针对问题一，首先建立整数非线性规划模型，采用两阶段的的Floyd（最短路径）算法，分别利用铁路距离邻接矩阵和公路距离领接矩阵。利用LING0软件编程，求得最优订购与运输方案，并得到总费用最小为115.8438亿元。进而对Floyd算法进行改进，引入最优权重系数得到改进后的Dijkstra算法即New-Dijkstra算法，对原模型进行处理，从而把两类运输问题转化为了一类运输问题，然后对整数非线性规划模型进行灵敏度分析，其中着重对数据整数化处理与现实问题的误差进行了分析。针对问题二，首先在问题一模型和程序的基础上进行分析和求解。利用问题一中的程序一分别对不同钢厂价格变动进行分析，得到不同钢厂在不同价格变动情况下的总费用和订购、运输方案。其中S1钢厂钢管的销价的变化对购运计划和总费用影响最大。在考虑各钢厂的上限时，首先确定受题中说确定上限影响的钢厂，然后去除上限，观察其总费用和订购、运输费用的变化。经分析可得到S1钢厂钢管的产量的上限的变化对购运计划和总费用的影响最大.针对问题三，对公路和铁路运费浮动设置微小变量，分析相应情况下运购计划和总费用变化。当铁路运费的增浮较小时，一般在1%左右，不超过3%，此时最小总费用小于原运费下的费用。当铁路运费的增浮较大时，一般在5%左右，不小于3%，此时最小总费用大于原运费下的费用，这与一般的预期相一致。当公路运费的价格增加时，最小总费用反而小于原运费下的费用。这与一般预期相悖，但随着增浮增加，总费用增加，但仍小于降价前的费用。针对问题四，首先考虑铁路、公路和管道构成网络状与问题一中线性管道的联系。实际上，问题一是问题四的特例。在问题一模型的基础上建立整数-网络型规划模型，采用改进后的Floyd算法进行模型分析。利用LINGO软件编程，求得最优订购育运输方案，并得到总费用为129.8408亿元。最后给出模型的优缺点与模型的推广。关键字：整数非线性规划模型Floyd算法最优权重系数New-Dijkstra算法整数-网络型规划模型21.问题重述1.1问题背景在经济建设中，经常碰到大量物资调运问题，尤其是我国地域广阔，自然资源丰富且尚待大力开发，但分布又不均衡。我国西部地域广阔，自然资源丰富，有巨大的发展潜力，加快发展西部地区可以促进各种资源的合理配置和流动，为国民经济的发展提供广阔的空间和巨大的推动力量。“西气东输”工程，设计管道长约4000公里。其中生产管道的工厂有若干家，每家的生产能力、订购费用、及相距铺设点的距离都不一样。根据已有的铁路、公路网，应如何制定订购和运输钢管方案，将这些钢管运到沿线各铺设地点而总花费最小就显得尤为重要。1.2问题描述要铺设一条1521AAA的输送天然气主管道,如图一所示。经筛选后可以生产这种主管道钢管的钢厂有126,,SSS。图中粗线表示铁路，单细线表示公路，双细线表示要铺设的管道(假设沿管道或者原来有公路，或者建有施工公路)，圆圈表示火车站，每段铁路、公路和管道旁的阿拉伯数字表示里程(单位km)。为方便计，1km主管道钢管称为1单位钢管。一个钢厂如果承担制造这种钢管，则该钢厂在指定期限内最小生产600个单位，最大生产is个单位，钢管出厂销价1单位钢管为ip万元，如下表：i123456is15008001500250028003000ip1501601551501551551单位钢管的铁路运价如下表：里程(km)≤300301～350351～400401～450451～500运价(万元)2024273032里程(km)501～600601～700701～800801～900901～1000运价(万元)36455358601000km以上每增加1至100km运价增加5万元。3
公路运输费用为1单位钢管每公里0.1万元（不足整公里部分按整公里计算）。钢管可由铁路、公路运往铺设地点（不只是运到点1521,,,AAA，而是管道全线）。（1）建立数学模型，制定合理的钢管订购和运输计划。（2）请就（1）的模型分析：哪个钢厂钢管的销价的变化对购运计划和总费用影响最大，哪个钢厂钢管的产量的上限的变化对购运计划和总费用的影响最大，并给出相应的数字结果。（3）当公路和铁路运费浮动不超过5%时，讨论运购计划和总费用变化情况。（4）如果要铺设的管道不是一条线，而是如图二那样，铁路、公路和管道构成网络，请给出图二的解决办法（1221,,,AAA）。A1325801010315012427510881070627050204030450120311750606194205210680480320220230420500620306195202720690520180680462160330160110280115011501250A2A3A4A5A6A7A8A9A10A11A12A13A14A15S1S2S3S4S5S6图一42.问题分析2.1问题一的分析对于问题一，所涉及的是6家厂商向15个关节点提供钢管，求费用最小时钢管订购和运输计划的优化问题。在这个问题中关键是求各厂商到各关节点的最短路径和各厂商的产量分配，在求解时，要注意铁路和公路的区别，故不能直接用最短路径算法求解，此外还要注意厂商的最低产量为600或为0.2.2问题二的分析对于问题二，需要根据问题一所建立的整数非线性规划模型和求解的最优方案进行分析。主要分析两个方面，在其他因素不变的情况下，钢厂钢管的销价的变化对购运计划和总费用影响，以及钢厂钢管的产量的上限的变化对购运计划和总费用的影响，并求出影响最大的钢厂。2.3问题三的分析对于问题三，在其他因素不变的情况下，当公路和铁路运费浮动不超过5%时，考虑订购和运输方案的变化，以及最小总费用的变化。我们可以分别给铁路运费和公路运费一个微小的变量，来考察其对订购和运输方案的影响。2.4问题四的分析5对于问题四，是在问题一的基础上做出了一点改动，将问题一中的线性管道改为了网络状，而其他条件均不发生改变，要求计算此情况下的管道订购和运输方案。实际上，问题一是问题四的特例。所以，在问题一模型和算法的基础上，对问题四进行建模和求解。3.模型假设与符号系统3.1模型的假设1）假设题中所给数据正确且合理。2）考虑火车运载和汽车运载的装卸费用；3）沿铺设管道边或者原来有公路，或者建有施工公路，可以运送所需钢管；4）管道衔接紧密，即要铺设的管道线路总长为钢管总长；5）钢管在铺设时，先将钢管运到结点处，再由结点处向左右两方相邻点铺设；6）运送的钢管路途中没有损耗；7）在具体铺设每一公里时，我们只把钢管运到每一公里结束的地方，再沿管道铺设，具体的铺设费用我们不予考虑，只考虑运输费用；8）设每段待铺设钢管均是整公里长度，不存在小数．3.2符号系统符号意义ijx表示由钢管厂iS运送到结点jA处的钢管数量ijc表示单位钢管由钢厂iS运送到结点jA处的最小费用，包括订购费用和运输费用（万元/单位）is表示钢管厂iS生产钢管数量的上限jT表示结点jA和1jA，之间待铺管道的长度；jy表示从结点jA，开始向右铺设的管道长度(1jA方向)ip表示向钢管厂iS订购钢管的单位价格（万元/单位）ir表示第i家钢管厂iS生产或者不生产钢管，其中1ir,表示钢管厂iS生产钢管；0ir，表示钢管厂iS不生产钢管C总费用（万元/单位）61C钢管从钢厂iS运抵jA所需的费用2C钢管运抵各节点jA后,再运到具体铺设地点的费用4.问题一的建模与求解4.1问题分析对于问题一，经仔细分析，可将问题一分为以下三个部分:1）各个工厂(iS点)生产一定数量的钢管2）把钢管从工厂(iS点)运送到铺设管道的关节点(jA点)3）从关节点(jA点)将管道运至铺设地点.问题一的目的是寻求最优的订购和运输方案，即使总费用最小。总费用可以分成两部分：第一部分为钢管从钢管厂iS运到结点jA的运费（包括订购费用），第二部分为将钢管从结点jA运到每个具体铺设点的运费．根据问题一中所给出的数据,我们可以计算出由iS经单位运费最小路线运至jA点时单位钢管的费用(即运费与出厂销价之和ijc).4.1.1对公路和铁路运费函数的分析由于公路运费函数是运输里程的线性函数，具有可加性；铁路运费函数是运输里程的分段函数，铁路和公路组成的混合交通网的费用函数具有不可加性．所以，不能直接利用最短路算法来求最小购运费用矩阵，需先对铁路、公路网进行处理，再运用最短路算法求出从钢管厂iS到结点jA，运送单位钢管的最小购运费用ijc，由于从钢管厂iS运送到结点jA的钢管数量为ijx，因此从各钢管厂iS将所订购的钢管沿费用最小的路线运到结点jA的总购运费用为61511ijijijcx．4.1.2对钢管铺设途中运费函数的分析设一段待铺管道1jjAA，其长度为jT，每单位长度钢管的运费为0．1万元／7公里．运至jA结点处的钢管向右铺设了jy单位长度的管道，而运至1jA结点处的钢管向左铺设了数量为jjTy单位的钢管．因此jA结点向右铺的钢管数量的变化为：,1,2,......2,1jjjyyy是一个等差数列。则铺完jy单位管道所需运费为：0.1*1......210.051jjjjyyyy(1)同理，可以计算出1jA结点向左铺的运费：0.05()(1)jjjjTyTy综上可得，钢管的铺设可以简化为在每个铺设结点处钢管以等差递减数列铺设，从而1jjAA段的铺设途中运费可表示为：0.0511jjjjjjyyTyTy4.2模型的建立4.2.1决策变量我们首先引入一组0-1变量126,,...rrr其中ir表示钢厂iS是否承担制造这种钢管.如果钢厂iS承担制造这种钢管,则1ir,否则0ir.所有的钢管,都是先运到1215,,......AAA后,然后转运到其它地方,或者在包含jA的一个区段内铺设.我们设从钢厂iS运抵jA且在包含jA的一个区段内铺设的钢管数量为ijy,这里i=1,2,...6;j=1,2,...15.从而，我们引入了两组决策变量(1,2,...6)iri，(1,2,...6;1,2,...15)ijyij4.2.2目标函数问题1的目的是寻求好的订购和运输方案,使得总费用最小。由上面分析知，总费用可以分成两部分。第一部分包括钢管的订购费用和钢管从钢厂运抵各节点所需的运费；我们用ijc来表示单位钢管从钢厂iS运抵jA所需的最小订购和运输费用，则第一部分费用为：615111ijijijCcx（2）第二部分费用是指钢管运抵各节点后,再运到具体铺设地点的费用：15120.0511jjjjjjjCyyTyTy（3）8则总费用为:12CCC(4)4.2.3约束条件首先,由于一个钢厂如果承担制造这种钢管,则至少需要生产600个单位,且钢厂iS在指定期限内能生产钢管的最大数量为is个单位.所以,可得到一下约束条件：151600iijiijrxsri=1,2,...6（5）铺设一条1521AAA的输送天然气主管道，总里程数为5246，所以：615115246ijijx（6）运抵jA的钢管总数量,等于向包含jA的区段铺设的里程数,那么应有：6111ijjjjixyTyj=1,2,...15（7）4.2.4数学模型根据以上分析，建立问题一整数非线性规划模型：61515111min0.0511ijijjjjjjjijjcxyyTyTy(8)151600iijiijrxsri=1,2,...,66111ijjjjixyTyj=1,2,...,15S.t615115246ijijx(9)00150,0,0Tyy0,1iri=1,2,...