《2000年数学建模B题钢管订购和运输全解答.doc》由会员分享，可在线阅读，更多相关《2000年数学建模B题钢管订购和运输全解答.doc（17页珍藏版）》请在三一文库上搜索。
1、钢管订购和运输摘要：本文建立了一个运输问题的最优化模型。通过分析题图一，我们利用Floyd算法求出铁路网和公路网各点间最短路线，然后转化成最少运输，去掉了铁路和公路的性质，使运输网络变成一张供需运输价格表，然后建立了一个以总费用为目标函数的非线性规划模型，利用Lingo软件，求出问题一的最优解为1278632万元通过对问题一中lingo运行结果的分析，我们得出 S5钢厂钢管的销价的变化 对购运计划和总费用影响最大，S1钢厂钢管的产量的上限的变化对购运计划和总费 用的影响最大。问题三模型的建立原理和问题一的相同，利用Lingo软件，求得最优解为1407149 万元.关键词：Floyd算法，非线性
2、规划，0-1规划一问题重述有7个生产厂，可以生产输送天然气主管道的钢管S1,S2/ s7。要沿着AA2 - A5的主管道铺设，如题图一所示。图中粗线表示铁路，单细线表示公路，双细线表示要铺设的管道（假设沿管道或者原来有公路，或者建有施工公路），圆圈表示火车站，每段铁路、公路和管道旁的阿拉伯数字表示里程（单位km）。为方便计，1km主管道钢管称为1单位钢管。一个钢厂如果承担制造这种钢管，至少需要生产500个单位。钢厂S在指定期限内能生产该钢管的最大数量为Si个单位，钢管出厂销价 1单位钢管为Pi万元，如下表：i1234567Si80080010002000200020003000Pi160155
3、1551601551501601单位钢管的铁路运价如下表:里程（km） 5，然后才能向左或右铺设。必须求出每个钢管厂S,S2,S7到每个节点A A2rrA15的每单位钢管的最小运输费用。对最小运费的求解， 我们采用Floyd算法。先求出铁路网上钢管厂到铁路上任意两点Vi , Vj的最短路线的长度Lj ,用matlab求得Lj对应的铁路单位运费 Dj ；同理用Floyd算法求出公路网上的 任意两点Vj , Vk的最短公路路线的长度Ljk，结果乘以0.1得到公路运费。耳。 Gk =min（Dj D1jQ，j表示所有运输中转点，于是就得到从某钢厂到某铺设点运输单位钢管的 最少运输费用。每个铺设点分别
4、向 R,L两个方向展开，通过 Lingo编程求出最小铺设费用。运输费用加上购 买费用再加上铺设费用就是我们所要求的总费用。问题二，通过问题一里面Lin go编程运行得出的结果，分析哪个钢厂钢管的销价的变化对购运计划和总费用影响最大，哪个钢厂钢管的产量的上限的变化对购运计划和总费用的影响最大。问题三，如铺设的管道是一个树形图，铁路、公路和管道构成网络对于题图二，我们可以延用问题一里面的思想，在题图一的基础上多几条铺设路段，9，11 ,17节点的铺设方向变为 R, L,Z三个方向，其他不变。三 模型的假设与符号说明1）基本假设：CD钢管在运输中由铁路运转为公路运时不计中转费用；所需钢管均由S（i
5、=1,7）钢厂提供；C假设运送的钢管路途中没有损耗。C把“钢厂钢管的销价和产量上限变化对总费用和运购计划的影响”理解为在最优解附近的微小变化对总费用和运购计划的影响。销价最小变化是1万元，产量上限的最小变化是1个单位。（C沿管道或者原来有公路或者建有施工公路。 一个钢管厂如果承担制造钢管，至少要生产500个单位。 公路运输费用为1单位钢管每公里0.1万元，不足整公里按整公里计算。2）符号说明1：S ：钢厂S的最大生产能力；Pi：钢厂S的出厂钢管单位价格（单位：万元）；d :公路上一单位钢管的每公里运费（d = o. 1万元）；Dj ：铁路网上两点间的单位钢管最少运输费用；D1jk :题图一公路
6、网上两点间的单位钢管最少运输费用；D2jk :题图二公路网上两点间的单位钢管最少运输费用；e：铁路上一单位钢管的运费（分段函数见表1）；cij : 1单位钢管从钢厂 S运到Aj的最小费用（单位：万元）；bj :从Aj到A1之间的距离（单位：千米）；1 （其中i =1,2,7而对于第一问：j =1,2,15,对于第二问：j =1,2,21）Xj ：钢厂S运到Aj的钢管数；Lj :运到Aj地的钢管向左铺设的数目Rj :运到Aj地的钢管向右铺设的数目Zj ：运到Aj地的钢管向第三个方向铺设的数目 ；勺钢厂Si提供钢管；t :二乜=。钢厂Si不提供钢管；W :问题一中所求钢管订购、运输的总费用 （单位
7、：万元）；W* :问题二中所求钢管订购、运输的总费用 （单位：万元）；四模型的建立与求解问题一的模型：针对题图一，我们采用Floyd算法，用matlab编程求出单位钢管从S运输到Aj的最小运输费用，具体数据如下表1：表1单位钢管从S运输到Aj的最小运输费用（单位：万元）S1S2S3S4S5S6S7A1170.7215.7230.7260.7255.7265.7275.7A2P 160.3205.3220.3250.3245.3255.3265.3 :A3140.2190.2200.2235.2225.2235.2245.2A498.6171.6181.6216.6206.6216.6226.6
8、A5P 38.0111.0r 121.0156.0146.0 :156.0166.0A620.595.5105.5140.5130.5140.5150.5A73.186.096.0131.0121.0131.0141.0A821.271.286.2116.2111.2121.2131.2A9P 64.2114.248.284.279.284.299.2A1092.0142.082.062.057.062.077.0A1196.0146.086.051.033.051.066.0A12P 106.0156.0r 96.061.051.0 :45.056.0 :A13121.2171.2111.2
9、76.271.226.238.2A14128.0178.0118.083.073.011.026.0A15142.0192.0132.097.087.028.02.0对表1的数据进行分析，我们得到一个非线性规划模型:目标函数是总费用W ,它包含三项：钢管出厂总价 Q ,运输费P ,及铺设费T.即715其中Q八7 pXji 1 j 4715P D Gji 1 j _1Xij ，T宁目标函数为:mi nW715二二Pi Xiji 4 j715一 HCiji 4 jj必 d：5j 4 一 21 Lj Lj1Rj Rj215约束条件为：生产能力的限制：500 *ti 八 Xjj X tj (i = 1
10、,7) (tj 二 0或 1)j二运到 Aj 的钢管用完：、Xj 二LjRj (j =1,.,15)i 土A与Aj 1之间的钢管：片-Ljbj (j =1,14)变量非负性限制：Xjj _0,Lj _0,R _0, (i =1,.,7, j =1,.,15)运到A的钢管整数限制：Xij N运用数学软件Lin go编程求解最优最小费用W =1278632.万元问题二的模型通过分析问题一中关于销价的约束，Lin go运行后得到的结果得S1S2S3S4S5S6S7影子价格吝-800-800-10000-1320-1250.990影子价格表示在最优解下“资源”增加一个单位时“效益”的增量，即每个钢厂销
11、售价格每减少一万元，对总费用的影响。从表中数据分析，S5钢厂钢管的销价的变化对购运计划和总费用的影响最大。通过分析问题一中关于产量的约束，Lin go运行后得到的结果得S1S2S3S4S5S6S7影子价格各10335253.330016分析表中数据，得 S1钢厂钢管的产量上限的变化对购运计划和总费用的影响最大。问题三的模型题图二为树形图，采用Floyd算法，用matlab编程求出单位钢管从S运输到Aj的最小运输费由于树形图的出现，则某些管道处会出现多支路。时可考虑多增加一些支路变量，并增加约束，在目标函数中增加相应的铺设费。 目标函数：Rj不再适用，此721minWpi 悯二二i i j 47
12、21CijXiji 1 j 421 1 L.7 jLj J41Rj Rjj 12+ R(Rn +1)2.Zm(Z m2(m =9,11,17 ,n =17,19,20)-1)用，具体数据如下表 2: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
13、.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
14、.0192.0132.097.087.028.02.0表2单位钢管从S运输到Aj的最小运输费用 （单位：万元）则模型一中模型的 Lj约束条件:生产能力的限制：500 *ti21-、Xij- SijT(i =1,7)(ti运到Aj的钢管用完：=LjRj(j胡,.21且厂9,11,17)Aj与Aj 1之间的钢管R17 L19 =190R17 Xiji=1二 Lj Rj:RjLj 1 = bjZj (j =9,11,17)(j 7,14)乙7 -10L20 = 260L17 - J厂 130r20 l21 = 100变量非负性限制：Xij -,Lj -,Rj-,Zj (i =1,.,7,j =10)
15、运到Aj的钢管整数限制：为 N运用数学软件Lin go编程求出最优最小费用 W =1407149.万元五模型优缺点1. 本文先从简单的角度着手建立模型，采用Floyd算法，简化运输网络。过程严谨，理论性强，逻辑严密，而且易于理解。2. 在计算最短路径时，我们采用Floyd算法，相比与Dijkstra算法，减少了大量的重复计算，提高了工作效率。3. 本文大量运用了计算机程序，所有数据均由计算机处理，故误差由计算机精度产生，模型 据有良好的稳定性。参考文献:1 谢金星，薛毅.优化建模与UNGO/LINGO软件.北京：清华大学出版社，2005宗容,施继红，尉洪，李海燕.数学实验与数学建模.云南：云南
16、大学岀版社，2009附录用matlab建立Floyd函数的M文件，编程如下:function D,path=floyd(a)n=size(a,1);D=a;path=zeros(n,n);for i=1:nfor j=1:nif D(i,j)=infpath(i,j)=j;endendend问题一：for k=1:nfor i=1:nfor j=1:nif D(i,k)+D(k,j)D(i,j)+D1(k,j+8) c(i,k)=D(i,j)+D1(k,j+8);%对于所有中转点，在铁路网和公路网上的下标相差8endendendendfor i=1:7for k=1:15if c(i,k)D(
17、i,1)+D1(k,33)运行结果如下：c(i,k)=D(i,1)+D1(k,33);%33代表第一个钢管生产厂S1点endif c(i,k)D(i,6)+D1(k,34) c(i,k)=D(i,6)+D1(k,34);%34代表第六个钢管生产厂S6点endif c(i,k)D(i,7)+D1(k,35) c(i,k)=D(i,7)+D1(k,35);%35代表第七个钢管生产厂S7点endend%因为S1,S6,S7这三个钢管厂有公路直接连接到铺 设节点，所以把这三个点单独处理end20000200002000020000200002000020000200002000020000200002
18、0000200002000020000;200002000020000200002000020000200002000020000200002000020000200002000020000;200002000020000200002000020000200002000020000200002000020000200002000020000;200002000020000200002000020000200002000020000200002000020000200002000020000;2000020000200002000020000200002000020000200002000020
19、00020000200002000020000;200002000020000200002000020000200002000020000200002000020000200002000020000 La3=500*t(i);for (supply(i):sum(need(j):x(i,j)0in2U3IE16IT3$加i170 700016D.：3OOO140 20009B.6000362050003.100021.2000S4.20OO9296口121.200013614295100105115125：215.7000205.300019020CO171.6000111SHKD9671.2
20、0001U.2000U2146IfiE171.20001731921451501551651753230 7000220.300020020001211055003曲加00&2!：-6lil.ZKD113132勒85暫a1(K1154360血.son335 zm21B.BOOO.汕1405003IB4X00R51647620098397soso6070as5轴.30002為西00ZE.am14S111蓉 200057詢7翅0073FP/n45&575B265 7000255.3000235 3X0216.50001561405000131121 20C004.2COO52513716.2003
21、1128803337100I2757000265.3000245 2000226.6000Tl：i19J5000141131.200099.2000775G36.20002&295B3505532%for i=1:7m=1;fork=1,2,3,4,5,6,7,8,9,10,11,12,13,14,15 ,24,27,28,29,30,34for j=8:24if h(i,m)D(i,j)+D2(k,j+8) h(i,m)=D(i,j)+D2(k,j+8);endendm=m+1;endendfor i=1:7m=1;运行结果如下：fork=1,2,3,4,5,6,7,8,9,10,11,12
22、,13,14,15,24,27,28,29,30,34if h(i,m)D(i,1)+D2(k,33)h(i,m)=D(i,1)+D2(k,33);endif h(i,m)D(i,6)+D2(k,34)h(i,m)=D(i,6)+D2(k,34);endif h(i,m)D(i,7)+D2(k,35) h(i,m)=D(i,7)+D2(k,35);endm=m+1;endend问题三用软件Lingo编程：model :sets :supply/S1.S7/:p,s,t;need/A1.A21/:L,R, Z,b;links(supply,need):c,x;endsetsdata :p=160
23、 155 155160 155 150 160;s=800 800 1000 2000 2000 2000 3000; 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, 171.6, 111,95.5, 86, 71.2, 1
24、14.2, 142, 146, 156, 171.2, 178, 192, 110, 145, 150, 155, 165, 175230.7, 220.3, 200.2, 181.6, 121, 105.5, 96, 86.2, 48.2, 82, 86, 96, 111.2, 118, 132, 44, 85, 90, 95, 105, 115260.7, 250.3, 235.2, 216.6,156, 140.5,131,116.2, 84.2, 62,51,61,76.2,83,97, 80, 50, 55,60,70, 80255.7, 245.3, 225.2, 206.6,14
25、6, 130.5,121,111.2, 79.2, 57,33,51,71.2,73,87, 75, 32, 45,50,65, 75265.7, 255.3, 235.2, 216.6,156, 140.5,131,121.2, 84.2, 62,51,37, 16.2,11,28, 80, 50, 37,36,10, 0275.7, 265.3, 245.2, 226.6,166, 150.5,141,131.2, 99.2, 77,64,56, 38.2,26,2, 95, 63, 50, 55, 32, 26;enddatamin = sum(links(i,j):(p(i)+c(i,
26、j)*x(i,j)+0.05*(sum(need(j)|j#GE#2 #AND#j#LE#21 :L(j)a2+L(j)+sum(need(j)|j#LE#14 :R(j)A2+R(j)+sum(need(j)|j#EQ#9 #OR# j#EQ#11 #OR# j#EQ#17 :Z(j)A2+Z(j)+sum(need(j)|j#EQ#17#OR# j#EQ#19 #OR# j#EQ#20 :R(j)A2+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)|j#NE#9 #AND# j#NE#11 #AND# 倂NE#17:Z(j)=0);for (n