钢管订购和运输数学建模论文.docx

《钢管订购和运输数学建模论文.docx》由会员分享，可在线阅读，更多相关《钢管订购和运输数学建模论文.docx（16页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

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

2、408859.4 和1403948 万元钢管订购和运输数学建模论文一、问题的提出已知有 7 个钢厂，可生产输送天然气主管道的钢管，用S 表i示(i=1,2,7)。现有个地点（A ,A ,A），沿着这个地1215点铺设一条输送天然气的主管道。为方便计，1km 主管道称为 单位钢管。一个钢厂如果承担制造这种钢管，至少需要生产 500 个单位。钢厂 Si在指定期限内能生产该钢管的最大数量为 s 个单位，钢管i出厂销价 1 单位钢管为 p 万元，如下表：isipii1234567800800100020002000200030001601551551601551501601 单位钢管的铁路运价如下表：

3、里程(km)300301350351400401450451500运价(万元)2023262932里程(km)5016006017007018008019009011000运价(万元)37445055601000km 以上每增加 1 至 100km 运价增加 5 万元。公路运输费用为 1 单位钢管每公里 0.1 万元（不足整公里部分按整公里计算）。钢管可由铁路、 公路运往铺设地点（ 不只是运到点A , A , A，而是管道全线）1215。（1） 请制定一个主管道钢管的订购和运输计划，使总费用最小（给钢管订购和运输数学建模论文出总费用)。（2） 请就（1）的模型分析：哪个钢厂钢管的销价的变化对购

4、运计划和总费用影响最大，哪个钢厂钢管的产量的上限的变化对购运计划和总费用的影响最大，并给出相应的数字结果。（3） 如果要铺设的管道不是一条线，而是一个树形图，铁路、公路和管道构成网络，请就这种更一般的情形给出一种解决办法，并对图二按（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）

6、在 Si 厂购买钢管要么为零,要么至少为 500 单位。（二）符号说明：x ：从钢厂 S 运到结点 A 的单位钢管数；ijijfSA：单位钢管从钢厂运到结点的的最少成本费用；ijijjjj+1t ：第 A 点与 A点间的路线长度，j=1,2,14；jjy ：从结点 A 开始沿管道向右铺设的路线长度, j=1,2,3,15； w：钢管订购和运输的总费用；m : 钢厂 S 的最小产量，m =500，i=1,2,3,4,5,6,7iiiiiiin : 钢厂 S 的产量上限，n =s ，i=1,2, ，7 bi:图一中各节点（见附录七）Vi:图二中各节点（见附录八）四、模型的建立与求解（一）问题一及其

7、求解：针对图（一），我们首先采用图上作业法对所给图进行分析，利用枚举法，我们求出一单位钢管由钢管厂 Si运输至管道结点 的最小i成本费用，具体数据如下表：ii表一单位钢管由S 运输至 的最小成本费用(单位：万元)S1S2S3S4S5S6S7A1330.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.525

8、0.5260.5300.5285.5290.5310.5A7163.1241251291276281301A8181.2226.2241.2276.2266.2271.2291.2A9224.2269.2203.2244.2234.2234.2259.2A10252297237222212212237A11256301241211188201226A12266311251221206195216A13281.2326.2266.2236.2226.2176.2198.2A14288333273243228161186A15302347287257242178162这样，原问题即转化为通常的运输

9、问题。我们进一步对上表数据进行分析，得到结论：结论 1：将4、S5 两列数据进行对比，发现同一行中 S4 列数据均大于 S5 列。由此得出，应优先考虑钢厂 S5，只有当对 S5 的需求量超过其最大产量时，才需要考虑钢厂S4。进一步对原图进行分析可得：结论 2：由于 A1 点只有通过A2 点才能与钢厂Si 连接,故模型中不需考虑往A1 运输钢管。模型(一)：对表一数据进一步分析。将各行数据由小到大排序，发现由A2 至 A9 各行中费用最小的前四个数据均在 S1,S2,S3,S5 列中，由 A10 至A15 各行中费用最小的前三个数据均在S5,S6,S7 中，直观感觉到： A1 至 A9 需要来自

10、 S6 及 S7 等后一部分钢厂的钢管的可能性很小， 而且 A9 至 A15 不太可能需要S1、S2、S3 等前一部分钢厂生厂的钢管，故把原图分为两个子图考虑，分别为A1 至A9 和A9 至A15， 即分为两个子模型，分别进行最优化，得到两个子模型(非线性规划模型)如下：子模型 1：min4 8x*f+ 0 .18( y 2+(t-y) 2+ t)i ( j + 1 )i ( j + 1 )2jjjji =1 j =1j =1m 8 x n or8 x= 0;(i = 1,2,3,4)j =1j =1ii ( j +1)ii( j +1)x+ x + x + x= t + y ；s.t. 12

11、223242124 i=1xi( j +1)= t - y + y;（j = 2,3,.7)jjj +1y子模型 2：x + x + x + x19293949= t -88min 7 15 x*iji = 5 j = 9f+ 0 .1 15ij2j = 9( y 2 + (t-jjy ) 2 + t )jjm 15 x n or15 x= 0;(i = 5,6,7)ij =9ijiijj =9x+ x + xs.t.x5969 79= y ；9y 5,15+ x6,15+ x7,15= t +;1414 7i=5x = tijj +1- y+ y ;（j = 10,11,.14)j -1j由

12、于这两个子模型属于非线性规划问题，且第一个约束条件很复杂，利用结论 1、2，采用分支定界法用 LINGO 软件分别进行编程（见附录一、二）得到：w1=859629.3w2=419866.7模型一的总费用为w=w1+w2=1279496（万元）。模型（二）：由于前面的模型直观将管道分为两端，即原图分为两个子图， 可能存在一定的误差。下面对模型（一）进行优化，即对主管道建立统一模型，如下：min 7 14i =1 j =1x*i ( j + 1 )f+i ( j + 1 )0 .1 142j =1( y 2 + (t-jjy ) 2 + t )jjm 14j =1j =1ixi ( j + 1 )

13、 n or 14ixi ( j + 1 )= 0 ; ( i = 1, 2 ,., 7 ) 7 i = 1x i ,15= t 14- y;14 7s .t . i = 1x i 2=+ y;t12 7t i = 1x i ( j + 1) =j - y j + yj + 1; ( j = 2 ,3,., 13 ) y = 01同样利用结论 1、2 并采用分支定界法，利用 LINGO 软件编程（见附录三）运行得出:最优解 W=1278632 万元，各节点向右铺设的管道单位数：Y1=0Y2=175Y3=282Y4=0Y5=10Y6=16Y11=145Y7=76Y12=11Y8=175Y13=34

14、Y9=159Y14=335Y10=30表二各钢厂定购计划：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;300S3-b9-b8-b4-b2-b3-A3;319S3-b9-b8-S1-b7-b6-b5-A5-A4

15、;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;（二）问题（2）的求解165通过模型（二）的求解，我们确定对图（一）仅需要 S1、S2、S3、S5、S6 承担生产任务即可取得最优解。对模

16、型所用程序进行灵敏度分析，并具体考虑当钢厂钢管的销价增加 1 万元或产量上限增加1 单位时，购运计划和总费用的变化情况，结果如下表：表四 钢厂Si 的钢管产量上限增加 1 单位对总费用的影响S1S2S3S4S5S6S7总费用1278529127859712786071278632127863212786321278632减少量10335250000则可以发现：钢厂 S1 的钢管产量上限的变动对购运计划和总费用影响最大。表五 钢厂 Si 的钢管销价增加 1 万元对总费用的影响S1S2S3S4S5S6S7总费用12794321279432127963212786321279639137983412

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

18、个新的线性管道；如，图二中 A9 至 A16 段，可将该段接到A15 点，再分别从原图 A9、A16 点连一条长度为 0 的公路，而在 A15 点之间连一条长度为 0 的公路并增加一新的结点 A9，同时约定 A15 点不向右铺设管道。其它各段类似处理。（3） 按照问题（一）的思路建立模型进行求解。建立如下非线性规划模型：钢管订购和运输数学建模论文min K Li =1 j =1x*i ( j +1 )f+i ( j +1 )0 .1 L2j =1( y 2 + (t-jjy ) 2 + tj)(1)jm Lj =1j =1ixi ( j +1 ) n or Lixi ( j +1 )= 0 ;

19、 ( i = 1, 2 ,., K ) K i = 1x i , L + 1 = t L - y L ; K s .t . i = 1x i 2=+ y;t12( 2 ) Kt i = 1x i ( j + 1) =j - y+ yjj + 1;( j = 2 ,3,., L -1) y = 01其中K 表示钢厂的总数，L+1 表示管道节点总数。2、问题三图（二）的求解图（二）为树形图，将其转化为类似图（一）的线性图。利用枚举法，求出一单位钢管由钢管厂 Si 运输至管道结点i 的最小成本费用，具体数据如下表：表六单位钢管由 Si 运输至i 的最小成本费用(单位：万元)S1S2S3S5S6S7A

20、1330.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.2A10252297237212211237A1125630124118

21、8201224A12266311251206187216A13281.2326.2266.2226.2166.2198.2A14288333273228161186A15302347287242178162钢管订购和运输数学建模论文A16220265199230230255A17255300240187197223A18260305245200183210A19265310250205186215A20275320260220160192A21285330270230150186模型（三）首先类似于模型一，按分段的思想建立模型。由 A1A9 、A16 为一段可得如下模型：min 4 9i =1

22、 j =1x*i ( j +1 )f+i ( j +1 )0 .1 92j =1( y 2 + (t-jjy ) 2 + t )jjm 9j =1j =1ixi ( j +1 ) n or 9ixi ( j +1 )= 0 ; ( i = 1, 2 ,., 4 ) 4 i =1x i ,10=- y;t99 4s .t . i =1=+ y;xti 212 4t i =1x i ( j + 1) =j - y+ yjj + 1;( j = 2 ,3,., 8 ) y = 01由A21-A20-A19-A17-A11-A12-A13-A14-A15-A9-A10-A11-A17-A18 为一段可

23、得如下模型：min 7 14 x *iji = 5 j =1f+ 0 .1 14ij2j =1( y 2 + (t-jjy ) 2 + t )jjm 14ij =1x nijior 14 xijj =1= 0 ; ( i = 5 ,6 ,7 ) 7 i = 5s .t . 7x i ,14 = 14tx= y ;- y;14 i1 i = 57t x= i = 5ij1j - 2 - y+ yj -1;( j = 2 ,3,., 13 )j运用LINGO 软件进行编程（见附录四、五）运行结果为： 费用w1=69127.2w2=539732.2则总费用为：w=w1+w2=1408859.4模型（

24、四）：对整个图进行考虑，可得如下模型：min 7 23i =1 j =1x*i ( j +1 )f+i ( j +1 )0 .1 232j =1( y 2 + (t-jjy ) 2 + t )jjm 23j =1j =1ixi ( j +1 ) n or 23ixi ( j +1 )= 0 ; ( i = 1, 2 ,., 7 ) 7 i =1x i , 24=- y;t2323 7s .t . i =1=+ y;xti 212 7t i =1x i ( j + 1) =j - y+ yjj + 1;( j = 2 ,3,., 23 ) y = 01利用LINGO 软件编程（见附录六）运行得出

25、最优解w= 1403948S1S2S3S4S5S6S7数量80080010000130320000万元，同时得出下表数据： 表七各钢厂定购计划：表八运输计划如下（Vi 含义参见附录八）:路 线运量S1-V7-V6-V5-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;300S3- A16-V8-V4-V2-V3-A3;336S3-A16-A9;664S5-A17-V10-V9-A16-V8-V4-V2-V3-A3;1S5-A17-V

26、10-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、本文从简单的角度入手建立模型，运用枚举法、图上作业法、图论等多种方法对模型进行逐步优化。过程严谨

27、，理论性强，逻辑严密，而且易于理解。2、模型一、三为问题的近似解，但涉及变量少，易于求解，且精度较高；模型二、四为问题的精确解，变量多，求解稍难。3、一般模型（1）（2）式具有很强的通用性，网络、树型图转化为线性图的方法也具有一般性；4、本文大量运用了计算机程序，所有数据均由计算机处理，故误差由计算机精度产生，模型具有较好的稳定性。参考文献（1） 李德、钱颂迪运筹学清华大学出版社1982 年；（2） 许卓群等数据结构高等教育出版社1987 年；（3）滕传琳管理运筹学中国铁道出版社1986 年；（4）美E 米涅卡网络和图的最优计算方法评注：中国道出铁版社1984 年；本题是一个典型的离散优化问题

28、，实际上最终归结为两个二次规划模型。求解的关键包括定购和运输单价的计算、二次规划模型的建立和求解。其中的难点是题中复杂图的恰当处理和模型中变量数特别是整型变量数过多的灵活解决。本优秀论文在对这两问题的处理上颇有特色：其一是对问题一的图，作者首先根据直观分析，将原图分成两个小图分别求解，再合二为一建立优化模型；而针对问题二的树形图，通过增加一个长度为零费用为零的线路转化为线性图后，问题二的求解方法就与问题一的求解方法相同了。这是“从简单到复杂，从局部到全局，化繁琐为简单”的建模思想的具体体现。其二是对变量数过多问题的解决，作者经过约束条件的松弛化处理后，充分利用非线性规划软件Lingo的强大功能，主要是循环语句的灵活使用，得出了最优解。