数学建模钢管订购和运输优化模型PPT.ppt

建模案例：钢管订购和运输优化模型建模案例：钢管订购和运输优化模型20002000年年“网易杯网易杯”全国大学生数学建模竞赛全国大学生数学建模竞赛B B综合案例分析综合案例分析 一.问题的提出问题的提出二二.基本假设基本假设1.1.沿铺设的主管道已有公路或者有施工公路沿铺设的主管道已有公路或者有施工公路.2.1km 2.1km 主管道钢管称为一单位钢管，在主管道上，每主管道钢管称为一单位钢管，在主管道上，每千米卸千米卸1 1单位的钢管单位的钢管.3.3.公路运输费用为公路运输费用为1 1单位钢管每千米单位钢管每千米0.10.1万元万元（不足整千米部分按整千米计算）（不足整千米部分按整千米计算）4.4.在计算总费用时，只考虑运输费用和购买钢管的费用，在计算总费用时，只考虑运输费用和购买钢管的费用，而不考虑其他的费用（诸如中转费用）而不考虑其他的费用（诸如中转费用）5.5.假设钢管在铁路运输路程超过假设钢管在铁路运输路程超过1000km,1000km,铁路每增加铁路每增加1 1 至至100km,1100km,1单位钢管运输的运价增至单位钢管运输的运价增至5 5万元万元.6.订购的钢管数量刚好等于需要铺设的钢管数量订购的钢管数量刚好等于需要铺设的钢管数量7.7.销售价和运输价不受市场价格变化的影响销售价和运输价不受市场价格变化的影响三三.符号说明符号说明第 个钢厂,第个钢厂的最大产量，输送天然气的主管道上的第个点，第个钢厂 1 单位钢管的销售价格，钢厂向第个点运输的钢管数量（单位）在点与点之间的公路上，运输点向点方向铺设的钢管数量，1 单位钢管从钢厂到点的最少总费用，即公路运费，铁路运费和钢管销售之和，与第个点相连的公路和铁路的相交点,与第个点相连的的第m条公路和铁路的相交点,相邻结点与点之间的距离,四四.模型的建立与求解模型的建立与求解问题一：讨论如何调整主管道钢管的订购和运输方案使总费用最小问题一：讨论如何调整主管道钢管的订购和运输方案使总费用最小1.1.求钢管从钢厂求钢管从钢厂运到运输点运到运输点的最小费用的最小费用1 1）将图）将图1 1转换为一系列以单位钢管的运输费用为权的赋权图转换为一系列以单位钢管的运输费用为权的赋权图.所以可先求出钢厂所以可先求出钢厂到铁路与公路相交点到铁路与公路相交点的最短路径的最短路径.如图如图3 3 由题意可知：将钢管从钢厂运到运输点的费用包括钢管的销售价格、钢管的铁路运输费用和钢管的公路运输费用.在费用最小时，对钢管的订购和运输进行分配，可得出本问题的最佳方案.总费用总费用=钢厂到各节点的费用钢厂到各节点的费用+主管道的运输（铺设费用）主管道的运输（铺设费用）450801150110030619520202120072069052017069016088462703201607029030图-42）计算单位钢管从计算单位钢管从到到的最少运输费用的最少运输费用根据根据图图4，借助，借助图论软图论软件包中求最短路的方法求出件包中求最短路的方法求出单单位位钢钢管从管从到的最短路，从而得出将单位钢管从的最短路，从而得出将单位钢管从 运输到各运输点运输到各运输点最小费用最小费用。运输费用依次为：运输费用依次为：170.7170.7，160.3160.3，140.2140.2，98.698.6，3838，20.520.5，3.13.1，21.221.2，64.264.2，9292，9696，106106，121.2121.2，128128，142142（单位：万元）（单位：万元）加上单位钢管的销售加上单位钢管的销售价价 得出从钢厂得出从钢厂购买单位钢管运输到点购买单位钢管运输到点的最小费用的最小费用依次为依次为:330.3，320.3，300.2，258.6，198，180.5，163.1，181.2，224.2，252，256，266，281.2，288，302（单位：万元）.同理，可用同样的方法求出钢厂同理，可用同样的方法求出钢厂 到到 的最小费用，从而得出各钢厂的最小费用，从而得出各钢厂Si到运输节点到运输节点 Aj 最小运总费用。见表最小运总费用。见表1.LINGO LINGO 程序：程序：min-costmin-cost1.lg4 计算结果：计算结果：min-cost1.lgr表表1 Si 到点到点 Aj 的最小费用的最小费用2.2.建立模型建立模型运输总费用可分为两部分：运输总费用可分为两部分：运输总费用运输总费用=钢厂到各点的运输费用钢厂到各点的运输费用+主管道的运输（铺设）费用主管道的运输（铺设）费用.从而得出总费用：从而得出总费用：2)2)约束条件约束条件因此本问题可建立如下的非线性规划模型因此本问题可建立如下的非线性规划模型：非线性规划模型可用LINGO软件包或MATLAB软件包来求解，但这些软件包不能直接处理约束条件：可用分支定界法将此条件改为可用分支定界法将此条件改为模型变为模型变为1 1）不让钢厂）不让钢厂S S7 7生产，模型变为生产，模型变为:计算结果：12786321278632（万元）（此时每个钢厂的产量都满足条件）（万元）（此时每个钢厂的产量都满足条件）2 2）要求钢厂）要求钢厂S S7 7 产量不小于产量不小于500500个单位，模型变为个单位，模型变为:计算结果计算结果：12796641279664（万元）（此时每个钢厂的产量都满足条件）（万元）（此时每个钢厂的产量都满足条件）.比较这两种情况，得最优解为比较这两种情况，得最优解为S7不让生产不让生产:=1278632=1278632（万元）具体的购运计划如表（万元）具体的购运计划如表2 2：订购量A2A3A4A5A6A7A8A9A10A11A12A13A14A15S18000201133200266000000000S28001791114295003000000000S31000139111860006640000000S4000000000000000S5101503582420000004150000S6155600000000035186333621165S7000000000000000表表2 2 问题问题1 1的订购和调运方案的订购和调运方案fi表示钢厂表示钢厂i是否使用；是否使用；xij是从钢厂是从钢厂i运到节点运到节点j的钢管量的钢管量yj是从节点是从节点j向左铺设的钢管量；向左铺设的钢管量；zj是向右铺设的钢管量是向右铺设的钢管量 比较好的方法：引入比较好的方法：引入0-10-1变量变量LINDO/LINGO得到的结果比得到的结果比matlab得到的好得到的好yj zjjGUANDAO.lg4参考程序1）运输问题的0-1规划模型将全长5171km的管道按公里分段，共5171个需求点，钢厂为7个供应点，构成如下的运输问题cij为从供应点i到需求点j的最小购运费xij=1表示从点i到点j购运1单位钢管求解时要针对规模问题寻求改进算法Cij 规模太大麻烦规模太大麻烦 问题二问题二、就（、就（1 1）的模型分析：哪个钢厂钢管的销价的变）的模型分析：哪个钢厂钢管的销价的变化对购运计划和总费用影响最大，哪个钢厂钢管的产量的上化对购运计划和总费用影响最大，哪个钢厂钢管的产量的上限的变化对购运计划和总费用的影响最大，并给出相应的数限的变化对购运计划和总费用的影响最大，并给出相应的数字结果字结果.由于钢厂钢管的销售价格变化和钢厂钢管产量的上限变化对购运计划和总费用由于钢厂钢管的销售价格变化和钢厂钢管产量的上限变化对购运计划和总费用造成影响，为更好地考察影响，下面分别进行讨论造成影响，为更好地考察影响，下面分别进行讨论方案中运往各点的运输量的变化量的绝对值之和称为方案中运往各点的运输量的变化量的绝对值之和称为运输方案变化量运输方案变化量1 1）讨论钢厂钢管的销售价格变化对购运计划和总费用的影响）讨论钢厂钢管的销售价格变化对购运计划和总费用的影响 当钢厂钢管的销售价格当钢厂钢管的销售价格 变化时，会对购运计划和总费用造成影响。为更好变化时，会对购运计划和总费用造成影响。为更好地观察每一个钢厂的销售价格地观察每一个钢厂的销售价格 变化时所造成的影响，本问题采用比较法。即：变化时所造成的影响，本问题采用比较法。即：每次只让一个钢厂钢管的销售价格发生相同的变化，其余钢厂钢管的销售价格每次只让一个钢厂钢管的销售价格发生相同的变化，其余钢厂钢管的销售价格不发生变化；当每个钢厂的销售价个发生同样的变化不发生变化；当每个钢厂的销售价个发生同样的变化 C C 时，求出相应的总费时，求出相应的总费用，然后比较。用，然后比较。分析：分析：表3 C=-5表4 C=5表5 C=1表6 C=-1从上述四个表格中可以看出：钢厂钢管的销售价格变化时从上述四个表格中可以看出：钢厂钢管的销售价格变化时，S6对总费用对总费用影响最大影响最大，S5对购运计划影响最大对购运计划影响最大。2)2)讨论钢厂产量的上限变化对购运计划和总费用的影响讨论钢厂产量的上限变化对购运计划和总费用的影响 本问题同样采用比较法。即：每次只改变一个钢厂本问题同样采用比较法。即：每次只改变一个钢厂钢管产量的上限钢管产量的上限，其余，其余钢厂钢管产量上限不发生变化的情况，利用问题一中的模型进行讨论钢厂钢管产量上限不发生变化的情况，利用问题一中的模型进行讨论。a.对产量不受限制的情况计算得到下表对产量不受限制的情况计算得到下表表7 产量不受限制的情形b.对产量下降对产量下降100100的情况计算得到下表的情况计算得到下表表8 产量下降100的情况c.对产量升高对产量升高100 100 的情况计算得到下表的情况计算得到下表表9 产量升高100的情况结论结论：从上述表格中可以看出钢厂钢管产量的上限变化时，从上述表格中可以看出钢厂钢管产量的上限变化时，S S1 1对对 总费用和购运计划影响最大。总费用和购运计划影响最大。问题三、讨论铁路、公路构成网络的情形问题三、讨论铁路、公路构成网络的情形 本问题是讨论铺设的管道是树形图，铁路、公路构成网络的情形，对于这种本问题是讨论铺设的管道是树形图，铁路、公路构成网络的情形，对于这种问题的求解过程，以图问题的求解过程，以图-2-2进行说明。进行说明。1.1.铺设管道是树形图时，基本解法原理铺设管道是树形图时，基本解法原理图图-3A1325801010312012427010881070627030202030450104301750606194205201680480300220210420500600306195202720690520170690462160320160110290115011001200A2A3A4A5A6A7A8A9A10A11A12A13A14A15S1S2S3S4S5S6S7 为求出一般由铁路、公路、管道构成网络情况下的最优购运和最小总费用为求出一般由铁路、公路、管道构成网络情况下的最优购运和最小总费用方案，方案，首先必须求出各钢厂到个管道节点的最短费用路径首先必须求出各钢厂到个管道节点的最短费用路径。由于在途中可能。由于在途中可能发生火车发生火车汽车汽车火车的转运方案，而这种情况发生的前提条件是公路火车的转运方案，而这种情况发生的前提条件是公路（或管道）的两端必须都是火车站点，由于铁路运输的费用是分段函数，故（或管道）的两端必须都是火车站点，由于铁路运输的费用是分段函数，故求各钢厂到各管道结点的最小费用步骤如下：求各钢厂到各管道结点的最小费用步骤如下：1）首先找出公路的两个端点都是火车站站点的结点）首先找出公路的两个端点都是火车站站点的结点V V1 1,V,V2 2,Vs,Vs2)2)把公路网和铁路网分开，分别组成网络；把公路网和铁路网分开，分别组成网络；3 3）在铁路网中求出各钢厂）在铁路网中求出各钢厂S Si i及各点及各点V Vi i到各火车站点的最短路，并把它转化到各火车站点的最短路，并把它转化 为最小费用路为最小费用路4)4)在公路网中求出各管道结点到各火车站点的最短路，并把它转化为最小在公路网中求出各管道结点到各火车站点的最短路，并把它转化为最小 费用路费用路5 5）把前面的结点合并成一个网络，分别求出各钢厂）把前面的结点合并成一个网络，分别求出各钢厂S Si i 到各管道结点的最小到各管道结点的最小 运输费用路运输费用路。并求出各钢厂并求出各钢厂 Si到各管道结点到各管道结点Aj的最小费用，由此可得到的最小费用，由此可得到最小费用最小费用 Aij 见下表见下表10.430.1750.3205(1)(2)(3)S2(34)(22)(23)1900.2(4)(24)60125(5)60.61(25)110(6)19.40.595(26)1(27)(28)3.1(7)(8)20.520.11.2(29)(9)68(16)4.2(30)(10)748(11)(17)(18)(12)301137(19)19(13)(20)(21)(14)(15)(31)(32)(33)122214250266.211322190190175180165108585 70110135145150145 程序：min-cost 2.lg4 2.2.一般模型一般模型故有：3.3.问题三的求解问题三的求解1 1）不让钢厂）不让钢厂S S7 7生产，计算结果为生产，计算结果为:14056111405611（万元）（此时每个钢厂的产量都满足条件）（万元）（此时每个钢厂的产量都满足条件）2 2）要求钢厂）要求钢厂S7 S7 产量不小于产量不小于500500个单位，计算结果为个单位，计算结果为:14051971405197（万元）（此时每个钢厂的产量都满足条件）（万元）（此时每个钢厂的产量都满足条件）.比较这两种情况的最优解比较这两种情况的最优解:其订购方案见表11 和表12701088107062300220210170690462160320160A10A11A12S4S5S6130A17A18A19A20190260100(jk)是连接Aj,Ak的边，E是树形图的边集，ljk是(jk)的长度，yjk是由Aj沿(jk)铺设的钢管数量模型简单表示模型简单表示