2011高教社杯全国大学生数学建模竞赛 承 诺 书 我们仔细阅读了中国大学生数学建模竞赛的竞赛规则. 我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。 我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。 我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。 我们参赛选择的题号是（从A/B/C/D中选择一项填写）： B 我们的参赛报名号为（如果赛区设置报名号的话）： 所属学校（请填写完整的全名）： 参赛队员 (打印并签名) ：1. 指导教师或指导教师组负责人 (打印并签名)： 日期： 2012 年 8 月 12 日 赛区评阅编号（由赛区组委会评阅前进行编号）： 2011高教社杯全国大学生数学建模竞赛 编 号 专 用 页 赛区评阅编号（由赛区组委会评阅前进行编号）： 赛区评阅记录（可供赛区评阅时使用）： 评 阅 人 评 分 备 注 全国统一编号（由赛区组委会送交全国前编号）： 全国评阅编号（由全国组委会评阅前进行编号）： 钢管订购和运输 摘要 本文要解决三个问题，其中问题二和问题三是建立在问题一的基础上的，所以我们首要的问题是解决问题一。而问题一是一个非线性的整数规划模型，我们需要写出总的最小花费的函数以及约束条件。 首先，问题一的函数比较复杂，我们可以分成三步进行：钢管的出厂花费，钢管的道路运输费用，钢管的铺设运输费用。而道路运输费用又可以分为铁路运输费用和公路运输费用。对上述函数分布求出其花费后求和即是最小花费的函数。然后是列出约束条件，利用lingo求得问题一中的最小花费为：1278632万元。 在问题一的基础上，我们开始分析问题二中，各钢厂钢管的销售价格和产量上限改变对订购计划的影响。分别上调和下调各钢厂的销售价格一万元后，所得的最小花费与问题一中的最小花费进行比较，并对花费差价绝对值求和，比较各厂对 问题的重述 要铺设一条的输送天然气的主管道,经筛选后可以生产这种主管道钢管的钢厂有。 一个钢厂如果承担制造这种钢管，至少需要生产500个单位。钢厂在指定期限内能生产该钢管的最大数量为个单位，钢管出厂销价1单位钢管为万元，如下表： 1 2 3 4 5 6 7 800 800 1000 2000 2000 2000 3000 160 155 155 160 155 150 160 钢管可由铁路、公路从钢厂运往铺设地点（不只是运到点，而是管道全线）。1单位钢管公路运费为0.1万元每公里，铁路运费为一分段函数，具体如下： 里程(km) ≤300 301～350 351～400 401～450 451～500 501～600 601～700 701～800 801～900 901～1000 运价(万元) 20 23 26 29 32 37 44 50 55 60 问题： （1）制定一个主管道钢管的订购和运输计划，使总费用最小（给出总费用)。 （2）就（1）的模型分析：哪个钢厂钢管的销价的变化对购运计划和总费用影响最大，哪个钢厂钢管的产量的上限的变化对购运计划和总费用的影响最大，并给出相应的数字结果。 （3）如果要铺设的管道不是一条线，而是一个树形图（树形图略），铁路、公路和管道构成网络，请就这种更一般的情形给出一种解决办法，并对树形图按（1）的要求给出模型和结果。 解决问题（1），我们可以直接得出从各厂的的订购数量和运输费用的最优解，即最小花费的具体方案。解决问题（2），我们可以得出各个钢厂销售价格及产量上限的变化对购运计划的影响。解决问题（3），我们可以完成对树形管道的运购计划制定的推广。 模型的假设 1. 假设沿管道或者原来有公路，或者建有施工公路; 2. 在选择路线时仅考虑运输花费的多少而不考虑运输的路况等其他因素的影响； 3. 在计算总费用时，仅考虑出厂及运输费用，不考虑其他费用； 4. 在铺设运输时，每公里卸1单位的钢管，且假设到终点后才卸下； 5. 钢厂因各种原因导致生产上限的变化时，变化幅度不超过本身的10%。 符号系统 符号 说明 第个钢厂， 第个钢厂的最大产量， 第个钢厂1单位钢管的出厂价格， 待铺设管道上的第个节点， 铁路与公路第个分界点， 钢厂至节点1单位钢管的出厂运输费用，， 节点向钢厂订购的钢管数量，， 节点向左铺设的距离， 节点向右铺设的距离， 节点与节点的距离， 节点向各钢厂订购的总数， 出厂道路运输铺设运输总花费 ,时提供钢管，时不提供钢管， 树形图中钢厂至节点1单位钢管的出厂运输费用，， 树形图中节点向钢厂订购的钢管数量，， 节点向节点铺设的距离，， 节点向各钢厂订购的总数， 树形图出厂道路运输铺设运输总花费 模型的分析与求解 我们有三个问题需要解决，而第二个问题是建立在第一个问题解决的情况下，第三个问题又是第一个问题的推广，所以解决第一个问题是解决所有问题的关键。 第一个问题需要我们找出钢管的最优订购及运输计划，使钢管铺设的花费最小。为简化分析，我们可以将铺设花费分成三部分：出厂费用（钢管销售价格），道路运输费用，铺设运输费用三部分。首先，我们分析1单位钢管的花费。 1单位钢管的出厂费用 我们可以直接从题中得到1单位钢管各钢厂的出厂费用，单位：万元。 表一 1单位钢管各钢厂的出厂费用 厂家 1 2 3 4 5 6 7 出厂价格 160 155 155 160 155 150 160 1单位钢管的道路运输费用 钢管的道路运输费用可以分为铁路运输费用和公路运输费用，而铁路运输费用为一分段函数，故和公路运输费用分别计算。 为分别计算铁路与公路的运输费用，我们增设公路与铁路分界点，共17个，具体分布见下图。 图一 铁路与公路分界点具体分布图 铁路运输的费用和运输距离有关，首先计算从到铁路与公路交点的最短路径。把上图的铁路路线视作图论中的图，首先给所有的节点进行标号，然后以节点之间的距离作为系数写出图对应的稀疏矩阵。通过调用matlab函数graphshortestpath()计算出各个钢厂到各个公路和铁路分界点的最短距离，计算最短距离使用Dijkstra算法。得到最短路径，最短路径结果详见附录。再将结果代入铁路运费的分段函数中，就可以得到对应的最小铁路运输费用，单位：万元。 表二 从到铁路与公路交点的最短路径所花费用 160 205 220 250 245 255 265 140 190 200 235 225 235 245 80 125 140 170 165 175 185 37 110 120 155 145 155 165 20 95 105 140 130 140 150 20 85 95 130 120 130 140 0 85 95 130 120 130 140 20 70 85 115 110 120 130 60 110 44 80 75 80 95 85 135 75 55 50 55 70 95 145 85 50 32 50 65 105 155 95 60 50 44 55 115 165 105 70 65 20 32 130 180 115 80 75 0 26 125 175 115 80 70 20 23 140 190 130 95 85 26 20 140 190 130 95 90 26 0 再考虑公路的运输费用，1单位钢管的最下铁路运输费用加上公路运输费用，用图表示成以下形式：以为例。 将公路长度量化成单位钢材的运输费用，加上各钢厂到公路铁路节点处最短路径费用，可得各钢厂到各节点的最少运费，用1单位钢管的道路运输费用表示。 计算最短最小费用的方法和计算最短路径的方法相同，把如上所示的运费图用稀疏矩阵表示，节点之间的价格作为系数。考虑到节点的重合情况（比如在上图中，钢厂S1和节点b7重合），我们约定其为两个节点，其间的运费规定为0。对于不直接相连的节点，在用矩阵表示的时候规定运费为无穷大（inf）。在输入到matlab函数graphshortestpath()时，由于函数默认系数为零表示不相关的点，所以我们把得到的矩阵中所有的inf换成0，把所有的0换成eps（其值为），计算出各个钢厂到各个节点的最小运费，最小运费的表格详见附录。 1单位钢管的订购道路运输费用 上述结果加上对应的销售价格可以得出购买和运输1单位钢管的最小费用。即得到1单位钢管从钢厂运输到所需最小费用，如下表所示。 1单位钢管从出厂到铺设节点的最小花费表，单位：万元。 表三 1单位钢管从出厂到铺设节点的最小花费 330.7 370.7 385.7 420.7 410.7 415.7 435.7 320.3 360.3 375.3 410.3 400.3 405.3 425.3 300.2 345.2 355.2 395.2 380.2 385.2 405.2 258.6 326.6 336.6 376.6 361.6 366.6 386.6 198 266 276 316 301 306 326 180.5 250.5 260.5 300.5 285.5 290.5 310.5 163.1 241 251 291 276 281 301 181.2 226.2 241.2 276.2 266.2 271.2 291.2 224.2 269.2 203.2 244.2 234.2 234.2 259.2 252 297 237 222 212 212 237 256 301 241 211 188 201 226 266 311 251 221 206 195 216 281.2 326.2 266.2 236.2 226.2 176.2 198.2 288 333 273 243 228 161 186 302 347 287 257 242 178 162 1单位钢管从钢厂运输到节点所需最小费用（包含出厂费用及道路运输费用）为，即是节点向钢厂订购钢材出厂运输费的系数矩阵。钢管的出厂运输费用为，及除铺设运输费用的其他费用之和。 各节点的铺设运输费用 将钢材运到各个节点后，我们最后考虑的就是把钢材运输到施工点进行铺设运输。而一个节点既可以往左铺设又可以往右铺设（端节点除外）。 节点向左铺设的距离为，向右铺设的距离为，节点从各个钢厂订购的总数为，则有。又的距离为，则有。 从向铺设的距离为，则其铺设运费为： 从向铺设的距离为，则其铺设运费为： 且有的关系。 那么钢管的铺设运输费用为： 总费用的计算 总费用包括出厂运输费及铺设运输费，总花费为： 又一个钢厂承担制造任务的最小量为500单位，而钢厂在指定期限内最大生产量为，所以有约束或者不承担。综上，该问题可以转化为以下非线性规划模型： 上述约束中，在lingo的实际运用中比较困难，我们引入，将上述约束简化成，，。用lingo代码求出最小花费为1278632万元，具体的各厂运到个铺设点的结果如下，具体代码详见附录。 表四 各节点向钢厂的订购方案 0 0 0 0 0 0 0 0 179 0 0 0 0 0 0 0 0 0 509 0 0 0 321 146 0 0 0 0 336 0 188 0 92 0 0 199 0 0 0 0 0 0 265 0 0 0 0 0 0 0 300 0 0 0 0 0 0 0 0 0 0 0 0 0 0 666 0 350 0 0 0 0 0 0 415 0 0 0 0 0 0 0 86 0 0 0 0 0 0 333 0 0 0 0 0 0 621 0 0 0 0 0 0 165 0 总和 800 800 1000 0 1366 1205 0 各钢厂钢管销价的变化对购运计划的影响 针对问题二中销价对购运计划的影响，我们把每个钢厂的价格上调和降低一万元，求得结果与原来最小结果的差进行比较，运算的结果做成表格如图所示： 表五 各钢厂钢管销价的变化对购运计划 价格上涨一单位最小花费增幅 800 800 1000 0 1008 1203 0 价格下降一单位最小花费增幅 -800 -800 -1000 0 -1369 -1563 0 两个增幅绝对值之和的平均值 800 800 1000 0 1188.5 1383 0 上表中，在改变相同价格的情况下，钢厂的销价变化对最小花费的结果影响最大。各钢厂钢管销价的变化对购运计划的影响 对于产量上限的分析，我们同上述销价方法一样，增加或减少原产量上限的10%，求得结果与原来最小结果的差进行比较，运算的结果做成表格如图所示： 表六 钢厂钢管销价的变化对购运计划的影响 生产上限增加10%最小花费增幅 -8240 -2800 -2500 0 0 0 0 生产上限降低10%最小花费增幅 8240 2800 2500 0 0 0 0 两个增幅绝对值之和的平均值 8240 2800 2500 0 0 0 0 上表中，在生产上限改变相同幅度的情况下，钢厂的生产上限的变化对最小花费结果影响最大。 问题三树形图的推广 对于第三个问题,我们可以采用与第一个问题相同的方法。首先计算出钢厂到铁路与公路分界点（共18个，具体的标示详见附录。）的最短距离，然后再计算出1单位钢管从各钢厂到各节点（管道端点）的最小运输费用。 在第一问的基础上，计算铁路最短运输距离时，我们只需多加一个铁路与公路的分界点即可，计算最小运费的时候只需多添加6个节点。所以可以按照相同的方法利用matlab求解。 计算所得1单位钢管从运至的最短铁路运输费用，及1单位钢管从运至的最少运输费用如下表所示，单位：万元 表六 1单位钢管从运至的最短铁路运输费用 160 205 220 250 245 255 265 140 190 200 235 225 235 245 80 125 140 170 165 175 185 37 110 120 155 145 155 165 20 95 105 140 130 140 150 20 85 95 130 120 130 140 0 85 95 130 120 130 140 20 70 85 115 110 120 130 60 110 44 80 75 80 95 85 135 75 55 50 55 70 95 145 85 50 32 50 65 105 155 95 60 50 44 55 100 150 90 55 50 37 0 115 165 105 70 65 20 32 130 180 115 80 75 0 26 125 175 115 80 70 20 23 140 190 130 95 85 26 20 140 190 130 95 90 26 0 表七 1单位钢管从运至的最少运输费用 170.7 215.7 230.7 260.7 255.7 265.7 275.7 160.3 205.3 220.3 250.3 245.3 255.3 265.3 140.2 190.2 200.2 235.2 225.2 235.2 245.2 98.6 171.6 181.6 216.6 206.6 216.6 206.6 38 111 121 156 146 156 146 20.5 95.5 105.5 140.5 130.5 138.5 128.5 3.1 86 96 131 121 121.1 111.1 21.2 71.2 86.2 116.2 111.2 121.2 129.2 64.2 114.2 48.2 84.2 79.2 84.2 92 92 142 82 62 57 54 44 96 146 86 51 33 24 14 106 156 96 61 51 43 33 121.2 171.2 111.2 76.2 64.2 26.2 38.2 121 171 111 76 66 11 21 142 192 132 97 87 28 2 60 110 44 80 75 80 93.2 95 145 85 50 32 23 13 100 150 90 55 45 10 0 105 155 95 60 50 42 32 115 165 105 70 58 20 32 110 160 100 65 55 0 10 树形图中，表示节点向钢厂订购的钢管数量，上表为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:7 [dist,path]=graphshortestpath(tu_tielu_sparse,S(i),B) dist_7(i,:)=dist; end 附录二 从到铁路与公路交点的最短路径 S1 S2 S3 S4 S5 S6 S7 A1 2902 2532 1302 521 215 20 0 A2 3900 3530 2300 1923 1617 1422 1402 A3 4110 3740 2510 2133 1827 1632 1612 A4 4800 4430 3200 2823 2517 2322 2302 A5 4660 4290 3060 2683 2377 2182 2162 A6 4820 4450 3220 2843 2537 2342 2322 A7 5070 4700 3470 3093 2787 2592 2572 A8 2902 2532 1302 521 215 20 0 A9 3900 3530 2300 1923 1617 1422 1402 A10 4110 3740 2510 2133 1827 1632 1612 A11 4800 4430 3200 2823 2517 2322 2302 A12 4660 4290 3060 2683 2377 2182 2162 A13 4820 4450 3220 2843 2537 2342 2322 A14 5070 4700 3470 3093 2787 2592 2572 A15 2902 2532 1302 521 215 20 0 附录三 最小道路运费的matlab函数（注：要在相应目录下运行。）： clear all; clc; load expense_tielu; load yunshu_jiage; expense_suoyou=zeros(7,15); for i=1:7 jiage(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; 附录四 单位钢管从钢厂运输到所需最小道路运输费用 S1 S2 S3 S4 S5 S6 S7 A1 170.7 215.7 230.7 260.7 255.7 265.7 275.7 A2 160.3 205.3 220.3 250.3 245.3 255.3 265.3 A3 140.2 190.2 200.2 235.2 225.2 235.2 245.2 A4 98.6 171.6 181.6 216.6 206.6 216.6 226.6 A5 38 111 121 156 146 156 166 A6 20.5 95.5 105.5 140.5 130.5 140.5 150.5 A7 3.1 86 96 131 121 131 141 A8 21.2 71.2 86.2 116.2 111.2 121.2 131.2 A9 64.2 114.2 48.2 84.2 79.2 84.2 99.2 A10 92 142 82 62 57 62 77 A11 96 146 86 51 33 51 66 A12 106 156 96 61 51 45 56 A13 121.2 171.2 111.2 76.2 71.2 26.2 38.2 A14 128 178 118 83 73 11 26 A15 142 192 132 97 87 28 2 附录五 运算的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.1 181.2 224.2 252 256 266 281.2 288 302 370.7 360.3 345.2 326.6 266 250.5 241.0 226.2 269.2 297 301 311 326.2 333 347 385.7 375.3 355.2 336.6 276 260.5 251.0 241.2 203.2 237 241 251 266.2 273 287 420.7 410.3 395.2 376.6 316 300.5 291.0 276.2 244.2 222 211 221 236.2 243 257 410.7 400.3 380.2 361.6 301 285.5 276.0 266.2 234.2 212 188 206 226.2 228 242 415.7 405.3 385.2 366.6 306 290.5 281.0 271.2 234.2 212 201 195 176.2 161 178 435.7 425.3 405.2 386.6 326 310.5 301.0 291.2 259.2 237 226 216 198.2 186 162; enddata min=@sum(links(i,j):a(i,j)*x(i,j))+0.05*@sum(pushedian(j):y(j)^2+y(j)+z(j)^2+z(j)); //最小花费函数 @for(gangchang(i):@sum(pushedian(j):x(i,j))>=500*t(i); @sum(pushedian(j):x(i,j))<=s(i)*t(i); @bin(t(i))); //每个钢厂生产钢的总量满足的条件 @for(pushedian(j):@sum(gangchang(i):x(i,j))=y(j)+z(j)) // @for(pushedian(j)|j#NE#15:d(j)=z(j)+y(j+1)); z(15)=0;y(1)=0; @for(gangchang(i):@for(pushedian(j):@gin(x(i,j)))); End 本文档由香当网(https://www.xiangdang.net)用户上传
