1、第31卷第1期2001年1月数学的实践与认识MA THEMA T ICS I N PRACT ICE AND THEORYVol131No11Jan.2001管道订购和运输马欣,郭世强,王佳指导老师:教师组(大连海事大学,大连116026)编者按:本文只是B题的第一问的求解部分,该求解过程对所建立的非线性优化模型,采用两阶段法求解,首先通过对铺设路线上运输费用的分析,为非线性规划的线性化提供了依据,从而直接采用线性规划方法求解.然后采用拆分法,将原管道运输网络图分成二部分,利用类似于原网络的方法,逐步对问题调优.最后,以所得可行解为初始点,采用模拟退火算法,求得最后的近似最优解.摘要:在对图形
2、一分析的基础之上,首先建立了问题一的非线性规划的模型.然后采用了两种方法分别对问题一求解.1问题的重述(略)2基本假设(略)3符号约定Pi:各钢厂的钢管的出厂销价(万元?单位).Ci,j:单位钢管从钢厂Si购出并经单位运费最小路运至Aj时单位钢管的所需费用包括销价和运费两部分.Xi,j:从Si到Aj运输钢管的总数.lj:从Aj点到Aj+1点所需要铺设钢管的数量.Caj:表示从Aj到Aj+1段上钢管的运输费用.D:钢管总的需求量.si:各钢厂Si的最大供给力.aj:运到Aj的钢管总数.aj,1:为从Aj向左铺设的里程数.aj,2:为从Aj向右铺设的里程数.ti:钢厂Si的实际供给量.Cost:总
3、费用函数.4问题的分析和模型的建立(1)分析:依照题目中所给出的数据,我们可以计算出由Si经单位运费最小路运至Aj点时单位钢管的费用(即运费与出厂销价之和Ci,j).1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http:/获取更多数学建模相关资料关注【公众号：数模加油站】国赛交流分享群：544457657获取更多数学建模相关资料关注【公众号：数模加油站】国赛交流分享群：544457657(2)模型的建立:在运送钢管时,必须将钢管先运到各Aj点,再由各Aj点转运到铺设地点,因此我
4、们考虑下将整个购运过程分为两个阶段:?.将钢管从各钢厂Si(i=1,7)运到Aj(j=1,15)点.从Ai分别向左右两端运输并铺设.在?阶段中,费用为Cost1=7i=115j=1Ci,jXi,j在 阶段中,费用用为Cost2=jCaj其中任意施工段Lj内所花费的运输费用为Caj=0.1(aj,2-1)aj,22+0.1(aj+1,1-1)aj+1,12再根据题目所要求的各种约束条件,我们可以建立模型如下:m inCost=cost1+cost2=7i=115j=1Ci,jXi,j+15j=1(aj,1-1)aj,12+(aj,2-1)aj,22011s.taj,2+aj+1,1=lj(j=1
5、,14)50015j=1Xi,jSior15j=1Xi,j=07i=1Xi,j=aj,2+aj+1,1(j=1,14)Xi,j0,aj,10,aj,205模型的求解由于目标函数的图像是一个多维的抛物面,它的约束条件所对应的区域不是凸集,因而模型给出的是在非连续可行域上的二次规划问题.这样就很难找到一个统一的方法来求解.我 们 注 意 到:在A2和A15处,有a2,1=104,a15,2=0;在A1A2 A15上 有aj,2+aj+1,1=lj,并且Caj=0.05(aj,2)2+(aj+1,1)2-aj,2-aj+1,1=0.05(aj,2)2+(aj+1,1)2-(aj,2+aj+1,1)=
6、0.05(aj,2)2+(aj+1,1)2-lj0.05(2aj,2aj+1,1-lj)及Caj=0.1(aj,2-1)aj,2+(lj-aj,2-1)(lj-aj,2)?2=0.052(aj,2)2+l2j-2ljaj,2-lj=0.052(aj,2-lj?2)2+l2j?2-lj所以,当aj,2=aj+1,1成立时,在这段路上费用最少;当aj,2=0时,这段路上的费用最大.综合以上,我们可以得到Caj的最值为:m inCaj=0.1(lj)2-2lj?4,从而得m inCaj=610641325,maxCaj=0.1(lj)2-lj?2,从而得maxCaj=12238712,于是,maxC
7、aj-m inCaj=613221875.我们先把?,两个阶段分开分析,因为公路和铁路的路线较长并且单价已经加入到08数学的实践与认识31卷 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http:/获取更多数学建模相关资料关注【公众号：数模加油站】国赛交流分享群：544457657获取更多数学建模相关资料关注【公众号：数模加油站】国赛交流分享群：544457657Si到Aj的费用上,这一段的费用占总费用的大部分,所以考虑先将Aj各点的钢管到达量固定.由上面的推断,我们知道,在不
8、考虑其他条件时,当aj,2=aj+1,1=lj?2时费用最低.所以,我们先固定aj=(lj-1+lj)?2.这时模型变成:m inCost1=7i=115j=1Ci,jXi,js1t7i=1Xi,j=aj(j=1,14)50015j=1Xi,jSior15j=1Xi,j=0Xi,j0(i=1,7,j=1,14)如果让所有工厂全部生产500单位以上时,即忽略掉约束的后一半,那么原问题就被简化成为一个线性规划问题.通过计算,得到总费用最优时的供给情况如下表所示:S1S2S3S4S5S6S7供给量8008001000500831740500此时目标函数的值为:1242957.我们发现,工厂S4和S7
9、都只生产500个单位,那么有可能是在让S4和S7不生产时费用更低.在前面的线性规划中可以假设钢厂S4不生产,就得到结果如下表所示:S1S2S3S4S5S6S7供给量800800100001331740500此时目标函数的值为:1237047.同样,当S7不生产时,得到结果如下表所示:S1S2S3S4S5S6S7供给量800800100050083112400此时目标函数的值为:1241672.当S4和S7都不生产时,得到结果如下表所示:S1S2S3S4S5S6S7供给量8008001000094116300此时目标函数的值为:1236122.可以看到,当S4和S7都不生产时,目标函数更优化一些
10、.因此,当我们固定aj的值时,可以得到沿管道的运输费用为61064,进而,得到总费用为:1236122+61064=1297186.这是一个满足模型约束的可行解.为了进一步优化,我们尝试将这个图形进行拆分.观察下表:A10A11A12A13A14A15S5212188206221.2228242S6212201195176.2161178通过对图的右半部分作简单的计算,可以发现:由S6单独供应A14A15时的费用要比由S7单独供应或S7,S6共同供应时的费用少,S6181期马欣等:管道订购和运输 1994-2008 China Academic Journal Electronic Publi
11、shing House.All rights reserved.http:/获取更多数学建模相关资料关注【公众号：数模加油站】国赛交流分享群：544457657获取更多数学建模相关资料关注【公众号：数模加油站】国赛交流分享群：544457657离A11,A12,A13,A14比S7更近,但这几段管道的总需求不能使S6的供给达到饱和,所以由S6而不是S7来供应A11,A12A13,A14,同理由于S4距A10,A11,A12比S5远,所以由S5而不是S4来供应A10,A11,A12.所以A11,A12由S5和S6共同供应.根据上述模型,我们可以求出各段所用的费用,相加便得到右半部分费用的最小值为
12、14j=10Caj=306972.6而在前面求得的线性规划问题的最优解中,S1,S2,S3的供给量已经达到饱和,这说明左半部分的需求量比供给量大,需要由右半部分来补充,补充量为445单位.通过观察可以发现在右半部分的工厂中,S5距离这些点是最近的,而且在供给左半部分不足部分后其供给量也不会达到饱和.这样图的左半部分A1到A10加上工厂S1,S2,S3,S4,S5就形成了一个类似原大图模型的小模型,但已经不存在不生产的工厂,因为右半部分已经可以求到最优,再对左边继续进行优化.类似前述对大图进行优化的方法,我们固定aj,依旧求解线性规划,得出到各Aj点的运输费用:934628,再加上沿管道的运输费
13、用46725,得到总费用1288326.至此我们就得到了一个更优化的解,可以相信已经非常接近最优值,以这个值为初值,继续进行优化,我们采取了模拟退火算法来优化,得到目标函数值为:Cost=1278198.参考文献:1钱颂迪,薛华成.运筹学.清华大学出版社,北京,1990.2盛昭瀚,曹忻.最优化方法基本教程.东南大学出版社,江苏,1992.3陈宝林.最优化理论和算法.清华大学出版社,北京,1989.4杨冰.使用最优化方法及计算机程序.哈尔滨船舶工程学院出版社,哈尔滨,19941M odel for Ordering and Transportation of PipelineMA Xin,GUO
14、 Shi2qiang,WAN G Jia(DalianM ariti me U niversity,Dalian116026)Abstract:By analysing of the graph,we gave a nonlinear opti mum modelof question one,andwe solve the question one in two ways.28数学的实践与认识31卷 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http:/获取更多数学建模相关资料关注【公众号：数模加油站】国赛交流分享群：544457657获取更多数学建模相关资料关注【公众号：数模加油站】国赛交流分享群：544457657
