钢管铺设).doc

钢管铺设问题摘要本文以铺设一条输送天然气的主管道为背景。通过对问题的深入分析后，建立了关于钢管铺设的总费用最小的非线性规划优化模型。针对问题一：我们首先利用图论思想来分析数据，并求到了每单位钢管从钢厂运到结点的最少总费用（即公路运费铁路运费和钢管销价之和）。数据处理完后，我们根据模型在进行求解时，利用分枝定界的思想将模型转化成典型的二次规划问题。并利用Matlab数学软件求解出钢管铺设的最小费用为min1278632（万元）以及向钢管厂订购的计划表（详见模型求解）。针对问题二：我们主要是利用问题一的模型对每个钢厂销价的变化以及产量的上限的变化进行单独讨论，然后作相对比较，最终得出：、钢厂销价的变化对总费用的影响最大；产量上限的变化对总费用影响最大。针对问题三：我们从枢纽站点的各个方向出发，并在问题一的基础上建立了此问题更一般的优化模型。最后，和问题一的求解方式一样得出钢管铺设的最小费用min=1406631（万元）以及向钢管厂订购的计划表（详见模型求解）。通过对本文中的模型用计算机模拟检验结果得到,我们的模型是成功的,求解是正确的.对路线的安排是合理的。本论文所建立的数学模型有成熟的理论基础,可靠性高,操作简单,容易实施,在一些运输问题上都可以用此方法。本文最后指出的模型的缺陷给我们指明了今后继续研究的方向。关键字：优化模型 二次规划 图论思想 问题重述某地要从这7个预选钢管厂订购一批数量为5171km单位长度的主管道钢管，通过铁路、公路运送到十五个铺设点铺设一条的输送天然气的主管道，其中为便于计算我们把1km的主管道称为1单位钢管，并且要求满足一个钢管厂如果要承担制造这种钢管至少要生产500个单位，钢管厂在指定范围内能生产该钢管最大数量为个单位，其销价分别为万元/每单位。请你根据题中所给出的铁路和公路运价以及图（1）（2）路程长度铺设图中制定一个主管道钢管的订购和运输计划，使得总费用最少（假设装卸费忽略不计入运费中），求出总费用具体值；并分析哪个钢管厂的销价变化对购运计划合总费用影响最大，给出相应的数字结果并思考如果铺设的管道是树形图，再另外给出解决该问题的模型，并计算出结果。模型假设1 沿铺设的主渠道以有公路或者有施工公路.2 在主渠道上，每千米卸1单位的钢管.3 公路运输费用为1单位钢管每千米0.1万元（不足整千米部分按整千米计算）4 在计算总费用时，只考虑运输费和购买钢管的费用，而不考虑其他费用.5 在计算钢厂的产量对购运计划影响时，只考虑钢厂的产量足够满足需要的情况，即钢厂的产量不受限制.6 假设钢管在铁路运输路程超过1000km时，铁路每增加1至100km，1单位钢管的运价增加5万元.变量说明：表示第i个钢厂；（）：表示第i个钢厂的最大产量；（）:表示输送管道（主渠道）上的第个地点；（）:表示第个钢厂钢管的单位销价；（）:表示钢管厂向点运送的钢管数量；（）:表示相邻点与之间的距离；（）:表示1单位钢管从钢厂运到结点的最少总费用，即公路运费铁路运费和钢管销价之和；（）：表示与点相连的公路和铁路的相交点；（）模型分析与建立问题一：讨论如何调整主渠道钢管的订购和运输方案使总费用最小。（一）数据分析与处理：由题意可知，钢管从钢厂到运输结点的费用包括钢管的销价钢管的铁路运输费用和钢管的公路运输费用.在费用最小时，对钢管的订购和运输进行分配，可得出本问题的最佳方案.1. 求钢管从钢厂运到运输点的最小费用1）先通过题中图表可得到钢管厂到运输结点的最短铁路路径权值为：由于钢管从钢厂运到运输点要通过铁路和公路运输，而铁路运输费用是分段函数，与全程运输总距离有关.又由于钢厂直接与铁路相连，所以可先求出钢厂到铁路与公路相交点的最短路径.如图1图1钢厂到铁路与公路相交点的最短路径依据钢管的铁路运价表，算出钢厂到铁路与公路相交点的最小铁路运输费用，并把费用作为边权赋给从钢厂到的边.再将与相连的公路、运输点及其与之相连的要铺设管道的线路（也是公路）添加到图上，根据单位钢管在公路上的运价规定，得出每一段公路的运费，并把此费用作为边权赋给相应的边.以为例得图2图2 钢管从钢厂运到各运输点的铁路运输与公路运输费用权值图同理可知：由到可得到由2b2b3b4b5b6b7b8b9b10b11b12b13b14b15S1160140803720020608595105115125140205190125110958570110859510511512514014514514012010595854475858510010512018018017015514013011580555050657085175170165145130120110755032445565801751701651451301201107550444420202618518518016014513512590606055322320(表1）到最小铁路终点最小费用b2b3b4b5b6b7b8b9b10b11b12b13b14b15S10.30.26010.53.11.24.27116.2320.30.26010.53.11.24.27116.2320.30.26010.53.11.24.27116.2320.30.26010.53.11.24.27116.2320.30.26010.53.11.24.27116.2320.30.26010.53.11.24.27116.21120.30.26010.53.11.24.27116.232（表2）到最小公路终点最小费用2).计算单位钢管从到的最少运输费用根据以上数据，我们用上的最小铁路费用加上的最小公路费用求出单位钢管从到的最少运输费用依次为：70.7，160.3，140.2，98.6，38，20.5，3.1，21.2，64.2，92，96，106，121.2，128，142（单位：万元）.加上单位钢管的销售价，得出从钢厂购买单位钢管运输到点的最小费用依次为：330.3，320.3，300.2，258.6，198，180.5，163.1，181.2，224.2，252，256，266，281.2，288，302（单位：万元）.同理，可用同样的方法求出钢厂到点的最小费用，从而得出钢厂到点的最小总费用（单位：万元）为：A2A3A4A5A6A7A8A9A10A11A12A13A14A15S1320.3300.2258.6198180.5163181.2224.2252256266281.2288302360.3345.2326.6266250.5241226.2269.2297301311326.2333347375.3355.2336.6276260.5251241.2203.2237241251266.2273287410.3395.2376.6316300.5291276.2244.2222211221236.2243257400.3380.2361.6301285.5276266.2234.2212188206226.2228242405.3385.2366.6306290.5281271.2234.2212201195176.2161178425.3405.2386.6326310.5301291.2259.2237226216198.2186162（表3）到点最小费用（二）模型建立1：根据题意可以分析出运输总费用可分为两部分：运输总费用=钢厂到各点的运输费用+铺设费用. 运输费用：若运输点向钢厂订购单位钢管，则钢管从钢厂运到运输点所需的费用为，则：=.铺设费用：当钢管从钢厂运到点后，钢管就要向运输点的两边段和段运输铺设管道.设向段铺设的管道长度为，则设向和段铺设的长度分别为则向段的铺设费用为：.（万元）同理到段的铺设费用为：（万元）则铺设费用为：=（万元）运输加铺设总费用最小为：约束条件:1. 钢管厂向点运送的钢管数量要等于点需要铺设钢管的数量：2. 针对钢管厂有两种情况 (选或者不选)：.若不选则订购量为0；.若选择钢管厂则一个钢管厂至少要大于500而且要小于钢厂的最大产量；3.由于枢纽站运往两边的量受路段长度的制约，故：4由于枢纽站的左边和的右边都没有路段了，故：，5.对于设的管道长度为以及单位钢管数量都应该为正整数。即：综上所述：st.问题二：哪个钢厂钢管销价的变化对购运计划和总费用影响最大以及哪个钢厂钢管的产量的上限的变化对购运计划和总费用的影响最大。针对该问题主要是利用问题一的模型对每个钢厂销价的变化以及产量的上限的变化进行单独讨论，然后作相对比较，最终得出结论。问题三：如果要铺设的管道不是一条线，而是一个树形图，铁路、公路和管道构成网络，请就这种更一般的情形给出一种解决办法，并对图2按（1）的要求给出模型和结果。(一).模型的分析与建立2针对问题三，由于铺设的管道不是一条线，而是一个树形图。因此，有些枢纽站点不只是单独的向左边和右边运送。于是将运输到点的钢管总量不能简单地分为和两部分，而应该考虑从出发的各个方向。于是有：其中E是树形图的边集，是连接点和的边，是到的钢管沿边和方向铺设的数量。对于约束条件，其约束条件同问题一的类似，故为：模型求解3问题一的求解：由以上分析，由于约束条件：的存在，因此模型的求解不能简单地调用二次规划的软件。于是我们先考虑将该约束条件改为大范围0到进行求解于是此模型便转化为了典型的二次规划优化模型，如果结果符合原有约束条件，则便是原问题的最优解，如果存在个别的，使，那么可以针对这些，用分枝定界法的思想强制的将它分为和两种情况考虑，然后找出其中最有的结果。根据这种思想，我们用Matlab软件中的解决二次规划问题的命令求解得到的最优解中，。于是将从供应厂名单中删除，再将第7家工厂的供货量改为0以及不小于500两种情况重做。相比之下，取0的情况总费用较小，从而也应把删除。得到问题一的最优解为：min1278632（万元）具体的购运计划如表：订购量A2A3A4A5A6A7A8A9A10A11A12A13A14A15S18000201133200266000000000S28001791114295003000000000S31000139111860006640000000S4000000000000000S5101503582420000004150000S6155600000000035186333621165S7000000000000000问题二的求解：问题二相当于规划问题一的灵敏度分析，一般来说应该对销价变化和产量上限的变化求出总的费用的变化。但是针对本题的情况，要得到费用的变化关于销价变化和产量上限的变化的函数关系，几乎是不可能的，好在本题只要求对每个钢厂进行单独讨论，然后做相对比较。现在我们对各个钢厂单位钢管的销价分别增加1万元和减少一万元，然后利用Matlab计算得到总费用4。如下表(4)：钢厂销价增加1万元，总费用的增加量销价减少1万元，总费用的减少量S18008008008001000800S51008136812021563表(4)其中： 、钢厂销价的变化对总费用没有影响，可以看出，、钢厂销价的变化对总费用的影响最大。将各个钢厂的产量的上限分别增加100个单位和减少100个单位也就是将原模型中的分别增加100和减少100,。为此我们计算出总费用的变化情况如下表（5）：钢厂产量上限增加100个单位总费用的减少量产量上限减少100个单位总费用的增加量S110300103003500350025002500表（5）其中：S4 、 S5 、S6 、产量上限的变化对总费用没有影响。可以看出产量上限的变化对总费用影响最大。综上分析所得：销价的变化影响最大为：或；产量上限的变化影响最大为：问题三的求解5：同问题一可得树形图最优运费为：min=1406631（万元）其具体的购运计划如表（6）：订购量A2A3A4A5A6A7A8A9A10A11A12A13A14A15A16A17A18A19A20A21S18000201133200266000000000000000S28001791114295003000000000000000S31000139111860006640000000000000S4000000000000000000000S513030358242000000415000288000000S62000000000000351863336210220002240165S7000000000000000000000表（6）模型评论与推广我们建立的模型和构造算法思路简单，易懂，切对各种可能的情况都进行比较全面的考虑，故该模型的一般性很强,。不仅能求解由铁路、公路构成的交通网络的钢管订购和运输的最优化问题，给出订购计划，最佳运输路径和铺设管道方式，还可以推广到更为一般的运输、网络、节点和分配问题，所以该模型更能贴近生活，实用于生活，被广大群众所接受采用。但在作为图论问题的技术而言，求解过程比较难，不易求出最优解；并且在求解最短路时，若果网络更为复杂化我们用人工计算处理容易出错、工作量也比较大。参考文献1姜启源，数学模型，北京：北京高等教育出版社，1993年2韩中庚主编，数学建模竞赛，北京：科学出版社，2007年3许洪范，数学建模教程，北京：国防工业出版社，2007年4费培之，数学与建模使用教程，成都：四川大学出版社，1998年5李志林等，数学建模及典型案例分析，北京：化学工业出版社，2006年附录 1.部分程序：（1）当在解决二次规划问题中的约束条件为时T=104 301 750 606 194 205 201 680 480 300 220 210 420 500;S=800 800 1000 1000 2000 2000 2000;C=170.7 160.3 140.2 98.6 38 20.5 3.1 21.2 64.2 92 96 106 121.2 128 142;215.7 205.3 190.2 171.6 111 95.5 86 71.2 114.2 142 146 156 171.2 178 192;230.7 220.3 200.2 181.6 121 105.5 96 86.2 48.2 82 86 96 111.2 118 132;260.7 250.3 235.2 216.6 156 140.5 131 116.2 84.2 62 51 61 76.2 83 97;255.7 245.3 225.2 206.6 146 130.5 121 111.2 79.2 57 33 51 71.2 73 87;265.7 255.3 235.2 216.6 156 140.5 131 121.2 84.2 62 51 45 26.2 11 28;275.7 265.3 245.2 226.6 166 150.5 141 131.2 99.2 76 66 56 38.2 26 2;P=160 155 155 160 155 150 160P=kron(P,ones(1,15);D=C+P;0.05*ones(2,15);f=D(:);H=zeros(105,105) zeros(105,30); zeros(30,105) 0.1*eye(30,30);A1=kron(eye(7,9),ones(1,15);b1= S;temp=eye(15);e1=zeros(1,15);temp(1,:);el5=temp(15,:);zeros(1,15);A2=zeros(2,105) el5 e1b2=zeros(2,1);A=A1;A2;b=b1;b2;Aeq1=kron(ones(1,7) -ones(1,2),eye(15);beq1=zeros(15,1);Aeq2=zeros(14,105) temp(1:14,:) temp(2:15,:);beq2=T;Aeq=Aeq1;Aeq2;beq=beq1;beq2;x0=x;x,fval,exitflag=quadprog(H,f,A,b,Aeq,beq,zeros(135,1),x0);exitflagx=round(x); %取整xm=reshape(x,15,9) %调运方案矩阵m=xm(1:7,:);order=sum(m) %订购方案矩阵format long;fval=0.5*x*H*x+f*x %输出取整后的总费用;format short;（2）当在解决二次规划问题中令是的解：T=104 301 750 606 194 205 201 680 480 300 220 210 420 500;S=800 800 1000 0 2000 2000 0;C=170.7 160.3 140.2 98.6 38 20.5 3.1 21.2 64.2 92 96 106 121.2 128 142;215.7 205.3 190.2 171.6 111 95.5 86 71.2 114.2 142 146 156 171.2 178 192;230.7 220.3 200.2 181.6 121 105.5 96 86.2 48.2 82 86 96 111.2 118 132;260.7 250.3 235.2 216.6 156 140.5 131 116.2 84.2 62 51 61 76.2 83 97;255.7 245.3 225.2 206.6 146 130.5 121 111.2 79.2 57 33 51 71.2 73 87;265.7 255.3 235.2 216.6 156 140.5 131 121.2 84.2 62 51 45 26.2 11 28;275.7 265.3 245.2 226.6 166 150.5 141 131.2 99.2 76 66 56 38.2 26 2;P=160 155 155 160 155 150 160P=kron(P,ones(1,15);D=C+P;0.05*ones(2,15);f=D(:);H=zeros(105,105) zeros(105,30); zeros(30,105) 0.1*eye(30,30);A1=kron(eye(7,9),ones(1,15);b1= S;temp=eye(15);e1=zeros(1,15);temp(1,:);el5=temp(15,:);zeros(1,15);A2=zeros(2,105) el5 e1b2=zeros(2,1);A=A1;A2;b=b1;b2;Aeq1=kron(ones(1,7) -ones(1,2),eye(15);beq1=zeros(15,1);Aeq2=zeros(14,105) temp(1:14,:) temp(2:15,:);beq2=T;Aeq=Aeq1;