关于钢管订购和运输的优化模型

1《运筹学》最短路、最小费用最大流经典作品关于钢管订购和运输的优化模型队员：陈显健陈瑜斌陈振松2007年6月5日附件22摘要：本文首先运用图论知识中的最短路算法求出iS到jA的最优路径。然后将模型转化为最小费用最大流的网络优化问题，从而求出近似最优解。在分析出求解该网络优化模型的解法后，运用Lingo软件包求出了该问题的近似最优解。对问题一而言，求出了较优的订购和运输计划（见表三），其最小费用为1291630万元。对于第二个问题而言，可得出钢厂6S的钢管销价的变化对购运计划和总费用的影响最大；钢管厂1S的钢管产量的上限的变化对总费用的影响最大，钢管厂3S的产量上限的变化对购运计划的影响最大。对问题三，给出了一般解，求出了较优的订购和运输计划（见表四），其最小费用为1396099万元，最后对模型进行了综合评价并提出了改进方向。关键词：网络流最小费用最大流一、问题重述要铺设一条1521AAA的输送天然气的主管道，如图一所示,经筛选后可以生产这种主管道的钢厂有721,,,SSS。图中粗线表示铁路，单细线表示公路，双细线表示要铺设的管道（假设沿管道或者原来有公路，或者建有施工公路），圆圈表示火车站，每段铁路、公路和管道旁的阿拉伯数字表示里程（单位km）。为了方便，1km主管道称为1单位钢管。一个钢厂如果承担制造这种钢管，至少需要生产500个单位。钢厂iS在指定期限内能生产该钢管的最大生产数量为is个单位，钢厂出厂销价为ip万元，如下表：表一i1234567is80080010002000200020003000ip1601551551601551501601单位钢管的铁路运价如下表：（表二）里程（km）300350~301351~400401~450451~500运价（万元）20232629323里程（km）501~600601~700701~800801~900901~1000运价（万元）37445055601000km以上每增加1至100km运价增加5万元。公路运输费用为1单位管道每公里0.1万元（不足整公里的按整公里计算）。管道可由铁路、公路运往铺设地点（不只是运到点1521AAA，而是管道全线）。要求：（1）请制定一个主管道钢管的订购和运输计划，使总费用最小，并给出总费用。（2）请就（1）的模型进行分析：哪个钢厂钢管的销价的变化对购运计划和总费用影响最大，哪个钢厂钢管的产量的上限的变化对购运计划和总费用的影响最大，并给出相应的数字结果。（3）如果要铺设的管道不是一条线，而是一个树形图。铁路、公路和管道购成网络，请就这种更一般的情形给出一种解决办法，并对图二按（1）的要求给出数学模型和结果。4二、基本假设1．沿管道铺设路线上有公路，在计算运费时，与其它普通公路相同；2．订购的钢管数量刚好等于需要铺设的钢管数量；3．公路运输费用为1单位钢管每公里0.1万元（不足整公里的按整公里计算）；4．1km主管道钢管称为1单位钢管；5．一个钢厂如果承担制造这种钢管，至少需要生产500个单位；6．1单位钢管的铁路运价如（表二）所示，1000km以上每增加1至100km运价增加5万元；7．管道可由铁路、公路运往铺设地点（不只是运到点1521,,,AAA，而是管道全线）；8．本问题只考虑在铁路和公路上运输的问题，而不考虑在其它路径上的情况；9．每个钢管厂生产的钢管均满足铺设要求；10．模型只考虑钢管销价费用和钢管从钢管厂运送到铺设点的钢管运费，而不考虑其它费用，如转运费用等；11．在公路上卸货,按铺路的要求卸车；12．销售价和运输价不受市场价格变化的影响。三、符号说明iS第i钢管厂5is表示iS的最大生产能力jA表示需要铺设管道路径上的车站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点相邻的两段管道上。因此，本问题可以按以下步骤求解。第一步：确定从i地到j地的最优路径，从而确定出单位钢管从i地运往j地的最小运费。设)7,2,1(iSi表示钢管厂，)7,2,1(isi表示iS的最大生产能力，)15,,2,1(jAj表示需要铺设钢管路径上的车站。假设从iS运往jA的钢管用于铺设jA点前后侧的钢管数为jix,单位，单位产品从iS到jA地的运费为jiF,万元，用jif,表示单位钢管从iS地运往jA地的最小费用，则：j,,minijiFf（1）第二步：建立从iS厂运送j,ix单位钢管到jA点的运费的模型：6用1z表示订购的所有钢管全部运到jA点的总运费，则：001500..,1,171,151,151,15171,,1jijjjjijijjiiiijjiiijjijijijixAyyxyySSxsxtsfxz不生产时当生产时当（2）其中：jy和jy分别表示运到jA地钢管用于铺jA点前边和后边的钢管长度；1,jjA表示1jjAA和之间需要铺设的管道长度第三步：将运到jA处的钢管铺到相邻两段路上的运输费用根据假设，在铺设钢管时，dx单位钢管从第1kk点运到点的运费为：10.1kkdx=0.1（3）由（3）式可得如下模型（1）当1jjyy和均为整单位数时，设其运费用21z表示,则：15111212)1()1(1.0jjjjjyyyyz（2）当1jjyy和均为非整单位数时，设其运费用22z表示,则：])}[2()1(])[2(])[1{(05.02])[1(])[(2][)1(1.02])[1(])[(2][])[1(1.0111111122jjjjjjjjjjjjjjjjyyyyyyyyyyyyyyyyz7其中：][jy表示jy的整数部分；][1jy表示1jy的整数部分;综合上述两式可得：1511112])}[2()1(])[2(])[1{(05.0jjjjjjjyyyyyyz（4）01][][01500..,1,11,171,151,151,jijjjjjjjjijijjiiiijjiiijjixAyyAyyxyySSxsxts不生产时当生产时当其中：2z表示运到jA处的钢管铺到相邻两段路上的运输费用第四步：建立订购费用的模型设3z表示订购管道的总费用，则可建立如下模型：jiiixpz,71151j3（5）用z表示订购和运输的总费用，由（2）、（4）、（5）可得本问题的优化模型如下：321minzzzz即：jiiijijijijjjjjjjxpfxyyyyyyz,71151j15171,,151111])}[2()1(])[2(])[1{(05.0min801][][01500..,1,11,171,151,151,jijjjjjjjjijijjiiiijjiiijjixAyyAyyxyySSxSxts不生产时当生产时当2、模型的求解（1）首先求解jif,此问题相当于求解最小费用流问题，即求出从iS点运送单位钢管到jA点的最小费用。按常规，本问题可以按求最短路的常规方法求解。但由于本问题中沿铁路的单位运费由它前边经过的铁路长度而变化。根据问题的需要，我们不妨假设如果从iS点到jA点的钢管经过铁路后，一旦走公路，那么，该钢管将不会再通过铁路运输。则假设沿铁路行走，直到走到与公路相连为止。那么，我们可以将已知图中铁路的费用直接表示出。因此从iS点到jA点的通路如图三所示。190190b23175b22180b21205190145b20b12125110135155165b1b2b495858570110b14b19b9b11b12b5b6b7b80.30.26010.513.11.24.27116.27560.65A7A20.19A11A13A425015A10.42A30.13A4A19.46A20.58A68910A302212A2114A（图三）A1b24S29现在需要求出每个钢管厂iS到每条公路上的节点jA的最优路径，即：如果需要从iS点运钢管到jA点，则需要找出从该点到目的点间的最优路线。现在从每个钢厂出发，求出每个钢厂到需要铺设管道的路径上的每个节点的单位钢管量的最小费用。那么，我们以iS，jA以及铁路的端点等为点，以钢管的可能运输路线为边，以单位钢管的运输费用为权建立形如（图三）所示的加权图。（其中，边上的权的确定的具体方案参见文献[2]，本题中，以iS为起点，以需铺设管道的路上的节点为终点，那么从iS到jA的路程中根据铁路和公路的运费特点不难得出形如图三所示的赋权图），根据Dijkstra标号法[2]可以求出每个钢管厂iS到各个节点jA的最小单位运输费用。现在我们以2S点为起点，以每个铺设管道的节点为终点，通过观察与简单运算得出图三的加权图，则以图三为基础，运用Lingo软件包中的求最短路问题的程序DYNAMB.LG4（见附录一）可求得单位钢管的最小运输费用如下：F(j)单位钢管的运输费F(j)单位钢管的运输费F(1)215.7000F(2)205.3000F(3)190.2000F(4)171.6000F(5)111.0000F(6)95.50000F(7)86.00000F(8)71.20000F(9)114.2000F(10)142.0000F(11)146.0000F(12)156.0000F(13)171.2000F(14)178.0000F(15)192.0000其中：F(j)(j=1,…,15)表示从2S到jA的最小单位钢管运费。同理可得1S，3S，4S，5S，6S，7S各点到目的点的最优单位运费如下1S点到需要铺设管道的路上的各节点的单位运输费F(1)170.7000F(2)160.3000F(3)140.2000F(4)98.60000F(5)38.00000F(6)20.50000F(7)3.100000F(8)21.20000F(9)64.20000F(10)92.00000F(11)96.00000F(12)106.0000F(13)121.2000F(14)128.0000F(15)142.0000103S点到需要铺设管道的路上的各节点的单位运输费F(1)230.7000F(2)220.3000F(3)200.2000F(4)181.6000F(5)121.0000F(6)105.5000F(7)96.00000F(8)86.20000F(9)48.20000F(10)82.00000F(11)86.00000F(12)96.00000F(13)111.2000F(14)118.0000F(15)132.00004S点到需要铺设管道的路上的各节点的单位运输费F(1)260.7000F(2)250.3000F(3)235.2000F(4)216.6000F(5)156.0000F(6)