钢管订购与运输建模论文.doc

2011高教社杯全国大学生数学建模竞赛承 诺 书我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。我们参赛选择的题号是（从A/B/C/D中选择一项填写）： B 我们的参赛报名号为（如果赛区设置报名号的话）： 所属学校（请填写完整的全名）： 参赛队员 (打印并签名) ：1. 指导教师或指导教师组负责人 (打印并签名)： 日期： 2012 年 8 月 12 日赛区评阅编号（由赛区组委会评阅前进行编号）：2011高教社杯全国大学生数学建模竞赛编 号 专 用 页赛区评阅编号（由赛区组委会评阅前进行编号）：赛区评阅记录（可供赛区评阅时使用）：评阅人评分备注全国统一编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评阅前进行编号）：钢管订购和运输摘要本文要解决三个问题，其中问题二和问题三是建立在问题一的基础上的，所以我们首要的问题是解决问题一。而问题一是一个非线性的整数规划模型，我们需要写出总的最小花费的函数以及约束条件。首先，问题一的函数比较复杂，我们可以分成三步进行：钢管的出厂花费，钢管的道路运输费用，钢管的铺设运输费用。而道路运输费用又可以分为铁路运输费用和公路运输费用。对上述函数分布求出其花费后求和即是最小花费的函数。然后是列出约束条件，利用lingo求得问题一中的最小花费为：1278632万元。在问题一的基础上，我们开始分析问题二中，各钢厂钢管的销售价格和产量上限改变对订购计划的影响。分别上调和下调各钢厂的销售价格一万元后，所得的最小花费与问题一中的最小花费进行比较，并对花费差价绝对值求和，比较各厂对问题的重述 要铺设一条的输送天然气的主管道,经筛选后可以生产这种主管道钢管的钢厂有。一个钢厂如果承担制造这种钢管，至少需要生产500个单位。钢厂在指定期限内能生产该钢管的最大数量为个单位，钢管出厂销价1单位钢管为万元，如下表：123456780080010002000200020003000160155155160155150160 钢管可由铁路、公路从钢厂运往铺设地点（不只是运到点，而是管道全线）。1单位钢管公路运费为0.1万元每公里，铁路运费为一分段函数，具体如下：里程(km)3003013503514004014504515005016006017007018008019009011000运价(万元)20232629323744505560问题： （1）制定一个主管道钢管的订购和运输计划，使总费用最小（给出总费用)。 （2）就（1）的模型分析：哪个钢厂钢管的销价的变化对购运计划和总费用影响最大，哪个钢厂钢管的产量的上限的变化对购运计划和总费用的影响最大，并给出相应的数字结果。 （3）如果要铺设的管道不是一条线，而是一个树形图（树形图略），铁路、公路和管道构成网络，请就这种更一般的情形给出一种解决办法，并对树形图按（1）的要求给出模型和结果。 解决问题（1），我们可以直接得出从各厂的的订购数量和运输费用的最优解，即最小花费的具体方案。解决问题（2），我们可以得出各个钢厂销售价格及产量上限的变化对购运计划的影响。解决问题（3），我们可以完成对树形管道的运购计划制定的推广。 模型的假设1. 假设沿管道或者原来有公路，或者建有施工公路;2. 在选择路线时仅考虑运输花费的多少而不考虑运输的路况等其他因素的影响；3. 在计算总费用时，仅考虑出厂及运输费用，不考虑其他费用；4. 在铺设运输时，每公里卸1单位的钢管，且假设到终点后才卸下；5. 钢厂因各种原因导致生产上限的变化时，变化幅度不超过本身的10%。符号系统符号说明第个钢厂，第个钢厂的最大产量，第个钢厂1单位钢管的出厂价格，待铺设管道上的第个节点，铁路与公路第个分界点，钢厂至节点1单位钢管的出厂运输费用，节点向钢厂订购的钢管数量，节点向左铺设的距离，节点向右铺设的距离，节点与节点的距离，节点向各钢厂订购的总数，出厂道路运输铺设运输总花费,时提供钢管，时不提供钢管，树形图中钢厂至节点1单位钢管的出厂运输费用，树形图中节点向钢厂订购的钢管数量，节点向节点铺设的距离，节点向各钢厂订购的总数，树形图出厂道路运输铺设运输总花费模型的分析与求解我们有三个问题需要解决，而第二个问题是建立在第一个问题解决的情况下，第三个问题又是第一个问题的推广，所以解决第一个问题是解决所有问题的关键。第一个问题需要我们找出钢管的最优订购及运输计划，使钢管铺设的花费最小。为简化分析，我们可以将铺设花费分成三部分：出厂费用（钢管销售价格），道路运输费用，铺设运输费用三部分。首先，我们分析1单位钢管的花费。1单位钢管的出厂费用我们可以直接从题中得到1单位钢管各钢厂的出厂费用，单位：万元。 表一 1单位钢管各钢厂的出厂费用厂家1234567出厂价格1601551551601551501601单位钢管的道路运输费用 钢管的道路运输费用可以分为铁路运输费用和公路运输费用，而铁路运输费用为一分段函数，故和公路运输费用分别计算。 为分别计算铁路与公路的运输费用，我们增设公路与铁路分界点，共17个，具体分布见下图。图一 铁路与公路分界点具体分布图 铁路运输的费用和运输距离有关，首先计算从到铁路与公路交点的最短路径。把上图的铁路路线视作图论中的图，首先给所有的节点进行标号，然后以节点之间的距离作为系数写出图对应的稀疏矩阵。通过调用matlab函数graphshortestpath()计算出各个钢厂到各个公路和铁路分界点的最短距离，计算最短距离使用Dijkstra算法。得到最短路径，最短路径结果详见附录。再将结果代入铁路运费的分段函数中，就可以得到对应的最小铁路运输费用，单位：万元。表二 从到铁路与公路交点的最短路径所花费用1602052202502452552651401902002352252352458012514017016517518537110120155145155165209510514013014015020859513012013014008595130120130140207085115110120130601104480758095851357555505570951458550325065105155956050445511516510570652032130180115807502612517511580702023140190130958526201401901309590260 再考虑公路的运输费用，1单位钢管的最下铁路运输费用加上公路运输费用，用图表示成以下形式：以为例。 将公路长度量化成单位钢材的运输费用，加上各钢厂到公路铁路节点处最短路径费用，可得各钢厂到各节点的最少运费，用1单位钢管的道路运输费用表示。计算最短最小费用的方法和计算最短路径的方法相同，把如上所示的运费图用稀疏矩阵表示，节点之间的价格作为系数。考虑到节点的重合情况（比如在上图中，钢厂S1和节点b7重合），我们约定其为两个节点，其间的运费规定为0。对于不直接相连的节点，在用矩阵表示的时候规定运费为无穷大（inf）。在输入到matlab函数graphshortestpath()时，由于函数默认系数为零表示不相关的点，所以我们把得到的矩阵中所有的inf换成0，把所有的0换成eps（其值为），计算出各个钢厂到各个节点的最小运费，最小运费的表格详见附录。1单位钢管的订购道路运输费用上述结果加上对应的销售价格可以得出购买和运输1单位钢管的最小费用。即得到1单位钢管从钢厂运输到所需最小费用，如下表所示。1单位钢管从出厂到铺设节点的最小花费表，单位：万元。表三 1单位钢管从出厂到铺设节点的最小花费330.7370.7385.7420.7410.7415.7435.7320.3360.3375.3410.3400.3405.3425.3300.2345.2355.2395.2380.2385.2405.2258.6326.6336.6376.6361.6366.6386.6198266276316301306326180.5250.5260.5300.5285.5290.5310.5163.1241251291276281301181.2226.2241.2276.2266.2271.2291.2224.2269.2203.2244.2234.2234.2259.2252297237222212212237256301241211188201226266311251221206195216281.2326.2266.2236.2226.2176.2198.2288333273243228161186302347287257242178162 1单位钢管从钢厂运输到节点所需最小费用（包含出厂费用及道路运输费用）为，即是节点向钢厂订购钢材出厂运输费的系数矩阵。钢管的出厂运输费用为，及除铺设运输费用的其他费用之和。各节点的铺设运输费用将钢材运到各个节点后，我们最后考虑的就是把钢材运输到施工点进行铺设运输。而一个节点既可以往左铺设又可以往右铺设（端节点除外）。节点向左铺设的距离为，向右铺设的距离为，节点从各个钢厂订购的总数为，则有。又的距离为，则有。从向铺设的距离为，则其铺设运费为： 从向铺设的距离为，则其铺设运费为：且有的关系。 那么钢管的铺设运输费用为：总费用的计算 总费用包括出厂运输费及铺设运输费，总花费为： 又一个钢厂承担制造任务的最小量为500单位，而钢厂在指定期限内最大生产量为，所以有约束或者不承担。综上，该问题可以转化为以下非线性规划模型：上述约束中，在lingo的实际运用中比较困难，我们引入，将上述约束简化成，。用lingo代码求出最小花费为1278632万元，具体的各厂运到个铺设点的结果如下，具体代码详见附录。表四 各节点向钢厂的订购方案00000000179000000000509000321146000033601880920019900000026500000003000000000000000066603500000004150000000860000003330000006210000001650总和80080010000136612050各钢厂钢管销价的变化对购运计划的影响 针对问题二中销价对购运计划的影响，我们把每个钢厂的价格上调和降低一万元，求得结果与原来最小结果的差进行比较，运算的结果做成表格如图所示：表五 各钢厂钢管销价的变化对购运计划价格上涨一单位最小花费增幅80080010000100812030价格下降一单位最小花费增幅-800-800-10000-1369-15630两个增幅绝对值之和的平均值800800100001188.513830 上表中，在改变相同价格的情况下，钢厂的销价变化对最小花费的结果影响最大。各钢厂钢管销价的变化对购运计划的影响对于产量上限的分析，我们同上述销价方法一样，增加或减少原产量上限的10%，求得结果与原来最小结果的差进行比较，运算的结果做成表格如图所示：表六 钢厂钢管销价的变化对购运计划的影响生产上限增加10%最小花费增幅-8240-2800-25000000生产上限降低10%最小花费增幅8240280025000000两个增幅绝对值之和的平均值8240280025000000上表中，在生产上限改变相同幅度的情况下，钢厂的生产上限的变化对最小花费结果影响最大。问题三树形图的推广对于第三个问题,我们可以采用与第一个问题相同的方法。首先计算出钢厂到铁路与公路分界点（共18个，具体的标示详见附录。）的最短距离，然后再计算出1单位钢管从各钢厂到各节点（管道端点）的最小运输费用。在第一问的基础上，计算铁路最短运输距离时，我们只需多加一个铁路与公路的分界点即可，计算最小运费的时候只需多添加6个节点。所以可以按照相同的方法利用matlab求解。计算所得1单位钢管从运至的最短铁路运输费用，及1单位钢管从运至的最少运输费用如下表所示，单位：万元表六 1单位钢管从运至的最短铁路运输费用1602052202502452552651401902002352252352458012514017016517518537110120155145155165209510514013014015020859513012013014008595130120130140207085115110120130601104480758095851357555505570951458550325065105155956050445510015090555037011516510570652032130180115807502612517511580702023140190130958526201401901309590260表七 1单位钢管从运至的最少运输费用170.7215.7230.7260.7255.7265.7275.7160.3205.3220.3250.3245.3255.3265.3140.2190.2200.2235.2225.2235.2245.298.6171.6181.6216.6206.6216.6206.63811112115614615614620.595.5105.5140.5130.5138.5128.53.18696131121121.1111.121.271.286.2116.2111.2121.2129.264.2114.248.284.279.284.2929214282625754449614686513324141061569661514333121.2171.2111.276.264.226.238.2121171111766611211421921329787282601104480758093.29514585503223131001509055451001051559560504232115165105705820321101601006555010树形图中，表示节点向钢厂订购的钢管数量，上表为1单位钢管的出厂运输费用表示，则钢管的出厂运输费用为。最后考虑树形图的铺设运输费用，双向铺设的节点和问题一种的计算完全一样，三向铺设的点有，三个节点，显然只要特殊考虑满足铺设要求即可。 所以钢管的铺设运输费用为：再加上前面的钢管的出厂运输费，则有，钢管的总花费为：最后我们得到树形图的非线性规划模型：参考文献附录附录一最短路径的matlab求解程序（注：要在相应目录下运行。）：clear all;clc;load tu_tielu_sparse.mat;S=8 9 11 15 17 22 24;B=1 3 4 5 6 7 8 10 12 13 16 18 20 22 21 23 24;dist_7=zeros(7,17);for i=1:7dist,path=graphshortestpath(tu_tielu_sparse,S(i),B)dist_7(i,:)=dist;end附录二从到铁路与公路交点的最短路径S1S2S3S4S5S6S7A1290225321302521215200A23900353023001923161714221402A34110374025102133182716321612A44800443032002823251723222302A54660429030602683237721822162A64820445032202843253723422322A75070470034703093278725922572A8290225321302521215200A93900353023001923161714221402A104110374025102133182716321612A114800443032002823251723222302A124660429030602683237721822162A134820445032202843253723422322A145070470034703093278725922572A15290225321302521215200附录三最小道路运费的matlab函数（注：要在相应目录下运行。）：clear all;clc;load expense_tielu;load yunshu_jiage;expense_suoyou=zeros(7,15);for i=1:7jiage(1,2:18)=expense_tielu(i,:);jiage(2:18,1)=expense_tielu(i,:);jiage_sparse=sparse(jiage);B = 19:1:33;expense=graphshortestpath(jiage_sparse,1,B);expense_suoyou(i,:)=expense;end;附录四单位钢管从钢厂运输到所需最小道路运输费用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.18696131121131141A821.271.286.2116.2111.2121.2131.2A964.2114.248.284.279.284.299.2A10921428262576277A11961468651335166A121061569661514556A13121.2171.2111.276.271.226.238.2A1412817811883731126A151421921329787282附录五运算的lingo代码model: sets: gangchang/S1.S7/:s,t; pushedian/A1.A15/:y,z,d; links(gangchang,pushedian):a,x; endsets data: s=800 800 1000 2000 2000 2000 3000; /表示每个钢厂生产的上限 d=104,301,750,606,194,205,201,680,480,300,220,210,420,500,0; /相邻铺设点之间的距离，最 后一个用0代替 a=330.7 320.3 300.2 258.6 198 180.5 163.