钢管的订购与运输

钢管的订购与运输摘要：本文目的为求最小费用的的优化问题。关键是要根据题目的要求，找出总费用、钢管的订购和运输三者之间的关系。首先，根据图论中求最短路径的方法，对图中各结点进行编号，将各点间的距离转化成各点所需的运输费用，好形成一张费用网。运用Floyd算法，求出各点之间的最小费用矩阵及其最小费用路线矩阵，再从中提取出管道各枢纽到钢厂的最小费用矩阵及最小费用路线。然后，将订购的钢管按最小费用路线运输到各枢纽点，再由各枢纽点向邻接边进行铺设。最后，通过计算向两边铺设的总费用进行二次优化。对模型的灵敏度分析，由于最小总费用没有明确的表达式，无法通过求偏导来解决问题。故我们采用分析的方法，对最终得到的数据进行分析。对于模型的推广，将铺设管道现改成树形结构，可以通过扩展问题一的模型来解决，把运送到的钢管改为向连接边的各个方向铺设即可。关键字：Floyd算法最小总费用二次优化一、问题重述要铺设一条1521AAA的输送天然气的主管道。经筛选后可以生产这种主管道钢管的钢厂有721,,SSS。图中粗线表示铁路，单细线表示公路，双细线表示要铺设的管道(假设沿管道或者原来有公路，或者建有施工公路)，圆圈表示火车站，每段铁路、公路和管道旁的阿拉伯数字表示里程(单位km)。为方便计，1km主管道钢管称为1单位钢管。一个钢厂如果承担制造这种钢管，至少需要生产500个单位。钢厂iS在指定期限内能生产该钢管的最大数量为is个单位，钢管出厂销价1单位钢管为ip万元，如下表：i1234567is80080010002000200020003000ip1601551551601551501601单位钢管的铁路运价如下表：里程(km)≤300301～350351～400401～450451～500运价(万元)2023262932里程(km)501～600601～700701～800801～900901～1000运价(万元)37445055601000km以上每增加1至100km运价增加5公路运输费用为1单位钢管每公里0.1万元（不足整公里部分按整公里计算）。钢管可由铁路、公路运往铺设地点（不只是运到点1521,,,AAA，而是管道全线）。（1）请制定一个主管道钢管的订购和运输计划，使总费用最小（给出总费用)。（2）请就（1）的模型分析：哪个钢厂钢管的销价的变化对购运计划和总费用影响最大，哪个钢厂钢管的产量的上限的变化对购运计划和总费用的影响最大，并给出相应的数字结果。（3）如果要铺设的管道不是一条线，而是一个树形图，铁路、公路和管道构成网络，请就这种更一般的情形给出一种解决办法，并对图二按（1）的要求给出模型和结果。二、问题分析本文为求最小费用的的优化问题。在问题一中，关键就是找出总费用、钢管的订购和运输三者之间的关系。首先，我们可以根据图论中求最短路径的方法，对图中各结点进行重新编号，将各点间的距离转化成所需的运输费用形成一张费用网。再运用Floyd算法，求出各点之间的最小费用矩阵及其最小费用路线矩阵，再从中提取出管道各枢纽到钢厂的最小费用矩阵及最小费用路线。然后，将订购的钢管按最小费用路线运输到各枢纽点，再由各枢纽点向邻接边进行铺设。最后，通过计算向两边铺设的总费用进行二次优化。因此，在本题的编程中，我们使用了Matlab中的软件包求出各枢纽点间的最小费用和最小费用路径。对于问题二，是对模型的灵敏度分析，由于最小总费用没有明确的表达式，无法通过求偏导来解决问题。故我们采用分析的方法，对最终得到的数据进行分析。关于问题三，虽然将铺设管道现改成了树形结构，但是仍然可以通过扩展问题一的模型来解决，把运送到的钢管改为向连接边的各个方向铺设即可。三、模型假设及说明假设：2沿管道或者原来有公路，或者建有施工公路。31km的管道钢管称为1单位钢管。4钢管可由铁路、公路运往铺设地点（不只是运到点1521,,,AAA，而是管道全线）。5公路运输时，不足整公里部分按整公里计算。6如果钢厂承担生产钢管，则至少生产500个单位，且不能大于其产量上限。7在铺设过程中，钢管总长和铺设道路总长一样，不考虑钢管连接的损失。8不考虑天气、气候、突发情况及铺设效率对运输及铺设的影响。9每个厂都必须确保有钢管输出。说明：3假设1假定沿管道或者原来有公路，或者建有施工公路，是为了确保钢管能够运送到每个所需的位置。4假设2、4、6是为了简化计算，我们将在模型的误差分析中对这些损失进行考虑。5假设5设定每个钢厂如果要生产的最小值，这是符合实际情况的，以免造成资源浪费。6假设8设定每个厂都必须确保有钢管输出，由于在Matlab中，无法直接处理约束条件：ijijsx152500或0152jijx，为编程方便，我们将其改变为ijijsx152500，即不考虑有钢厂不生产的情况。四、符号说明jA：输送管道（主管道）上的第j个点；15,,2,1jiS：第i个钢厂；7,,2,1iis：第i个钢厂的最大产量；7,,2,1iip：第i个钢厂1单位钢管的销价；7,,2,1iijx：钢厂iS向点jA运输的钢管量；7,,2,1i15,,2,1j1,jjA：相邻点jA与1jA之间的距离；14,,2,1jijy：1单位钢管从钢厂iS运到结点jA的最小总费用，即公路运费﹑铁路运费和钢管销价之和；7,,2,1i15,,2,1jf：总费用jt：在点jA与点1jA之间的公路上，运输点jA向点1jA方向铺设的钢管量；14,,3,2,1j(01t)jn：运输到点jA的总钢管量15....,3,2j五、模型的建立和求解1、计算单位钢管从iS运输到jA的最小费用1）将铁路网络图转化成任意两点的运输费用图由于钢管从iS运输到jA要通过铁路和公路，而公路的收费是分段函数，所以为便于计算，我们先把公路与铁路、铁路与铁路的各结点间的距离直接转化为运输费用，从而得到运输费用图。2）计算单位钢管从iS运输到jA的最小运输费用根据上图，利用Matlab中的软件包和Floyd算法的思想来求得图中任意两点的最小运费矩阵。该算法的基本思想是：直接在图的带权邻接矩阵中用插入定点的方法依次构造v个矩阵)()2()1(....vDDD、、，使最后得到的矩阵)(vD成为图的距离矩阵，同时也求出插入点矩阵以便得到两点间的最短路径。然后从所得矩阵中提取出从iS运输到jA的最小费用矩阵。3）计算单位钢管从iS运输到jA的最小费用由2）可以知道单位钢管从iS运输到jA的最小运输费用，为了模型的简便，我们将把各厂的生产费用转化到运费上。也就是说，在每次从iS运出的运输费用上加上iS厂生产单位钢管的销价ip，从而得到单位钢管从iS运输到jA的最小费用（单位：万元）ijy。图表如下：A2A3A4A5A6A7A8A9A10A11A12A13A14A15S1320.3300.2258.6198180.5163181.2224.2252256266281.2288302S2360.3345.2326.6266250.5241226.2269.2297301311326.2333347S3375.3355.2336.6276260.5251241.2203.2237241251266.2273287S4410.3395.2376.6316300.5291276.2244.2222211221236.2243257S5400.3380.2361.6301285.5276266.2234.2212188206226.2228242S6405.3385.2366.6306290.5281271.2234.2212201195176.2161178S7425.3405.2386.6326310.5301291.2259.2237226216198.21861622、模型的建立由题意可知，总费用可分为两个部分：总费用=运输费用+铺设费用运输费用：考虑钢厂iS向枢纽点jA运输ijx单位钢管，则钢管从钢厂iS运到枢纽点jA所需的费用为ijijyx。由于当钢管运到1A时必须经过2A，所以可不考虑1A，那么所有钢管从各钢厂运到各运输点上的总费用为：ijjiijyx15271。铺设费用：当钢管从钢厂iS运到点jA后，钢管就要向运输点jA的两边1jjAA段和jjAA1段运输（铺设）管道。设jA向1jjAA段铺设的管道长度为jt，则jA向1jjAA段的运输费用为201)21(1.0jjjttt（万元）；由于相邻运输点jA与1jA之间的距离为1.jjA，那么1jA向1jjAA段铺设的管道长为jjjtA1.，所对应的铺设费用为2011.1.jjjjjjtAtA（万元）。所以，主管道上的铺设费用为：1411.1.201201jjjjjjjjjtAtAtt。故，总费用711521411.1.201201ijjjjjjjjjjijijtAtAttyxf015,,2,7,,10500,152,3,j..20)1)((20)1((min1.152171152711411.1.jjjijjijijijjiijijjjjjjjjjjAtjixsxnxtsaxtAtAttf）因此，可建立模型如下：3、模型的求解化简f，可得：)()2022(1,21411,141152711,2jjjjjijjjiijjjjjAAyxtAtf记'fijjjiijjjjjyxtAt141152711,2)2022(现通过Matlab编程，我们可以得出订购方案和'f的最小值，有如下结果：d=1.0e+003*-0.0000-0.00000.00000.00000.00000.00000.00000.10400.00000.00000.0000-0.00000.0000-0.00000.00000.301000.0000-0.0000-0.0000-0.0000-0.0000-0.00000.75000.00000.0000-0.00000.00000.0000-0.00000.00000.6060-0.0000-0.0000-0.00000.00000.0000-0.00000.00000.19400.5000-0.0000-0.0000-0.0000-0.00000.0000-0.00000.20500.00000.50000.0000-0.00000.00000.0000-0.00000.20100.0000-0.00000.5000-0.00000.00000.00000.00000.68000.0000-0.00000.0000-0.0000-0.00000.0000-0.00000.4800-0.00000.00000.00000.50000.50000.00000.00000.3000-0.00000.00000.0000-0.00000.0000-0.0000-0.00000.2200-0.0000-0.0000-0.00000.0000-0.00000-0.00000.21000.00000.0000-0.0000-0.00000.00002.00000.00000.42000.0000-0.00000.0000-0.0000-0.0000-0.00000.67100.5000favl=8.0376e+005即：问题一的订购和调运方案订购量A2A3A4A5A6A7A8A9A10A11A12A13A14A15S15000000050000000000S25000000005000000000S35000000000500000000S45000000000005000000S55000000000005000000S620000000000