订购和运输钢管的最优方案.pdf

第31卷第1期2001年1月数学的实践与认识MA THEMA T ICS I N PRACT ICE AND THEORYVol131No11Jan.2001distance network to a supply2demand transportation price table.Based on this,we constructedthree models:the linear2cost2network2flow model,the developed linear2cost2network2flowmodel and the non2linear2cost2network2flow model.By generlizing the traditional m ini mum2cost2maxi mum2flow algorithm,we solved the non2linear2cost2network2flow model.W e alsogave the truth proving and the complexity2analysis to our algorithm.订 购 和 运 输 钢 管 的 最 优 方 案陆维新,林皓,陈晓东指导老师:周杰(四川大学,成都610064)编者按:该文建立了用于天燃气管道铺设的钢管订购和运输总费用最省的二次规划模型.总费用作为目标函数,钢管生产厂的产量限制等作为约束条件.所建模型通过定性分析与使用L ingo软件求解获得了满意的方案,并且计算量大大减少了.整篇文章理由描述充分,层次清楚,洞察力强而篇幅较短.摘要:本文研究铺设天燃气钢管的最优方案问题.我们建立了一个以总费用为目标函数的二次规划模型.1问题的重述与分析(略)2模型的假设与符号说明1)基本假设:要铺设的管道侧有公路,可运送所需钢管;钢管在运输中由铁路运转为公路运时不计换车费用;所需钢管均由Si(i=1,7)钢厂提供;假设运送的钢管路途中没有损耗.2)符号说明(i=1,2,7,j=1,2,15):si:钢厂Si的最大生产能力;pi:钢厂Si的出厂钢管单位价格(单位:万元);d:公路上一单位钢管的每公里运费(d=0.1万元);e:铁路上一单位钢管的运费(分段函数见表1);cij:1单位钢管从钢厂Si运到Aj的最小费用(单位:万元);bj:从Aj到Aj+1之间的距离(单位:千米);xij:钢厂Si运到Aj的钢管数;yj:运到Aj地的钢管向左铺设的数目;zj:运到Aj地的钢管向右铺设的数目;ti:=1,钢厂Si提供钢管0,钢厂Si不提供钢管;W:所求钢管订购、运输的总费用(单位:万元);表1铁路的单位运费r(单位:公里)r300301r350351r400401r450451r500e(单位:万元)2023262932501r600601r700701r800801r900901r1000r100037445055605r-1000100+1+603模型的建立我们的目标函数是总费用W,它包含三项:钢管出厂总价Q,运输费P,及铺设费T.即W=Q+P+T其中Q=7i=115j=1pjxij,P=7i=115j=1cijxij,铺设费T可以如下来确定:Aj开始从左右两个方向铺设,yj与zj单位长钢管的费用为d1+d2+dyj=d(1+yj)yj2与d(1+zj)zj2故T=d15j=1(1+yj)yj2+(1+zj)zj2约束条件为:生产能力的限制:500ti15j=1xijsiti(i=1,7)(ti=0或1)运到Aj的钢管用完:7i=1xij=yj+zj(j=1,15)Aj与Aj-1之间的钢管:zj+yj+1=bj(j=1,14)变量非负性限制:xij0,yj0,zj0,(i=1,7,j=1,15).综合以上讨论,得出问题?的数学模型如下:Obj1:m inW=7i=115j=1pixij+7i=115j=1cijxij+d15j=1(1+yj)yj2+(1+zj)zj2s.t.500ti15j=1xijsiti(i=1,7)7i=1xij=yj+zj(j=1,15)zj+yj+1=bj(j=1,14)y1=0,z15=0 xij0,yj0,zj0,(i=1,7,j=1,15)ti=0或1(i=1,7)4对模型Obj1的求解:为了求解模型,必须求出系数(cij)715,其中每一cij表示Si到Aj的最小费用,因而,求571期陆维新等:订购和运输钢管的最优方案解cij实际上是一个求最短路的问题.总路段由铁路和公路组成,由于单位运费的差别,分别计算就有一定难度,因此考虑将单位运费乘以路程来作为“距离”,这样将两者统一起来,利用最短路的算法,可得到从Si到Aj的最小运费.具体实现算法如下:将图中39个点构成一个3939的权矩阵A3939,其中aij表示从Ai到Aj的最短路程,若Ai,Aj不能直接相连,用aij=表示.铁路自身构成A13939,公路自身构成一个A23939,分别对A1和A2运用弗洛依德算法,得出局部最短路程矩阵和最短路径矩阵path1,paht2.对公路,将0.1A2记为公路局部最短“距离”(运费)矩阵A1,对铁路,用铁路的费用e进行转换,得局部最短“距离”(运费)矩阵A2.令A=m in(A1,A2),m in表示A1 与A2中对应元素较小者.对得到的A,再使用一次弗洛依德算法,得到全局的最短“距离”,实际上,就是每两点间最小运费矩阵,从中抽取出Si到Aj之间的子矩阵C.为了便于以后计算,将Si的单价pi加到C 中Si对应的列上,得最小费用矩阵C(略).下面先通过分析,对模型解进行估计.首先,由题图可估计,最右边的钢厂,如S6、S7一定不会运往A1A3等较左边的点.其次,由最小费用矩阵C来决定订购的优先级,Aj中费用最小的权所对应的Si即为最优,可分析得:对A1A8:S1最优,S2次优,S3再次;对A9:S3最优,S1次优;对A10A11:S5最优,S6次优,S4再次;对A12A14:S6最优,S7次优;对A15:S7最优.另外,由于钢厂一旦开工就必须生产500单位,而A15至多需要铺500单位,所以可能不从S7购运.S4对应的权基本为每一行中最大成本,所以为最末考虑因素,所以可能不运出.再考虑生产上限因素,由于S5S7上限很大,所以A10A15由S5S7应能完全供给,并达到目标值最优.而S1上限只有800单位,所以先满足A1A8中优先级较高的,接下面方法排序:令sub(SiAj,Si Aj)表示从Si到Aj所需单位成本与Si 到Aj 所需的成本之差.若差值越大,表明越应该由两者较小的来提供Aj的钢管,如sub(S1A5,S2A5)=68单位,而sub(S1A7,S2A7)=78单位,表示S1应优先满足A7.可得优先级为A7A6A5=A4A8A3A1.再由Si的产量上限以及Aj两边要铺设的钢管数,得到结论:S1,S2,S3必须满荷运出,即S1=800单位,S2=800单位,S3=1000单位,才能使目标值较优,且由要铺的所有钢管数,可大致推出:S1A5,A6,A7;S2A1,A2,A3;S3A4,A7,A8,A9;S5A10,A11;S6A12,A13,A14;S7=0;S4=0.然后,再把S1,S2,S3可运到的铺设点范围放宽,观察(cij)矩阵,其中该矩阵右上角和左下角的cij比较大,故可考虑把其对应的xij取为0,则只需考虑(xij)矩阵的左上角、右下角对应的38矩阵求解,运用数学软件L ingo 510,编程求出:W31=11282142106(万元).5对模型Obj1的灵敏度分析1)确定哪个钢厂的销价的变化对购运计划和总费用的影响最大我们假设该钢厂的销价变化在10pi万元以内,这是较为合理的.将目标函数的W表示为pi的函数,W=f(p1,p2,p7),W=5fp1p1+5fp2p2+5f5p7p7.67数学的实践与认识31卷因此在销价的变化量相同时,5f5pi越大,则pi的变化对w的变化影响越大.由模型Obj1计算得到的数据可以知道5f5p6=2000单位是最大的,所以S6的销价变化对购运计算和总费用的影响最大,我们可以通过简单的分析来证明:由于S6提供的数量最大,销价只要很小变化的,就会引起总费用的很大变化,同时,当价格越来越高,由于p6和15j=1x6j互为消长的关系,当S6越来越小,它在总需求中占的份额减少,影响减弱,S6下降的速度也将放慢.除了销价的升高,我们还必须考虑销价的降低,此时应尽量满足提供量最少的点S5,当价格越来越低,由互为消长关系,S5点的提供量将增加,它占总需求的份额增加,影响增强,对于S5上升的速度将放慢.2)确定哪个钢厂的生产上限的变化对物运计划和总费用的影响最大由于S1是A1到A8的最优首选,因此若S1与其它Si同时扩大相同的 S容量,则S1会更优,所以推断S1应为影响最大者.由最小费用矩阵C可以知道,Ai(i=1,8)所需的钢管量最好都能由S1提供,则此时S1达到最大需求量,在模型Obj1的条件下,S1为2536单位,而S1的上限为800单位,考虑到实际钢厂的投入与产出,在很短的时期内生产要达到原来的3倍,不符合实际意义,所以考虑S1在10%范围内变化.同理对于A9点,最优为S3全部提供,即S3应提供634单位,对于A12、A13、A14、A15,由S6全部提供为最优,即S6应提供1205单位,A11、A10由S5全部提供为最优,即S5应提供796单位.利用计算机模拟,得出5个供货钢厂分别扩建1%,2%,4%,6%,8%,10%时的成本的增长率,见表2.可以看出,相同的 S下A1产生的增长率最大,符合上述分析.一旦工厂扩建范围超过最大需求量,则不再会使目标函数优化,则此时增长率为0,即是上图中S5、S6的情况.而对于S1,一旦S1 2536,则其增长率也为0.(S1的数字结果见表2)表2某个Si在变化 S的情况下目标函数减小量及减小的比率SS1S2S3S5S6z(万元)zz(%)z(万元)zz(%)Z(万元)zz(%)z(万元)zz(%)z(万元)zz(%)1%8720.0683280.0253100.02400002%17440.1366560.0516200.04800004%34880.27213120.10212400.09600006%52320.40819680.15318600.14500008%69760.54426240.20424800.193000010%87200.68532800.25631000.24200006问题 的分析若要铺设的道路不是一条钱,而是一个树形图,则有以下两个问题.首先,模型一中给出的算法可以进行扩展,对于网络中不同性质的路有n种,设n个与原矩阵同阶的局部距离矩阵,局部最优后,再统一求解.其次,由于树形图的出现,则某些管道处会出现多支路.则模型一中模型的yj(左铺),zj771期陆维新等:订购和运输钢管的最优方案(右铺)不再适用,此时可考虑多增加一些支路变量,如y1j,y2j,z1j,z2j,之类,增加约束条件y1j+y2j+z1j+z2j+=xij,在目标函数中增加相应的铺设费,具体做法可由下面对图二的模型获知,问题 建模如下(mj是运到Aj的钢管向第三支路铺设的数目):Obj2:m inW=7i=121j=1pixij+7i=121j=1cijxij+d15i=2yi(yi+1)2+14i=1zi(zi+1)2+m9(m9+1)2+m11(m11+1)2+m17(m17+1)2s.t.500ti21j=1xijsiti(i=1,7)7i=1xij=yj+zj(j=1,21且j9,11,17)7i=1xij=yj+zj+mj(j=9,11,17)zj+yj+1=bj(j=1,2,14)m9+y16=42,z19+y20=260z20+y21=100,m11+m17=10y17+y18=130,z17+y19=190 xij,yj,zj,mj0(i=1,7,j=1,21),ti=0或1(i=1,7)运用数学软件L ingo5.0编程求出:W32=1.40633106(万元)参考文献:1姜启源.数学模型.高等教育出版社,北京,1996.2严蔚敏,吴伟民.数据结构.清华大学出版社,北京,1992.3叶其孝.大学生数学建模竞赛辅导教材.湖南教育出版社,长沙,1993.Opti mal Scheme for Purchasing andTransporting Steel TubesLU W ei2xin,L I N Hao,CHEN Xiao2dong(Sichuan U niversity,Chengdu610064)Abstract:The opti mal scheme in the construction of the nature gas pipeline has been studiedin this article.W e have set up a quadratic programm ingmodel in which the objective function isthe total expense of the construction.87数学的实践与认识31卷