建模案例：钢管订购和运输优化模型,2000年“网易杯”全国大学生数学建模竞赛B,综合案例分析,http:/www.docin.com/sundae_meng,一.问题的提出,二.基本假设,1.沿铺设的主管道已有公路或者有施工公路. 2.1km 主管道钢管称为一单位钢管，在主管道上，每千米卸1单位的钢管. 3.公路运输费用为1单位钢管每千米0.1万元 （不足整千米部分按整千米计算）,4.在计算总费用时，只考虑运输费用和购买钢管的费用， 而不考虑其他的费用（诸如中转费用）,5.假设钢管在铁路运输路程超过1000km,铁路每增加1 至100km,1单位钢管运输的运价增至5万元.,6.订购的钢管数量刚好等于需要铺设的钢管数量,7.销售价和运输价不受市场价格变化的影响,http:/www.docin.com/sundae_meng,三. 符号说明,第,个钢厂,第,个钢厂的最大产量，,输送天然气的主管道上的第,个点，,第,个钢厂 1 单位钢管的销售价格，,钢厂,向第,个点,运输的钢管数量（单位）,在点,与点,之间的公路上，运输点,向点,方向铺设的钢管数量，,1 单位钢管从钢厂,到点,的最少总费用，即公路运费，铁路运费和钢管销售,之和，,与第,个点,相连的公路和铁路的相交点,与第,个点,相连的的第m条公路和铁路的相交点,相邻结点,与点,之间的距离,http:/www.docin.com/sundae_meng,四. 模型的建立与求解,问题一：讨论如何调整主管道钢管的订购和运输方案使总费用最小,求钢管从钢厂,运到运输点,的最小费用,1）将图1转换为一系列以单位钢管的运输费用为权的赋权图.,所以可先求出钢厂,到铁路与公路相交点,的最短路径.如图3,由题意可知：将钢管从钢厂,运到运输点,的费用,包括钢管的销售价格、,钢管的铁路运输费用和钢管的公路运输费用.在费用,最小时，对钢管的订购和运输,进行分配，可得出本问题的最佳方案.,总费用=钢厂到各节点的费用+主管道的运输（铺设费用）,http:/www.docin.com/sundae_meng,450,http:/www.docin.com/sundae_meng,图-4,http:/www.docin.com/sundae_meng,2）计算单位钢管从,到,的最少运输费用,根据图4，借助图论软件包中求最短路的方法求出单位钢管从,到,的最短路，从而得出将单位钢管从,运输到各运输点,最小费用。,运输费用依次为：170.7，160.3，140.2，98.6，38，20.5，3.1，21.2， 64.2，92，96，106，121.2，128，142（单位：万元）,加上单位钢管的销售价,得出从钢厂,购买单位钢管运输到点,的最小费用,依次为:,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 程序：min-cost1.lg4,计算结果：min-cost1.lgr,http:/www.docin.com/sundae_meng,表1 Si 到点 Aj 的最小费用,2. 建立模型,运输总费用可分为两部分：,运输总费用=钢厂到各点的运输费用+主管道的运输（铺设）费用.,http:/www.docin.com/sundae_meng,http:/www.docin.com/sundae_meng,从而得出总费用：,2) 约束条件,http:/www.docin.com/sundae_meng,因此本问题可建立如下的非线性规划模型：,非线性规划模型可用LINGO软件包或MATLAB软件包来求解，但这些软件包不能 直接处理约束条件：,可用分支定界法将此条件改为,模型变为,http:/www.docin.com/sundae_meng,1）不让钢厂S7生产，模型变为:,http:/www.docin.com/sundae_meng,计算结果：,1278632（万元）（此时每个钢厂的产量都满足条件）,2）要求钢厂S7 产量不小于500个单位，模型变为:,计算结果：,1279664（万元）（此时每个钢厂的产量都满足条件）.,http:/www.docin.com/sundae_meng,比较这两种情况，得最优解为S7不让生产:,=1278632（万元）具体的购运计划如表2：,表2 问题1的订购和调运方案,http:/www.docin.com/sundae_meng,fi表示钢厂i是否使用；xij是从钢厂i运到节点j的钢管量 yj是从节点j向左铺设的钢管量；zj是向右铺设的钢管量,比较好的方法：引入0-1变量,LINDO/LINGO得到的结果比matlab得到的好,yj zj,j,GUANDAO.lg4,参考程序,http:/www.docin.com/sundae_meng,1）运输问题的0-1规划模型,将全长5171km的管道按公里分段，共5171个需求点，钢厂为7个供应点，构成如下的运输问题,cij为从供应点i到需求点j的最小购运费,xij=1表示从点i到点j购运1单位钢管,求解时要针对规模问题寻求改进算法,Cij 规模太大麻烦,http:/www.docin.com/sundae_meng,问题二、就（1）的模型分析：哪个钢厂钢管的销价的变化对购运计划和总费用影响最大，哪个钢厂钢管的产量的上限的变化对购运计划和总费用的影响最大，并给出相应的数字结果.,由于钢厂钢管的销售价格变化和钢厂钢管产量的上限变化对购运计划和总费用 造成影响，为更好地考察影响，下面分别进行讨论,方案中运往各点的运输量的变化量的绝对值之和称为运输方案变化量,1）讨论钢厂钢管的销售价格变化对购运计划和总费用的影响,当钢厂钢管的销售价格 变化时，会对购运计划和总费用造成影响。为更好地观察每一个钢厂的销售价格 变化时所造成的影响，本问题采用比较法。即：每次只让一个钢厂钢管的销售价格发生相同的变化，其余钢厂钢管的销售价格不发生变化；当每个钢厂的销售价个发生同样的变化 C 时，求出相应的总费用，然后比较。,分析：,http:/www.docin.com/sundae_meng,表3 C=-5,表4 C=5,http:/www.docin.com/sundae_meng,表5 C=1,表6 C=-1,从上述四个表格中可以看出：钢厂钢管的销售价格变化时，S6对总费用 影响最大，S5对购运计划影响最大。,http:/www.docin.com/sundae_meng,2) 讨论钢厂产量的上限变化对购运计划和总费用的影响,本问题同样采用比较法。即：每次只改变一个钢厂钢管产量的上限，其余 钢厂钢管产量上限不发生变化的情况，利用问题一中的模型进行讨论。,a. 对产量不受限制的情况计算得到下表,表7 产量不受限制的情形,b. 对产量下降100的情况计算得到下表,表8 产量下降100的情况,http:/www.docin.com/sundae_meng,c.对产量升高100 的情况计算得到下表,表9 产量升高100的情况,结论：从上述表格中可以看出钢厂钢管产量的上限变化时，S1对 总费用和购运计划影响最大。,问题三、讨论铁路、公路构成网络的情形,本问题是讨论铺设的管道是树形图，铁路、公路构成网络的情形，对于这种 问题的求解过程，以图-2进行说明。,http:/www.docin.com/sundae_meng,1. 铺设管道是树形图时，基本解法原理,图-3,http:/www.docin.com/sundae_meng,为求出一般由铁路、公路、管道构成网络情况下的最优购运和最小总费用 方案，首先必须求出各钢厂到个管道节点的最短费用路径。由于在途中可能 发生火车汽车火车的转运方案，而这种情况发生的前提条件是公路 （或管道）的两端必须都是火车站点，由于铁路运输的费用是分段函数，故 求各钢厂到各管道结点的最小费用步骤如下：,1）首先找出公路的两个端点都是火车站站点的结点V1,V2,Vs,2) 把公路网和铁路网分开，分别组成网络； 3）在铁路网中求出各钢厂Si及各点Vi到各火车站点的最短路，并把它转化 为最小费用路 4)在公路网中求出各管道结点到各火车站点的最短路，并把它转化为最小 费用路 5）把前面的结点合并成一个网络，分别求出各钢厂Si 到各管道结点的最小 运输费用路。并求出各钢厂 Si到各管道结点Aj的最小费用，由此可得到 最小费用 Aij 见下表,http:/www.docin.com/sundae_meng,10.4,30.1,75,0.3,205,(1),(2),(3),S2(34),(22),(23),190,0.2,(4),(24),60,125,(5),60.6,1,(25),110,(6),19.4,0.5,95,(26),1,(27),(28),3.1,(7),(8),20.5,20.1,1.2,(29),(9),68,(16),4.2,(30),(10),7,48,(11),(17),(18),(12),30,1,13,7,(19),19,(13),(20),(21),(14),(15),(31),(32),(33),1,22,21,42,50,26,6.2,11,3,2,2,190,190,175,180,165,10,85,85,70,110,135,145,150,145,程序：min-cost 2.lg4,http:/www.docin.com/sundae_meng,http:/www.docin.com/sundae_meng,2.一般模型,故有：,http:/www.docin.com/sundae_meng,http:/www.docin.com/sundae_meng,3.问题三的求解,http:/www.docin.com/sundae_meng,http:/www.docin.com/sundae_meng,1）不让钢厂S7生产，计算结果为:,1405611（万元）（此时每个钢厂的产量都满足条件）,2）要求钢厂S7 产量不小于500个单位，计算结果为:,1405197（万元）（此时每个钢厂的产量都满足条件）.,比较这两种情况的最优解:,其订购方案见表11 和表12,http:/www.docin.com/sundae_meng,http:/www.docin.com/sundae_meng,(jk)是连接Aj,Ak的边，E是树形图的边集， ljk是(jk)的长度， yjk是由Aj沿(jk)铺设的钢管数量,模型简单表示,http:/www.docin.com/sundae_meng,