钢管订购和运输

钢管订购和运输要铺设一条1521AAA的输送天然气的主管道,如图一所示。经筛选后可以生产这种主管道钢管的钢厂有721,,SSS。图中粗线表示铁路，单细线表示公路，双细线表示要铺设的管道(假设沿管道或者原来有公路，或者建有施工公路)，圆圈表示火车站，每段铁路、公路和管道旁的阿拉伯数字表示里程(单位km)。为方便计，1km主管道钢管称为1单位钢管。一个钢厂如果承担制造这种钢管，至少需要生产500个单位。钢厂iS在指定期限内能生产该钢管的最大数量为is个单位，钢管出厂销价1单位钢管为ip万元，如下表：i1234567is80080010002000200020003000ip1601551551601551501601单位钢管的铁路运价如下表：里程(km)≤300301～350351～400401～450451～500A13258010103120124270108810706270302020304501043017506061942052016804803002202104205006003060195202720690520170690462160320160110290115011001200A2A3A4A5A6A11A711A11A8A11A911A11A10A11A12A13A14A15S1S2S3S4S5S6S7图一运价(万元)2023262932里程(km)501～600601～700701～800801～900901～1000运价(万元)37445055601000km以上每增加1至100km运价增加5公路运输费用为1单位钢管每公里0.1万元（不足整公里部分按整公里计算）。钢管可由铁路、公路运往铺设地点（不只是运到点1521,,,AAA，而是管道全线）。（1）请制定一个主管道钢管的订购和运输计划，使总费用最小（给出总费用)。（2）请就（1）的模型分析：哪个钢厂钢管的销价的变化对购运计划和总费用影响最大，哪个钢厂钢管的产量的上限的变化对购运计划和总费用的影响最大，并给出相应的数字结果。摘要：本文建立一个钢管订购和运输模型，从钢厂到主管道结点的运费是影响总费用的重要因素。为使总费用最小，须使从钢厂到主管道结点的运费——钢管运输费最小。对求网络中最短路径的Dijkstra算法进行改进，得到新的算法，可对含多种权重计算方式的网络进行搜索，得出最小费用路径（最短路径）。在此基础上，建立起描述总费用的函数，把钢管的订购和运输问题归结为在一定约束条件下求最小总费用的二次规划问题。对于问题（１），运用Lingo软件包求出了较优的订购和运输计划（见表4，表5），其最小费用为1278632万元。对于问题（2）而言，可得出钢厂6S钢厂销价变化对总费用影响最大，56,SS钢厂钢管的销价的变化对购运计划影响最大，1S钢厂钢管的产量的上限的变化对总费用影响最大，购运计划影响较小。关键词：穷举法非线性规划一、问题重述和分析要铺设一条1521AAA的输送天然气的主管道，如图一所示,经筛选后可以生产这种主管道的钢厂有721,,,SSS。图中粗线表示铁路，单细线表示公路，双细线表示要铺设的管道（假设沿管道或者原来有公路，或者建有施工公路），圆圈表示火车站，每段铁路、公路和管道旁的阿拉伯数字表示里程（单位km）。为了方便，1km主管道称为1单位钢管。一个钢厂如果承担制造这种钢管，至少需要生产500个单位。钢厂iS在指定期限内能生产该钢管的最大生产数量为is个单位，钢厂出厂销价为ip万元，如下表：表1i1234567is80080010002000200020003000ip1601551551601551501601单位钢管的铁路运价如下表：表2里程（km）300350~301351~400401~450451~500运价（万元）2023262932里程（km）501~600601~700701~800801~900901~1000运价（万元）37445055601000km以上每增加1至100km运价增加5万元。公路运输费用为1单位管道每公里0.1万元（不足整公里的按整公里计算）。管道可由铁路、公路运往铺设地点（不只是运到点1521AAA，而是管道全线）。要求：（1）制定一个主管道钢管的订购和运输计划，使总费用最小，并给出总费用。（2）就（1）的模型进行分析：哪个钢厂钢管的销价的变化对购运计划和总费用影响最大，哪个钢厂钢管的产量的上限的变化对购运计划和总费用的影响最大，并给出相应的数字结果。二、基本假设1．在计算运费时，沿管道铺设路线上的公路与其它普通公路相同（1单位钢管每公里0.1万元）；2．订购的钢管数量刚好等于需要铺设的钢管数量；3．管道可由铁路、公路、管道全线运往铺设地点（不只是运到点1521,,,AAA）；4．模型只考虑钢管销价费用和钢管从钢管厂运送到铺设点的钢管运费，而不考虑其它费用，如不计换车、转站的时间和费用，不计装卸费用等；5．不计运输时由于运输工具出现故障等意外事故引起工期延误造成损失；6．销售价和运输价不受市场价格变化的影响。三、符号说明iS：第i钢管厂is：表示iS的最大生产能力jA：表示需要铺设管道路径上的车站ijx：从所有iS运往jA的钢管数cij：表示单位钢管从iS地运往jA地的最小费用ip：从iS订购钢管的单位价格Q：订购的所有钢管全部运到)15,,2,1(jAj点的总运费T：当钢管从钢厂iS运到点jA后，钢管向jA的左右两边运输（铺设）管道的运输费用Z：用于订购和运输的总费用jy：运到jA地向左铺设的数目jz：运到jA地向右铺设的数目d：单位钢管1公里的公路运输费用1,jjA：表示1jjAA和之间需要铺设的管道长度四、模型的建立与求解问题一1、模型的建立钢管的订购和运输方案是直接影响工程费用的主要原因，因此，选取费用最小的路线运送货物，合理的订购计划是决定该工程费用的重要因素，首先利用图论的方法，来确定从钢管生产厂家到施工结点的费用最小路线，然后建立工程费用的优化模型，从中优化出最佳购运方案。对本问题而言，实际上是一个要求制定订购和运输计划，使总费用最小的优化问题。本模型的总费用包括钢管的销价和运输总的费用。首先，向某厂订购钢管，然后将在每个厂订购的钢管运往需要铺设的全路段。欲解决本问题可以按以下方案进行思考：首先，需要确定将货物从i地运往j地的最优路线（费用最小）；然后，求出向每个钢管厂的订购计划，并确定出运输计划；最后计算将运往j地的钢管铺到各个管道上的运输费用，我们不妨假设运往以j为终点的钢管只铺到与j点相邻的两段管道上。因此，本问题可以按以下步骤求解。第一步：确定从i地到j地的最优路径，从而确定出单位钢管从i地运往j地的最小运费。)7,2,1(isi表示钢管厂)7,2,1(iSi的最大生产能力，)15,,2,1(jAj表示需要铺设钢管路径上的车站。假设从iS运往jA的钢管用于铺设jA点左右侧的钢管数为jix,单位，单位产品从iS到jA地的运费为jiF,万元，用ji,c表示单位钢管从iS地运往jA地的最小费用，则：jcminijiF……………………………………………………（1）第二步：建立从iS厂运送j,ix单位钢管到jA点的运费的模型：用Q表示订购的所有钢管全部运到)15,,2,1(jAj点的总运费，则：15711Qcijijjix；……………………………………………………（2）第三步：将运到jA处的钢管铺到相邻两段路上的运输费用对于运到jA的钢管，它向左运输的总量jy，它向左运输的总费用为：(1)(2)1jjjydydydd＝0.1(12)0.051jjjyyy（万元）；同理它向右运输的总费用为：jjzzd2)1(＝0.051jjzz用T表示当钢管从钢厂iS运到点jA后，钢管向jA的左右两边运输（铺设）管道的运输费用，得：15jjj1T0.051yy1jjzz……………………………………（3）之间存在的关系：和jzjy7iji11,1x;(1,2,,15);(1,2,,14)jjjjjjyzjzyAj………………………………………………（4）（1,jjA表示1jjAA和之间需要铺设的管道长度）第四步：建立订购费用的模型设W表示订购管道的总费用，则可建立如下模型：715,1j1Wiijipx…………………………………………………………（5）又因为一个钢厂如果承担制造钢管任务，至少需要生产500个单位，钢厂iS在指定期限内最大生产量为is个单位，故ijijsx152500或0152jijx，用Z表示订购和运输的总费用，由（2）、（3）、（4）、（5），本问题可建立如下的非线性规划模型：目标函数71515i111minWQT()0.0511iijijjjjjjjZpcxyyzz约束条件7iji11,1151522x;(1,2,,15);(1,2,,14)5000;(1,2,,7)01,,7,2,,15jjjjjjijiijjjijyzjzyAjxsxixij或…………………………………………（6）（1,jjA表示1jjAA和之间需要铺设的管道长度）2、模型的求解（1）首先求解ijc由于钢管从钢厂iS运到运输点jA要通过铁路和公路运输，而铁路运输费用是分段函数，与全程运输总距离有关。又由于钢厂iS直接与铁路相连，所以可先求出钢厂iS到铁路与公路相交点jb的最短路径。依据钢管的铁路运价表，算出钢厂iS到铁路与公路相交点jb的最小铁路运输费用，并把费用作为边权赋给从钢厂iS到jb的边。再将与jb相连的公路、运输点iA及其与之相连的要铺设管道的线路（也是公路）添加到图上，根据单位钢管在公路上的运价规定，得出每一段公路的运费，并把此费用作为边权赋给相应的边。这样就转换为以单位钢管的运输费用为权的赋权图，再利用E.W.Dijkstra的最短路算法计算出一个单位钢管从钢厂运到工地的最少费用系数阵ijc，MATLAB程序见附录一。表3表中对应的值为对应两点最优路径单位钢管运输费用S1S2S3S4S5S6S7A1170.7215.7230.7260.7255.7265.7275.7A2160.3205.3220.3250.3245.3255.3265.3A3140.2190.2200.2235.2225.2235.2245.2A498.6171.6181.6216.6206.6216.6226.6A538111121156146156166A620.595.5105.5140.5130.5140.5150.5A73.18696131121131141A821.271.286.2116.2111.2121.2131.2A964.2114.248.284.279.284.299.2A10921428262576276A11961468651335166A121061569661514556A13121.2171.2111.276.271.226.238.2A1412817811883731126A151421921329787282(2)根据以上结果,继续求解非线性规划模型：71515i111min()0.0511iijijjjjjjjZpcxyyzz7iji11,1151522x;(1,2,,15);(1,2,,14).5000;(1,2,,7)01,,7,2,,15jjjjjjijiijjjijyzjzyAjstxsxixij或由于不能直接处理约束条件：ijijsx152500或0152jijx，我们可先将此条件改为ijijsx152，得到如下模型：71515i111min(