您的当前位置：首页正文

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

来源：爱够旅游网

（1）如果要铺设的管道不是一条线，而是一个树形图，铁路、公路和管道构成网络，请

就这种更一般的情形给出一种解决办法，并对图二（见附录一）按（1）的要求给

出模型和结果。

（二）问题的分析

本题要铺设一条A1 ~A15的天然气管道，使得总费用最小。可以这样考虑问题：我们可以先把钢厂生产的钢管运到各个站点

Ai(i1)再往两边运送，再计算出总的费用使之最小。事实上我们并不知道每个站点上要运去多少货，所以设每个钢厂运往站点的数量为一变量及站点运往两边的钢管量也为变量，再通过图中已知信息相应的列出一些恒等式和约束条件。为了使问题便于求解，我们把铁路费用及销价相应转换为公路费用（其简化的图示见附录一的图三），又因为铁路运费为一分段函数，故要对一些点之间加线使运费相当。转换完毕后再利用赋权图的性质求出厂到站点的最短路。（其具体数据见附录三）

（三）模型的假设

（１）运钢管过程中若用火车则可直接把钢管运到公路与铁路交接处,即下了火车不上火车。（２）假设运输单位可提供足够的火车与汽车。

（３）费用计算时按照钢管数量来算，不考虑其他计费方法及因素。（４）运费中不足整公里部分按整公里计。（５）假设向每个钢管厂都订购钢管。

（６）设１Ｋm主管道钢管为１单位钢管。

（７）路中铺设的钢管只允许由其相邻站点提供。（８）不计各个环节中的装卸费用。

（四）符号说明

Ｓi: 表示生产钢管的钢厂（i=1,2…7）。 Ai：表示暂存钢管的站点。(i=1,2…15)

Ｘk,k1与Ｘk,k1：分别表示Ａk运往Ａk1方向的钢管的数量和Ａk运往Ａk1方向的钢管的数量。（其中Ｋ=2,3…15 X21=104, X15,16=0）Ｂk：表示存放在Ａk处的钢管数量（k=2,3…15）. Yij: 表示从Ｓi－>Aj所运的钢管数量。Ｆ(Xij,Yij): 表示总的费用。（单位:万元） △Ｐi : 表示钢管销价的变化量。

（五）模型的建立与求解

题Ⅰ：为了使问题简化，我们可采取如下原则：

(1)总费用公路化原则：就是将铁路运费及钢管销价恰当的转换为公路运费。 (2)就近原则：(a)指路上所铺设的钢管只允许来自与它相邻的站点。 (b)指每个站点所获得的钢管尽量来自与其较近的厂家。（i）建立模型

Ｂk＝Ｘk,k1＋Ｘk,k1 (k=2,3…15) 且满足如下条件： X23+X32=301 X34+X43=750 X45+X54=606 X56+X65=194 X67+X76=205 X78+X87=201 X89+X98=680 X9,10+X10,9=480 X10,11+X11,10=300 X11,12+X12,11=220 X12,13+X13,12=210 X13,14+X14,13=420 X14,15+X15,14=500

MinF=(

k214Xk2,k12157Xk2,k14967+-+5356)*0.1+CijYij

22j2i1k315 (Cij的数据见附录三)

s.t Yij0

15Y

i11j7

i,k

=Bk (k=2,3…15),

15500Yj1800, 500Y2j800,

j1500Yj115153j1000 500Y4j 2000,

j11515500Yj1155j 2000 500Y6j 2000

j1500Yj17j3000

下面对目标函数进行说明：

由于在铺设管道的路上可以边卸边运，故在铺设管道上的运费成等差数列，然后对运费求和得(

k214Xk2,k12Xk2,k14967+-+5356)*0.1。

22k315

根据程序（见附录二）可计算得到从Ｓi到Ａi的最短路，转换成运费即为Ｃij，则表示从Ｓi到Ａj 的总费用。

需要求的是最小总费用F，而F可分为在铺设管道的路上的费用和从Si运到Aj的路费这两部分，因此得到上述目标函数。

(ii)模型的求解及结果

因为我们的LINGO软件只能最多有100个变量和50个约束条件，若把变量Yij全都输入的话，那么将无法求解，故先按照就近原则(b)适当的去掉一些Yij,也就是说可令一些Yij=0。通过LINGO软件的计算得到总费用最小minF=1280235万元。

现在来分析一下模型假设对结果的影响：事实上并不需要向每个钢厂都订购，即允许i1,7 ，s,t

CYj2i1157ijij

Yj215ij=0，再利用LINGO软件进行计算，得到当钢厂Ｓ4和Ｓ7都不生产时有minF=1274304

万元。（具体的求解过程请详见附录四）

按照上面的分析可以确定一个主管道钢管的订购和运输计划，如下：

(1) 向各厂家的订购量：向Ｓ1订购800个单位，向Ｓ2订购800个单位，向Ｓ3订购1000个单位，向Ｓ5订购1105个单位，向Ｓ6订购1466个单位，向Ｓ4，Ｓ7订购０个单位。 (2) 运输计划：总的原则是走前面所得到的最短路径，具体运送方向及数量，如下： Y14=313, Y15=251, Y17=236, Y22=179, Y23=55, Y26=244, Y

28=322, Y

34=78, Y

35=314, Y

39=608, Y53=448, Y

54=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个单位，再观察哪一个钢厂提供的数量有明显增大，那么就认为它对总费用的影响最大）得知Ｓ1对总F影响最甚，使得minF=1183800万元。对于（２）：我们考虑销价变化对对费用的影响时，可以设定参数△Ｐi (i=1,2…7)，从实际情况考虑，一个产品在销价方面的变化不会太大。这一点也可以从原来的信息：两个不同厂家之间的最大销价差仅10万元得知。所以完全可假定△Ｐi ∈[-10,10], i1,7。再把其代入题Ⅰ中的目标函数，用LINGO软件计算出最小值及此时的△Ｐi值，再进行横向比较，看哪个厂家相对于前面所得之结论变化最大，那么我们就认为其之影响最大，也就是我们要的结

果。

由于还是变量过多，故只能人为取有限个值△Ｐi，进行运算得到近似解，从而有Ｓ６对总费用的影响最大，其波动范围为［-1.89, 1.18］亿元。（具体的演算过程这里从略）

题Ⅲ：仔细观察，分析图（二）可知，铺设Ａ1～Ａ7这一段，完全与题Ⅰ相同，不同的是所增加的集中于Ｓ５，Ｓ６旁的一些需铺设的路段，并且管道形成一个树形图。显然费用将大大增加，所以解决该问题可以先解决分支部分，而后做主干部分，也就是先计算出所增加铺设路段的最小费用。（计算的方法可参照问题Ⅰ的算法）再把其加到题Ⅰ中的目标函数，当然函数的约束条件将有所变化（具体的请见附录五），这里只给出结果minF=1408343万元.。按照上面的分析可以确定一个主管道钢管的订购和运输计划，如下：

(1) 向各厂家的订购量：向Ｓ1订购800个单位，向Ｓ2订购800个单位，向Ｓ3订购1000个单位，向Ｓ4订购０个单位,向Ｓ5订购1412个单位，向Ｓ6订购1391个单位，向Ｓ7订购500个单位。 (2) 运输计划：总的原则是走前面所得到的最短路径，具体运送方向及数量，如下： Y14=113, Y15=451, Y17=236, Y22=179, Y23=54, Y26=244, Y

28=323, Y

34=350, Y

39=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) 卜月华. 图论及其应用东南大学出版社

附录一：

A1S4690A18320160170B8520A16B9884621031201A712680A8480300A10A9S5220A11210A1210A137062A19S6110420500A14A2016070302020B10290B1130S7S3S21200B77201100B31150B145080B03104A12600B210194606A4A5B45205A6306B520220B619510S14270A17690 A15750301A3A2 图（一）

S4690S3A18320160170B9B813052088A1670A174621031201A712680A8480300A9A1019010S5220A11210A12A1370260A19S6110420500A14A201607062100302020B10290B1130S7 S2 1200B76907201100B31150B145080B031042600B210194606A5B45205A6306B520220B619510S1A1542750301A3A4A2

图（二） SjS1

A1A2A3AiAi+1

图（三）

S7A14A15附录二：

#define M x /*x表示用来存储图中各边权值的矩阵的阶*/

#define MAX 65535 /*没有边直接相连的两点间的距离为无穷大*/ void zdljq(int co[][M],int n) {

int ad[M][M],p[M][M]; /*矩阵ad用来存放两点间最短距离的值，p用来存放两点间的最短路径*/ int i,j,k,wm; for (i=0;ifor(k=0;kif(ad[i][k]+ad[k][j]for(i=0;i{ for(j=0;jprintf(\"\\n\"); }

main()

{ int co[][M]=a[I][j] /*a[i][j]表示图的邻接矩阵*/ zdljq(co, M); }_

附录三：

C=(cij)=

320.3 300.2258.6198 180.5163.1 181.2224.2252 256 266 281.2288 302

360.3 375.3 345.2 355.2 326.6 330.5 266 269.9 240.5 250.5 241 251 226.2 241.2 269.2 203.8 297 237 301 241 311 251 326.2 266.2 333 273 347 287 410.3 400.3 395.2 380.2 370.2 360.5 309.9 299.9 290.5 280.5 291 276 276.2 266.2 244.2 234.2 222 212 211 188 221 206 236.2 226.2 243 228 257 242 405.3 385.2 360.5 299.9 280.5 281 271.2 234.2 212 201 195 176.2 161 178 425.3 405.2 380.5 319.9 300.5

301

291.2 259.2 237 226 216 198.2 186 162

附录四：题Ⅰ的运算过程

MODEL:

MIN=(1/2*(X23^2+X34^2+X45^2+X56^2+X67^2+X78^2+X89^2+X910^2+X1011^2+

X1112^2+X1213^2+X1314^2+X1415^2+(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 Y64 0.0000000 0.0000000 Y65 123.9969 0.0000000 Y66 0.0000000 5.000061 Y67 0.0000000 16.00000 Y68 0.0000000 9.999408 Y69 0.0000000 0.3985321

Y610 -0.5816328E-02 -0.2243042E-02 Y611 0.0000000 12.99776 Y612 86.00181 0.0000000 Y613 332.9981 0.0000000 Y614 621.0005 0.0000000

Y615 165.0001 0.1525879E-04 Y75 0.0000000 36.00000 Y76 0.0000000 41.00005 Y77 0.0000000 51.99999 Y78 0.0000000 45.89940 Y79 0.0000000 41.39852 Y710 0.0000000 40.99775 Y711 0.0000000 53.99775 Y712 0.0000000 36.99999 Y713 0.0000000 37.99999 Y714 0.0000000 40.99999 Y715 0.0000000 0.0000000

附录五：题Ⅲ的运算过程：