钢管订购及运输优化方案

钢管的订购及运输优化方案承 诺 书我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。我们参赛选择的题号是（从A/B/C/D中选择一项填写）： A 我们的参赛报名号为（如果赛区设置报名号的话）： 所属学校（请填写完整的全名）： 吉林省建筑工程学院建筑装饰学院 参赛队员 (打印并签名) ：1. 姜 磊 2. 魏文超 3. 张晓斌 指导教师或指导教师组负责人 (打印并签名)： 杨雪 日期： 2009 年 9 月 14 日赛区评阅编号（由赛区组委会评阅前进行编号）：2009高教社杯全国大学生数学建模竞赛编 号 专 用 页赛区评阅编号（由赛区组委会评阅前进行编号）：赛区评阅记录（可供赛区评阅时使用）：评阅人评分备注全国统一编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评阅前进行编号）：摘要:从本题中可以看出我们要解决的问题是钢管怎样订购，怎样运输，才能使得总费用最少。所以，我们从两个方面着手考虑这个问题，首先我们考虑怎样从钢厂订购货物，接下来我们考虑在订购好货物后我们怎样把货物运输到目的地。对于这两个问题，从题目可知，订购和运输联系密切，所以，我们必须同时考虑考虑钢管的订购与运输。再由题中给的钢厂与天然气管道路线分布图可以看出，该问题等同于把起点的信息通过最优路（即就是花费最少的路径）径送到目的地，在送往的途中可以有信息的流失，流失的信息即就是用于铺设道路的货物，但不管流失多少信息，到达目的地时，总还有剩余的信息。所以，我们就把钢管的运输看成了最小费用最大流问题。所以，我们通过对线路的标号，我们利用floyd算出最大流问题算出每一个钢厂到每个点的单位最优路径，然后，再算出在运送途中钢管用于铺设管道所花费的费用，我们把这两种费用相加，就得到了总的费用。我们通过计算，得出应从哪些钢厂订购多少货物，以怎样的路径进行运送才能使总费用最小。经过计算我们得出最优解：其最小费用为1291630万元。在第二问中，我们通过对问题一的精度分析可得：钢厂的钢管销价的变化对购运计划和总费用的影响最大；钢管厂的钢管产量的上限的变化对总费用的影响最大，钢管厂的产量上限的变化对购运计划的影响最大。对于第三问，我们同样运用问题一的解决办法，先求出每一个钢厂到每段道路的最短路径，然后再求出每一钢厂运送的数量，还有运送途中铺路石所花费的单位费用，最后得出最优解：其最小费用为1396099万元。问题重述：（略）问题分析：本题看似复杂，但经过分析我们可以看出该问题是求在一个有权图中寻求最优路径的问题，然后再求各个钢厂的运送花费问题，对于运送费用问题，由于我们不知道在哪一个钢厂订货，也不知道定多少，也不知道走哪一条路最合适，所以我们我们利用线性规划中的方法，先利用01规划模型，当取0时，我们就认为不在该厂订货，或者说我们不选择某一条路径，这样我们就轻易的将这个复杂的问题分解为线性规划问题。该题中从钢厂运送货物到目的地的路径问题等同于把起点的信息通过最优路（即就是花费最少的路径）径送到目的地，在送往的途中可以有信息的流失，流失的信息即就是用于铺设道路的货物，但不管流失多少信息，到达目的地时，总还有剩余的信息。所以，我们就把钢管的运输看成了最小费用最大流问题。所以，我们通过对线路的标号，我们利用最大流问题算出每一个钢厂到每个点的单位最优路径，然后，再算出在运送途中钢管用于铺设管道所花费的费用，我们把这两种费用相加，就得到了总的费用。对于问题二，可以利用问题一在LINGO中对问题已进行编程求解，然后根据该软件中的精度分析对每一个钢厂进行精度分析。我们也可以对每一个钢厂进行精度分析，也就是利用主成分分析的方法。在第三问中，我们可以利用问题一的思路，先找出每一点的最短路径，再根据01规划问题进行求解。基本假设1 沿管道铺设路线上有公路，在计算运费时，与其它普通公路相同；2 公路运输费用为1单位钢管每公里0.1万元（不足整公里的按整公里计算）；3 1主管道钢管称为1单位钢管；4 一个钢厂如果承担制造这种钢管，至少需要生产500个单位；5 1单位钢管的铁路运价（如表一所示），1000以上每增加1至100运价增加5万元；6 管道可由铁路、公路运往铺设地点（不只是运到点，而是管道全线）；7 本问题只考虑在铁路和公路上运输的问题，而不考虑在其它路径上的情况；8 模型只考虑钢管销价费用和钢管从钢管厂运送到铺设点的钢管运费，而不考虑其它费用， 如转运费用等；9 在公路上卸货,按铺路的要求卸车；10 销售价和运输价不受市场价格变化的影响。11.钢厂生产的钢管都是合格的，不存在返回退货问题；符号说明：第钢管厂表示的最大生产能力表示需要铺设管道路径上的车站从所有运往的钢管用于铺设点前后侧的钢管数单位产品从到地的运费表示单位钢管从地运往地的最小费用表示两车站之间需要铺设的管道长度从订购钢管的单位价格用于订购和运输的总费用模型的建立与求解:问题一1、 模型的建立对本问题而言，实际上是一个要求制定订购和运输计划，使总费用最小的优化问题。本模型的总费用包括钢管的销价和运输总的费用。首先，向某厂订购钢管，然后将在每个厂订购的钢管运往需要铺设的全路段。由本题的要求可以知道在铺设管道时必须经过点。首先，需要确定将货物从地运往地的最优路线；然后，确定运输计划；最后计算将运往地的钢管铺到各个管道上的运输费用，我们不妨假设运往以为终点的钢管只铺到与点相邻的两段管道上。因此，本问题可以按以下步骤求解。1、确定从地到地的最优路径，从而确定出单位钢管从地运往地的最小运费。设表示钢管厂，表示的最大生产能力，表示需要铺设钢管路径上的车站。假设从运往的钢管用于铺设点前后侧的钢管数为单位，单位产品从到地的运费为万元，用表示单位钢管从地运往地的最小费用，则： （1）2、建立从厂运送单位钢管到点的运费的模型：用表示订购的所有钢管全部运到点的总运费，则： （2）其中：和分别表示运到地钢管用于铺点前边和后边的钢管长度；表示之间需要铺设的管道长度3将运到处的钢管铺到相邻两段路上的运输费用根据假设，在铺设钢管时，单位钢管从第点的运费为：=0.1 （3）由（3）式可得如下模型（1）当均为整单位数时，设其运费用表示,则：（2）当均为非整单位数时，设其运费用表示,则：其中：表示的整数部分；表示的整数部分;综合上述两式可得： （4）其中：表示运到处的钢管铺到相邻两段路上的运输费用4建立订购费用的模型设表示订购管道的总费用，则可建立如下模型： （5）用表示订购和运输的总费用，由（2）、（4）、（5）可得本问题的优化模型如下：即：模型的求解:（1）首先求解S2b24此问题相当于求解最小费用流问题，即求出从点运送单位钢管到点的最小费用。按常规，本问题可以按求最短路的常规方法求解。但由于本问题中沿铁路的单位运费由它前边经过的铁路长度而变化。根据问题的需要，我们不妨假设如果从点到点的钢管经过铁路后，一旦走公路，那么，该钢管将不会再通过铁路运输。则假设沿铁路行走，直到走到与公路相连为止。如果需要从点运钢管到点，则需要找出从该点到目的点间的最优路线。现在从每个钢厂出发，求出每个钢厂到需要铺设管道的路径上的每个节点的单位钢管量的最小费用。那么，我们以，以及铁路的端点等为点，以钢管的可能运输路线为边，以单位钢管的运输费用为权建立加权图，根据flyod算法求出每个钢管厂到各个节点的最小单位运输费用。如下表所示：(2)根据以上结果, 继续求解最小总费用的模型原问题属于非线性规划问题的最优解，但针对我们现在的情况来说，不能找到较好的方法求解，我们可以根据线性（非线性）规划问题与网络流分析之间的密切联系，将原问题转化为下面的网络流问题进行求解。本问题在求出点到点的单位最小运费后，可以转化为有个钢管厂给个铺设公路点供钢管，然后第个铺设点的钢管运往铺设处（管道全线）的网络流问题，假设用表示第个钢管厂的最大生产量，表示从地运往地的单位运价，每单位钢管的成本为万元，运往j点后的每个点输出的管道数为运费为.。用表示第地流出的钢管总数。我们可以构造源和汇, 可建立如下的网络流优化问题。其网络流如下图所示该网络中每段弧上的两个数字，前者是该段弧的容量，后者是与该段弧相应的费用。符号表示该段弧容量无限制。图中：表示第个钢厂的生产能力表示第个钢厂生产钢管的销价表示从地运往地的单位钢管的运费表示运往的钢管运往铺道上的费用 表示运往地的钢管数目, x1 汇源S7 x7在上述网络中必须知道，这样必须在上述求解网络的基础上加上枚举法。但是，在这样短的时间里不能编出求解此问题的全局最优解。现在只有运用求近似解的方法求解。否则不能求解。我们可以运用现成的软件，比如说Lingo数学软件，但是，在用它求解的过程中，不能将枚举法加在程序里，只有通过其他一些方法求出较好的初始值，然后求出前面一部分的最优解。我们可以在确定处的钢管数后，运用将钢管铺到整段路上的运输费最小为目标确定出下一个局部的最优解。将上述两部分的解结合起来便可求出本问题的近似最优解。首先，根据以下准则，确定出求下图的最优解的初始解。在未给定初始值的情况下,为了使我们的解尽可能地解接近其最优解,我们根据自身的特点和工厂、铁路、公路以及铺设点分布情况，从而我们作出如下规则来确定模型的初始解域：运输位置一旦离开铁路，而到达公路上后就不会再回到铁路上。邻近原则：即将离工厂最近的铺设点为我们优先考虑定购点。钢厂与铺设点之间的运输费用最少的优先考虑为我们的定购点。一旦某工厂被定为定购点，它将尽最大的需求量去定购。大致根据以上规则和其分布特点，我们得到如下较优的初始值，即：堆积点所定购的钢管量为0，261，482，515，571，153，373，212，574，330，317，170，257，655，141。将上述数据作为我们的初始可行解，由后面的程序即可求出其最小费用为：1291630万元，其具体的订货、运输安排如下：订货安排运输安排80080010000134812230问题二：通过分析问题一中关于销价的约束，Lingo运行后得到的结果得影子价格表示在最优解下“资源”增加一个单位时“效益”的增量，即每个钢厂销售价格每减少一万元，对总费用的影响。从表中数据分析，S5钢厂钢管的销价的变化对购运计划和总费用的影响最大。通过分析问题一中关于产量的约束，Lingo运行后得到的结果得分析表中数据，得S1钢厂钢管的产量上限的变化对购运计划和总费用的影响最大。问题三题图二为树形图，采用Floyd算法，用matlab编程求出单位钢管从运输到的最小运输费用由于树形图的出现，则某些管道处会出现多支路。 则模型一中的一些条件就不再适用，此时可考虑多增加一些支路变量，并增加约束，在目标函数中增加相应的铺设费。目标函数：3在确定出上述结果后，运用下列准则，确定下列初始解，再利用相同的方法编制附录中的程序。从而可得到如下最优解：总的最小费用为1396099万元，具体的订货和运输计划详细见下表订货安排运输安排8008005540200017490结果分析由于总费用由订购费用和运输费两部分组成，运输费又由一般线路上的运输费和铺设管道上的运输费组成。我们将其分段求出最优，然后综合考虑，这种解法不容易得到全局最优解，但经过我们多次的反复优化，使我们的结果趋于稳定。预想求出全局最优解，可以按我们在上面提出的非线性优化或网络最小费用最大流求解。另外，我们借助于Lingo软件求解，同时进行了灵敏度分析。模型的评价及改进1优点：1）本问题中运用了现代使用较广的网络流算法，同时又结合枚举法进行求解。这样模型的推广性较强，计算结果较为准确2）问题将费用流转化为网络流，具有较强的推广性和准确性3）本问题构造出的模型算法较简单，也可以运用手算的方法来得到比较满意的结果。2缺点：1）由于本问题有现成的比较先进的解法，但由于缺乏基本的数学软件资料，不能将其准确求解。于在求解最短路时，我们用人工计算容易将问题复杂化，同时，容易出错。3）作为图论问题的技术而言，求解过程较难，且不易求出最优解参考文献1、数学建模（第三版） 姜启源 谢金星 叶俊 高等教育出版社 2006.82、数学模型（第二版） 姜启源 高等教育出版社 19933、数学建模原理与案例 冯杰 黄力伟 王勤 尹成义 科学出版社 2007.5附录用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;endendendfor 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(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这三个钢管厂有公路直接连接到铺设节点，所以把这三个点单独处理end运行结果如下：问题一用Lingo软件求解的编程：model:sets:supply/S1.S7/:p,s,t;need/A1.A15/:L,R,b;links(supply,need):c,x;endsetsdata: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.0215.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.0230.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.0260.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.0255.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.0265.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.0275.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;enddatamin=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);endendm=m+1;endendfor i=1:7m=1;for k=1,2,3,4,5,6,7,8,9,10,11,12,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 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,