钢管运输的最短运行

钢管运输的最短运行

1问题的描述和分析省略2钢管生成分段放置的管道侧有一条路，可以运送必要的管道。②钢管在运输中由铁路运转为公路运时不计换车费用;③所需钢管均由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不提供钢管={1‚钢厂Si提供钢管0‚钢厂Si不提供钢管;W:所求钢管订购、运输的总费用(单位:万元);3问题的数学模型我们的目标函数是总费用W,它包含三项:钢管出厂总价Q,运输费P,及铺设费T.即W=Q+Ρ+Τ其中Q=7∑i=115∑j=1pj⋅xij‚Ρ=7∑i=115∑j=1cij⋅xij‚铺设费T可以如下来确定:Aj开始从左右两个方向铺设,yj与zj单位长钢管的费用为d⋅1+d⋅2+⋯+d⋅yj=d(1+yj)yj2与d(1+zj)zj2故Τ=d15∑j=1((1+yj)yj2+(1+zj)zj2)约束条件为:①生产能力的限制:500⋅ti≤15∑j=1xij≤si⋅ti(i=1,⋯‚7)(ti=0或1)②运到Aj的钢管用完:7∑i=1xij=yj+zj(j=1,⋯,15)③Aj与Aj-1之间的钢管:zj+yj+1=bj(j=1,…,14)④变量非负性限制:xij≥0,yj≥0,zj≥0,(i=1,…,7,j=1,…,15).综合以上讨论,得出问题Ⅰ的数学模型如下:Obj1:minW=7∑i=115∑j=1pi⋅xij+7∑i=115∑j=1cij⋅xij+d15∑j=1[(1+yj)yj2+(1+zj)zj2]s.t.500⋅ti≤15∑j=1xij≤si⋅ti(i=1,⋯,7)7∑i=1xij=yj+zj(j=1,⋯,15)zj+yj+1=bj(j=1,⋯,14)y1=0‚z15=0xij≥0,yj≥0,zj≥0,(i=1,⋯‚7‚j=1,⋯‚15)ti=0或1(i=1,⋯‚7)4模型解的估计为了求解模型,必须求出系数(cij)7×15,其中每一cij表示Si到Aj的最小费用,因而,求解cij实际上是一个求最短路的问题.总路段由铁路和公路组成,由于单位运费的差别,分别计算就有一定难度,因此考虑将单位运费乘以路程来作为“距离”,这样将两者统一起来,利用最短路的算法,可得到从Si到Aj的最小运费.具体实现算法如下:①将图中39个点构成一个39×39的权矩阵A39×39,其中aij表示从Ai到Aj的最短路程,若Ai,Aj不能直接相连,用aij=∞表示.铁路自身构成A139×39,公路自身构成一个A239×39,分别对A1和A2运用弗洛依德算法,得出局部最短路程矩阵和最短路径矩阵path1,paht2.②对公路,将0.1×A2记为公路局部最短“距离”(运费)矩阵A1′,对铁路,用铁路的费用e进行转换,得局部最短“距离”(运费)矩阵A2′.令A=min(A1′,A2′),min表示A1′与A2′中对应元素较小者.③对得到的A,再使用一次弗洛依德算法,得到全局的最短“距离”,实际上,就是每两点间最小运费矩阵,从中抽取出Si到Aj之间的子矩阵C′.④为了便于以后计算,将Si的单价pi加到C′中Si对应的列上,得最小费用矩阵C(略).下面先通过分析,对模型解进行估计.首先,由题图可估计,最右边的钢厂,如S6、S7一定不会运往A1～A3等较左边的点.其次,由最小费用矩阵C来决定订购的优先级,Aj中费用最小的权所对应的Si即为最优,可分析得:对A1～A8:S1最优,S2次优,S3再次;对A9:S3最优,S1次优;对A10～A11:S5最优,S6次优,S4再次;对A12～A14:S6最优,S7次优;对A15:S7最优.另外,由于钢厂一旦开工就必须生产500单位,而A15至多需要铺500单位,所以可能不从S7购运.S4对应的权基本为每一行中最大成本,所以为最末考虑因素,所以可能不运出.再考虑生产上限因素,由于S5～S7上限很大,所以A10～A15由S5～S7应能完全供给,并达到目标值最优.而S1上限只有800单位,所以先满足A1～A8中优先级较高的,接下面方法排序:令sub(Si→Aj,Si′→Aj′)表示从Si到Aj所需单位成本与Si′到Aj′所需的成本之差.若差值越大,表明越应该由两者较小的来提供Aj的钢管,如sub(S1→A5,S2→A5)=68单位,而sub(S1→A7,S2→A7)=78单位,表示S1应优先满足A7.∴可得优先级为A7>A6>A5=A4>A8>A3>A1.再由Si的产量上限以及Aj两边要铺设的钢管数,得到结论:S1,S2,S3必须满荷运出,即S1=800单位,S2=800单位,S3=1000单位,才能使目标值较优,且由要铺的所有钢管数,可大致推出:S1→A5,A6,A7;S2→A1,A2,A3;S3→A4,A7,A8,A9;S5→A10,A11;S6→A12,A13,A14;S7=0;S4=0.然后,再把S1,S2,S3可运到的铺设点范围放宽,观察(cij)矩阵,其中该矩阵右上角和左下角的cij比较大,故可考虑把其对应的xij取为0,则只需考虑(xij)矩阵的左上角、右下角对应的3×8矩阵求解,运用数学软件Lingo5.0,编程求出:W*1=1.282142×106(万元).5s1对总费用的影响1)确定哪个钢厂的销价的变化对购运计划和总费用的影响最大我们假设该钢厂的销价变化在±10%pi万元以内,这是较为合理的.将目标函数的W表示为pi的函数,W=f(p1,p2,⋯‚p7),ΔW=∂fΔp1⋅Δp1+∂fΔp2Δp2+⋯+∂f∂p7Δp7.因此在销价的变化量相同时,∂f∂pi越大,则pi的变化对w的变化影响越大.由模型Obj1计算得到的数据可以知道∂f∂p6=2000单位是最大的,所以S6的销价变化对购运计算和总费用的影响最大,我们可以通过简单的分析来证明:由于S6提供的数量最大,销价只要很小变化的,就会引起总费用的很大变化,同时,当价格越来越高,由于p6和15∑j=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)6增加约束条件若要铺设的道路不是一条钱,而是一个树形图,则有以下两个问题.首先,模型一中给出的算法可以进行扩展,对于网络中不同性质的路有n种,设n个与原矩阵同阶的局部距离矩阵,局部最优后,再统一求解.其次,由于树形图的出现,则某些管道处会出现多支路.则模型一中模型的yj(左铺),zj(右铺)不再适用,此时可考虑多增加一些支路变量,如y1j,y2j,…,z1j,z2j,…之类,增加约束条件y1j+y2j+…+z1j+z2j+…=xij,在目标函数中增加相应的铺设费,具体做法可由下面对图二的模型获知,问题Ⅲ建模如下(mj是运到Aj的钢管向第三支路铺设的数目):Οbj2:minW=7∑i=121∑j=1pixij+7∑i=121∑j=1cijxij+d[15∑i=2yi(yi+1)2+14∑i=1zi(zi+1)2+m9(m9+1)2+m11(m11+1)2+m17(m17+1)2]s.t.500⋅ti≤21∑j=1xij≤si⋅ti(i=1,⋯,7)7∑i=1xij=yj+zj(j=1,⋯,21且j≠9‚11‚