2000年数学建模B题解答.doc

钢管订购和运输摘要： 本文建立了一个运输问题的最优化模型。通过分析题图一，我们利用Floyd算法求出铁路网和公路网各点间最短路线，然后转化成最少运输，去掉了铁路和公路的性质，使运输网络变成一张供需运输价格表，然后建立了一个以总费用为目标函数的非线性规划模型，利用Lingo 软件，求出问题一的最优解为1278632万元通过对问题一中lingo运行结果的分析，我们得出S5钢厂钢管的销价的变化对购运计划和总费用影响最大，S1钢厂钢管的产量的上限的变化对购运计划和总费用的影响最大。问题三模型的建立原理和问题一的相同，利用Lingo 软件，求得最优解为1407149万元.关键词：Floyd算法，非线性规划，0-1规划一 问题重述有7个生产厂，可以生产输送天然气主管道的钢管。要沿着的主管道铺设, 如题图一所示。图中粗线表示铁路，单细线表示公路，双细线表示要铺设的管道(假设沿管道或者原来有公路，或者建有施工公路)，圆圈表示火车站，每段铁路、公路和管道旁的阿拉伯数字表示里程(单位km)。为方便计，1km主管道钢管称为1单位钢管。一个钢厂如果承担制造这种钢管，至少需要生产500个单位。钢厂在指定期限内能生产该钢管的最大数量为个单位，钢管出厂销价1单位钢管为万元，如下表：1单位钢管的铁路运价如下表：里程(km)300301350351400401450451500运价(万元)2023262932里程(km)5016006017007018008019009011000运价(万元)37445055601000km以上每增加1至100km运价增加5万元。公路运输费用为1单位钢管每公里0.1万元（不足整公里部分按整公里计算）。钢管可由铁路、公路运往铺设地点（不只是运到点，而是管道全线）。（1）请制定一个主管道钢管的订购和运输计划，使总费用最小（给出总费用)。（2）请就（1）的模型分析：哪个钢厂钢管的销价的变化对购运计划和总费用影响最大，哪个钢厂钢管的产量的上限的变化对购运计划和总费用的影响最大，并给出相应的数字结果。（3）如果要铺设的管道不是一条线，而是一个树形图，铁路、公路和管道构成网络，请就这种更一般的情形给出一种解决办法，并对题图二按（1）的要求给出模型和结果。二 问题分析问题一，首先，所有钢管必须运到天然气主管道铺设路线上的节点，然后才能向左或右铺设。必须求出每个钢管厂到每个节点的每单位钢管的最小运输费用。对最小运费的求解，我们采用Floyd算法。先求出铁路网上钢管厂到铁路上任意两点，的最短路线的长度,用matlab求得对应的铁路单位运费；同理用Floyd 算法求出公路网上的任意两点， 的最短公路路线的长度，结果乘以0.1得到公路运费。，j表示所有运输中转点，于是就得到从某钢厂到某铺设点运输单位钢管的最少运输费用。每个铺设点分别向两个方向展开，通过Lingo编程求出最小铺设费用。运输费用加上购买费用再加上铺设费用就是我们所要求的总费用。问题二，通过问题一里面Lingo编程运行得出的结果，分析哪个钢厂钢管的销价的变化对购运计划和总费用影响最大，哪个钢厂钢管的产量的上限的变化对购运计划和总费用的影响最大。问题三，如铺设的管道是一个树形图，铁路、公路和管道构成网络对于题图二，我们可以延用问题一里面的思想，在题图一的基础上多几条铺设路段，9，11，17节点的铺设方向变为 三个方向，其他不变。三 模型的假设与符号说明1) 基本假设:钢管在运输中由铁路运转为公路运时不计中转费用；所需钢管均由 钢厂提供；假设运送的钢管路途中没有损耗。把“钢厂钢管的销价和产量上限变化对总费用和运购计划的影响”理解为在最优解附近的微小变化对总费用和运购计划的影响。销价最小变化是1万元，产量上限的最小变化是1个单位。沿管道或者原来有公路或者建有施工公路。一个钢管厂如果承担制造钢管，至少要生产500个单位。公路运输费用为1单位钢管每公里0.1万元，不足整公里按整公里计算。2) 符号说明 : 钢厂的最大生产能力;: 钢厂 的出厂钢管单位价格(单位: 万元) ;: 公路上一单位钢管的每公里运费( = 0. 1 万元) ;：铁路网上两点间的单位钢管最少运输费用；：题图一公路网上两点间的单位钢管最少运输费用；：题图二公路网上两点间的单位钢管最少运输费用；: 铁路上一单位钢管的运费(分段函数见表1) ;: 1 单位钢管从钢厂运到的最小费用(单位: 万元) ;: 从 到之间的距离(单位: 千米) ;: 钢厂运到的钢管数;: 运到地的钢管向左铺设的数目;: 运到地的钢管向右铺设的数目;：运到地的钢管向第三个方向铺设的数目;: = : 问题一中所求钢管订购、运输的总费用(单位: 万元) ; : 问题二中所求钢管订购、运输的总费用(单位: 万元) ;四 模型的建立与求解问题一的模型：针对题图一，我们采用Floyd算法，用matlab编程求出单位钢管从运输到的最小运输费用，具体数据如下表1：表1 单位钢管从运输到的最小运输费用（单位：万元）对表1的数据进行分析，我们得到一个非线性规划模型：目标函数是总费用W , 它包含三项: 钢管出厂总价Q , 运输费P , 及铺设费T. 即W = Q + P + T其中 ， ， 目标函数为： 约束条件为: 生产能力的限制: 运到的钢管用完: 与之间的钢管: 变量非负性限制: , 运到的钢管整数限制: 运用数学软件Lingo编程求解 最优最小费用万元问题二的模型通过分析问题一中关于销价的约束，Lingo运行后得到的结果得影子价格表示在最优解下“资源”增加一个单位时“效益”的增量，即每个钢厂销售价格每减少一万元，对总费用的影响。从表中数据分析，S5钢厂钢管的销价的变化对购运计划和总费用的影响最大。通过分析问题一中关于产量的约束，Lingo运行后得到的结果得分析表中数据，得S1钢厂钢管的产量上限的变化对购运计划和总费用的影响最大。问题三的模型题图二为树形图，采用Floyd算法，用matlab编程求出单位钢管从运输到的最小运输费用，具体数据如下表2：表2 单位钢管从运输到的最小运输费用 （单位：万元）由于树形图的出现，则某些管道处会出现多支路。 则模型一中模型的 ，不再适用，此时可考虑多增加一些支路变量，并增加约束，在目标函数中增加相应的铺设费。目标函数： 约束条件： 生产能力的限制: 运到的钢管用完: 与之间的钢管: 变量非负性限制: , 运到的钢管整数限制: 运用数学软件Lingo编程求出 最优最小费用万元五 模型优缺点1. 本文先从简单的角度着手建立模型，采用Floyd算法，简化运输网络。过程严谨，理论性强，逻辑严密，而且易于理解。2. 在计算最短路径时，我们采用Floyd算法，相比与Dijkstra算法，减少了大量的重复计算，提高了工作效率。3. 本文大量运用了计算机程序，所有数据均由计算机处理，故误差由计算机精度产生，模型据有良好的稳定性。参考文献：1 谢金星,薛毅.优化建模与LINGO/LINGO软件.北京：清华大学出版社,20052 宗容,施继红,尉洪,李海燕.数学实验与数学建模.云南：云南大学出版社，2009附录用matlab建立Floyd函数的M文件，编程如下：function D,path=floyd(a)n=size(a,1);D=a;path=zeros(n,n);for i=1:n for j=1:n if D(i,j)=inf path(i,j)=j; end endendfor k=1:n for i=1:n for j=1:n if D(i,k)+D(k,j)D(i,j)+D1(k,j+8) c(i,k)=D(i,j)+D1(k,j+8);%对于所有中转点，在铁路网和公路网上的下标相差8 end end endendfor i=1:7for k=1:15 if c(i,k)D(i,1)+D1(k,33) c(i,k)=D(i,1)+D1(k,33);%33代表第一个钢管生产厂S1点 end if c(i,k)D(i,6)+D1(k,34) c(i,k)=D(i,6)+D1(k,34);%34代表第六个钢管生产厂S6点 end if c(i,k)D(i,7)+D1(k,35) c(i,k)=D(i,7)+D1(k,35);%35代表第七个钢管生产厂S7点 endend%因为S1,S6,S7这三个钢管厂有公路直接连接到铺设节点，所以把这三个点单独处理end 运行结果如下：问题一用Lingo软件求解的编程：model: sets: supply/S1.S7/:p,s,t; need/A1.A15/:L,R,b; links(supply,need):c,x; endsets data: s=800 800 1000 2000 2000 2000 3000; b=104,301,750,606,194,205,201,680,480,300,220,210,420,500,; c=170.7 160.3 140.2 98.6 38.0 20.5 3.1 21.2 64.2 92.0 96.0 106.0 121.2 128.0 142.0 215.7 205.3 190.2 171.6 111.0 95.5 86.0 71.2 114.2 142.0 146.0 156.0 171.2 178.0 192.0 230.7 220.3 200.2 181.6 121.0 105.5 96.0 86.2 48.2 82.0 86.0 96.0 111.2 118.0 132.0 260.7 250.3 235.2 216.6 156.0 140.5 131.0 116.2 84.2 62.0 51.0 61.0 76.2 83.0 97.0 255.7 245.3 225.2 206.6 146.0 130.5 121.0 111.2 79.2 57.0 33.0 51.0 71.2 73.0 87.0 265.7 255.3 235.2 216.6 156.0 140.5 131.0 121.2 84.2 62.0 51.0 45.0 26.2 11.0 28.0 275.7 265.3 245.2 226.6 166.0 150.5 141.0 131.2 99.2 77.0 66.0 56.0 38.2 26.0 2.0; enddata min=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)D(i,j)+D2(k,j+8) h(i,m)=D(i,j)+D2(k,j+8); end end m=m+1; endendfor i=1:7 m=1; for k=1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,24,27,28,29,30,34 if h(i,m)D(i,1)+D2(k,33) h(i,m)=D(i,1)+D2(k,33); end if h(i,m)D(i,6)+D2(k,34) h(i,m)=D(i,6)+D2(k,34); end if h(i,m)D(i,7)+D2(k,35) h(i,m)=D(i,7)+D2(k,35); end m=m+1; endend运行结果如下：问题三用软件Lingo编程：model: sets: supply/S1.S7/:p,s,t; need/A1.A21/:L,R,Z,b; links(supply,need):c,x; endsets data: p=160 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, 114.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, 146, 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; en