大学建模案例钢管订购和运输优化模型

1、建模案例：钢管订购和运输优化模型建模案例：钢管订购和运输优化模型20002000年年“网易杯网易杯”全国大学生数学建模竞赛全国大学生数学建模竞赛b b综合案例分析综合案例分析http:/ 一.问题的提出问题的提出二二. .基本假设基本假设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.销售价和运输价不受市场价格变化的影响销售价和运输价不受市场价格变化的影响http:/ 符号

3、说明符号说明第 个钢厂,第个钢厂的最大产量，输送天然气的主管道上的第个点，第个钢厂 1 单位钢管的销售价格，钢厂向第个点运输的钢管数量（单位） 在点与点之间的公路上，运输点向点方向铺设的钢管数量，1 单位钢管从钢厂到点的最少总费用，即公路运费，铁路运费和钢管销售之和，与第个点相连的公路和铁路的相交点,与第个点相连的的第m条公路和铁路的相交点,相邻结点与点之间的距离,http:/ . 模型的建立与求解模型的建立与求解问题一：讨论如何调整主管道钢管的订购和运输方案使总费用最小问题一：讨论如何调整主管道钢管的订购和运输方案使总费用最小isisja1.1.求钢管从钢厂求钢管从钢厂运到运输点运到运输点的

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

5、费用依次为：运输费用依次为：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（单位：万元）（单位：万元） 加上单位钢管的销售加上单位钢管的销售价价 1sja得出从钢厂得出从钢厂购买单位钢管运输到点购买单位钢管运输到点的最小费用的最小费用依次为依次为: : ja1330.3，320.3，300.2，258.6，198，180.5，163.1，181.2，224.2，252，256，266，281.2，2

6、88，302（单位：万元）.同理，可用同样的方法求出钢厂同理，可用同样的方法求出钢厂 到到 的最小费用，从而得出各钢厂的最小费用，从而得出各钢厂si到运输节点到运输节点 aj 最小运总费用。见表最小运总费用。见表1.lingo lingo 程序：程序：min-costmin-cost1.lg4 计算结果：计算结果：min-cost1.lgrhttp:/ si 到点到点 aj 的最小费用的最小费用2. 2. 建立模型建立模型运输总费用可分为两部分：运输总费用可分为两部分：运输总费用运输总费用= =钢厂到各点的运输费用钢厂到各点的运输费用+ +主管道的运输（铺设）费用主管道的运输（铺设）费用. .

7、http:/ 2) 约束条件约束条件http:/ 非线性规划模型可用lingo软件包或matlab软件包来求解，但这些软件包不能直接处理约束条件：可用分支定界法将此条件改为可用分支定界法将此条件改为模型变为模型变为http:/ 1）不让钢厂）不让钢厂s s7 7生产，模型变为生产，模型变为: :http:/ 计算结果：1f12786321278632（万元）（此时每个钢厂的产量都满足条件）（万元）（此时每个钢厂的产量都满足条件） 2 2）要求钢厂）要求钢厂s s7 7 产量不小于产量不小于500500个单位，模型变为个单位，模型变为: :计算结果计算结果：2f 12796641279664（万

8、元）（此时每个钢厂的产量都满足条件）（万元）（此时每个钢厂的产量都满足条件）. . http:/ 121),min(minffff=1278632=1278632（万元）具体的购运计划如表（万元）具体的购运计划如表2 2： 订购量a2a3a4a5a6a7a8a9a10a11a12a13a14a15s18000201133200266000000000s28001791114295003000000000s31000139111860006640000000s4000000000000000s5101503582420000004150000s61556000000000351863336211

9、65s7000000000000000表表2 2 问题问题1 1的订购和调运方案的订购和调运方案http:/ 比较好的方法：引入比较好的方法：引入0-10-1变量变量.7,.,1,1 ,0,0.14,.,1.15,.,1,.7,.,1,500.)1()1(21.0151171151151,ifzyjbzyjzyxifsxftszzyyxaminijjjjjiijiijijijjjjjjiijij lindo/lingo得到的结果比得到的结果比matlab得到的好得到的好yj zjjguandao.lg4参考程序http:/ jixjxisxtsxcijiijijijijijijcij为从供应点

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

11、和总费用造成影响，为更好地考察影响，下面分别进行讨论造成影响，为更好地考察影响，下面分别进行讨论方案中运往各点的运输量的变化量的绝对值之和称为方案中运往各点的运输量的变化量的绝对值之和称为运输方案变化量运输方案变化量1 1）讨论钢厂钢管的销售价格变化对购运计划和总费用的影响）讨论钢厂钢管的销售价格变化对购运计划和总费用的影响 当钢厂钢管的销售价格当钢厂钢管的销售价格 变化时，会对购运计划和总费用造成影响。为更好变化时，会对购运计划和总费用造成影响。为更好地观察每一个钢厂的销售价格地观察每一个钢厂的销售价格 变化时所造成的影响，本问题采用比较法。即：变化时所造成的影响，本问题采用比较法。即：每次

12、只让一个钢厂钢管的销售价格发生相同的变化，其余钢厂钢管的销售价每次只让一个钢厂钢管的销售价格发生相同的变化，其余钢厂钢管的销售价格不发生变化；当每个钢厂的销售价个发生同样的变化格不发生变化；当每个钢厂的销售价个发生同样的变化 c c 时，求出相应的时，求出相应的总费用，然后比较。总费用，然后比较。分析：分析：http:/ c=-5表4 c=5http:/ c=1表6 c=-1从上述四个表格中可以看出：钢厂钢管的销售价格变化时从上述四个表格中可以看出：钢厂钢管的销售价格变化时，s6对总费用对总费用影响最大影响最大，s5对购运计划影响最大对购运计划影响最大。http:/ 2) 讨论钢厂产量的上限变

13、化对购运计划和总费用的影响讨论钢厂产量的上限变化对购运计划和总费用的影响 本问题同样采用比较法。即：每次只改变一个钢厂本问题同样采用比较法。即：每次只改变一个钢厂钢管产量的上限钢管产量的上限，其余，其余钢厂钢管产量上限不发生变化的情况，利用问题一中的模型进行讨论钢厂钢管产量上限不发生变化的情况，利用问题一中的模型进行讨论。 a. 对产量不受限制的情况计算得到下表对产量不受限制的情况计算得到下表表7 产量不受限制的情形b. 对产量下降对产量下降100100的情况计算得到下表的情况计算得到下表表8 产量下降100的情况http:/ 100 的情况计算得到下表的情况计算得到下表表9 产量升高100的

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

15、627030202030450104301750606194205201680480300220210420500600306195202720690520170690462160320160110290115011001200a2a3a4a5a6a7a8a9a10a11a12a13a14a15s1s2s3s4s5s6s7http:/ 为求出一般由铁路、公路、管道构成网络情况下的最优购运和最小总费用为求出一般由铁路、公路、管道构成网络情况下的最优购运和最小总费用方案，方案，首先必须求出各钢厂到个管道节点的最短费用路径首先必须求出各钢厂到个管道节点的最短费用路径。由于在途中可能。由于在途中可能发

16、生火车发生火车汽车汽车火车的转运方案，而这种情况发生的前提条件是公路火车的转运方案，而这种情况发生的前提条件是公路（或管道）的两端必须都是火车站点，由于铁路运输的费用是分段函数，故（或管道）的两端必须都是火车站点，由于铁路运输的费用是分段函数，故求各钢厂到各管道结点的最小费用步骤如下：求各钢厂到各管道结点的最小费用步骤如下：1）首先找出公路的两个端点都是火车站站点的结点）首先找出公路的两个端点都是火车站站点的结点v v1 1,v,v2 2, ,vsvs2) 2) 把公路网和铁路网分开，分别组成网络；把公路网和铁路网分开，分别组成网络；3 3）在铁路网中求出各钢厂）在铁路网中求出各钢厂s si

17、i及各点及各点v vi i到各火车站点的最短路，并把它转化到各火车站点的最短路，并把它转化 为最小费用路为最小费用路4)4)在公路网中求出各管道结点到各火车站点的最短路，并把它转化为最小在公路网中求出各管道结点到各火车站点的最短路，并把它转化为最小 费用路费用路5 5）把前面的结点合并成一个网络，分别求出各钢厂）把前面的结点合并成一个网络，分别求出各钢厂s si i 到各管道结点的最小到各管道结点的最小 运输费用路运输费用路。并求出各钢厂并求出各钢厂 si到各管道结点到各管道结点aj的最小费用，由此可得到的最小费用，由此可得到最小费用最小费用 aij 见下表见下表http:/ 70110135145150145 程序：min-cost 2.lg4 http:/ 1）不让钢厂）不让钢厂s s7 7生产，计算结果为生产，计算结果为: :14056111405611（万元）（此时每个钢厂的产量都满足条件）（万元）（此时每个钢厂的产量都满足条件） 1f2 2）要求钢厂）要求钢厂s7 s7 产量不小于产量不小于500500个单位，计算结果为个单位，计算结果为: 140519714