数学建模实验二.doc

钢管订购和运输一、实验目的学习数学规划建模方法，并能够利用lindo或lingo 完成计算，并完成一篇完整论文，对问题结果做简单分析。二、实验内容1、 原始问题(2000-B-1)有7个生产厂，可以生产输送天然气主管道的钢管Sii=1,2,3,4,5,6,7。要沿着Aii=115的主管道铺设, 如题图一所示。图中粗线表示铁路，单细线表示公路，双细线表示要铺设的管道(假设沿管道或者原来有公路，或者建有施工公路)，圆圈表示火车站，每段铁路、公路和管道旁的阿拉伯数字表示里程(单位km)。为方便计，1km主管道钢管称为1单位钢管。一个钢厂如果承担制造这种钢管，至少需要生产500个单位。钢厂Si在指定期限内能生产该钢管的最大数量为Si个单位，钢管出厂销价1单位钢管为Pi万元，如下表：表 1钢铁厂的最大产量和单位钢管的价格表 2 1单位钢管的铁路运价如下表里程(km)300301350351400401450451500运价(万)2023262932里程(km)5016006017007018008019009011000运价(万)37445055601000km以上每增加1至100km运价增加5万元。公路运输费用为1单位钢管每公里0.1万元（不足整公里部分按整公里计算）。钢管可由铁路、公路运往铺设地点（不只是运到点，而是Aii=115管道全线）。请制定一个主管道钢管的订购和运输计划，使总费用最小（给出总费用)？2、 Floyd算法介绍通过一个图的权值矩阵求出它的每两点间的最短路径矩阵。从图的带权邻接矩阵A=a(i,j)n*n开始，递归地进行n次更新，最终得到D(n)，矩阵的i行j列元素是i号顶点到j号顶点的最短路径长度，称D(n)为图的距离矩阵，同时还可引入一个后继结点矩阵path来记录两点间的最短路径。算法过程为： 从任意一条单边路径开始。所有两点之间的距离是边的权，如果两点之间没有边相连，则权为无穷大。 对于每一对顶点 u 和 v，看看是否存在一个顶点 w 使得从 u 到 w 再到 v 比已知的路径更短。如果是更新它。 把图用邻接距阵G表示出来，如果从Vi到Vj有路可达，则Gi,j=d，d表示该路的长度；否则Gi,j=无穷大。 定义一个距阵D用来记录所插入点的信息，Di,j表示从Vi到Vj需要经过的点，初始化Di,j=j。 把各个顶点插入图中，比较插点后的距离与原来的距离，Gi,j = min( Gi,j, Gi,k+Gk,j )，如果Gi,j的值变小，则Di,j=k。 在G中包含有两点之间最短道路的信息，而在D中则包含了最短通路径的信息。比如，要寻找从V5到V1的路径。根据D，假如D(5,1)=3则说明从V5到V1经过V3，路径为V5,V3,V1，如果D(5,3)=3，说明V5与V3直接相连，如果D(3,1)=1，说明V3与V1直接相连。3、 问题分析首先，所有钢管必须运到天然气主管道铺设路线上的节点Aii=115，然后才能向左或右铺设。必须求出每个钢管厂Sii=1,2,3,4,5,6,7到每个节点Aii=115的每单位钢管的最小运输费用。对最小运费的求解，我们采用Floyd算法。先求出铁路网上钢管厂到铁路上任意两点Vi，Vj的最短路线的长度Lij,用matlab求得Lij对应的铁路单位运费Dij；同理用Floyd 算法求出公路网上的任意两点Vj，Vk 的最短公路路线的长度Ljk，结果乘以0.1得到公路运费D1jk。Cik=min(Dij+D1jk)，j表示所有运输中转点，于是就得到从某钢厂到某铺设点运输单位钢管的最少运输费用。每个铺设点分别向R.L两个方向展开，通过Lingo编程求出最小铺设费用。运输费用加上购买费用再加上铺设费用就是我们所要求的总费用。4、模型的假设与符号说明1) 基本假设钢管在运输中由铁路运转为公路运时不计中转费用；所需钢管均由Sii=1,2,3,4,5,6,7 钢厂提供；假设运送的钢管路途中没有损耗。2) 符号说明Si:钢厂Si的最大生产能力;Pi:钢厂Si 的出厂钢管单位价格(单位: 万元) ;d:公路上一单位钢管的每公里运费(d = 0. 1 万元) ;Dij铁路网上两点间的单位钢管最少运输费用；D1jk:公路网上两点间的单位钢管最少运输费用；e:铁路上一单位钢管的运费(分段函数见表1) ;Cij:1单位钢管从钢厂Si运到Aj的最小费用(单位: 万元) ;bj:从Aj 到Aj+1之间的距离(单位: 千米) ;Xij:钢厂Si运到Aj的钢管数;Lj:运到Aj地的钢管向左铺设的数目;Rj:运到Aj地的钢管向右铺设的数目;Zj运到Aj地的钢管向第三个方向铺设的数目;ti: =W :所求钢管订购、运输的总费用(单位: 万元) 。5、 模型的建立与求解我们采用Floyd算法，用Matlab编程求出单位钢管从Si运输到Aj的最小运输费用，具体数据如下表3：表 3单位钢管从Si运输到Aj的最小运输费用对表3的数据进行分析，我们得到一个非线性规划模型：目标函数是总费用W , 它包含三项: 钢管出厂总价Q , 运输费P , 及铺设费T. 即： W = Q + P + T (1)其中 (2) (3) (4)目标函数为： (5) 约束条件为: 生产能力的限制: 500*tixij*ti (i=17,j=115,ti=0或1) (6) 运到Aj的钢管用完: ixij=Lj+Rj（i=17,j=115） (7) Aj与Aj+1之间的钢管: Lj+1+Rj=bj (j=1.14) (8) 变量非负性限制: Xij0,Lj0,Rj0 (i=1.7,j=114) (9) 运到Aj的钢管整数限制: (10) 运用数学软件Lingo编程求解，最优最小费用万元6、模型优缺点1) 本文先从简单的角度着手建立模型，采用Floyd算法，简化运输网络。过程严谨，理论性强，逻辑严密，而且易于理解。2) 在计算最短路径时，我们采用Floyd算法，相比与Dijkstra算法，减少了大量的重复计算，提高了工作效率。3) 本文大量运用了计算机程序，所有数据均由计算机处理，故误差由计算机精度产生，模型据有良好的稳定性。7、程序1）Floyd算法函数在matlab下的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;endendendfor k=1:nfor i=1:nfor j=1:nif D(i,k)+D(k,j)D(i,j)+D1(j-7,k);c(i,k-17)=D(i,j)+D1(j-7,k);%对于所有中转点，在铁路网和公路网上的下标相差8endendendend%因为S1,S6,S7这三个钢管厂有公路直接连接到铺设节点，所以把这三个点单独处理for i=1:7for k=18:32 if c(i,k-17)D(i,1)+D1(33,k) c(i,k-17)=D(i,1)+D1(33,k);%33代表第一个钢管生产厂S1点 end if c(i,k-17)D(i,6)+D1(34,k) c(i,k-17)=D(i,6)+D1(34,k);%34代表第六个钢管生产厂S6点 end if c(i,k-17)D(i,7)+D1(35,k) c(i,k-17)=D(i,7)+D1(35,k);%35代表第七个钢管生产厂S7点endendend MATLAB程序运行结果：3）用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)=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)=15