钢管订购和运输问题

钢管订购和运输问题摘要： 我们利用Floyd算法求出铁路网和公路网各点间最短路线，然后转化成最少运输，去掉了铁路和公路的性质，使运输网络变成一张供需运输价格表，然后建立了一个以总费用为目标函数的非线性规划模型，利用Lingo软件，求出问题一的最优解为1278632万元。通过对问题一中lingo运行结果的分析，我们得出S5钢厂钢管的销价的变化对购运计划和总费用影响最大，S1钢厂钢管的产量的上限的变化对购运计划和总费用的影响最大。问题三模型的建立原理和问题一的相同，利用Lingo软件，求得最优解为1407149万元.关键词：非线性方程组 Floyd算法灵敏度.问题重述要铺设一条41f4-…fA15的输送天然气的主管道，如图一所示（见下页）。经筛选后可以生产这种主管道钢管的钢厂有sjs2,…S7。图中粗线表示铁路，单细线表示公路，双细线表示要铺设的管道（假设沿管道或者原来有公路，或者建有施工公路），圆圈表示火车站，每段铁路、公路和管道旁的阿拉伯数字表示里程（单位km）。为方便计，1km主管道钢管称为1单位钢管。一个钢厂如果承担制造这种钢管，至少需要生产500个单位。钢厂s在i指定期限内能生产该钢管的最大数量为S.个单位，钢管出厂销价1单位钢管为2万元，如下表：

i1234567si80080010002000200020003000P.i1601551551601551501601单位钢管的铁路运价如下表:里程（km）W300301〜350351〜400401〜450451〜500运价（万元）2023262932里程（km）501〜600601〜700701〜800801〜900901〜1000运价（万元）37445055601000km以上每增加1至100km运价增加5万元。公路运输费用为1单位钢管每公里0.1万元（不足整公里部分按整公里计算）。钢管可由铁路、公路运往铺设地点（不只是运到点/&,,4，而是管道全线）。（1）请制定一个主管道钢管的订购和运输计划，使总费用最小（给出总费用）。（2）请就（1）的模型分析：哪个钢厂钢管的销价的变化对购运计划和总费用影响最大，哪个钢厂钢管的产量的上限的变化对购运计划和总费用的影响最大，并给出相应的数字结果。（3）如果要铺设的管道不是一条线，而是一个树形图，铁路、公路和管道构成网络，请就这种更一般的情形给出一种解决办法，并对图二按（1）的要求给出模型和结果。.模型假设（1）只考虑订购费用和运输费用，不考虑装卸等其它费用。（2）在运输和铺设过程中无能量损耗。（3）钢管单价与订购量、订购次数、订购日期无关。（4）沿管道或者原来有公路或者建有施工公路。.符号说明S,:钢厂S,的最大生产能力；pi:钢厂S,的出厂钢管单位价格（单位：万元）；d:公路上一单位钢管的每公里运费（d=0.1万元）；勺：铁路网上两点间的单位钢管最少运输费用；D1jk:题图一公路网上两点间的单位钢管最少运输费用；D2jk:题图二公路网上两点间的单位钢管最少运输费用；':铁路上一单位钢管的运费；J1单位钢管从钢厂外运到々的最小费用（单位：万元）；九:从％到^1之间的距离（单位：千米）；.问题分析（一）问题1的分析问题一属于运输类求最短路的问题。题目要求七个钢厂生产的钢管运输到十五个铺设点，又由于运输的时候，运输费用不是简单的路程长短决定的，因此要先考虑最短的运输到铺设点的最小费用，我们的模型建立目标函数，建立起约束条件，运用（二）问题2的分析问题二是对问题一中的模型进行灵敏度分析。是讨论钢厂钢管的销价的变化和钢厂钢管的产量的上限的变化对购运计划和总费用的影响，同时判别哪家钢厂在这两方面发生的变化对购运计划和总费用的影响最大，使得钢管销售价和钢管生产上限在发生变化时，能够利用原有模型进行判断，是否需要对购运计划进行修改，以满足新情况下的最优。（三）问题3的分析问题三是对问题一的一个扩展。如铺设的管道是一个树形图，铁路、公路和管道构成网络对于题图二，我们可以延用问题一里面的思想，在题图一的基础上多几条铺设路段，即多几个函数。对最小运费的求解，我们采用Floyd算法。先求出铁路网上钢管厂到铁路上任意两点匕，\的最短路线的长度l巾用matlab求得l对应的铁路单位运费q；同理用Floyd算法求出公路网上的任意两点Vj，匕的最短公路路线的长度l也，结果乘以0.1得到公路运费D1jk。，=min（D+D1J，j表示所有运输中转点，于是就得到从某钢厂到某铺设点运输单位钢管的最少运输费用。每个铺设点分别向R,L两个方向展开，通过Lingo编程求出最小铺设费用。运输费用加上购买费用再加上铺设费用就是我们所要求的总费用。问题二，通过问题一里面Lingo编程运行得出的结果，分析哪个钢厂钢管的销价的变化对购运计划和总费用影响最大，哪个钢厂钢管的产量的上限的变化对购运计划和总费用的影响最大。问题三，如铺设的管道是一个树形图，铁路、公路和管道构成网络对于题图二，我们可以延用问题一里面的思想，在题图一的基础上多几条铺设路段，9，11，17节点的铺设方向变为R,l,z三个方向，其他不变。.模型的建立与求解针对题图一，我们采用Floyd算法，用matlab编程求出单位钢管从S,运输到勺的最小运输费用，具体数据如下表1：表1单位钢管从S,运输到勺的最小运输费用（单位：万元）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.6A538.0111.0121.0156.0146.0156.0166.0A620.595.5105.5140.5130.5140.5150.5A73.186.096.0131.0121.0131.0141.0A821.271.286.2116.2111.2121.2131.2A964.2114.248.284.279.284.299.2A1092.0142.082.062.057.062.077.0A1196.0146.086.051.033.051.066.0A12106.0156.096.061.051.045.056.0A13121.2171.2111.276.271.226.238.2A14128.0178.0118.083.073.011.026.0A15142.0192.0132.097.087.028.02.0对表1的数据进行分析，我们得到一个非线性规划模型:

目标函数是总费用W,它包含三项：钢管出厂总价Q,运输费P,及铺设费T.即其中15p•Xi=1j=1其中15p•Xi=1j=1P=££C•X

ijij

i=1j=1mmW=££pii=1j=1ij ijiji=1j=1，T j21+R约束条件为:①生产能力的限制:(广0或1)500•t«£5xj<s•t①生产能力的限制:(广0或1)j=1②运到A.的钢管用完：:J」+R.(j=1,...15)J i=1③A与A.之间的钢管：RMj+1=bj(j=1,…,14)④变量非负性限制：x/0,j0,R20,(i=I-，7,j=1，…，⑸/⑤运到Aj的钢管整数限制：x『N运用数学软件Lingo编程求解最优最小费用卬=1278632.万元问题二的模型通过分析问题一中关于销价的约束，Lingo运行后得到的结果得S1S2S3S4S5S6S7影子价格-800-800-10000-1320-1250.990影子价格表示在最优解下“资源”增加一个单位时“效益”的增量，即每个钢厂销售价格每减少一万元，对总费用的影响。从表中数据分析，S5钢厂钢管的销价的变化对购运计划和总费用的影响最大。

通过分析问题一中关于产量的约束，Lingo运行后得到的结果得S1S2S3S4S5S6S7影子价格10335253.330016分析表中数据，得S1钢厂钢管的产量上限的变化对购运计划和总费用的影响最大。问题三的模型题图二为树形图，采用Floyd算法，用matlab编程求出单位钢管从S,运输到勺的最小运输费用，具体数据如下表2：表2单位钢管从S,运输到勺的最小运输费用（单位：万元）S1S2S3S4S5S6S7A11707215723072607255726572757A21603205322032503245325532653A31402190220022352225223522452A4986171618162166206621662266A5380111012101560146015601660A620595510551405130514051505A7318609601310121013101410A82127128621162111212121312A96421142482842792842992A109201420820620570620770A1196.0146.086.051.033.051.066.0A1210601560960610510450560A13121217121112762712262382A14128017801180830730110260A1514201920132097087028020由于树形图的出现，则某些管道处会出现多支路。则模型一中模型的勺，，不再适用，此时可考虑多增加一些支路变量，并增加约束，在目标函数中增加相应的铺设费。目标函数:minW*=iij=minW*=iij==1j=1+££i=1j=1ijijLj=2l+LL£(+RRz(Z+1) R(R+1)一jj+ jjImm1nn2 2 2 2j=1 」(m=9,11,17,n=17,19,20)约束条件:①生产能力的限制：500•产：)"1,…，7)(广。或1)J一，②运到勺的钢管用完："j"j+R (J=L..,21且J牛9,11,17)1 Z=1fx=L十R十ZJJJJ(J=9,11,17)Z=1③Aj与Aj』1之间的钢管：J々J%(j=1，...J4)Z+L=42Z+Z=10L+L=1309 16 11 17 17 18R17+L19=190 R+L2260 R20+L、=100④变量非负性限制：J0，Lj-0，R~°，Z-0,(i21,...,7,J21,...,21)⑤运到Aj的钢管整数限制：xj$N运用数学软件Lingo编程求出最优最小费用卬*=1407149.万元6.模型评价与推广此模型是针对钢管订购运输问题的处理方案，其中主要方面在于运输路径的选择，模型中将路径的选择分成两大部分处理，先将货物运到节点，再从节点向全线运输。同时，在解决第一个问题时，把铁路和公路分开计算，最后进行统一，简化了运算。但模型也存在一些不足之处，在对铁路运费矩阵和公路运费矩阵进行统一时，取的还是相对近似值。另外，由于我们在建立约束条件时要求从节点向其他方向运输时，相邻两节点运量加和恰好等于两点间线路距离，因此忽略了跨节点运输的情况，而这里面可能出现较之更优的方案。在解决本题时，我们主要采用的是通过点来表示线路的，同时应用图

论中的floyd算法解决最短路径问题。在生活中，求最短路径的问题常常会碰到，我们可以对模型稍加修改，使之符合问题的条件，进而进行求解。参考文献：【1】周品赵新芬，MATLAB数学建模与仿真，北京：国防工业出版社，2009.4【2】谭永基蔡志杰，数学模型，上海：复旦大学出版社，2011.1【3】谢金星，薛毅.《优化建模与LINGO/LINGO软件》.北京：清华大学出版社,2005【4】宗容,施继红，尉洪，李海燕.《数学实验与数学建模》.云南：云南大学出版社，2009附录：用matlab建立Floyd函数的M文件，编程如下:function[D,path]=floyd(a)n=size(a,1);D=a;path=zeros(n,n);fori=1:nforj=1:nifD(i,j)~=infpath(i,j)=j;endendfork=1:nfori=1:nforj=1:nfork=1:nfori=1:nforj=1:nifD(i,k)+D(k,j)<D(i,j)D(i,j)=D(i,k)+D(k,j);path(i,j)=path(i,k);endendendendendend问题一:1)用Floyd算法求铁路最短距离，以7个钢管厂和17个中转点建立初始距离矩阵%2的4，对于任意两点之间的距离，如果两点之间有铁路直接连接，其值为两点间铁路的距离；如果两点之间没有铁路直接连接，则其值为inf。2)用Floyd算法求公路最短距离，以15个铺设节点、17个中转点和S1、S6、S7三个钢管厂建立初始距离矩阵D125*35，对于任意两点之间的距离，如果两点之间有公路直接连接，其值为两点间公路的距离；如果两点之间没有公路直接连接，则其值为inf。3)用Floyd算法求铁路和公路最少费用，编程如下：%距离转换为费用的程序D1=D1*0.1; %把公路最短距离换算成公路最少费用fork=1:300m1(k)={k};endfork=1:50m2(k)={300+k}D1=D1*0.1; %把公路最短距离换算成公路最少费用fork=1:300m1(k)={k};endfork=1:50m2(k)={300+k}m3(k)=[350+k}m4(k)={400+k}m5(k)={450+k)endfork=1:100m6(k)={500+k)m7(k)={600+k}m8(k)={700+k}m9(k)={800+k}m0(k)={900+k)endfori=1:24换算成铁路最爹费用铁路最短距离

switchD(i,j)

case0D(i,j)=0;casem1D(i,j)=20;casem2D(i,j)=23;casem3D(i,j)=26;casem4D(i,j)=29;casem5D(i,j)=32;casem6D(i,j)=37;casem7D(i,j)=44;casem8D(i,j)=50;casem9D(i,j)=55;casem0D(i,j)=60;otherwiseD(i,j)=ceil((D(i,j)-1000)/100)*5+60;end endend%c矩阵表示七个钢管生产厂到十五个铺设节点之间的距离，先把它们都设成20000（任意一个钢管厂到任意一个铺设节点之间的距离不会超过20000），然后用for循环求出最小值c=[200002000020000200002000020000200002000020000200002000020000200002000020000;200002000020000200002000020000200002000020000200002000020000200002000020000;200002000020000200002000020000200002000020000200002000020000200002000020000;200002000020000200002000020000200002000020000200002000020000200002000020000;200002000020000200002000020000200002000020000200002000020000200002000020000;200002000020000200002000020000200002000020000200002000020000200002000020000;200002000020000200002000020000200002000020000200002000020000200002000020000];fori=1:7 %7个钢管 设节点生产厂forj=8:24 %7个钢管生生产厂fork=1:15%15个铺 产厂和17个中转点，i=1，表示第一个钢管生产厂，j=8,表示第一个中转点ifc(i,k)>D(i,j)+D1(k,j+8)c(i,k)=D(i,j)+D1(k,j+8);%对于所有中转点，在铁路网和公路网上的下标相差8endendendendfori=1:7fork=1:15ifc(i,k)>D(i,1)+D1(k,33)c(i,k)=D(i,1)+D1(k,33);%33代表第一个钢管生产厂S1点end运行结果如下：ifc(i,k)>D(i,6)+D1(k,34)c(i,k)=D(i,6)+D1(k,34);%34代表第六个钢管生产厂S6点endifc(i,k)>D(i,7)+D1(k,35)c(i,k)=D(i,7)+D1(k,35);%35代表第七个钢管生产厂S7点endend%因为S1,S6,S7这三个钢管厂有公路直接连接到铺设节点，所以把这三个点单独处理end1工345g7ag ioLl12L3L5170.70DO1E03EMD140.2000aaemo3H206DQDi.iaoD2ijmD£4.20DO92的1QE121.3am13B142工215.7000WK3EMD131.2000izrsmo111955DQDEE71.3mD114.20DO1J214fi15E171.2am17B1S232ZO70COX0.33L0181GKID121茹而如口46.330032%96111.330]11B15243E0700]250.30102S.33L0216.6010lEfi140.5010i31116.2mo34.幻EC6251S176.3]m93975255.70CO245.3MD225.31H]205.6MD146121111.2KID79.3JM57335171.3am73B7e2E5.TOCO255J3IH0216.6D0015614O,5M013112t2OT084.20CC62514E25.200]11困T275.70CO2®JOTO明5.20印22660301EEi®5mo141131.2OT0%.2000770655田20W252问题一用Lingo软件求解的编程:model:sets:supply/S1..S7/:p,s,t;need/A1..A15/:L,R,b;links(supply,need):c,x;endsetsdata:s=80080010002000200020003000;b=104,301,750,606,194,205,201,680,480,300,220,210,420,500,;c=170.7160.3140.298.638.020.53.121.264.292.096.0106.0121.2128.0142.0215.7205.3190.2171.6111.095.586.071.2114.2142.0146.0156.0171.2178.0192.0230.7220.3200.2181.6121.0105.596.086.248.282.086.096.0111.2118.0132.0260.7250.3235.2216.6156.0140.5131.0116.284.262.051.061.076.283.097.0255.7245.3225.2206.6146.0130.5121.0111.279.257.033.051.071.273.087.0265.7255.3235.2216.6156.0140.5131.0121.284.262.051.045.026.211.028.0275.7265.3245.2226.6166.0150.5141.0131.299.277.066.056.038.226.02.0;enddatamin=@sum(links(i,j):(p(i)+c(i,j))*x(i,j))+0.05*@sum(need(j):L(j厂2+L(j)+R(j厂2+R(j));@for(supply(i):@sum(need(j):x(i,j))>=500*t(i));@for(supply(i):@sum(need(j):x(i,j))<=s(i)*t(i));@for(supply(i):@bin(t(i)));@for(need(j):@sum(supply(i):x(i,j))=L(j)+R(j));@for(need(j)|j#NE#15:b(j)=R(j)+L(j+1));R(15)=0;L(1)=0;@gin(@sum(links(i,j):x(i,j)));p(1)=160;p(2)=155;p(3)=155;p(4)=160;p(5)=155;p(6)=150;p(7)=160;end问题三（1）用Floyd算法求铁路最短距离，matlab编程与问题一相同（2）用Floyd算法求公路最短距离，以21个铺设节点和14个中转点建立初始距离矩阵D2了1*35，D2矩阵的意义与前面D矩阵相似（3）再次调用距离转费用程序，求出铁路和公路最少费用%h矩阵表示七个钢管生产厂到21个铺设节点之间的距离，先把它们都设成20000（任意一个钢管厂到任意一个铺设节点之间的距离不会超过20000），然后用for循环求出最小值h=[20000200002000C200002000020000200002000020000200002000020000200002000020000200002000020000200002000020000;200002000020000200002000020000200002000020000200002000020000200002000020000200002000020000200002000020000;200002000020000200002000020000200002000020000200002000020000200002000020000200002000020000200002000020000;200002000020000200002000020000200002000020000200002000020000200002000020000200002000020000200002000020000;200002000020000200002000020000200002000020000200002000020000200002000020000 200002000020000

fori=1:7m=1;forfori=1:7m=1;fork=[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,24,27,28,29,30,34]forj=8:24ifh(i,m)>D(i,j)+D2(k,j+8)h(i,m)=D(i,j)+D2(k,j+8);endendm=m+1;endendfori=1:7m=1;fork=[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,24,27,28,29,30,34]ifh(i,m)>D(i,1)+D2(k,33)h(i,m)=D(i,1)+D2(k,33);endifh(i,m)>D(i,6)+D2(k,34)h(i,m)=D(i,6)+D2(k,34);endifh(i,m)>D(i,7)+D2(k,35)h(i,m)=D(i,7)+D2(k,35);endm=m+1;endend200002000020000200002000020000200002000020000200002000020000200002000020000200002000020000200002000020000;200002000020000200002000020000200002000020000200002000020000200002000020000200002000020000200002000020000];运行结果如下:1LE 3q5 6T 8■&]LJ233LQL516]7JS192n2LL1707DDQ16D3DD]I4DZD0把Em口362a.fflCD3.1000212QC0B4300092961EE12120DD1231J2即95I0D1D51151252215.7D003J5.3CO：ilyozjr171口»111195.9000玲7120皿1U3ZC014b1%17L20001用192HQ14515D1%165175323a7ooa2203DOJ200ZDO1&1EO1D121im.fflCD死bg2am43300032BGEG11120D0iia□2uB53D951051115128D17D0026D.3CO：i1品14A.S1D013111G3X0函3ZC06251B1而20co0337ffl印砧印7：BO52557HH2J5JOMZ253D0NDGEffl口I4Ena.fflra121-in2ara7930005733517120D073a7753245印EE75金26E7COJ255：3COj2363X£216meIS14Q.90DO131博》］m的2i⑪625137162000112BEO373B1CUTnfsjoh2E5JDO]2452000I6Eifla.fflca141131zim99300D7?皿35LHRDO2S2&35D55322G问题三用软件Lingo编程:model:sets:supply/S1..S7/:p,s,t;need/A1..A21/:L,R,Z,b;links(supply,need):c,x;endsetsdata:p=160155155160155150160;s=80080010002000200020003000;b=104,301,750,606,194,205,201,680,480,300,220,210,420,500,,42,10,130,190,260,100;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,60,95,100,105,115,125215.7,205.3,190.2,17