钢管订购和运输问题的数学模型

1、钢管订购和运输问题的数学模型摘要 本文根据问题的条件和要求，建立了两个模型，模型一为单目标非线性规划模型；模型二为双容量最小费用循环流模型，并通过求解这两个模型，完整地解决了问题。由于铁路运输费用函数具有不可加性，不能直接应用现有的最短路算法来求铁路和公路交通网中任意两点间最小费用路问题。本文采用了一种启发式递推算法，巧妙地解决了这一问题。在单目标非线性规划模型中，将管道铺设分为两个过程。先将钢管从钢管厂运到管道和路道交叉口，再从交叉口铺设到管道线上。这样，总的运输费用就化为两个过程的运输费用之和。由于本模型的目标函数是非线性的，这里采用遗传算法对其求解。所得问题（1）的最小费用为127.96

2、61亿元。问题（2）的结果为的钢管销售价格的变化对购运计划及总费用影响最大，而的钢管产量的上限变化对购运计划及费用影响最大。把5171公里长的主管道线路按每公里划分一段，分为5171个点，每个点对应一个单位的钢管。从钢管厂运送5171个单位的钢管到5171个点，每个钢厂的容量有上、下限，由此可以将该问题转化为图论中的一个双容量最小费用循环流模型。文中设计了一个近似有效的算法，对该模型进行求解，所得问题（1）的最小费用为128.025亿元；问题（2）的结果与模型一得结果相同，问题（3）的费用为130.9840305亿元。文中对两个模型都作了一定的理论分析，具有较广泛的适应性。由于模型二将连续的管

3、道线简化分成了5171个点，求解所得到的结果稍劣于模型一得结果，但模型二具有较高的理论价值。对于实际中，将一些实际问题抽象简化为数学问题来解决，从方法上具有一定的启发性。最后，对该问题进行了深刻探讨，不仅解决了管道线为树形图的情况，还解决了管道线为一个网络的情况，同时将此问题推广到了一个更一般的网络图问题。对于n=1,n=2的情形已完全解决，对于问题提出了它是一个NP完全问题的猜想。关键词：运输问题 非线性规划双容量最小费用循环流 效益问题1问题的重述要铺设一条的输送天然气的主管道，入附图6-1所示。经筛选后可以生产这种主管道的钢管厂有。图中粗线表示铁路，单线条表示公路，双细线表示要铺设的管道

4、（假设沿管道或者原来有公路，或者建有施工公路），圆圈表示火车站（图中的T（），每段铁路、公路和管道旁的数字表示里程（单位km）。1km主管道成为1单位钢管。如果一个钢管厂承担制造这种钢管任务，至少需要生产500个单位。钢管厂S在指定期限内能生产该钢管的最大数量为s个单位，钢管出厂销售1个单位的钢管为p万元，具体数据如表6-1所示。1个单位钢管的铁路运价如表6-2所示，1000km以上每增加1至100km运价增加5万元。表6-1 钢管厂的销售单价i1234567s80080010002000200020003000p16015515516015515016表6-2 钢管的铁路运输单价里程/km3

5、00301350351400401450451500运价/万元2023262932里程/km5016006017007018008019009011000运价/万元3744505560公路运输费用为1单位0.1万元/km（不足整公里部分按整公里计算）。钢管可由铁路、公路运往铺设地点（不只是运送到,而是管道全线）。需要解决的问题是：（1） 制定一个主管道的订购和运输计划，使总费用最小（给出总费用）。（2） 就问题（1）的模型进行分析，哪个钢管厂的钢管销售价格变化对购运计划和总费用影响最大，并给出相应的数字结果。（3） 如果要铺设的管道不是一条线，而是一个树形图，铁路、公路和管道构成网络，对这种更

6、为一般的情形给出一种解决办法，并对于附图6-2按问题（1）的要求给出模型结果。2.模型的假设 (1)在制定订购钢管计划时，数据加精确到0.001个单位，即精确到米。此假设保证在理论上得到精确的结果。（2）在运输和铺设的过程中钢管数量无损耗。不需要考虑钢管运输过程中除运费外的其他费用。3.符号及文字说明A表示住管道树型图的第j（）个顶点；S表示第个钢铁厂；c表示从S运送一个单位的钢管到A得最小费用；T表示铁路树形图除S外的顶点（具体标号见附图6-1）;U表示钢厂S（）生产这种钢管的数量；t表示第第k（）段管道的长度；v表示铁路、公路和管道构成网络的所有节点；V表示所有v的集合；（y）表示y的小数

7、部分；y表示不超过y的整数部分；“最小费用路”表示从S(i=1,2,)运输1个单位钢管道A（）运输费用最小的路。4.问题的分析无论采用哪一条运输路线，最终铺设到主管线上的每单位钢管均要经过与它所在位置相邻的一个主管道顶点（即运输路线上经过的最后一个主管道顶点）。因此，可将管道的铺设分成两个过程，即可形象地认为先将钢管堆积到主管道顶点A处，再将堆积在A处的钢管沿与其邻接的主管道线进行铺设。4.1 对公路和铁路运输费用函数的分析定义6.1 运输费用Y为线路长度d的函数，对任意三点A,B,C,设d为A,B之间的线路长度，d为点B,C之间的线路长度。若Y（d）+Y（d）=Y（d +d），则称该费用函数

8、具有可加性。否则，即存在d和d，使得Y（d）+Y（d）Y（d +d），则称该费用函数具有不可加性。由此定义可得如下的三个结论：结论1 公路运输费用函数Y（d）为线性函数，具有可加性；铁路运输费用函数Y（d）为分段函数，具有不可加性。结论2 铁路与公路组成交通网的费用函数具有不可加性。如图6-1所示是由公路与铁路组成一段运输线路（细线表示公路，粗线表示铁路），则 Y(AB)=1000.1+20=30, Y(BC)=20+500.1=25,Y(BC)=1000.1+23+500.1=38。显然有Y(AB)+Y(BC)Y(AC)。 图6-1 公路与铁路运输线路示意图结论3 在公路与铁路交通网中，两点

9、间距离最短不一定运输费用最少。一个单位的钢管从S运到A总是存在一条运输费用最小的路，但是由结论3，不能直接应用求两点间最短的算法求S运到A最小费用路径。4.2 对公路运输费用需安公里取整计算的分析 题目要求公路运输费用不足整公里部分按整公里计算。附图6-1中各段公路均为整数，因此，运输钢管到顶点A的过程中存在不足整公里的问题。而将钢管从A沿主管道线路铺设，铺设的长度等于钢管的总长度，可能会出现非整公里的情况，因此，需要从A铺设过程中出现不足整公里的问题，设从顶点A向右沿主管道线铺设y单位（km）钢管。情形一 当y为整数时，铺设费用为y10.1+（y1）10.1+110.1=。情形二 当y为非整

10、数时，铺设费用为y10.1+（y1）10.1+110.1=+在实际计算中，对y为非整数的情况不容易处理，但注意到=，0y<1.当y=0.5时，最大为0.0125，其数值非常小，同样课分析从顶点A向左沿主管道铺设=ty所花铺设费用。其总误差为+=0.3375(万元).而铺设管道费用是一笔相当大的资金，相比之下此误差也微不足道，所以为简化计算，在后面做具体计算时不考虑小数部分影响，即无论y是否为整数，都将铺设费用为。4.3 对钢厂是否承担制造这种钢管的分析 由题意，如果一个钢厂承担制造这种钢管，则该厂至少需要生产500个单位。考虑一个特列，假如该厂S到各顶点A的最少费用均比该厂S的费用低，若

11、该钢厂承担制造这种钢管任务，且在S生产上限允许的条件下，这500个单位的钢管完全由S生产，总费用将会降低，否则该厂S不承担制造这种钢管的任务，总费用将会减少，因此，为使总费用最少，要充分考虑应由哪些钢厂承担制造这种钢管的任务，哪些钢厂不承担制造任务，根据题意的要求，建立如下两个模型：模型一：单目标非线性规划模型；模型二：双容量最小费用循环流模型。5模型的建立5.1 模型一：单目标非线性规划模型因为钢厂数目较少，不妨设7个钢厂都承担制造这种钢管任务，在这种情况下，分析所得结果，再决定哪些钢厂不应承担制造这种钢管的任务。用变量x表示由钢厂S运往A点的钢管数量。变量y（j2）为从A沿主管道线向右铺设

12、的钢管数量。针对问题（1），根据问题的条件和要求，我们可以的得到：钢厂生产这种钢管数量上下限的约束为， 对于（）的约束为， 由于堆积在A处的钢管必须全部铺设到与其邻接的主管道线上，于是对于节点A有；对于其他节点A（）有，对于节点A有 问题的总费用Q由三部分费用组成，即包括购买钢管的费用M，从钢厂到主管道线上各节点处的运输费用Y和从各节点向与其邻接的主管道线铺设钢管的费用P，即Q=M+Y+P.事实上，这三部分费用分别为 , .综上所述，得到问题一的目标非线性规划模型;问题 （2） 是在此优化模型中对销售价格和产量上限作灵敏度分析。问题 （3） 的优化模型为s.t.该模型对问题（3）主管道为树形图

13、的情形完全适用，只需增设变量（参附表6-2），其实树形图只是增加了一些叶和节点，对叶与A的约束分析问题（2）中叶A的分析，对节点A，A，A的约束分析同问题（1）中其他节点的分析。2 模型二：双容量最小费用循环流模图 理论准备 定义6.2 设D=（V,A）是一个有向图，l,c是定义在A上的两个非负实函数，并且对一切aA,有l(a)c（a),则称l(a)与c(a）为弧a的下容量与上容量，称D为双容量网络，记D=（V，A；l,c)。 定义6.3 设f为双容量网络D=（v，A；l,a)的弧集A上的一个实值函数，记f=,则称f为D上的一个循环流。如果对任意给定的vA，f满足0，则称f为f通过(v,v)的

14、流量，对每个流量定义一个费用函数w，这时D称为双容量费用网络，记D=(V,A;l,c,w). 定义6.4 如果D上循环f还满足l(a)，对任意,则称f是D的可行循环流。 模型的实现 将钢管运输到铺设地点本来是一个连续的过程，但可以将其离散化，即视为钢管是一个单位接一个单位地运送到铺点地点，每单位的钢管对应于它所要铺设的1km长的主管道。这样在附表图6-1中吧5171km长的主管道线按单位公里来划分，即可分成5171个点任意点到钢厂均有一条最小费用路相连，而一个单位的钢管从出厂的价格为万元，所以，一个单位的钢管从运到任意点的最小费用为“最消费用+一个单位钢管的售价”，记为。 由于题目要求知，要从

15、钢厂订购钢管则至少需订购500个单位，且对最大订购量均有限制，由此，可得到了一个有向图，其顶点集为 V=，其弧集为=A。定义在弧集A上的函数l,c为弧集A上的费用函数w定义为则有函数l的定义可知，D=（v,A；l,c,w)为双容量费用网络，此网络的任一可行流f均可应用于问题（1）的一种方案，则问题(1)转化为在此双容量费用网络中求一个费用最小的可行循环流，即求双容量最小费用循环流问题。问题（2）的钢厂钢管销售价格变化对应于D=（V,A;l,c,w)中上容量函数c的变化，由此，通过分别改变费用函数w与上容量函数C来观察对购运计划和总费用的影响。对问题（3），同问题（1)的分析方法一样，也可将其转

16、化为双容量最小费用循环流问题，亦即不管铺设的管道是线，还是树形图，甚至管道本身就是一个网络，均可同样的转化为最小费用循环流问题，而无本质上的区别。6模型的求解6.1 对求解任意两点间的最小费用路对于附表图6-1和附表图6-2，一个最简单的方法就是用穷举法来实现，即便两点间的所有路，比较其费用，就可以求出最小费用，从而可以求出其最小费用路，但是一个指数时间算法，为寻找公路与铁路网中任意两点之间最小费用路问题，设计提出了一个可行的启发算式递推法，在这里先给出两个概念。定义6.5 一条路中从公路转到铁路或由铁路转到公路的点称为这条路上的转折点。定义6,6 从一点到另一条路中，最后一个中间点称为这条路

17、的前继节点。 算法思想首先分别求出任何两点间只经过公路和只经过铁路的最短路径，进而求出任何两点间只经过铁路和只经过公路的最小费用，其次，以此为基础，求出任一两点之间先经过铁路，且只有一个转折点（先铁路后公路）的最小费用路，以及所需费用值，然后，在已知不超过个转折点的最小费用路相比较，即求出任意两点之间的最小费用路，以及最小费用值。 算法的基本步骤步骤1 将铁路和公路网看成一个图G=（V，E），,并针对铁路和公路分别定义矩阵A=（a)和B=（）为步骤2 利用Floyd算法求出任意两点之间只经过铁路的最短距离矩阵A及前继节点矩阵，同理，求出任意两点之间只经过公路的最短距离矩阵B及前继节点矩阵。步骤

18、3 由矩阵A求出任意两点之间只经过铁路的最小费用矩阵A及前继节点矩阵，同理，求出任意两点之间只经过铁路的最小费用矩阵B及前继节点矩阵。步骤4 对于任意的V，v，记，并记为最小值得t,构成矩阵A和，即为从点v先经过公路再经过铁路到v的最小费用矩阵和前继节点矩阵。记，并记B和从点v先经过公路再经过铁路到v的最小费用矩阵和前继节点矩阵。步骤5 步骤5 以知A和B，对任意的v，vV,记 a=并记a为最小值时的t，从而构成矩阵A和，即点v先以铁路开始经k+1个转折点后到达点v的最小费用矩阵和前继节点矩阵。 注意到，当k为偶数时，第k条边仍为铁路，故为（a+a）;当k为奇数时，第k条边为公路，故为（a+b

19、）。并且可以证明，对任意给定的l,其值相等。步骤6 若k<n-2,则k=k+1，返回步骤5。若k,则执行步骤3。步骤7 比较A, A,。，A和B，B，。B的最小值，即为从v到v的所有路中的最小费用路的费用。利用前继节点矩阵即可以求出最小费用路的路径。6.2 模型一得求解 要确定一个单位钢管从S到A的最少费用路径及最小费用c.由上一节中给出的算法编程进行求解可以得到c，由于模型一所建立的是一个非线性规划模型，而遗传算法是解决非线性规划的一种比较有效的方法，因此这里采用遗传算法对模型一进行求解，编程实现可得到结果。 问题（1）的解 选择种群规模POP SIZE=30，交叉概率pc=0.3，变

20、异率0.5，评价函数中参数a=0.05,经过10000代后得到问题（1）的最优值为128.6201亿元。而且可以得到各钢厂的制造钢管的数量分别为U=800,U=800,U=1000,U=500,U=861,U=710,U=500.这是7个钢厂均承担制造这种钢管时的最小费用，事实上，分析可知，此解并不一定是问题（1）的最优解，实际中可能是在某些钢厂不承担制造钢管的情况下得到问题（1）的解更优。显然U，U，U均已达到上限 ，说明钢厂S,S,S的钢管供不应求，故S,S,S在最优方案中不一定能去掉，而U，U达到了下限，说明钢厂S,S的钢管运往主管道上各顶点费用较高，因而可考虑在S,S或二者均不承担制造

21、钢管任务的情况下，来求问题（1）的最优解。将以上三种情况继续对模型一利用遗传算法求解，则可得到在S不承担制造钢管任务的条件下，最小总费用为127.96661亿元，而且各钢厂的制造数量为U=800,U=800,U=1000,U=0,U=1361,U=710,U=500.具体的订购及运输计划建附表6-1和6-3。6.2.2 问题（2）的求解 令钢厂的销售价格在一定范围（）内变化，可知钢厂S的钢管销售价格p变化对购运计划和总费用影响最大，具体情况如表6-3。表6-3 S的销售价格变化影响结果变化值 10104040总费用变化量71785138600221785654735订购计划的变化U=500U=

22、1571U=1411U=660U=500U=1571U=552U=2000U=519另一方面，从问题（1）结果可知，在总费用最少时，U，U，U远没有达到上限。分别与其上限相差639,1290,2500，所以在较大范围（639）内对S，S,S的上限作变动，对购运计划和总费用不会造成影响，于是只需分别对S,S,S在一定范围（）内作变动，可知S的产量上限的变化对购运计划和总费用影响最大，具体情况如表6-4所示。表6-4 S的产量上限影响结果产量上限120016002000最小总费用123.84161亿元120.0820亿元117.9616亿元订购计划U=1200，U=948， U=723U=925，

23、U=500， U=846U=200，U=586，U=739，U=636，U=7106.2.3 问题（3）的求解 对于模型一。另一遗传算法来求解，同样在S不承担制造钢管的情况下得到问题（3）的最优解，其最小总费用为130.9840亿元。而且各钢厂的制造数量为 U=800,U=800,U=1000,U=772,U=1501,U=500,U=500.具体订购计划及运输计划见附表6-2和附表6-4所示。6.3 模型二的求解对于最小费用循环流问题，在这里设计了一种简单有效的算法。其主要思想是：首先给出一个初始可行流，然后通过转移操作与交叉操作逐渐向最优解逼近。 求解算法步骤步骤1初始化，先给出D的一可行

24、流；步骤2 转移操作，从弧（S,g1），（S，g2），（S,g7）中选出未达到容量上限的弧。改变这些弧的流值，使其向费用最小的目标靠近。步骤3交叉操作，设有弧（gi ，vs）与（gj ，vt）流量均为1，则执行交叉操作，置（gi ，vs）与（gj ，vt）流量为0，置（gi ，vt）与（gi ，vs）流量为1，比较两者的费用，选择其最少的。遍历所有这样流量均为1的弧对，执行交叉操作。步骤4 反复执行转移，交叉操作，直到指定步数。6.3.2 求解实现利用该算法编程实现求解，并结合考虑在某些钢厂可能不承担制造钢管任务的情况下，来求解得到最优解。既有 问题（1）的最小费用为127.9661亿元。 问

25、题（2）的解为S的钢管销售价格的变化对购运计划和总费用影响最大。S的钢管产量上限的变化对购运计划和总费用影响最大。 问题（3）的最小费用为130.9840305亿元。7. 模型的结果分析由问题（1）的求解结果可知，钢厂承担制造这种钢管时，总费用最小。分析一个单位钢管从运到的最小费用矩阵，比较和到的最小费用与（）可知，除了外，其余均有，且对均较大程度地大于同列中某些数。由所有的钢厂，全部承担制造钢管的任务时，其订购方案中=0，即说明不向运送钢管，又的生产上限为2000单位，其值是比较大的，所以由完全承担的生产量将会比生产500单位耗资少。因此，不承担制造这种钢管任务时，其最小费用较低，者也与问题

26、的分析较一致。 在总费用最小的情况下，的生产量均达到他们的生产上限分析矩阵，前8列中每列的值均较小，说明从钢厂，订购钢管到节点,8)的运输费用都比较低。因此，8）将尽可能地从订购钢管。，8）总共至少需要钢管2361单位，故钢厂产量均要达到上限。由问题（2）的结果可知，钢厂的钢管产量的上限变化对购运计划和总费用影响较大，这也是由从到,8)的最小运输费用最少决定的，从图上也可以看出，所处的地理位置距都较其他钢厂都近，且交通方便，利于运输。因此，建议在可能的条件下，由国家投资通过改进钢厂的生产技术等方式提高钢厂的生产量，以节省运输开支。8. 算法的理论分析命题 文中提出的递推算法的时间复杂度为。证明

27、 在算法的步骤1中，利用到了Floyd算法，其时间复杂度为。在步骤2中，需要用递推的方法求，每作一次迭代求解最多需计算2n(n-1)(n-2)次，总共求了n-1次，所以时间的复杂度还是为。另一方面，文中主要运用了遗传算法对模型一进行了求解。遗传算法是一种通过模拟自然进化过程搜索最优解的方法。它能从整个解空间寻找全局最优解，避免只得出局部最优解。因此，这些优美的性质从理论上保证了我们所得模型结果为全局范围的近似最优解。9. 模型的评价及进一步探讨9.1 模型的评价（1） 我们设计了求公路与铁路网络中任意两点最小费用路德一般性算法“递推法”。并证明了该算法的时间复杂度为。（2） 模型一和模型二同样

28、适用于管道、铁路、公路交叉纵横构成任意网络上铺设钢管的问题。例如，如果在附图6-2的基础上增加两条管道路线：与，这样就铺设的管道成为一个含有3个圈得网络。用模型一和模型二对他们进行求解，所得最小费用为132.8816亿元。（3） 由于模型二把一公里看作一个点，相对于模型一而言误差较大，我们给出了一种近似的最优算法，因此结果不如模型一理想。但模型二将一个实际问题抽象为图论中的最小费用循环流问题，具有一定的理论价值和实践意义，这对于一些实际问题抽象为数学理论问题，也具有一定的启发性。9.2 模型的进一步探讨对于题目中引出的公路与铁路交叉网问题，如何确定两点间最小费用路德问题，可以直接将其方法推广到

29、更一般的情形，其推广的方法如下：将网络中所有边分为N类，每一类定义一个价值函数，求G中任意两点的最小价值路；当N=1时就是两点之间最短路问题；当N=2时就是本题目中公路与铁路交叉构成的网络，可以用文中的递推算法求解；当N3时，仍可用该递推算法求解，但此时的算法的时间复杂度由N=2时的多项式时间迅速上升到指数时间，也就是说，对于N3的情形递推算法不再有效。我们对其进行了研究，没有找到多项式时间的算法，也无法证明它属于NP完全问题，所以，我们提出猜想：该问题在N3时是一个NP完全问题。参考文献1刘宝碇，赵瑞清，随机规划与模糊规划。北京：清华大学出版社，1998。2谢政，李建平。网络算法与复杂性理论

30、。长沙：国防科技大学，1995。3E.米涅卡.网络和图的最优化算法.北京：中国铁道出版社，1984.4唐善策等.数据结构用C语言描述.北京：高等教育出版社，1999.附表6-1问题（1）的钢管订购计划表123456711707（1）2157（1）2307（1）2607（1）2557（1）2657（1）2757（1）21603（1）2053（1）2203（1）2503（1）2453（1）2553（1）2653（1）31402（2）1902（2）2002（2）2352（2）2252（2）2352（2）2452 (2)4986（4）1716（4）1816（4）2166（4）2066（4）2166（4

31、）2266 (4)5380（4）1110（4）1210（4）1560（4）1460（4）1560 (4)1660 (4)6205（5）955（5）1055（5）1405（5）1305（5）1405 (5)1505 (5)731（7）860（6）960（6）1310（6）1210（6）1310 (6)1410 (6)8212（8）712（8）862（8）1162（8）1112（8）1212 (8)1312 (8)9642（9）1142（9）482（9）842（9）792（9）842 (9)992（9）10920（10）1420（10）820（10）620（10）570（10）620（10）770

32、（10）11960（11）1460（11）860（11）510（11）330（11）510（11）660（11）121060（12）1560（12）960（12）610（12）510（12）450（12）560（12）131212（13）1712（13）1112（13）762（13）712（13）262（13）382（13）141280（15）1780（15）1180（15）830（15）730（15）110（14）260（15）151420（16）1920（16）1320（16）970（16）870（16）280（16）20（17）附表6 -2问题（3）的钢管订购计划表12345671170

33、721572307260725572607275721603205322032503245325032653314021902200223522252235224524986171618162166206621662266538011101210156014601560166062059551055140513051405150573186096013101210128114108212712862116211121162131296421142482842792842992109201420820620570610770119601460860510330470640121060156096061051037056013121217121112762712162382141280178011808