钢管订购和运输数学建模

1、钢管订购和运输数学建模论文钢管订购和运输摘 要本文建立了一个运输问题的最优化模型。通过对图(一)的分析，我们首先直观地将路线分成两段，将图分为两个子图建立了模型一, 利用分支定界法求得总费用最优解为1279496万元。然后对模型一进行优化，得到全线的最优模型二，求得总费用最优解为1278632万元。通过对最优模型二的分析，我们得出钢厂s1的上限产量和钢厂s6的销价的的变化对运购计划和总费用的影响最大，并给出了数据结果。我们利用截取和连接的方法将树形图转化成为对线性图进行分析，并给出了一般的解决方法。对图(二)给出的具体模型，类似与问题一,分别建立了模型三和模型四,求得最优解分别为1408859

2、.4和1403948万元一、 问题的提出已知有7个钢厂，可生产输送天然气主管道的钢管，用si表示(i=1,2,7)。现有个地点（a1,a2,a15），沿着这个地点铺设一条输送天然气的主管道。为方便计，1km主管道称为单位钢管。 一个钢厂如果承担制造这种钢管，至少需要生产500个单位。钢厂在指定期限内能生产该钢管的最大数量为个单位，钢管出厂销价1单位钢管为万元，如下表：1234567800800100020002000200030001601551551601551501601单位钢管的铁路运价如下表：里程(km)300301350351400401450451500运价(万元)20232629

3、32里程(km)5016006017007018008019009011000运价(万元)37445055601000km以上每增加1至100km运价增加5万元。公路运输费用为1单位钢管每公里0.1万元（不足整公里部分按整公里计算）。钢管可由铁路、公路运往铺设地点（不只是运到点，而是管道全线）。（1）请制定一个主管道钢管的订购和运输计划，使总费用最小（给出总费用)。（2）请就（1）的模型分析：哪个钢厂钢管的销价的变化对购运计划和总费用影响最大，哪个钢厂钢管的产量的上限的变化对购运计划和总费用的影响最大，并给出相应的数字结果。（3）如果要铺设的管道不是一条线，而是一个树形图，铁路、公路和管道构成

4、网络，请就这种更一般的情形给出一种解决办法，并对图二按（1）的要求给出模型和结果。二、问题的分析 该问题是图论中运输问题的最优化问题。 经过分析，我们认为总费用可分为两种费用进行求解，分别为：（1）销价和运输钢管至管道结点ai(i=1,2,15)的总费用（称为成本费用）（2）铺设过程中的运输费用； 要解决此问题，我们认为有两点关键：（1）如何求出ai（i=1,2,15）至si(i=1,2,7)的最小成本费用；（2）如何调整使得各路径满足题中的最优指标。 针对上述问题，我们分别运用了图上作业法、枚举法、逐次修正法、重绕最小生成树法等方法，在综合考虑算法的精度和算法的复杂度后，我们选择了图上作业法

5、、枚举法、逐次修正法对模型进行逐次优化，直至求得最优解。三、模型的基本假设及符号说明（一） 基本假设：（1）运输方式的改变所花费用包含在运费中；（2）铁路线上任意两点可以直达，不需中途转车，即铁路线上两点间运费按线路总长计算；（3）假设一单位钢管可由任意长度钢管组成，购买钢管可以非整数单位购买;（4）不考虑其它外界因素对费用的影响；（5） 钢管在铺设时，先将钢管运到结点处，再由结点处向左右两方相邻结点铺设；（6） 在si厂购买钢管要么为零,要么至少为500单位。（二）符号说明： xij：从钢厂si运到结点aj的单位钢管数； fij：单位钢管从钢厂si运到结点aj的的最少成本费用； tj：第aj

6、点与aj+1点间的路线长度，j=1,2,14； yj：从结点aj开始沿管道向右铺设的路线长度, j=1,2,3,15； w：钢管订购和运输的总费用； mi: 钢厂si的最小产量，mi=500，i=1,2,3,4,5,6,7 ni: 钢厂si的产量上限，ni=si，i=1,2, ，7 bi: 图一中各节点（见附录七） vi: 图二中各节点（见附录八）四、模型的建立与求解（一）问题一及其求解：针对图（一），我们首先采用图上作业法对所给图进行分析，利用枚举法，我们求出一单位钢管由钢管厂si运输至管道结点i的最小成本费用，具体数据如下表：表一 单位钢管由si运输至i的最小成本费用 (单位：万元)s1s

7、2s3s4s5s6s7a1330.7370.7385.7420.7410.7415.7435.7a2320.3360.3375.3410.3400.3405.3425.3a3300.2345.2355.2395.2380.2385.2405.2a4258.6326.6336.6376.6361.6366.6386.6a5198266276316301306326a6180.5250.5260.5300.5285.5290.5310.5a7163.1241251291276281301a8181.2226.2241.2276.2266.2271.2291.2a9224.2269.2203.224

8、4.2234.2234.2259.2a10252297237222212212237a11256301241211188201226a12266311251221206195216a13281.2326.2266.2236.2226.2176.2198.2a14288333273243228161186a15302347287257242178162 这样，原问题即转化为通常的运输问题。我们进一步对上表数据进行分析，得到结论：结论1：将4、s5两列数据进行对比，发现同一行中s4列数据均大于s5列。由此得出，应优先考虑钢厂s5，只有当对s5的需求量超过其最大产量时，才需要考虑钢厂s4。 进一步对

9、原图进行分析可得：结论2：由于a1点只有通过a2点才能与钢厂si连接,故模型中不需考虑往a1运输钢管。模型(一)：对表一数据进一步分析。将各行数据由小到大排序，发现由a2至a9各行中费用最小的前四个数据均在s1,s2,s3,s5列中，由a10至a15各行中费用最小的前三个数据均在s5,s6,s7中，直观感觉到：a1至a9需要来自s6及s7等后一部分钢厂的钢管的可能性很小，而且a9至a15不太可能需要s1、s2、s3等前一部分钢厂生厂的钢管，故把原图分为两个子图考虑，分别为a1至a9和a9至a15，即分为两个子模型，分别进行最优化，得到两个子模型(非线性规划模型)如下： 子模型1： 子模型2：

10、由于这两个子模型属于非线性规划问题，且第一个约束条件很复杂，利用结论1、2，采用分支定界法用lingo软件分别进行编程（见附录一、二）得到： w1=859629.3 w2=419866.7模型一的总费用为w=w1+w2=1279496（万元）。模型（二）：由于前面的模型直观将管道分为两端，即原图分为两个子图，可能存在一定的误差。下面对模型（一）进行优化，即对主管道建立统一模型，如下：同样利用结论1、2并采用分支定界法，利用lingo软件编程（见附录三）运行得出:最优解w=1278632万元，各节点向右铺设的管道单位数：y1=0 y2=175 y3=282 y4=0 y5=10 y6=16 y7

11、=76 y8=175 y9=159 y10=30 y11=145 y12=11 y13=34 y14=335 表二 各钢厂定购计划：s1s2s3s4s5s6s7数量800800100001237.51333.50表三 运输计划如下（bi含义参见附图七）:路 线 运量s1-b7-b6-b5-a5-a4; 335s1-b7-b6-a6; 200s1-a7; 265;s2-b8-b4-b2-b1-a2; 179s2-b8-b4-b2-b3-a3; 131.3s2-b8-s1-b7-b6-b5-a5-a4; 116s2-b8-s1-b7-b6-b5-a5; 73.7s2-b8-a8; 300 s3-b

12、9-b8-b4-b2-b3-a3; 319s3-b9-b8-s1-b7-b6-b5-a5-a4; 11s3-b9-a9; 604s5-b12-b11-b10-b9-b8-b4-b2-b3-a3; 57.7s5-b12-b11-b10-b9-b8-s1-b7-b6-b5-a5; 542.3s5-b12-b11-b10-a10; 222.5s5-b12-a11; 415s6-b16-b15-b13-b11-b10-a10; 128.8s6-b16-b15-b13-b14-a12; 86s6-b16-b15-a13; 333s6-a14; 621s6-b16-b17-a15; 165（二）问题（2）

13、的求解 通过模型（二）的求解，我们确定对图（一）仅需要s1、s2、s3、s5、s6承担生产任务即可取得最优解。对模型所用程序进行灵敏度分析，并具体考虑当钢厂钢管的销价增加1万元或产量上限增加1单位时，购运计划和总费用的变化情况，结果如下表：表四 钢厂si的钢管产量上限增加1单位对总费用的影响s1s2s3s4s5s6s7总费用1278529127859712786071278632127863212786321278632减少量10335250000则可以发现：钢厂s1的钢管产量上限的变动对购运计划和总费用影响最大。表五 钢厂si的钢管销价增加1万元对总费用的影响s1s2s3s4s5s6s7总费

14、用1279432127943212796321278632127963913798341278632增加量80080010000100712020则可以发现：钢厂s6的钢管销价的微小变动对购运计划和总费用影响最大。（三） 问题（3）的求解 1、一般模型 经过对图（一）的分析求解可以看出，订购及运输钢管的总费用可由各段所需费用求和得到。若要铺设的管道是一个树形图， 则可以将其转化为线性管道进行分析。具体解题步骤如下：（1）运用图论的最小权匹配法（简单图可利用枚举法），求出从各钢厂定购并运输一单位钢管至主管道各结点的最小成本费用值。（2）将树型图转化为线性图： 在树形图中取其最长的线形段，称为主干

15、线形段；将图中剩余分支截取，并通过一个虚拟段（长度t为零）联接至主干线形段上，组成一个新的线性管道；如，图二中a9至a16段，可将该段接到a15 点，再分别从原图a9、a16点连一条长度为0的公路，而在a15点之间连一条长度为0的公路并增加一新的结点a9，同时约定a15点不向右铺设管道。其它各段类似处理。（3）按照问题（一）的思路建立模型进行求解。建立如下非线性规划模型：其中k表示钢厂的总数，l+1表示管道节点总数。2、问题三图（二）的求解图（二）为树形图，将其转化为类似图（一）的线性图。利用枚举法，求出一单位钢管由钢管厂si运输至管道结点i的最小成本费用，具体数据如下表：表六 单位钢管由si

16、运输至i的最小成本费用 (单位：万元)s1s2s3s5s6s7a1330.7370.7385.4410.7410.7435.7a2320.3360.3375400.3400.3425.3a3300.2345.2355.2380.2385.2405.2a4258.6326.6336.6361.6361.6386.6a5198216276301301326a6180.5250.5260.5285.5290.5310.5a7163.1241251276278.1301a8181.2226.2241.2266.2266.2291.2a9224.2269.2203.2234.2234.2259.2a10

17、252297237212211237a11256301241188201224a12266311251206187216a13281.2326.2266.2226.2166.2198.2a14288333273228161186a15302347287242178162a16220265199230230255a17255300240187197223a18260305245200183210a19265310250205186215a20275320260220160192a21285330270230150186模型（三） 首先类似于模型一，按分段的思想建立模型。由a1a9、a16为一段可

18、得如下模型：由a21-a20-a19-a17-a11-a12-a13-a14-a15-a9-a10-a11-a17-a18为一段可得如下模型：运用lingo软件进行编程（见附录四、五）运行结果为： 费用w1=69127.2 w2=539732.2 则总费用为：w=w1+w2=1408859.4模型（四）： 对整个图进行考虑，可得如下模型：利用lingo软件编程（见附录六）运行得出最优解w= 1403948万元，同时得出下表数据：表七 各钢厂定购计划：s1s2s3s4s5s6s7数量80080010000130320000表八 运输计划如下（vi含义参见附录八）:路 线 运量s1-v7-v6-v

19、5-a5; 335s1-v7-v6-a6; 200s1-a7; 265;s2-v8-v4-v2-v1-a2; 179s2-v8-v4-v2-v3-a3; 171s2-v8-s1-v7-v6-v5-a5; 150s2-v8-a8; 300 s3-a16-v8-v4-v2-v3-a3; 336s3-a16-a9; 664s5-a17-v10-v9-a16-v8-v4-v2-v3-a3; 1s5-a17-v10-v9-a16-v8-v4-a4; 468s5-a17-v10-v9-a16-v8-s1-v7-v6-v5-a5; 131s5-a17-v10-v9-a10; 218s5-a17-a11; 380s5-a17; 105s6-a20-a18-v10-v9-a10; 175s6-a20-a19-a17-a11; 111s6-a20-a13; 393s6-a14; 571s6-v11-v12-a15; 165s6-a20-a18; 130s6-a20-a19; 95s6-a20; 260s6-a21; 100（五）模型的评价1、本文从简单的角度入手建立模型，运用枚举法、图上作业法、图论等多种方法对模型进行逐步优化