数学建模 钢管订购和运输优化模型ppt课件

1、建模案例：钢管订购和运输优化模型建模案例：钢管订购和运输优化模型20002000年年“网易杯网易杯全国大学生数学建模竞赛全国大学生数学建模竞赛B B综合案例分析综合案例分析 一.问题的提出二二. .基本假设基本假设1.1.沿铺设的主管道已有公路或者有施工公路沿铺设的主管道已有公路或者有施工公路. . 2.1km 2.1km 主管道钢管称为一单位钢管，在主管道上，每主管道钢管称为一单位钢管，在主管道上，每千米卸千米卸1 1单位的钢管单位的钢管. .3.3.公路运输费用为公路运输费用为1 1单位钢管每千米单位钢管每千米0.10.1万元万元（不足整千米部分按整千米计算）（不足整千米部分按整千米计算）

2、 4. 4.在计算总费用时，只考虑运输费用和购买钢管的费用，在计算总费用时，只考虑运输费用和购买钢管的费用， 而不考虑其他的费用诸如中转费用）而不考虑其他的费用诸如中转费用） 5. 5.假设钢管在铁路运输路程超过假设钢管在铁路运输路程超过1000km,1000km,铁路每增加铁路每增加1 1 至至100km,1100km,1单位钢管运输的运价增至单位钢管运输的运价增至5 5万元万元. .6.订购的钢管数量刚好等于需要铺设的钢管数量7.7.销售价和运输价不受市场价格变化的影响销售价和运输价不受市场价格变化的影响三三. 符号说明符号说明第 个钢厂,第个钢厂的最大产量，输送天然气的主管道上的第个点，

3、第个钢厂 1 单位钢管的销售价格，钢厂向第个点运输的钢管数量单位） 在点与点之间的公路上，运输点向点方向铺设的钢管数量，1 单位钢管从钢厂到点的最少总费用，即公路运费，铁路运费和钢管销售之和，与第个点相连的公路和铁路的相交点,与第个点相连的的第m条公路和铁路的相交点,相邻结点与点之间的距离,四四. . 模型的建立与求解模型的建立与求解问题一：讨论如何调整主管道钢管的订购和运输方案使总费用最小问题一：讨论如何调整主管道钢管的订购和运输方案使总费用最小iSiSjA求钢管从钢厂求钢管从钢厂运到运输点运到运输点的最小费用的最小费用1 1将图将图1 1转换为一系列以单位钢管的运输费用为权的赋权图转换为一

4、系列以单位钢管的运输费用为权的赋权图. .iSjb所以可先求出钢厂所以可先求出钢厂到铁路与公路相交点到铁路与公路相交点的最短路径的最短路径. .如图如图3 3 由题意可知：将钢管从钢厂运到运输点的费用包括钢管的销售价格、钢管的铁路运输费用和钢管的公路运输费用.在费用最小时，对钢管的订购和运输进行分配，可得出本问题的最佳方案.总费用总费用= =钢厂到各节点的费用钢厂到各节点的费用+ +主管道的运输铺设费用）主管道的运输铺设费用）450801150110030619520202120072069052017069016088462703201607029030图-41SjA2计算单位钢管从到到的最

5、少运输费用的最少运输费用1SjA根据图根据图4，借助图论软件包中求最短路的方法求出单位钢管从，借助图论软件包中求最短路的方法求出单位钢管从到的最短路，从而得出将单位钢管从的最短路，从而得出将单位钢管从 1S运输到各运输点运输到各运输点jA最小费用。最小费用。运输费用依次为：运输费用依次为：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单位：万元）单位：万元） 加上单位钢管的销售价加上单位钢管的销售价

6、 1SjA得出从钢厂得出从钢厂购买单位钢管运输到点购买单位钢管运输到点的最小费用的最小费用依次为依次为: : jA1330.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-cost1.lg4 min-cost1.lg4 计算结果：计算结果：min-cost1.lgr表表1 Si 到

7、点到点 Aj 的最小费用的最小费用2. 2. 建立模型建立模型运输总费用可分为两部分：运输总费用可分为两部分：运输总费用运输总费用= =钢厂到各点的运输费用钢厂到各点的运输费用+ +主管道的运输铺设费用主管道的运输铺设费用. .从而得出总费用：从而得出总费用：2) 2) 约束条件约束条件因此本问题可建立如下的非线性规划模型：因此本问题可建立如下的非线性规划模型： 非线性规划模型可用LINGO软件包或MATLAB软件包来求解，但这些软件包不能直接处理约束条件：可用分支定界法将此条件改为可用分支定界法将此条件改为模型变为模型变为1 1不让钢厂不让钢厂S7S7生产，模型变为生产，模型变为: :1f

8、计算结果：2f12786321278632万元）（此时每个钢厂的产量都满足条件）万元）（此时每个钢厂的产量都满足条件） 2 2要求钢厂要求钢厂S7 S7 产量不小于产量不小于500500个单位，模型变为个单位，模型变为: :计算结果：计算结果： 1279664万元）（此时每个钢厂的产量都满足条件）. 121) ,min(minff ff比较这两种情况，得最优解为比较这两种情况，得最优解为S7不让生产不让生产: .7,.,1,1,0,0.14,.,1.15,.,1,.7,.,1,500.)1()1(21.0151171151151,ifzyjbzyjzyxifsxftszzyyxAMinijjj

9、jjiijiijijijjjjjjiijij=1278632=1278632万元具体的购运计划如表万元具体的购运计划如表2 2： 订购量A2A3A4A5A6A7A8A9A10A11A12A13A14A15S18000201133200266000000000S28001791114295003000000000S31000139111860006640000000S4000000000000000S5101503582420000004150000S6155600000000035186333621165S7000000000000000表表2 2 问题问题1 1的订购和调运方案的订购和调运方

10、案fi表示钢厂表示钢厂i是否使用；是否使用；xij是从钢厂是从钢厂i运到节点运到节点j的钢管量的钢管量yj是从节点是从节点j向左铺设的钢管量；向左铺设的钢管量；zj是向右铺设的钢管量是向右铺设的钢管量 比较好的方法：引入比较好的方法：引入0-10-1变量变量5171,1,7,1,1 ,05171,1,17,1,500,0.min71517117151711 jixjxisxtsxcijiijijijijijij LINDO/LINGO得到的结果比得到的结果比matlab得到的好得到的好yj zjjGUANDAO.lg4参考程序1运输问题的0-1规划模型将全长5171km的管道按公里分段，共51

11、71个需求点，钢厂为7个供应点，构成如下的运输问题cij为从供应点i到需求点j的最小购运费xij=1表示从点i到点j购运1单位钢管求解时要针对规模问题寻求改进算法Cij 规模太大麻烦规模太大麻烦 问题二、就问题二、就1 1的模型分析：哪个钢厂钢管的销价的变的模型分析：哪个钢厂钢管的销价的变化对购运计划和总费用影响最大，哪个钢厂钢管的产量的上化对购运计划和总费用影响最大，哪个钢厂钢管的产量的上限的变化对购运计划和总费用的影响最大，并给出相应的数限的变化对购运计划和总费用的影响最大，并给出相应的数字结果字结果. . 由于钢厂钢管的销售价格变化和钢厂钢管产量的上限变化对购运计划和总费用造成影响，为更

12、好地考察影响，下面分别进行讨论方案中运往各点的运输量的变化量的绝对值之和称为运输方案变化量方案中运往各点的运输量的变化量的绝对值之和称为运输方案变化量1 1讨论钢厂钢管的销售价格变化对购运计划和总费用的影响讨论钢厂钢管的销售价格变化对购运计划和总费用的影响 当钢厂钢管的销售价格 变化时，会对购运计划和总费用造成影响。为更好地观察每一个钢厂的销售价格 变化时所造成的影响，本问题采用比较法。即：每次只让一个钢厂钢管的销售价格发生相同的变化，其余钢厂钢管的销售价格不发生变化；当每个钢厂的销售价个发生同样的变化 C 时，求出相应的总费用，然后比较。分析：分析：表3 C=-5表4 C=5表5 C=1表6

13、 C=-1从上述四个表格中可以看出：钢厂钢管的销售价格变化时，从上述四个表格中可以看出：钢厂钢管的销售价格变化时，S6对总费用对总费用影响最大，影响最大，S5对购运计划影响最大。对购运计划影响最大。2) 2) 讨论钢厂产量的上限变化对购运计划和总费用的影响讨论钢厂产量的上限变化对购运计划和总费用的影响 本问题同样采用比较法。即：每次只改变一个钢厂钢管产量的上限，其他钢厂钢管产量上限不发生变化的情况，利用问题一中的模型进行讨论。 a. 对产量不受限制的情况计算得到下表表7 产量不受限制的情形b. 对产量下降100的情况计算得到下表表8 产量下降100的情况c.对产量升高100 的情况计算得到下表

14、表9 产量升高100的情况结论：从上述表格中可以看出钢厂钢管产量的上限变化时，结论：从上述表格中可以看出钢厂钢管产量的上限变化时，S1对对 总费用和总费用和购运计划影响最大。购运计划影响最大。问题三、讨论铁路、公路构成网络的情形问题三、讨论铁路、公路构成网络的情形 本问题是讨论铺设的管道是树形图，铁路、公路构成网络的情形，对于这种问题的求解过程，以图-2进行说明。1. 1. 铺设管道是树形图时，基本解法原理铺设管道是树形图时，基本解法原理图图-3A13258010103120124270108810706270302020304501043017506061942052016804803002

15、20210420500600306195202720690520170690462160320160110290115011001200A2A3A4A5A6A7A8A9A10A11A12A13A14A15S1S2S3S4S5S6S7 为求出一般由铁路、公路、管道构成网络情况下的最优购运和最小总费用方案，首先必须求出各钢厂到个管道节点的最短费用路径。由于在途中可能发生火车汽车火车的转运方案，而这种情况发生的前提条件是公路（或管道的两端必须都是火车站点，由于铁路运输的费用是分段函数，故求各钢厂到各管道结点的最小费用步骤如下：1首先找出公路的两个端点都是火车站站点的结点V1,V2,Vs2) 2) 把

16、公路网和铁路网分开，分别组成网络；把公路网和铁路网分开，分别组成网络；3 3在铁路网中求出各钢厂在铁路网中求出各钢厂SiSi及各点及各点ViVi到各火车站点的最短路，并把它转化到各火车站点的最短路，并把它转化 为最小费用路为最小费用路4)4)在公路网中求出各管道结点到各火车站点的最短路，并把它转化为最小在公路网中求出各管道结点到各火车站点的最短路，并把它转化为最小 费用路费用路5 5把前面的结点合并成一个网络，分别求出各钢厂把前面的结点合并成一个网络，分别求出各钢厂Si Si 到各管道结点的最小到各管道结点的最小 运输费用路。并求出各钢厂运输费用路。并求出各钢厂 SiSi到各管道结点到各管道结

17、点AjAj的最小费用，由此可得到的最小费用，由此可得到最小费用最小费用 Aij 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 70110145150145 程序：min-cost 2.lg4 2.2.一般模型一般模型故有：3.3.问题三的求解问题三的求解221) ,min(minff ff1 1不让钢厂不让钢厂S7S7生产，计算结果为生产，计算结果为: :14056111405611万元）（此时每个钢厂的产量都满足条件）万元）（此时每个钢厂的产量都满足条件） 2f2 2要求钢厂要求钢厂S7 S7 产量不小于产量不小于500500个单位，计算结果为个单位，计算结果为: : 1405197万元）（此时每个钢厂的产量都满足条件）