钢管的订购及运输优化方案

1钢管的订购及运输优化方案承诺书我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛规则的,如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。我们参赛选择的题号是（从A/B/C/D中选择一项填写）：A我们的参赛报名号为（如果赛区设置报名号的话）：所属学校（请填写完整的全名）：吉林省建筑工程学院建筑装饰学院参赛队员(打印并签名)：1.姜磊2.魏文超3.张晓斌指导教师或指导教师组负责人(打印并签名)：杨雪日期：2009年9月14日赛区评阅编号（由赛区组委会评阅前进行编号）：22009高教社杯全国大学生数学建模竞赛编号专用页赛区评阅编号（由赛区组委会评阅前进行编号）：赛区评阅记录（可供赛区评阅时使用）：评阅人评分备注全国统一编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评阅前进行编号）：3摘要:从本题中可以看出我们要解决的问题是钢管怎样订购，怎样运输，才能使得总费用最少。所以，我们从两个方面着手考虑这个问题，首先我们考虑怎样从钢厂订购货物，接下来我们考虑在订购好货物后我们怎样把货物运输到目的地。对于这两个问题，从题目可知，订购和运输联系密切，所以，我们必须同时考虑考虑钢管的订购与运输。再由题中给的钢厂与天然气管道路线分布图可以看出，该问题等同于把起点的信息通过最优路（即就是花费最少的路径）径送到目的地，在送往的途中可以有信息的流失，流失的信息即就是用于铺设道路的货物，但不管流失多少信息，到达目的地时，总还有剩余的信息。所以，我们就把钢管的运输看成了最小费用最大流问题。所以，我们通过对线路的标号，我们利用floyd算出最大流问题算出每一个钢厂到每个点的单位最优路径，然后，再算出在运送途中钢管用于铺设管道所花费的费用，我们把这两种费用相加，就得到了总的费用。我们通过计算，得出应从哪些钢厂订购多少货物，以怎样的路径进行运送才能使总费用最小。经过计算我们得出最优解：其最小费用为1291630万元。在第二问中，我们通过对问题一的精度分析可得：钢厂6S的钢管销价的变化对购运计划和总费用的影响最大；钢管厂1S的钢管产量的上限的变化对总费用的影响最大，钢管厂3S的产量上限的变化对购运计划的影响最大。对于第三问，我们同样运用问题一的解决办法，先求出每一个钢厂到4每段道路的最短路径，然后再求出每一钢厂运送的数量，还有运送途中铺路石所花费的单位费用，最后得出最优解：其最小费用为1396099万元。问题重述：（略）问题分析：本题看似复杂，但经过分析我们可以看出该问题是求在一个有权图中寻求最优路径的问题，然后再求各个钢厂的运送花费问题，对于运送费用问题，由于我们不知道在哪一个钢厂订货，也不知道定多少，也不知道走哪一条路最合适，所以我们我们利用线性规划中的方法，先利用0—1规划模型，当取0时，我们就认为不在该厂订货，或者说我们不选择某一条路径，这样我们就轻易的将这个复杂的问题分解为线性规划问题。该题中从钢厂运送货物到目的地的路径问题等同于把起点的信息通过最优路（即就是花费最少的路径）径送到目的地，在送往的途中可以有信息的流失，流失的信息即就是用于铺设道路的货物，但不管流失多少信息，到达目的地时，总还有剩余的信息。所以，我们就把钢管的运输看成了最小费用最大流问题。所以，我们通过对线路的标号，我们利用最大流问题算出每一个钢厂到每个点的单位最优路径，然后，再算出在运送途中钢管用于铺设管道所花费的费用，我们把这两种费用相加，就得到了总的费用。对于问题二，可以利用问题一在LINGO中对问题已进行编程求解，然后根据该软件中的精度分析对每一个钢厂进行精度分析。我们也可以对每一个钢厂进行精度分析，也就是利用主成分分析的方法。在第三问中，我们可以利用问题一的思路，先找出每一点的最短路径，5再根据0—1规划问题进行求解。基本假设1．沿管道铺设路线上有公路，在计算运费时，与其它普通公路相同；2．公路运输费用为1单位钢管每公里0.1万元（不足整公里的按整公里计算）；3．1km主管道钢管称为1单位钢管；4．一个钢厂如果承担制造这种钢管，至少需要生产500个单位；5．1单位钢管的铁路运价（如表一所示），1000km以上每增加1至100km运价增加5万元；6．管道可由铁路、公路运往铺设地点（不只是运到点1521,,,AAA，而是管道全线）；7．本问题只考虑在铁路和公路上运输的问题，而不考虑在其它路径上的情况；8．模型只考虑钢管销价费用和钢管从钢管厂运送到铺设点的钢管运费，而不考虑其它费用，如转运费用等；9．在公路上卸货,按铺路的要求卸车；10．销售价和运输价不受市场价格变化的影响。11.钢厂生产的钢管都是合格的，不存在返回退货问题；符号说明：iS第i钢管厂is表示iS的最大生产能力6jA表示需要铺设管道路径上的车站jix,从所有iS运往jA的钢管用于铺设jA点前后侧的钢管数jiF,单位产品从iS到jA地的运费jif,表示单位钢管从iS地运往jA地的最小费用1,jjA表示1jjAA和两车站之间需要铺设的管道长度ip从iS订购钢管的单位价格z用于订购和运输的总费用模型的建立与求解:问题一1、模型的建立对本问题而言，实际上是一个要求制定订购和运输计划，使总费用最小的优化问题。本模型的总费用包括钢管的销价和运输总的费用。首先，向某厂订购钢管，然后将在每个厂订购的钢管运往需要铺设的全路段。由本题的要求可以知道在铺设管道时必须经过1521,,AAA点。首先，需要确定将货物从i地运往j地的最优路线；然后，确定运输计划；最后计算将运往j地的钢管铺到各个管道上的运输费用，我们不妨假设运往以j为终点的钢管只铺到与j点相邻的两段管道上。因此，本问题可以按以下步骤求解。1、确定从i地到j地的最优路径，从而确定出单位钢管从i地运往j地的最小运费。设)7,2,1(iSi表示钢管厂，)7,2,1(isi表示iS的最大生产能力，)15,,2,1(jAj表示需要铺设钢管路径上的车站。假设从iS运往jA的钢管用7于铺设jA点前后侧的钢管数为jix,单位，单位产品从iS到jA地的运费为jiF,万元，用jif,表示单位钢管从iS地运往jA地的最小费用，则：j,,minijiFf（1）2、建立从iS厂运送j,ix单位钢管到jA点的运费的模型：用1z表示订购的所有钢管全部运到jA点的总运费，则：001500..,1,171,151,151,15171,,1jijjjjijijjiiiijjiiijjijijijixAyyxyySSxsxtsfxz不生产时当生产时当（2）其中：jy和jy分别表示运到jA地钢管用于铺jA点前边和后边的钢管长度；1,jjA表示1jjAA和之间需要铺设的管道长度3将运到jA处的钢管铺到相邻两段路上的运输费用根据假设，在铺设钢管时，dx单位钢管从第1kk点运到点的运费为：10.1kkdx=0.1（3）由（3）式可得如下模型（1）当1jjyy和均为整单位数时，设其运费用21z表示,则：15111212)1()1(1.0jjjjjyyyyz8（2）当1jjyy和均为非整单位数时，设其运费用22z表示,则：])}[2()1(])[2(])[1{(05.02])[1(])[(2][)1(1.02])[1(])[(2][])[1(1.0111111122jjjjjjjjjjjjjjjjyyyyyyyyyyyyyyyyz其中：][jy表示jy的整数部分；][1jy表示1jy的整数部分;综合上述两式可得：1511112])}[2()1(])[2(])[1{(05.0jjjjjjjyyyyyyz（4）01][][01500..,1,11,171,151,151,jijjjjjjjjijijjiiiijjiiijjixAyyAyyxyySSxsxts不生产时当生产时当其中：2z表示运到jA处的钢管铺到相邻两段路上的运输费用4建立订购费用的模型设3z表示订购管道的总费用，则可建立如下模型：jiiixpz,71151j3（5）用z表示订购和运输的总费用，由（2）、（4）、（5）可得本问题的优化模型9如下：321minzzzz即：jiiijijijijjjjjjjxpfxyyyyyyz,71151j15171,,151111])}[2()1(])[2(])[1{(05.0min01][][01500..,1,11,171,151,151,jijjjjjjjjijijjiiiijjiiijjixAyyAyyxyySSxSxts不生产时当生产时当模型的求解:（1）首先求解jif,此问题相当于求解最小费用流问题，即求出从iS点运送单位钢管到jA点的最小费用。按常规，本问题可以按求最短路的常规方法求解。但由于本问题中沿铁路的单位运费由它前边经过的铁路长度而变化。根据问题的需要，我们不妨假设如果从iS点到jA点的钢管经过铁路后，一旦走公路，那么，该钢管将不会再通过铁路运输。则假设沿铁路行走，直到走到与公路相连为止。如果需要从iS点运钢管到jA点，则需要找出从该点到目的点间的最优路线。现在从每个钢厂出发，求出每个钢厂到需要铺设管道的路径上的每b24S210个节点的单位钢管量的最小费用。那么，我们以iS，jA以及铁路的端点等为点，以钢管的可能运输路线为边，以单位钢管的运输费用为权建立加权图，根据flyod算法求出每个钢管厂iS到各个节点jA的最小单位运输费用。如下表所示：11(2)根据以上结果,继续求解最小总费用的模型原问题属于非线性规划问题的最优解，但针对我们现在的情况来说，不能找到较好的方法求解，我们可以根据线性（非线性）规划问题与网络流分析之间的密切联系，将原问题转化为下面的网络流问题进行求解。本问题在求出iS点到jA点的单位最小运费后，可以转化为有i个钢管厂给j个铺设公路点供钢管，然后第j个铺设点的钢管运往铺设处（管道全线）的网络流问题，假设用)7,,1(isi表示第i个钢管厂的最大生产量，jif,表示从i地运往j地的单位运价，每单位钢管的成本为ip万元，运往j点后的每个点输出的管道数为md运费为mc.。用ix表示第i地流出的钢管总数。我们可以构造源和汇,可建立如下的网络流优化问题。其网络流如下图所示该网络中每段弧上的两个数字，前者是该段弧的容量，后者是与该段弧相应的费用。符号表示该段弧容量无限制。图中：),,1(7Sisi表示第i个钢厂的生产能力)7,,1(ipi表示第i个钢厂生产钢管的销价jif,表示从i地运往j地的单位钢管的运费mc表示运往jA的钢管运往铺道上的费用15)1,2,m(md表示运往jA地的钢管数目121,1,f,1Sip15,1,f11,cd1,7,fS71515,cd15,7,f在上述网络中必须知道mc，这样必须在上述求解网络的基础上加上枚举法。但是，在这样短的时间里不能编出求解此问题的全局最优解。现在只有运用求近似解的方法求解。否则不能求解。我们可以运用现成的软件，比如说Lingo数学软件，但是，在用它求解的过程中，不能将枚举法加在程序里，只有通过其他一些方法求出较好的初始值，然后求出前面一部分的最优解。我们可以在确定j