钢管订购和运输

1、钢管订购和运输要铺设一条的输送天然气的主管道, 如图一所示。经筛选后可以生产这种主管道钢管的钢厂有。图中粗线表示铁路，单细线表示公路，双细线表示要铺设的管道(假设沿管道或者原来有公路，或者建有施工公路)，圆圈表示火车站，每段铁路、公路和管道旁的阿拉伯数字表示里程(单位km)。a13258010103120124270108810706270302020304501043017506061942052016804803002202104205006003060195202720690520170690462160320160110290115011001200a2a3a4a5a6a11a711a

2、11a8a11a911a11a10a11a12a13a14a15s1s2s3s4s5s6s7图一为方便计，1km主管道钢管称为1单位钢管。一个钢厂如果承担制造这种钢管，至少需要生产500个单位。钢厂在指定期限内能生产该钢管的最大数量为个单位，钢管出厂销价1单位钢管为万元，如下表：1234567800800100020002000200030001601551551601551501601单位钢管的铁路运价如下表：里程(km)300301350351400401450451500运价(万元)2023262932里程(km)5016006017007018008019009011000运价(万元)

3、37445055601000km以上每增加1至100km运价增加5万元。公路运输费用为1单位钢管每公里0.1万元（不足整公里部分按整公里计算）。钢管可由铁路、公路运往铺设地点（不只是运到点，而是管道全线）。（1）请制定一个主管道钢管的订购和运输计划，使总费用最小（给出总费用)。（2）请就（1）的模型分析：哪个钢厂钢管的销价的变化对购运计划和总费用影响最大，哪个钢厂钢管的产量的上限的变化对购运计划和总费用的影响最大，并给出相应的数字结果。摘要：本文建立一个钢管订购和运输模型，从钢厂到主管道结点的运费是影响总费用的重要因素。为使总费用最小，须使从钢厂到主管道结点的运费钢管运输费最小。对求网络中最短

4、路径的dijkstra算法进行改进，得到新的算法，可对含多种权重计算方式的网络进行搜索，得出最小费用路径（最短路径）。在此基础上，建立起描述总费用的函数，把钢管的订购和运输问题归结为在一定约束条件下求最小总费用的二次规划问题。对于问题（），运用lingo软件包求出了较优的订购和运输计划（见表4，表5），其最小费用为1278632万元。对于问题（2）而言，可得出钢厂钢厂销价变化对总费用影响最大，钢厂钢管的销价的变化对购运计划影响最大，钢厂钢管的产量的上限的变化对总费用影响最大，购运计划影响较小。关键词：穷举法 非线性规划 一、 问题重述和分析要铺设一条的输送天然气的主管道，如图一所示,经筛选后可

5、以生产这种主管道的钢厂有。图中粗线表示铁路，单细线表示公路，双细线表示要铺设的管道（假设沿管道或者原来有公路，或者建有施工公路），圆圈表示火车站，每段铁路、公路和管道旁的阿拉伯数字表示里程（单位）。为了方便，1主管道称为1单位钢管。一个钢厂如果承担制造这种钢管，至少需要生产500个单位。钢厂在指定期限内能生产该钢管的最大生产数量为个单位，钢厂出厂销价为万元，如下表：表11234567800800100020002000200030001601551551601551501601单位钢管的铁路运价如下表：表2里程（）351400401450451500运价（万元）2023262932里程（）50

6、16006017007018008019009011000运价（万元）37445055601000以上每增加1至100运价增加5万元。公路运输费用为1单位管道每公里0.1万元（不足整公里的按整公里计算）。管道可由铁路、公路运往铺设地点（不只是运到点，而是管道全线）。要求：（1） 制定一个主管道钢管的订购和运输计划，使总费用最小，并给出总费用。（2） 就（1）的模型进行分析：哪个钢厂钢管的销价的变化对购运计划和总费用影响最大，哪个钢厂钢管的产量的上限的变化对购运计划和总费用的影响最大，并给出相应的数字结果。二、 基本假设1 在计算运费时，沿管道铺设路线上的公路与其它普通公路相同（1单位钢管每公里

7、0.1万元）；2 订购的钢管数量刚好等于需要铺设的钢管数量；3 管道可由铁路、公路、管道全线运往铺设地点（不只是运到点）；4 模型只考虑钢管销价费用和钢管从钢管厂运送到铺设点的钢管运费，而不考虑其它费用，如不计换车、转站的时间和费用，不计装卸费用等；5 不计运输时由于运输工具出现故障等意外事故引起工期延误造成损失；6 销售价和运输价不受市场价格变化的影响。三、 符号说明：第钢管厂：表示的最大生产能力： 表示需要铺设管道路径上的车站：从所有运往的钢管数：表示单位钢管从地运往地的最小费用：从订购钢管的单位价格q： 订购的所有钢管全部运到点的总运费t： 当钢管从钢厂运到点后，钢管向的左右两边运输（铺

8、设）管道的运输费用z：用于订购和运输的总费用： 运到地向左铺设的数目： 运到地向右铺设的数目： 单位钢管1公里的公路运输费用： 表示之间需要铺设的管道长度四、 模型的建立与求解问题一1、 模型的建立钢管的订购和运输方案是直接影响工程费用的主要原因，因此，选取费用最小的路线运送货物，合理的订购计划是决定该工程费用的重要因素，首先利用图论的方法，来确定从钢管生产厂家到施工结点的费用最小路线，然后建立工程费用的优化模型，从中优化出最佳购运方案。对本问题而言，实际上是一个要求制定订购和运输计划，使总费用最小的优化问题。本模型的总费用包括钢管的销价和运输总的费用。首先，向某厂订购钢管，然后将在每个厂订购

9、的钢管运往需要铺设的全路段。欲解决本问题可以按以下方案进行思考：首先，需要确定将货物从地运往地的最优路线（费用最小）；然后，求出向每个钢管厂的订购计划，并确定出运输计划；最后计算将运往地的钢管铺到各个管道上的运输费用，我们不妨假设运往以为终点的钢管只铺到与点相邻的两段管道上。因此，本问题可以按以下步骤求解。第一步：确定从地到地的最优路径，从而确定出单位钢管从地运往地的最小运费。表示钢管厂的最大生产能力，表示需要铺设钢管路径上的车站。假设从运往的钢管用于铺设点左右侧的钢管数为单位，单位产品从到地的运费为万元，用表示单位钢管从地运往地的最小费用，则： （1）第二步：建立从厂运送单位钢管到点的运费的

10、模型：用q表示订购的所有钢管全部运到点的总运费，则： （2）第三步：将运到处的钢管铺到相邻两段路上的运输费用对于运到的钢管，它向左运输的总量，它向左运输的总费用为：（万元）；同理它向右运输的总费用为：用t表示当钢管从钢厂运到点后，钢管向的左右两边运输（铺设）管道的运输费用，得： （3）（4）（表示之间需要铺设的管道长度）第四步：建立订购费用的模型设w表示订购管道的总费用，则可建立如下模型： （5）又因为一个钢厂如果承担制造钢管任务，至少需要生产500个单位，钢厂在指定期限内最大生产量为个单位，故 或 ， 用表示订购和运输的总费用，由（2）、（3）、（4）、（5），本问题可建立如下的非线性规划模

11、型：目标函数约束条件 （6）（表示之间需要铺设的管道长度）2、模型的求解（1）首先求解 由于钢管从钢厂运到运输点要通过铁路和公路运输，而铁路运输费用是分段函数，与全程运输总距离有关。又由于钢厂直接与铁路相连，所以可先求出钢厂到铁路与公路相交点的最短路径。依据钢管的铁路运价表，算出钢厂到铁路与公路相交点的最小铁路运输费用，并把费用作为边权赋给从钢厂到的边。再将与相连的公路、运输点及其与之相连的要铺设管道的线路（也是公路）添加到图上，根据单位钢管在公路上的运价规定，得出每一段公路的运费，并把此费用作为边权赋给相应的边。这样就转换为以单位钢管的运输费用为权的赋权图，再利用e.w.dijkstra的最

12、短路算法计算出一个单位钢管从钢厂运到工地的最少费用系数阵，matlab程序见附录一。表3 表中对应的值为对应两点最优路径单位钢管运输费用s1s2s3s4s5s6s7a1170.7215.7230.7260.7255.7265.7275.7a2160.3205.3220.3250.3245.3255.3265.3a3140.2190.2200.2235.2225.2235.2245.2a498.6171.6181.6216.6206.6216.6226.6a538111121156146156166a620.595.5105.5140.5130.5140.5150.5a73.1869613112

13、1131141a821.271.286.2116.2111.2121.2131.2a964.2114.248.284.279.284.299.2a10921428262576276a11961468651335166a121061569661514556a13121.2171.2111.276.271.226.238.2a1412817811883731126a151421921329787282(2)根据以上结果, 继续求解非线性规划模型：由于不能直接处理约束条件：或，我们可先将此条件改为，得到如下模型： 用lingo求解，程序见附录二。分析结果后发现购运方案中钢厂的生产量不足500单位，下

14、面我们采用不让钢厂生产和要求钢厂的产量不小于500个单位两种方法计算： 1）不让钢厂生产,程序见附录三。 计算结果：1278632（万元）（此时每个钢厂的产量都满足条件）. 2）要求钢厂的产量不小于500个单位，程序见附录四。 计算结果：1285281（万元） （此时每个钢厂的产量都满足条件）.比较这两种情况，得最优解为，=1278632（万元）。所以根据上述的模型，得运输总费用最小为：1278632（万元）。具体的购运计划和铺设方案如表4，表5：表4 问题一的订购和调运方案 订购量a2a3a4a5a6a7a8a9a10a11a12a13a14a15s180000402952002650000

15、0000s280017900321003000000000s31000003360000664000000s4000000000000000s510150508920000004150000s6155600000000351086333621165s7000000000000000表5 问题一的铺设方案yza10.0000000.000000a2104.000075.00000a3226.0000282.0000a4468.00000.000000a5606.00009.500000a6184.500015.50000a7189.500076.00000a8125.0000175.0000a9

16、505.0000159.0000a10321.000030.00000a11270.0000145.0000a1275.0000011.00000a13199.0000134.0000a14286.0000335.0000a15165.00000.000000问题二：针对问题一的求解模型，讨论钢厂钢管的销售价格变化对购运计划和总费用影响及钢厂钢管产量的上限变化对购运计划和总费用的影响 定义 方案中运往各点的运输量的变化量的绝对值之和称为运输方案变化量 1、讨论钢厂钢管的销售价格变化对购运计划和总费用的影响 当钢厂钢管销售价格变化时，会对购运计划和总费用造成影响。为了更好地观察每一个钢厂钢管销售

17、价格所造成的影响，采用比较法，即每次只让一个钢厂钢管的销售价格发生相同的变化，其余钢厂钢管的销售价格不发生变化。我们将各个钢厂单位钢管的销价分别增加1万元和减少1万元，借助lingo软件得出相应的总费用、运输方案、订购方案变化情况如表6、表7所示表6 各个钢厂单位钢管的销价分别增加1万元钢厂总费用总费用变化量运输方案变化量订购方案变化量s1127943280000s2127943280000s31279632100000s41278632000s5127963910074030s612798341202712712s71278632000表7 各个钢厂单位钢管的销价分别减少1万元钢厂总费用总费

18、用变化量运输方案变化量订购方案变化量s1127783280000s2127783280000s31277632100000s41278632000s512772631369712712s6127706815644030s71278632000由上述表格观察分析可得： 钢厂销价变化对总费用影响最大，钢厂钢管的销价的变化对购运计划影响最大。2、讨论钢厂钢管产量的上限的变化对购运计划和总费用的影响同样采用比较法，即每次只让一个钢厂钢管产量的上限的发生相同的变化，其余钢厂钢管产量的上限不发生变化。将各个钢厂的产量的上限分别增加100个单位和减少100个单位，分别计算，得到购运计划和总费用变化情况如表8

19、、表9所示表8 各个钢厂钢管的产量的上限分别增加100个单位钢厂总费用总费用变化量运输方案变化量订购方案变化量s1126833210300218200s212751323500404200s3127613225001786200s41278632000s51278632000s6127863208440s71278632000表9 各个钢厂钢管的产量的上限分别减少100个单位钢厂总费用总费用变化量运输方案变化量订购方案变化量s1128893210300260200s2128213235001244200s312811322500200200s41278632000s51278632000s61

20、278632000s71278632000由上述表格观察分析可得：钢厂钢管的产量的上限的变化对总费用影响最大，购运计划影响较小。五、 结果分析由于总费用由订购费用和运输费两部分组成，运输费又由一般线路上的运输费和铺设管道上的运输费组成。利用求网络中最短路径的dijkstra算法，进行改进得到新的算法，可对含多种权重计算方式的网络进行搜索，得出最小费用路径（最短路径），算出两点之间的最优路径，进而根据非线性规划，借助于lingo软件求解即可求出相应的结果。六、 模型的评价及改进1优点：1）本问题中运用了求网络中最短路径的dijkstra算法，进行改进得到新的算法，可对含多种权重计算方式的网络进行

21、搜索，算出两点之间的最优路径，计算结果准确。2）本问题构造出的模型算法较简单，也可以运用相应的其他编程软件来得到比较满意的结果。2缺点：1）由于本问题有现成的比较先进的解法，但由于缺乏基本的数学软件资料和相应的算法资料，不能将其准确求解。2） 于在求解最短路时，我们用人工计算容易将问题复杂化，同时，容易出错。3）作为图论问题的技术而言，求解过程较难，且不易求出最优解3模型改进本问题中需要用现成的先进的网络流求解，但本问题没有求解，实际上本问题中加权穷举法，可采用相应的网络法来代替。在求解问题三时可用最小树求解，同时，我们可将本问题运用于时间的变化等范围的推广。参考文献：1甘应爱，田丰等等.运行

22、学.清华大学出版社,北京,1994。2袁亚湘.孙文瑜著.最优化理论与方法.科学出版社，北京，1997.3徐俊明著.图论及其应用.中国科学技术大学出版社，合肥，1997.附录一s 1-s7与a1-a15间的最小费用矩阵a=;for i=1:39 for j=1:39 a(i,j)=inf; endendfor j=1:39 a(j,j)=0;enda(1,2)=104;a(2,1)=104;a(2,3)=301;a(3,2)=301;a(3,4)=750;a(4,3)=750;a(4,5)=606;a(5,4)=606;a(5,6)=194;a(6,5)=194;a(6,7)=205;a(7,6

23、)=205;a(7,8)=201;a(8,7)=201;a(8,9)=680;a(9,8)=680;a(9,10)=480;a(10,9)=480;a(10,11)=300;a(11,10)=300;a(11,12)=220;a(12,11)=220;a(12,13)=210;a(13,12)=210; a(13,14)=420;a(14,13)=420;a(14,15)=500;a(15,14)=500;a(15,22)=20;a(22,15)=20;a(15,39)=20;a(39,15)=20; a(14,38)=30;a(38,14)=30;a(14,21)=110;a(21,14)=

24、110;a(13,37)=62;a(37,13)=62;a(12,35)=10;a(35,12)=10;a(11,34)=10;a(34,11)=10;a(10,32)=70;a(32,10)=70;a(9,31)=42;a(31,9)=42;a(8,30)=12;a(30,8)=12; a(7,16)=31;a(16,7)=31;a(7,29)=10;a(29,7)=10;a(6,28)=5;a(28,6)=5;a(5,27)=10;a(27,5)=10; a(4,26)=600;a(26,4)=600;a(3,24)=2;a(24,3)=2;a(2,23)=3;a(23,2)=3;a(23

25、,25)=450;a(25,23)=450; a(24,25)=80;a(25,24)=80;a(25,26)=1150;a(26,25)=1150;a(26,30)=1100;a(30,26)=1100;a(17,30)=1200;a(30,17)=1200; a(30,16)=202;a(16,30)=202;a(16,29)=20;a(29,16)=20;a(29,28)=195;a(28,29)=195;a(28,27)=306;a(27,28)=306;a(30,31)=720;a(31,30)=720;a(31,18)=690;a(18,31)=690;a(31,32)=520;a

26、(32,31)=520;a(32,33)=170;a(33,32)=170; a(33,19)=690;a(19,33)=690;a(33,36)=160;a(36,33)=160;a(33,34)=88;a(34,33)=88;a(34,20)=462;a(20,34)=462; a(33,36)=160;a(36,33)=160;a(36,35)=70;a(35,36)=70;a(36,37)=320;a(37,36)=320;a(37,38)=160;a(38,37)=160;a(38,21)=70;a(21,38)=70;a(38,39)=290;a(39,38)=290;a(39,2

27、2)=30;a(22,39)=30; a;h=;hh=;for sw=16:39 l=; for i=1:40 h(i)=0; end for i=16:39 l(i)=a(sw,i); end t=l(16); s=16; for i=17:39 if tl(i); t=l(i); s=i; end end h(s)=1; for w=16:38 for i=16:39 while h(i)=1 i=i+1; end if i=40 break; end l1(i)=a(s,i); l3(i)=t+l1(i); if l3(i)l(i); t=l(i); s=i; end end h(s)=

28、1; end h(sw,:)=l;endfor i=16:39 %将距离转化为费用_ for j=16:39 hh(i,j)=ch741(h(i,j); % ch741 函数是将距离转化为费用_ endendfor i=1:15 % 将公路的费用也输入费用矩阵中 for j=1:39 hh(i,j)=a(i,j)*0.1; endendfor i=16:39 for j=1:15 hh(i,j)=a(i,j)*0.1; endendhh ;%计算任意两点间的最小费用，并将数据输入矩阵中_ hhh=;for sw=16:22; % 计算与其他点的最小费用 _ l=; for i=1:40 h(i

29、)=0; end for i=1:39 l(i)=hh(sw,i); end t=l(1); s=1; % t 为最小数的暂时空间_ for i=2:39 if tl(i); t=l(i); % 找最小数_ s=i; % s 为已用过的标志_ end end h(s)=1; for w=1:38 % w 为循环次数_ for i=1:39 % 换数 while h(i)=1 i=i+1; end if i=40 break; end l1(i)=hh(s,i); l3(i)=t+l1(i); if l3(i)l(i); t=l(i); s=i; end end h(s)=1; end hhh(

30、sw-15,:)=l;endfor j=1:7 for i=1:15 c(j,i)=hhh(j,i); endenddisp(s1-s7与a1-a15间的最小费用矩阵)c将距离转化为费用函数是:function f=ch741(ll)rr=ll; if rr=0 real1=0;elseif rr0 real1=20;elseif rr300.5 & rr350.5&rr400.5&rr450.5 & rr500.5 & rr600.5 & rr700.5 & rr800.5 real1=50;else real1=fix(rr-800.5)/100)*5+55 ;endf=real1;附录二

31、model:sets:gch/1.7/:p,s;gd/1.15/:a,y,z;links(gch,gd):x,c;endsetsdata:p = 160 155 155 160 155 150 160;s = 800 800 1000 2000 2000 2000 3000;c = 170.7 160.3 140.2 98.6 38 20.5 3.1 21.2 64.2 92 96 106 121.2 128 142215.7 205.3 190.2 171.6 111 95.5 86 71.2 114.2 142 146 156 171.2 178 192230.7 220.3 200.2

32、181.6 121 105.5 96 86.2 48.2 82 86 96 111.2 118 132260.7 250.3 235.2 216.6 156 140.5 131 116.2 84.2 62 51 61 76.2 83 97255.7 245.3 225.2 206.6 146 130.5 121 111.2 79.2 57 33 51 71.2 73 87265.7 255.3 235.2 216.6 156 140.5 131 121.2 84.2 62 51 45 26.2 11 28275.7 265.3 245.2 226.6 166 150.5 141 131.2 9

33、9.2 76 66 56 38.2 26 2;enddatamin = w + q + t;w = sum(links(i,j):p(i)*x(i,j);q = sum(links(i,j):c(i,j)*x(i,j);t = sum(gd(j):(1+y(j)*y(j)+(1+z(j)*z(j)*0.05;z(1)+y(2)=104 ;z(2)+y(3)=301 ;z(3)+y(4)=750 ;z(4)+y(5)=606 ;z(5)+y(6)=194 ;z(6)+y(7)=205;z(7)+y(8)=201;z(8)+y(9)=680;z(9)+y(10)=480;z(10)+y(11)=3

34、00;z(11)+y(12)=220;z(12)+y(13)=210;z(13)+y(14)=420;z(14)+y(15)=500;y(1)+z(1) = sum(gch(i):x(i,1);y(2)+z(2) = sum(gch(i):x(i,2);y(3)+z(3) = sum(gch(i):x(i,3);y(4)+z(4) = sum(gch(i):x(i,4);y(5)+z(5) = sum(gch(i):x(i,5);y(6)+z(6) = sum(gch(i):x(i,6);y(7)+z(7) = sum(gch(i):x(i,7);y(8)+z(8) = sum(gch(i):

35、x(i,8);y(9)+z(9) = sum(gch(i):x(i,9);y(10)+z(10) = sum(gch(i):x(i,10);y(11)+z(11) = sum(gch(i):x(i,11);y(12)+z(12) = sum(gch(i):x(i,12);y(13)+z(13) = sum(gch(i):x(i,13);y(14)+z(14) = sum(gch(i):x(i,14);y(15)+z(15) = sum(gch(i):x(i,15);for(gch(i):sum(gd(j):x(i,j)=s(i);end附录三model:sets:gch/1.7/:p,s;gd

36、/1.15/:a,y,z;links(gch,gd):x,c;endsetsdata:p = 160 155 155 160 155 150 160;s = 800 800 1000 2000 2000 2000 3000;c = 170.7 160.3 140.2 98.6 38 20.5 3.1 21.2 64.2 92 96 106 121.2 128 142215.7 205.3 190.2 171.6 111 95.5 86 71.2 114.2 142 146 156 171.2 178 192230.7 220.3 200.2 181.6 121 105.5 96 86.2 48

37、.2 82 86 96 111.2 118 132260.7 250.3 235.2 216.6 156 140.5 131 116.2 84.2 62 51 61 76.2 83 97255.7 245.3 225.2 206.6 146 130.5 121 111.2 79.2 57 33 51 71.2 73 87265.7 255.3 235.2 216.6 156 140.5 131 121.2 84.2 62 51 45 26.2 11 28275.7 265.3 245.2 226.6 166 150.5 141 131.2 99.2 76 66 56 38.2 26 2;end

38、datamin = w + q + t;w = sum(links(i,j):p(i)*x(i,j);q = sum(links(i,j):c(i,j)*x(i,j);t = sum(gd(j):(1+y(j)*y(j)+(1+z(j)*z(j)*0.05;z(1)+y(2)=104 ;z(2)+y(3)=301 ;z(3)+y(4)=750 ;z(4)+y(5)=606 ;z(5)+y(6)=194 ;z(6)+y(7)=205;z(7)+y(8)=201;z(8)+y(9)=680;z(9)+y(10)=480;z(10)+y(11)=300;z(11)+y(12)=220;z(12)+y

39、(13)=210;z(13)+y(14)=420;z(14)+y(15)=500;y(1)+z(1) = sum(gch(i):x(i,1);y(2)+z(2) = sum(gch(i):x(i,2);y(3)+z(3) = sum(gch(i):x(i,3);y(4)+z(4) = sum(gch(i):x(i,4);y(5)+z(5) = sum(gch(i):x(i,5);y(6)+z(6) = sum(gch(i):x(i,6);y(7)+z(7) = sum(gch(i):x(i,7);y(8)+z(8) = sum(gch(i):x(i,8);y(9)+z(9) = sum(gch

40、(i):x(i,9);y(10)+z(10) = sum(gch(i):x(i,10);y(11)+z(11) = sum(gch(i):x(i,11);y(12)+z(12) = sum(gch(i):x(i,12);y(13)+z(13) = sum(gch(i):x(i,13);y(14)+z(14) = sum(gch(i):x(i,14);y(15)+z(15) = sum(gch(i):x(i,15);for(gch(i):sum(gd(j):x(i,j)=s(i);sum(gd(j):x(7,j)=0;end附录四model:sets:gch/1.7/:p,s;gd/1.15/:a,y,z;links(gch,gd):x,c;endsetsdata:p = 160 155 155 160 155 150 160;s = 800 800 1000 2000 2000