钢管定购和运输最优规划的一个最优化模型

钢管定购和运输最优规划的一个最优化模型

需要铺设1a2以运送天然气的线性管道（如图1所示）和形状管道（如图2所示）。假设能够生产这种管道的钢钢丰本量为a1、a2、…或者s7。如果一家工厂能够承受如图所示的大规模生产，至少需要500台设备（由于方便计算，1km管道被称为1km管道）。基本问题是，根据每个工厂在规定的截止日期内最大生产能力的确定，以及铁路和公路的铁路货运成本和价格，制定图1和图2中形状管道的固定购买和运输计划（包含总成本）。分析哪道钢的销售价格的变化对图1中无论钢的产量和总成本的影响最大。哪道钢的产量上限和最重要的是购运规划和总成本，并给出相应的数字结果。2线程购买计划和成本模型2.1钢管si向aj转移的距离1.假定从各钢厂Si(i=1,…,7)处所定购的钢管全部运出,并用于管道铺设,且在运输和铺设过程中无损坏.2.假定A1不向钢厂定货.3.从节点Aj(j=2,…,14)出发,钢管铺设顺序是逐步向Aj+1或Aj-1方向铺,且铺第K个千米管道所需钢管运费为0.1K万元.A15只能往A14方向铺.注通过对比所给的钢管的价格及运费情况,因为钢管价格比运费高很多,所以可以认为从Si处定购的钢管将全部运输出去进行管道铺设,不会出现在Si处定购的数量大于从Si处运输出去的量.故假定1是合理的.对于假定2,显然从A2往A1铺较符合实际工程,因此认为A1不定货.符号说明xij表示Aj从Si厂定购的数量,其中i=1,2,3,4,5,6,7及j=1,2,…,15;yj(j=1,2,…,15)表示从Aj往Aj+1方向所要运的钢管数;ti(i=1,2,…,15)∈{0,1},ti=0表示不从Si定货,ti=1表示从Si定货;si钢厂Si在指定期限内能生产该钢管的最大数量;pi钢厂出厂销价1单位钢管的价格(万元);li表示从Aj到Aj+1的距离,j=1,2,…,14;ci,j表示把一单位钢管从Si运到Aj所需的最小费用.有关数据情况如下表:2.2模型中ci的计算首先由假定1,钢管定购的总数量为∑i=17∑j=115xij.总费用包括三部分,第一部分为定购费用,第二部分为运输所定购钢管到各节点所花费用,第三部分为各节点到铺设点所需运费之和.经过分析,若使总费用最小,应选择由钢厂运单位钢管到节点所需费用最小的一条运输路线.因此,在建立模型过程中,关键的一步需要找Si(i=1,…,7)到节点Aj(j=1,…,15)运一个单位钢管所需的最小费用ci,j(i=1,…,7;j=1,…15).注意到图1并非十分复杂,因此求ci,j可采用手工计算.以S1为例,首先求最好确定的c1,j.通过观察和必要的计算,可求得c1,7.接着便计算c1,6和c1,8.计算c1,6时,先求出从S1出发单位钢管经过A7而到达A6的最少运费,即c1,7加上从A7到A6的最少运费,再求出从S1出发不经过A7而到达A6的最少运费,比较二者取最小可得c1,6,类似地也可求出c1,8.依次类推,可逐次求出c1,5,c1,4,…,c1,1以及c1,8,c1,9,…,c1,15.为后面建模的需要,本文已算出ci,j(i=1,…,7j=1,…,15),见表1(显然,ci,j对应的线路也是清楚的,这里没有标明,只在后文的有关结论中加以叙述).依据表1,则可建立模型的第二部分费用.另外,根据所给信息及假定1,对Si厂来说,若要向其定购,则定购量至少大于(或等于)500单位,小于(或等于)其生产能力的上限,因此,向Si厂定购量需满足下面0-1规划约束条件:500ti≤∑j=115xij≤siti,i=1,⋯,5;ti∈{0,1}.ti取1表示向Si厂定购,ti取0表示不向Si厂定购.基于上述分析,下面进行建模.2.3构造钢管的购买计划由2.2的分析及2.1有关假定,建立如下模型:目标min∑j=115∑i=17pixij(定货费)+∑j=115∑i=17cijxij(从⌶厂到节点的运费)+∑j=114(yj(yj+1)2+(lj−yj)⋅(lj−yj+1)2)×0.1(铺轨时,从节点运到铺设点所需的运费)s.t.500ti≤∑j=115xij≤sititi∈{0,1},i=1,2,⋯,7.(定货的上、下界),∑i=17xij=yj+(lj−1−yj−1),j=2,⋯,14(运到节点的钢管数和从该节点运出去铺设的钢管数相等)∑i=17xi15=l14−y14,0≤yj≤lj,j=2,⋯,14,xij≥0,i=1,2,⋯,7;j=1,⋯,15y1=0问题1的结论为使总费用最小,订购计划及运输路线如下:分别向S1,S2,…,S7订购800,800,1000,0,1366,1205,0单位钢管.总费用为:1.2786×106万元.A1不向任何厂订购.A2向S2订购179单位钢管,路线为:s2→h→d→c→a→A2.A3向S2订购189单位钢管,路线为:s2→h→d→c→b→A3;A3向S5定购319单位钢管,路线为:S5→l→k→j→i→h→d→c→b→A3.A4向S2订购132单位钢管,路线为:S2→h→S1→g→f→e→A5→A4;A4向S3订购336单位钢管,路线为:S3→i→h→S1→g→f→e→A5→A4.A5向S1订购335单位钢管,路线为:S1→g→f→e→A5;A5向S5订购281单位钢管,路线为:S5→l→k→j→i→h→S1→g→f→e→A5.A6向S1订购200单位钢管,路线为:S1→g→f→A6;A7向S1订购265单位钢管,路线为:S1→A7.A8向S2订购300单位钢管,路线为:S2→h→A8.A9向S3订购664位钢管,路线为:S3→i→A9.A10向S5订购351单位钢管,路线为:S5→l→k→j→A10.A11向S5订购415单位钢管,路线为:S5→l→A11.A12向S6订购86单位钢管,路线为:S6→p→o→m→n→A12.A13向S6订购333单位钢管,路线为:S6→p→o→A13.A14向S6订购621单位钢管,路线为:S6→A14.A15向S6订购165单位钢管,路线为:S6→p→q→A15.问题2的分析当钢管的销价变化时,通过对其相应的最小总费用及购运计划的分析.钢厂S5的销价变化对其相应的最小费用及购运计划的影响最大.事实上,仅S1,S2,S3中的一个销价在已知的销价si,i=1,2,3周围的一定范围内变化时,譬如在[si-1,si+1],i=1,2,3范围内变化时,他们对购运计划几乎不产生影响.钢厂S2产量上限的变化对其相应的最小费用及购运计划的影响最大.费用变化见表3.1,3.2.3该管道的购买计划和成本模型3.1各节点一个米米管道的铺设1.同2.1节的第一个假定.2.假定A1不向钢厂定货.3.假设从各节点出发铺设管道的方向是逐步远离该节点,且铺第K个千米管道所需钢管运费为0.1K万元.3.248,10,12,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,设y16表示从A16往A9方向所需要的钢管数;y17表示从A17往A11方向所需要的钢管数;y18表示从A18往A17方向所需要的钢管数;y19表示从A19往A17方向所需要的钢管数;y20表示从A20往A19方向所需要的钢管数;y21表示从A21往A20方向所需要的钢管数.l16=42,l17=10,l18=130,l19=190,l20=260,l21=100,其它符号与2.1中意义一样(注意下标的变动).与2.2的分析类似,可建立如下目标函数:min∑j=121∑i=17pixij(定货费)+∑j=121∑i=17cijxij(从⌶厂到节点的运费)+∑j=1,j≠1521(yj(yj+1)2+(lj−yj)⋅(lj−yj+1)2)×0.1(铺轨时,从节点运到铺设点所需的运费)s.t.500ti≤∑j=121xij≤sititi∈{0,1},i=1,2,⋯,7;j=1,⋯21,∑i=17xij=yj+(lj−1−yj−1)j=2,⋯,8,10,12,13,14.∑i=17xi15=l14−y14,∑i=17xi9=y9+(l8−y8)+(l16−y16),∑i=17xi11=y11+(l10−y10)+(l17−y17),∑i=17xi16=y16,∑i=17xi7=y17+(l18−y18)+(l19−y19),∑i=17xi8=y18,∑i=17xi19=y19+(l20−y20),∑i=17xi20=y20+(l21−y21),∑i=17xi21=y21,1≤yj≤ljj=1,⋯,21且j≠15,xij≥0i=1,2,⋯,7;j=1,⋯,21,y1=0.仍用2.3节中的解法,我们可得问题(3)的结论.问题3结论为使总费用最小,订购计划及运输路线如下:分别向S1,S2,…,S7订购800,800,1000,0,1303,2000,0单位钢管.总费用为:1.4143×106万元.A1不向任何厂订购.A2向S2订购104单位钢管,路线为:S2→h→d→c→a→A2.A3向S2定购209单位钢管,路线为:S2→h→d→c→b→A3;A3向S5订货92单位钢管,路线为:S5→l→k→j→i→h→d→c→b→A3.A4向S1订购200单位钢管,路线为:S1→g→f→e→A5→A4;A4向S5定购550单位钢管,路线为:S5→l→k→j→i→h→S1→g→f→e→A5→A4.A5向S2订购312单位钢管,路线为:S2→h→S1→g→f→e→A5;A5向S3定购294单位钢管,路线为:S3→i→h→S1→g→f→e→S5.A6向S1订购399单位钢管,路线为:S1→g→f→e→A6.A7向S1订购201单位钢管,路线为:S1→A7.A8向S2订购175单位钢管,路线为:S2→h→A8.A9向S3订购664单位钢管,路线为:S3→i→A9.A10向S5订购96单位钢管,路线为:S5→l→k→j→A10;A10向S6订购225单位钢管,路线为:S6→A20→A18→k→j→A10.A11向S5订购410单位钢管,路线为:S5→l→A11.A12向S6订购110单位钢管,路线为:S6→A20→A19→A12或S6→A20→A18→A19→A12.A13向S6订购394单位钢管,路线为:S6