高教版《数学建模与数学实验(第3版)》管道运输与订购优化模型(CAI)

1钢管订购和运输优化模型要铺设一条1521AAA的输送天然气的主管道,如图1所示(见反面).经筛选后可以生产这种主管道钢管的钢厂有127,,,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，而是管道全线）.2问题：（1）请制定一个主管道钢管的订购和运输计划，使总费用最小（给出总费用).思考题：（2）请就（1）的模型分析：哪个钢厂钢管的销价的变化对购运计划和总费用影响最大，哪个钢厂钢管的产量的上限的变化对购运计划和总费用的影响最大，并给出相应的数字结果.（3）如果要铺设的管道不是一条线，而是一个树形图，铁路、公路和管道构成网络，请就这种更一般的情形给出一种解决办法，并对图2按（1）的要求给出模型和结果.A13258010103120124270108810706270302020304501043017506061942052016804803002202104205006003060195202720690520170690462160320160110290115011001200A2A3A4A5A6A7A11A8A11A911A11A10A11A12A13A14A15S1S2S3S4S5S6S7图13一、基本假设1．沿铺设的主管道以有公路或者有施工公路.2．在主管道上，每千米卸1单位的钢管.3．公路运输费用为1单位钢管每千米0.1万元（不足整千米部分按整千米计算）4．在计算总费用时，只考虑运输费和购买钢管的费用，而不考虑其他费用.5．在计算钢厂的产量对购运计划影响时，只考虑钢厂的产量足够满足需要的情况，即钢厂的产量不受限制.6．假设钢管在铁路运输路程超过1000km时，铁路每增加1至100km，1单位钢管A13258010103120124270108810706270302020304501043017506061942052016804803002202104205006003060195202720690520170690462160320160110290115011001200A19130190260100A2A3A4A5A6A7A8A11A9A10A11A12A13A14A15S1S2S3S4S5S6S7A16A17A18A20(A21)图24的运价增加5万元.二、符号说明：iS：第i个钢厂；7,,2,1iis：第i个钢厂的最大产量；7,,2,1ijA：输送管道（主管道）上的第j个点；15,,2,1jip：第i个钢厂1单位钢管的销价；7,,2,1iijx：钢厂iS向点jA运输的钢管量；7,,2,1i15,,2,1jjt：在点jA与点1jA之间的公路上，运输点jA向点1jA方向铺设的钢管量；14,,3,2,1j(01t)ija：1单位钢管从钢厂iS运到结点jA的最少总费用，即公路运费﹑铁路运费和钢管销价之和；7,,2,1i15,,2,1jjb：与点jA相连的公路和铁路的相交点；15,,3,2j1.jjA：相邻点jA与1jA之间的距离；14,,2,1j三、模型的建立与求解问题一：讨论如何调整主管道钢管的订购和运输方案使总费用最小由题意可知，钢管从钢厂iS到运输结点jA的费用ija包括钢管的销价﹑钢管的铁路运输费用和钢管的公路运输费用.在费用ija最小时，对钢管的订购和运输进行分配，可得出本问题的最佳方案.1.求钢管从钢厂iS运到运输点jA的最小费用1）将图1转换为一系列以单位钢管的运输费用为权的赋权图.5由于钢管从钢厂iS运到运输点jA要通过铁路和公路运输，而铁路运输费用是分段函数，与全程运输总距离有关.又由于钢厂iS直接与铁路相连，所以可先求出钢厂iS到铁路与公路相交点jb的最短路径.如图3图3铁路网络图依据钢管的铁路运价表，算出钢厂iS到铁路与公路相交点jb的最小铁路运输费用，并把费用作为边权赋给从钢厂iS到jb的边.再将与jb相连的公路、运输点iA及其与之相连的要铺设管道的线路（也是公路）添加到图上，根据单位钢管在公路上的运价规定，得出每一段公路的运费，并把此费用作为边权赋给相应的边.以1S为例得图4.6图4钢管从钢厂1S运到各运输点jA的铁路运输与公路运输费用权值图2）计算单位钢管从1S到jA的最少运输费用根据图4，借助图论软件包中求最短路的方法求出单位钢管从1S到jA的最少运输费用依次为：170.7，160.3，140.2，98.6，38，20.5，3.1，21.2，64.2，92，96，106，121.2，128，142（单位：万元）.加上单位钢管的销售价ip，得出从钢厂1S购买单位钢管运输到点jA的最小费用ja1依次为：330.3，320.3，300.2，258.6，198，180.5，163.1，181.2，224.2，252，256，266，281.2，288，302（单位：万元）.同理，可用同样的方法求出钢厂2S﹑3S﹑4S﹑5S﹑6S﹑7S到点jA的最小费用，从而得出钢厂到点的最小总费用（单位：万元）为：表1iS到点jA最小费用A2A3A4A5A6A7A8A9A10A11A12A13A14A15S1320.3300.2258.6198180.5163181.2224.2252256266281.22883022S360.3345.2326.6266250.5241226.2269.2297301311326.23333473S375.3355.2336.6276260.5251241.2203.2237241251266.22732874S410.3395.2376.6316300.5291276.2244.2222211221236.22432575S400.3380.2361.6301285.5276266.2234.2212188206226.22282426S405.3385.2366.6306290.5281271.2234.2212201195176.216117877S425.3405.2386.6326310.5301291.2259.2237226216198.21861622.建立模型运输总费用可分为两部分：运输总费用=钢厂到各点的运输费用+铺设费用.运输费用：若运输点jA向钢厂iS订购ijx单位钢管，则钢管从钢厂iS运到运输点jA所需的费用为ijijxa.由于钢管运到1A必须经过2A，所以可不考虑1A，那么所有钢管从各钢厂运到各运输点上的总费用为：15271jiijijax.铺设费用：当钢管从钢厂iS运到点jA后，钢管就要向运输点jA的两边1jjAA段和jjAA1段运输（铺设）管道.设jA向1jjAA段铺设的管道长度为jy，则jA向1jjAA段的运输费用为201)21(1.0jjjtty（万元）；由于相邻运输点jA与1jA之间的距离为1.jjA，那么1jA向1jjAA段铺设的管道长为jjjtA1.，所对应的铺设费用为2011.1.jjjjjjtAtA（万元）.所以，主管道上的铺设费用为：1411.1.201201jjjjjjjjjtAtAtt总费用为：711521411.1.201201ijjjjjjjjjjijijtAtAttaxf又因为一个钢厂如果承担制造钢管任务，至少需要生产500个单位，钢厂iS在指定期限内最大生产量为is个单位，故ijijsx152500或0152jijx因此本问题可建立如下的非线性规划模型：14157.1.112171151522.1(1)()(1)min(2020j2,3,,155000s.t.01,,7,2,,150jjjjjjjjijijjjiijjiijiijjjijjjjttAtAtfxaxnxsxxijtA或83.模型求解：由于MATLAB不能直接处理约束条件：ijijsx152500或0152jijx，我们可先将此条件改为ijijsx152，得到如下模型：用MATLAB求解，分析结果后发现购运方案中钢厂7S的生产量不足500单位，下面我们采用不让钢厂7S生产和要求钢厂7S的产量不小于500个单位两种方法计算：1）不让钢厂7S生产计算结果：1f1278632（万元）（此时每个钢厂的产量都满足条件）.2）要求钢厂7S的产量不小于500个单位计算结果：2f1279664（万元）（此时每个钢厂的产量都满足条件）.比较这两种情况，得最优解为，121),min(minffff=1278632（万元）具体的购运计划如表2：表2问题一的订购和调运方案订购量A2A3A4A5A6A7A8A9A10A11A12A13A14A15S18000201133200266000000000S28001791114295003000000000S31000139111860006640000000S4000000000000000S5101503582420000004150000S6155600000000035186333621165S700000000000000014157.1.112171152.1(1)()(1)min(2020j2,3,,15s.t.01,,7,2,,150jjjjjjjjijijjjiijjiijijijjjjttAtAtfxaxnxsxijtA