全国数模竞赛优秀论文钢管订购与运输的优化模型(浙江师范大学 胡国英 柯 懿 张惠锋).doc

钢管订购与运输的优化模型胡国英 柯 懿 张惠锋 (浙江师范大学)摘要：本文作者仔细研究了所给图的性质，得到将铁路运费与销价全都转换为公路运费的思想。再通过Floyd提出的求解两点间最短路径的算法（具体算法见附录二），求得各钢厂到各个站点的最短路，再利用相关的非线性规划理论构造一个目标函数，从而得到优化模型。最后再利用LINGO软件求得准优解。特别地对于问题(2),用规划论中的sensitivity analysis可得到所需之结论。对于问题(3) 中的树形图情形可以先解决其分支部分，再考虑它的主干部分。关键词：目标函数；LINGO软件；最短路；赋权图（一）问题的重述要铺设一条AAA的输送天然气的主管道，如图一（见附录一）。经筛选后可以生产这种主管道钢管的钢 厂有S,S,S。为方便计，Km主管道称为单位钢管。 一个钢厂如果承担制造这种钢管，至少需要生产500个单位。钢厂S在指定期限内能生产该钢管的最大数量为s个单位，钢管出厂销价单位钢管为P万元，如下表：i1234567S80080010002000200020002000P160155155160155150160 单位钢管的铁路运价如下表：里程（Km）300301350351400401450451500运价（万远）2023262932 里程（Km）5016006017007018008019009011000运价（万元）37445055601000 Km以上每增加至100Km运价增加5元。公路运输费用为单位钢管每公里0.1万元（不足整公里部分按整公里计算）。钢管可由铁路、公路运往铺设地点（不只是运到点A,A A，而是管道全线）。（1） 请制定一个主管道钢管的订购和运输计划，使总费用最小（给出总费用）。（2） 请就（1）的模型分析：哪个钢厂 钢管的销价的变化对购运计划和总费用影响最大，哪个钢厂的产量的上限的变化对购运计划 和总费用的影响最大，并给出相应的数字结果。（3） 如果要铺设的管道不是一条线，而是一个树形图，铁路、公路和管道构成网络，请就这种更一般的情形给出一种解决办法，并对图二（见附录一）按（1）的要求给出模型和结果。 （二）问题的分析本题要铺设一条A A的天然气管道，使得总费用最小。可以这样考虑问题：我们可以先把钢厂生产的钢管运到各个站点A(i1)再往两边运送，再计算出总的费用使之最小。事实上我们并不知道每个站点上要运去多少货，所以设每个钢厂运往站点的数量为一变量及站点运往两边的钢管量也为变量，再通过图中已知信息相应的列出一些恒等式和约束条件。为了使问题便于求解，我们把铁路费用及销价相应转换为公路费用（其简化的图示见附录一的图三），又因为铁路运费为一分段函数，故要对一些点之间加线使运费相当。转换完毕后再利用赋权图的性质求出厂到站点的最短路。（其具体数据见附录三） （三）模型的假设（） 运钢管过程中若用火车则可直接把钢管运到公路与铁路交接处,即下了火车不上火车。（） 假设运输单位可提供足够的火车与汽车。（） 费用计算时按照钢管数量来算，不考虑其他计费方法及因素。（） 运费中不足整公里部分按整公里计。（） 假设向每个钢管厂都订购钢管。（） 设m主管道钢管为单位钢管。（） 路中铺设的钢管只允许由其相邻站点提供。（） 不计各个环节中的装卸费用。（四）符号说明: 表示生产钢管的钢厂（i=1,27）。A：表示暂存钢管的站点。(i=1,215)与：分别表示运往方向的钢管的数量和运往方向的钢管的数量。（其中=2,315 X=104, X=0）：表示存放在处的钢管数量（k=2,315）.Y: 表示从>A所运的钢管数量。(X,Y): 表示总的费用。（单位:万元）i :表示钢管销价的变化量。 （五）模型的建立与求解题：为了使问题简化，我们可采取如下原则：(1)总费用公路化原则：就是将铁路运费及钢管销价恰当的转换为公路运费。(2)就近原则：(a)指路上所铺设的钢管只允许来自与它相邻的站点。 (b)指每个站点所获得的钢管尽量来自与其较近的厂家。（i）建立模型 (k=2,315) 且满足如下条件：X+X=301 X+X=750 X+X=606X+X=194 X+X=205 X+X=201X+X=680 X+X=480 X+X=300X+X=220 X+X=210 X+X=420X+X=500MinF=(+-+5356)*0.1+ (C的数据见附录三)s.tY0 =B (k=2,315), 500800, 500800, 5001000 500 2000,500 2000 500 20005003000 下面对目标函数进行说明：由于在铺设管道的路上可以边卸边运，故在铺设管道上的运费成等差数列，然后对运费求和得(+-+5356)*0.1。根据程序（见附录二）可计算得到从到的最短路，转换成运费即为，则 表示从到 的总费用。需要求的是最小总费用F，而F可分为在铺设管道的路上的费用和从S运到A的路费这两部分，因此得到上述目标函数。(ii)模型的求解及结果因为我们的LINGO软件只能最多有100个变量和50个约束条件，若把变量Y全都输入的话，那么将无法求解，故先按照就近原则(b)适当的去掉一些Y,也就是说可令一些Y=0。通过LINGO软件的计算得到总费用最小minF=1280235万元。现在来分析一下模型假设对结果的影响：事实上并不需要向每个钢厂都订购，即允许i ，s,t =0，再利用LINGO软件进行计算，得到当钢厂和都不生产时有minF=1274304万元。（具体的求解过程请详见附录四） 按照上面的分析可以确定一个主管道钢管的订购和运输计划，如下：(1) 向各厂家的订购量：向订购800个单位，向订购800个单位，向订购1000个单位，向订购1105个单位，向订购1466个单位，向，订购个单位。(2) 运输计划：总的原则是走前面所得到的最短路径，具体运送方向及数量，如下： Y=313, Y=251, Y=236, Y=179, Y=55, Y=244, Y=322, Y=78, Y=314, Y=608, Y53=448, Y=41, Y55=42, Y5,10=159, Y5,11=415, Y64=41, Y6,10=220, Y6,12=86, Y6,14=621, Y6,15=165, 题：问题转化为：（）上限变化对费用的影响。（）销价变化对费用的影响。先做（）：我们还是利用LINGO软件中的分析功能，（把上限全都改成6000个单位，再观察哪一个钢厂提供的数量有明显增大，那么就认为它对总费用的影响最大）得知对总F影响最甚，使得minF=1183800万元。对于（）： 我们考虑销价变化对对费用的影响时，可以设定参数i(i=1,27)，从实际情况考虑，一个产品在销价方面的变化不会太大。这一点也可以从原来的信息：两个不同厂家之间的最大销价差仅10万元得知。所以完全可假定i -10,10, i。再把其代入题中的目标函数，用LINGO软件计算出最小值及此时的i值，再进行横向比较，看哪个厂家相对于前面所得之结论变化最大，那么我们就认为其之影响最大，也就是我们要的结果。由于还是变量过多，故只能人为取有限个值i，进行运算得到近似解，从而有对总费用的影响最大，其波动范围为-1.89, 1.18亿元。（具体的演算过程这里从略）题：仔细观察，分析图（二）可知，铺设17这一段，完全与题相同，不同的是所增加的集中于，旁的一些需铺设的路段，并且管道形成一个树形图。显然费用将大大增加，所以解决该问题可以先解决分支部分，而后做主干部分，也就是先计算出所增加铺设路段的最小费用。（计算的方法可参照问题的算法）再把其加到题中的目标函数，当然函数的约束条件将有所变化（具体的请见附录五），这里只给出结果minF=1408343万元.。 按照上面的分析可以确定一个主管道钢管的订购和运输计划，如下：(1) 向各厂家的订购量：向订购800个单位，向订购800个单位，向订购1000个单位，向订购个单位,向订购1412个单位，向订购1391个单位，向订购500个单位。(2) 运输计划：总的原则是走前面所得到的最短路径，具体运送方向及数量，如下： Y=113, Y=451, Y=236, Y=179, Y=54, Y=244, Y=323, Y=350, Y=608, Y3,16=42, Y53=448, Y5,10=379, Y5,11=415, Y5,17=170, Y64=11, Y6,12=86, Y6,13=333, Y6,14=441, Y6,18=60, Y6,19=100, Y6,20=260, Y6,21=100, Y75=155, Y7,15=345, （六）模型的分析与检验现对假设及原则进行说明：对于假设(1)，从图（一）的连通性，铁、公路长短性及多次装卸与实际不符，知其具有合理性。对于假设(5)，是为了方便用LINGO软件计算，但并不十分合理，我们从后面的计算结果可知，可以去掉它。对于假设(7)，由于两相邻站点都较远，故显然不可能从较远处运来钢管进行铺设。对于模型的合理性可参考相关的报道。（七）模型的优缺点及改进方向题：(1) 本模型基本符合题目的要求，即所求得的最小费用与理论值较接近。(2) 本模型对第二小题有用，即通过sensitivity analysis 可以知道销价变化对最小费用的影响，孰弱孰强。(3) 本模型变量多于100个，为了能LINGO软件，在计算时，已经人为削去了一些变量，这就产生了一定的误差。若可以用企业版的LINGO软件系统，则可以得到更优解。(4) 我们是否可以这样考虑问题，会使模型更加精确，也就是说：每隔公里虚设一点，再利用计算机先向各个厂家搜索，找到所需费用的一家。题：(1) 解决该题时，充分利用了图本身的性质，但这并不利于模型的推广。(2) 此模型思想简单利于接受，运算也很方便。参考文献：(1) 叶其孝. 大学生数学建模竞赛辅导教材 湖南教育出版社 (2) 曾道智译最优化方法世界图书出版公司，北京 (3) 卜月华.图论及其应用东南大学出版社附录一：图（一）图（二）图（三）附录二：#define M x /*x表示用来存储图中各边权值的矩阵的阶*/#define MAX 65535 /*没有边直接相连的两点间的距离为无穷大*/void zdljq(int coM,int n)int adMM,pMM;/*矩阵ad用来存放两点间最短距离的值，p用来存放两点间的最短路径*/int i,j,k,wm;for (i=0;i<n;i+) for (j=0;j<n;j+) adij=coij; if (i=j) pij=0; else if(adij<MAX) pij=i+1; else pij=0; for(k=0;k<n;k+) for(i=0;i<n;i+) for (j=0;j<n;j+) if(adik+adkj<adij) adij=adik+adkj; pij=pkj; for(i=0;i<n;i+) for(j=0;j<n;j+)printf("%6d", adij);printf("n"); printf("n");main() int coM=aIj /*aij表示图的邻接矩阵*/ zdljq(co, M);_附录三： 320.3 360.3 375.3 410.3 400.3 405.3 425.3300.2 345.2 355.2 395.2 380.2 385.2 405.2258.6 326.6 330.5 370.2 360.5 360.5 380.5198 266 269.9 309.9 299.9 299.9 319.9180.5 240.5 250.5 290.5 280.5 280.5 300.5C=(c)= 163.1 241 251 291 276 281 301181.2 226.2 241.2 276.2 266.2 271.2 291.2224.2 269.2 203.8 244.2 234.2 234.2 259.2252 297 237 222 212 212 237256 301 241 211 188 201 226266 311 251 221 206 195 216281.2 326.2 266.2 236.2 226.2 176.2 198.2288 333 273 243 228 161 186302 347 287 257 242 178 162附录四：题的运算过程MODEL: MIN=(1/2*(X232+X342+X452+X562+X672+X782+X892+X9102+X10112+ X11122+X12132+X13142+X14152+(301-X23)2+(750-X34)2+(606-X45)2+ (194-X56)2+(205-X67)2+(201-X78)2+(680-X89)2+ (480-X910)2+(300-X1011)2+(220-X1112)2+(210-X1213)2+ (420-X1314)2+(500-X1415)2)-4967/2+ 5356)*0.1+320.3*Y12+300.2*Y13+258.6*Y14+198*Y15+180.5*Y16+ 163.1*Y17+181.2*Y18+224.2*Y19+252*Y110+256*Y111+266*Y112+ 360.3*Y22+345.2*Y23+326.6*Y24+ 266*Y25+240.5*Y26+241*Y27+226.2*Y28+269.2*Y29+297*Y210+301*Y211+ 311*Y212+326.2*Y213+375.3*Y32+ 355.2*Y33+330.5*Y34+269.9*Y35+250.5*Y36+251*Y37+241.2*Y38+ 203.8*Y39+237*Y310+241*Y311+251*Y312+266.2*Y313+273*Y314+ 287*Y315+410.3*Y42+ 395.2*Y43+370.2*Y44+309.9*Y45+290.5*Y46+291*Y47+276.2*Y48+ 244.2*Y49+222*Y410+211*Y411+221*Y412+236.2*Y413+243*Y414+ 257*Y415+380.2*Y53+360.5*Y54+299.9*Y55+280.5*Y56+276*Y57+266.2*Y58+ 234.2*Y59+212*Y510+188*Y511+206*Y512+ 226.2*Y513+228*Y514+242*Y515+360.5*Y64+299.9*Y65+280.5*Y66+ 281*Y67+271.2*Y68+234.2*Y69+212*Y610+ 201*Y611+195*Y612+176.2*Y613+161*Y614+178*Y615+319.9*Y75+300.5*Y76+ 301*Y77+291.1*Y78+259.2*Y79+237*Y710+ 226*Y711+216*Y712+198.2*Y713+186*Y714+162*Y715; Y12+Y22+Y32+Y42=104+X23; Y13+Y23+Y33+Y43+Y53=301-X23+X34; Y14+Y24+Y34+Y44+Y54+Y64=750-X34+X45; y15+Y25+Y35+Y45+Y55+Y65+Y75=606-X45+X56; Y16+Y26+Y36+Y46+Y56+Y66+Y76=194-X56+X67; y17+Y27+Y37+Y47+Y57+Y67+Y77=205-X67+X78; Y18+Y28+Y38+Y48+Y58+Y68+Y78=201-X78+X89; Y19+Y29+Y39+Y49+Y59+Y69+Y79=680-X89+X910; Y110+Y210+Y310+Y410+Y510+Y610+Y710=480-X910+X1011; y111+Y211+Y311+Y411+Y511+Y611+Y711=300-X1011+X1112; Y112+Y212+Y312+Y412+Y512+Y612+Y712=220-X1112+X1213; Y213+Y313+Y413+Y513+Y613+Y713=210-X1213+X1314; Y314+Y414+Y514+Y614+Y714=420-X1314+X1415; Y315+Y415+Y515+Y615+Y715=500-X1415; 500<=Y12+Y13+Y14+Y15+Y16+Y17+Y18+Y19+Y110+Y111+Y112; Y12+Y13+Y14+Y15+Y16+Y17+Y18+Y19+Y110+Y111+Y112<=800; 500<=Y22+Y23+Y24+Y25+Y26+Y27+Y28+Y29+Y210+Y211+Y212+Y213; 500<=Y32+Y33+Y34+Y35+Y36+Y37+Y38+Y39+Y310+Y311+Y312+Y313+Y314+Y315; 0=Y42+Y43+Y44+Y45+Y46+Y47+Y48+Y49+Y410+Y411+Y412+Y413+Y414+Y415; 500<=Y53+Y54+Y55+Y56+Y57+Y58+Y59+Y510+Y511+Y512+Y513+Y514+Y515; 500<=y64+Y65+Y66+y67+Y68+Y69+Y610+Y611+Y612+Y613+Y614+Y615; 0=Y75+Y76+Y77+Y78+Y79+Y710+Y711+Y712+Y713+Y714+Y715; Y22+Y23+Y24+Y25+Y26+Y27+Y28+Y29+Y210+Y211+Y212+Y213<=800; Y32+Y33+Y34+Y35+Y36+Y37+Y38+Y39+Y310+Y311+Y312+Y313+Y314+Y315<=1000; Y42+Y43+Y44+Y45+Y46+Y47+Y48+Y49+Y410+Y411+Y412+Y413+Y414+Y415<=2000; Y53+Y54+Y55+Y56+Y57+Y58+Y59+Y510+Y511+Y512+Y513+Y514+Y515<=2000; Y64+Y65+Y66+Y67+Y68+Y69+Y610+Y611+Y612+Y613+Y614+Y615<=2000; Y75+Y76+Y77+Y78+Y79+Y710+Y711+Y712+Y713+Y714+Y715<=3000;END题的具体解Objective value: 1274304. Variable Value Reduced Cost X23 74.99888 -0.2178615E-03 X34 276.5003 0.0000000 X45 -0.1542264 -0.2825982E-01 X56 0.0000000 5.005263 X67 50.00136 0.2149919E-03 X78 81.50305 0.0000000 X89 203.0043 0.0000000 X910 131.0039 0.0000000 X1011 30.00009 0.4258355E-04 X1112 144.9996 0.2149086E-02 X1213 11.00137 0.2101267E-03 X1314 133.9995 -0.1167746E-03 X1415 334.9999 0.0000000 Y12 0.0000000 26.90007 Y13 0.0000000 21.90008 Y14 473.4957 0.0000000 Y15 90.00263 0.0000000 Y16 0.0000000 6.900063 Y17 236.5017 0.0000000 Y18 0.0000000 21.89941 Y19 0.0000000 92.29853 Y110 0.0000000 141.8978 Y111 0.0000000 169.8978 Y112 0.0000000 172.9000 Y22 178.9989 0.0000000 Y23 54.49847 0.0000000 Y24 0.0000000 1.099931 Y25 0.0000000 1.099937 Y26 244.0014 0.0000000 Y27 0.0000000 10.99993 Y28 322.5013 -0.6607056E-03 Y29 0.0000000 70.39846 Y210 0.0000000 119.9977 Y211 0.0000000 147.9977 Y212 0.0000000 150.9999 Y213 0.0000000 184.9999 Y32 0.0000000 10.00154 Y33 0.0000000 5.001550 Y34 0.1959598E-02 0.1470566E-02 Y35 391.9985 0.1476669E-02 Y36 0.0000000 5.001532 Y37 0.0000000 16.00147 Y38 0.0000000 10.00088 Y39 607.9995 0.0000000 Y310 0.0000000 54.99923 Y311 0.0000000 82.99923 Y312 0.0000000 86.000015 Y315 0.0000000 139.0015 Y42 0.0000000 15.00007 Y43 0.0000000 15.00008 Y44 0.0000000 9.700000 Y45 0.0000000 10.00001 Y46 0.0000000 15.00006 Y47 0.0000000 26.00000 Y48 0.0000000 14.99941 Y49 0.0000000 10.39853 Y410 0.0000000 9.997757 Y411 0.0000000 22.99776147 Y313 0.0000000 120.0015 Y314 0.0000000 142. Y412 0.0000000 26.00000 Y413 0.0000000 60.00000 Y414 0.0000000 82.00000 Y415 0.0000000 79.00002 Y53 448.0030 0.2315668E-02 Y54 0.2012504E-02 0.2236322E-02 Y55 0.2012504E-02 0.2242426E-02 Y56 0.0000000 5.002297 Y57 0.0000000 11.00224 Y58 0.0000000 5.001644 Y59 0.0000000 0.4007684 Y510 378.9962 0.0000000 Y511 414.9995 0.0000000 Y512 0.0000000 11.00224 Y513 0.0000000 50.00224 Y514 0.0000000 67.00224 Y515 0.0000000 64.00225