天然气管道订购与运输最优方案建模

天然气管道订购与运输摘要 本文就使西气东输二线工程制定钢管的订购和运输方案总费用最小模型先针对特殊情况，即铺设管道呈一条线的情行，计算出钢管从钢厂经单位运费最小路径运输到施工节点的运输费用矩阵，建立了钢管订购和运输问题的带有0-1整数约束的二次规划模型，从而找到了钢管订购和运输的最优方案，并利用Lingo软件编程求出最小费用为万元。通过灵敏度分析得出钢厂的销价变化对目标函数影响最大，钢厂产量上限的变化对目标函数影响最大，且的产量上限每增加一个单位，目标函数就减少132万元。 对于铺设管道成树形图的一般情形，我们将树形图转化为有向图，建立了与铺设管道为一条线时类似的数学模型，经计算得最小费用为万元。关键字：钢管订购与运输，0-1规划，二次规划模型，灵敏度分析,有向图一、问题的提出要铺设一条从到的天然气管道，经筛选可以生产我们所需要的钢管的钢厂有到。由于生产能力的不同，每个钢厂在指定期限内能生产的钢管最大数量如表所示。一个钢厂若要承担制造这种钢管要求我们至少订购500个单位钢管（1km主管道钢管称为1单位钢管）。不同钢厂出售1单位钢管的价格如表所示。钢管订购后可经铁路，公路运输到要铺设的管道全线。试建立数学模型，制定钢管的订购及运输计划，使总费用最小。在所建立模型的基础上分析哪个钢厂钢管的销价的变化对购运计划和总费用影响最大，哪个钢厂钢管的产量的上限的变化对购运计划和总费用的影响最大，给出相应的数字结果。并就更一般的情形（即所要铺设的管道成树形：铁路，公路，管道构成网络）给出一种解决办法，建立模型，给出结果。二、符号说明2.1模型一、二的符号说明：第个钢厂； : 第个施工节点；: 钢厂在指定期限内能生产该种钢管的最大数量；：一单位钢管从厂运到施工节点的最小运费；：钢厂出售一单位钢管的价格；：钢厂运往施工节点的钢管单位数；：全部钢厂运往施工节点的钢管总量；：施工节点到的路程；：从施工节点向左铺设的长度；：从施工节点向右铺设的长度；：该项工程所需的总费用。2.2模型三的符号说明：第个钢厂； : 第个施工节点；: 钢厂在指定期限内能生产该种钢管的最大数量；：一单位钢管从厂运到施工节点的最小运费；：钢厂出售一单位钢管的价格；：钢厂运往施工节点的钢管单位数；：全部钢厂运往施工节点的钢管总量；：施工节点到的路程；：从施工节点向右铺设的长度；：运抵的所有钢管沿铺设的里程数；:树中的度数;:树中的入度;:树中的出度;：该项工程所需的总费用。三、模型假设1、不考虑火车运载和汽车运载的装卸费用；2、沿铺设管道边或者原来有公路,或者建有施工公路,可以运送所需钢管；3、管道衔接紧密,即要铺设的管道线路总长为钢管总长；4、不考虑其他外界因素对总费用的影响；5、在指定期间内钢管的价格不变，且指定期限即为该工程花费的总时间；6、将一单位管道所在地看成一个需求点，向一单位管道运输钢管即为向一个点运输钢管。四、问题的分析对于本模型的求解，我们可以把总费用分成三部分考虑：钢管订购费用、钢管从钢厂经单位运费最小路运至结点的运输费用、钢管在施工线路上铺设费用。4.1、 对钢管购买费用函数的分析 钢管在各个厂订购的费用是，故购买钢管所花费的总费用是 。4.2、对公路和铁路运费函数的分析由于公路运费函数是运输里程的线性函数，具有可加性。铁路运费函数是运输里程的分段函数，铁路和公路组成的混合交通网的费用函数具有不可加性。所以，不能直接利用Dijkstra 和Floyd等最短路算法来求最小购运费用矩阵。因此，在求解这个问题时，关键是要找到从钢厂到结点的路径，从本题图中可以看到从钢厂直接到结点没有路径可走，到和分别有两条路径可走，到其他路径只有一条路径可走。而本题并不复杂，故可用笔算方法分别算出由钢厂经单位运费最小路运至结点的运输费用。对于有两条路径可选的情况，分别计算出运费并取其最小值即可。4.3、 对钢管铺设过程中运费函数的分析在至路段，由于钢管必须经过才能到达，因此可不考虑，在至的路段任取一点（长度为一公里），我们需要确定的是通过哪个结点运至点使得总运费（包括钢管购买费用、公路铁路运输费用和铺设过程运输费用）最小。结合分析2中得到的数据表格: 若，若，那么通过或两点，费用最小。若，那么分别通过铺设点会更合适，即从每个结点(除了)向两边运输最优。五、模型的建立与求解5.1问题一的模型建立与求解5.1.1模型建立计算4.2中的钢厂经单位运费最小路径运至结点的运输费用，得到从到的最小运费矩阵，最小运费矩阵如下表A2A3A5A6A7A8A9A10A11A12A13A14A15S1160.3140.23820.53.121.264.29296106121.2128142S2205.3190.211195.588.171.2114.2142146156171.2178192S3220.3200.2121105.598.186.248.2828696111.2118132S4250.3235.2156140.5133.1116.284.262516176.28397S5245.3225.2146130.5123.1111.279.257335171.27387S6255.3235.2156140.5133.1121.284.262514526.21128S7265.3245.2166150.5143.1131.299.277665638.2262表一：最小运费矩阵列表在模型的分析中我们已经得到了购买钢管的总费用，钢管从钢厂运到结点的总费用，由于在每个结点处向两边同时铺设，向左边每铺设一千米卸下一单位钢管，故在该结点向左边铺设钢管的总费用是，同理向右边铺设钢管的总费用是，所以铺设管道的总费用即，目标函数为 （1）在每个结点向左铺设的路程与向右铺设的路程的和应该等于该结点处钢 总量，即 （2）在结点向左铺设的路程加上在结点向右铺设的路程应该等于到的路程，即 （3）由于结点，都不向右铺设，故结点向右铺设的量应该等于结点到的路程104，结点向右铺设的量应该等于0，即 ， （4） 每个钢厂提供的钢管量必须大于等于500个单位且不超过钢厂的最大产量或者是0，即或者此处可采用0-1整数规划，即设，则表达式可改为 （5）所以该题所建立的数学模型是:目标函数 （6） (7) 5.1.2模型求解以上得到的模型属于有0-1规划的二次规划模型，我们利用Lingo软件求解得到最优解为万元。并且得到订购和调运方案，如表二S1S2S3S4S5S6S7A2017900000179A3028913808100508A5335321980519001084A6200000000200A7265000000265A8030000000300A9006640000664A10000035100351A11000041500415A120000086086A13000003330333A14000006210621A15000001650165订购量800800100001366120505171表二：订购和调运方案图一：路线图1具体调运方案:A1不向任何厂订购;A2向S2订购179单位钢管,路线为:S2idbaA2.A3向S2订购289单位钢管,路线为:S2idbcA3;A3向S3订购138单位钢管,路线为:S3kidbcA3;A3向S5定购 81 单位钢管,路线为:S5nmlkidbcA3;A4不向任何厂订购;A5向S1订购335单位钢管,路线为:S1hfeA5;A5向S2订购 32 单位钢管,路线为:S2iS1hfeA5;A5向S3订购198单位钢管,路线为: S3kiS1hfeA5;A5向S5订购519单位钢管,路线为:S5nmlkiS1hfeA5;A6向S1订购200单位钢管,路线为:S1hfeA6;A7向S1订购265单位钢管,路线为:S1A7;A8向S2订购300单位钢管,路线为:S2iA8;A9向S3订购664位钢管,路线为:S3kA9;A10向S5订购351单位钢管,路线为:S5nmlA10;A11向S5订购415单位钢管,路线为:S5nA11;A12向S6订购86单位钢管,路线为:S6rqopA12;A13向S6订购333单位钢管,路线为:S6rqA13;A14向S6订购621单位钢管,路线为:S6A14;A15向S6订购165单位钢管,路线为:S6rtA15;5.2问题二模型建立与求解5.2.1销价变化的灵敏度分析当钢管的销价变化时,通过对其相应的最小总费用及购运计划的分析.钢厂的销价变化对其相应的最小费用及购运计划的影响最大，费用变化见表三销价变化对总费用影响表价格(万元)159160161总费用（万元）价格(万元)154155156总费用（万元）价格(万元)154155156总费用（万元）价格(万元)159160161总费用（万元）价格(万元)154155156总费用（万元）价格(万元)149150151总费用（万元）价格(万元)159160161总费用（万元）表三：销价变化对总费用影响表从表中可见销售价格增加一万元，目标函数（总费用）会增加1202万元。实际上价格最小而且被订购的量未达到生产上限，其销价的变化对目标函数影响最大是可以被解释的，这也证明了我们模型的正确性。5.2.2产量上限变化的灵敏度分析通过Lingo对模型求解的结果分析，当厂产量上限的变化对目标函数（总费用）影响最大，并且厂每增加一个单位的生产上限，总费用会减少103万元。5.3问题三模型的建立与求解5.3.1模型的建立先给树形图的每条边指定一个方向,使得所得到的有向树有一个度数为1的顶点的入度为0,而其它每个顶点的入度均为1。如此，再象问题一一样,我们可以引入0-1变量以及变量,它们的含义与问题1中的定义完全一致.类似于问题一,对于有向树的有向边,我们用表示运抵的所有钢管沿铺设的里程数。所以数学模型为：5.3.2模型的求解计算本模型的最小运费矩阵，得到最小运费矩阵（转置）如下表：S1S2S3S4S5S6S7A2160.3205.3220.3250.3245.3255.3265.3A3140.2190.2200.2235.2225.2235.2245.2A498.6171.6181.6216.6206.6216.6226.6A538111121156146156166A620.595.2105.5140.5130.5140.5150.5A738696131121131141A821.271.286.2116.2111.2121.2131.2A964.2114.248.284.279.284.299.2A10921428262575477A11961468651334866A121061569661513756A13121.2171.2111.276.271.216.238.2A1412817811883731126A151421921329787282A16601104480758095A17951458550254765A181001509055453350A191051559560503655A2011516510570651032A211251751158075026表四：最小运费矩阵（转置）带入问题三所给的数据建立对应的模型，并用Lingo软件可以求得的最小总费用是万元。图二：路线图2且具体调运方案:A1不向任何厂订购；A2向S2订购104单位钢管,路线为:S2hdcaA2；A3向S2定购209单位钢管,路线为:S2hdcbA3；A3向S5订货92单位钢管,路线为:S5A17kiA16hdcbA3；A4向S1订购200单位钢管,路线为:S1mfeA5A4;A4向S5定购550单位钢管,路线为:S5A17kiA16hS1mfeA5A4；A5向S2订购312单位钢管,路线为:S2hS1mfeA5;A5向S3定购294单位钢管,路线为:S3A16hS1mfeS5；A6向S1订购399单位钢管,路线为:S1mfeA6；A7向S1订购201单位钢管,路线为:S1A7；A8向S2订购175单位钢管,路线为:S2hA8；A9向S3订购664单位钢管,路线为:S3A16A9；A10向S5订购96单位钢管,路线为:S5A17kiA10;A10向S6订购225单位钢管,路线为:S6A20A18kiA10；A11向S5订购410单位钢管,路线为:S5A17A11；A12向S6订购110单位钢管,路线为:S6A20A19A12；A13向S6订购394单位钢管,路线为:S6A20A13；A14向S6订购571单位钢管,路线为:S6A14；A15向S6订购165单位钢管,路线为:S6pqA15；A16向S3订购42单位钢管,路线为:S3A16；A17向S5订购155单位钢管,路线为:S5A17；A18向S6订购80单位钢管,路线为:S6A20A18；A19向S6订购95单位钢管,路线为:S6A20A19；A20向S6订购260单位钢管,路线为:S6A20；A21向S6订购100单位钢管,S6与A21是同一点,无需运输。六、模型的评价优点：本文建立的模型通过0-1规划较好的解决了是否选择某钢厂的问题，从而避免了对二次规划模型中约束条件的讨论。利用有向图的方法，将第三问中的树形图简化为第一问中的线性图进行建模。缺点：对于本文所解决的问题，因为路线较单一所以从到的最小运费矩阵是手工计算，并没有给出具体的算法和程序，在实际生活中遇到的路线将是很复杂的，而此时手工计算将不合适。七、参考文献1 邬学军等.数学建模竞赛辅导教程.杭州：浙江大学出版社，2009年。2 甘应爱、田丰等.运筹学.北京：清华大学出版社，2005年。3 徐俊明.图论及其应用.中国科学技术大学出版社,合肥,1997。4 安冉，钢管定购和运输的策略优化，数学的实践与认识，第31卷第6期：646-653，2001年11月。5 段晓军等，钢管订购和运输策略，数学的实践与认识，第31卷第1期：63-66，2001年1月。Lingo程序：MODEL:SETS:FAC/S1,S2,S3,S4,S5,S6,S7/:S,P,c;POIN/A2,A3,A5,A6,A7,A8,A9,A10,A11,A12,A13,A14,A15/:M,r,l,d;YL(FAC,POIN):a,X;ENDSETSDATA:P=160,155,155,160,155,150,160;S=800,800,1000,2000,2000,2000,3000;M=2,3,5,6,7,8,9,10,11,12,13,14,15;d=301,1356,194,205,201,680,480,300,220,210,420,500,0;a=160.3 140.2 38 20.5 3.1 21.2 64.2 92 96 106 121.2 128 142205.3 190.2 111 95.5 88.1 71.2 114.2 142 146 156 171.2 178 192220.3 200.2 121 105.5 98.1 86.2 48.2 82 86 96 111.2 118 132250.3 235.2 156 140.5 133.1 116.2 84.2 62 51 6176.2 83 97245.3 225.2 146 130.5 123.1 111.2 79.2 57 33 5171.2 73 87255.3 235.2 156 140.5 133.1 121.2 84.2 62 51 4526.2 11 28265.3 245.2 166 150.5 143.1 131.2 99.2 77 66 5638.2 26 2;ENDDATA!The Objective;MIN=SUM(YL(I,J):(a(I,J)+P(I)*X(I,J)+0.05*SUM(POIN:r+r*r+l+l*l);!The Constraints;FOR(FAC(I):SUM(POIN(J):X(I,J)500*c(I);FOR(POIN(J):SUM(FAC(I):X(I,J)=r(J)+l(J);FOR(POIN(J)|M(J)#LT#15:l(J)+r(J+1)=d(J);r(1)=104;l(13)=0;FOR(FAC(I):BIN(c(I);END运行结果： Local optimal solution found. Objective value: . Objective bound: . Infeasibilities: 0. Extended solver steps: 20 Total solver iterations: 1711 Model Class: MINLP Total variables: 122 Nonlinear variables: 24 Integer variables: 7 Total constraints: 40 Nonlinear constraints: 1 Total nonzeros: 450 Nonlinear nonzeros: 24 Variable Value Reduced Cost SI( S1) 800.0000 0. SI( S2) 800.0000 0. SI( S3) 1000.000 0. SI( S4) 2000.000 0. SI( S5) 2000.000 0. SI( S6) 2000.000 0. SI( S7) 3000.000 0. L( S1) 1. -82400.00 L( S2) 1. -28000.00 L( S3) 1. -25000.00 L( S4) 0. 0. L( S5) 1. 0. L( S6) 1. 0. L( S7) 0. -48000.00 HM( A2) 2. 0. HM( A3) 3. 0. HM( A5) 5. 0. HM( A6) 6. 0. HM( A7) 7. 0. HM( A8) 8. 0. HM( A9) 9. 0. HM( A10) 10.00000 0. HM( A11) 11.00000 0. HM( A12) 12.00000 0. HM( A13) 13.00000 0. HM( A14) 14.00000 0. HM( A15) 15.00000 0. YJ( A2) 104.0000 0. YJ( A3) 226.0000 0. YJ( A5) 1074.000 0. YJ( A6) 184.5000 0. YJ( A7) 189.5000 0. YJ( A8) 125.0000 0. YJ( A9) 505.0000 0. YJ( A10) 321.0000 0. YJ( A11) 270.0000 0. YJ( A12) 75.00000 0. YJ( A13) 199.0000 0. YJ( A14) 286.0000 0. YJ( A15) 165.0000 0. ZJ( A2) 75.00000 0. ZJ( A3) 282.0000 0. ZJ( A5) 9. 0. ZJ( A6) 15.50000 0. ZJ( A7) 76.00000 0. ZJ( A8) 175.0000 0. ZJ( A9) 159.0000 0. ZJ( A10) 30.00000 0. ZJ( A11) 145.0000 0. ZJ( A12) 11.00000 0. ZJ( A13) 134.0000 0. ZJ( A14) 335.0000 0. ZJ( A15) 0. 0. AJ( A2) 301.0000 0. AJ( A3) 1356.000 0. AJ( A5) 194.0000 0. AJ( A6) 205.0000 0. AJ( A7) 201.0000 0. AJ( A8) 680.0000 0. AJ( A9) 480.0000 0. AJ( A10) 300.0000 0. AJ( A11) 220.0000 0. AJ( A12) 210.0000 0. AJ( A13) 420.0000 0. AJ( A14) 500.0000 0. AJ( A15) 0. 0. C( S1, A2) 320.3000 0. C( S1, A3) 300.2000 0. C( S1, A5) 198.0000 0. C( S1, A6) 180.5000 0. C( S1, A7) 163.1000 0. C( S1, A8) 181.2000 0. C( S1, A9) 224.2000 0. C( S1, A10) 252.0000 0. C( S1, A11) 256.0000 0. C( S1, A12) 266.0000 0. C( S1, A13) 281.2000 0. C( S1, A14) 288.0000 0. C( S1, A15) 302.0000 0. C( S2, A2) 360.3000 0. C( S2, A3) 345.2000 0. C( S2, A5) 266.0000 0. C( S2, A6) 250.5000 0. C( S2, A7) 243.1000 0. C( S2, A8) 226.2000 0. C( S2, A9) 269.2000 0. C( S2, A10) 297.0000 0. C( S2, A11) 301.0000 0. C( S2, A12) 311.0000 0. C( S2, A13) 326.2000 0. C( S2, A14) 333.0000 0. C( S2, A15) 347.0000 0. C( S3, A2) 375.3000 0. C( S3, A3) 355.2000 0. C( S3, A5) 276.0000 0. C( S3, A6) 260.5000 0. C( S3, A7) 253.1000 0. C( S3, A8) 241.2000 0. C( S3, A9) 203.2000 0. C( S3, A10) 237.0000 0. C( S3, A11) 241.0000 0. C( S3, A12) 251.0000 0. C( S3, A13) 266.2000 0. C( S3, A14) 273.