运筹学课件 第三节运输问题的进一步讨论

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,运筹学教程,第三节 运输问题的进一步讨论,一、产销不平衡的运输问题,供,大于求,供不应求,增加虚拟销地,增加虚拟产地,产销平衡的运输问题,对应的运价,？,转化,各地之间的运价在原问题运价表基础上进行扩展：,增加虚拟销地，,就地贮存的物品的不经过运输，运价等于零；,增加虚拟产地，,各个销地所欠缺的物品，其运价等于零；,考虑转运，,从一地运往自身的单位运价记为零或为负；不存在运输线路的则记为,M,（,一个足够大的正数）；,供应大于需求：数学模型,增加一个假想的目的地,B,1,B,2,B,n,B,n+1(,贮存,),产量,A,1,x,11,x,12,x,1n,X,1,n+1,a,1,A,2,x,21,x,22,x,2n,X,2,n+1,a,2,:,:,:,:,:,:,A,m,x,m1,x,m2,X,mn,X,m,n+1,a,m,销量,b,1,b,2,b,n,产地,销地,c,11,c,1n,c,2n,0,0,0,c,mn,c,m2,c,m1,c,22,c,21,c,12,二、有转运的运输问题,特点是所调运的物资不是由产地直接运送到销地，而是经过若干中转站送达。,求解思路：转化成一个等价的产销平衡运输问题，再用表上作业法求出最优调运方案。,第一步，将产地、转运点、销地重新编排，转运点既作为产地又作为销地；,第二步，各地之间的运价在原问题运价表基础上进行扩展：从一地运往自身的单位运价记为零或为负，不存在运输线路的则记为,M,（,一个足够大的正数）；,第三步，由于经过转运点的物资量既是该点作为销地的需求量，又是该点作为产地时的供应量，但事先又无法获取该数量的确切值，因此通常将调运总量作为该数值的上界。,对于产地和销地也作类似的处理。,例,1:,某公司有,A,1,、,A,2,两个分厂生产某种产品，分别供应,B,1,、,B,2,、,B,3,三个地区的销售公司销售。假设两个分厂的产品质量相同，假设有两个中转站,T,1,、,T,2,，,并且物资的运输允许在各产地、各销地及各转运站之间，即可以在,A,1,、,A,2,、,B,1,、,B,2,、,B,3,、,T,1,、,T,2,之间相互转运。有关数据如下表所示，试求总费用为最少的调运方案。,产 地,中转站,销 地,产量,A,1,A,2,T,1,T,2,B,1,B,2,B,3,产地,A,1,1,2,1,3,11,3,7,A,2,1,3,5,1,9,2,9,中转,T,1,2,3,1,2,8,4,T,2,1,5,1,4,5,2,销,地,B,1,3,1,2,4,1,4,B,2,11,9,8,5,1,2,B,3,3,2,4,2,4,2,需求量,4,7,5,产地、销地及中转站的有关数据、运价（元,/kg,）,发送,接受,解：,从表可以看出，从,A,1,到,B,2,直接运费单价为,11,元,/kg,；,但从,A,1,经,A,2,到,B,2,，,运价为,1+9=10,元,/kg,；,而从,A,1,经,T,2,到,B,2,只需,l+5=6,元,/kg,；,若从,A,1,到,A,2,再经,B,1,到,B,2,仅仅需,l+1+1=3,元,/kg,。,可见转运问题比一般运输问题复杂。现在我们把此转运问题化成一般运输问题，要做如下处理：,由于问题中的所有产地、中转站、销地都可以看成产地，也可以看成销地，因此整个问题可以看成一个有,7,个产地有,7,个销地的扩大的运输问题；,对扩大了的运输问题建立运价表，将表中不可能的运输方案用任意大的正数,M,代替；,所有中转站的产量等于销量，也即流入量等于流出量。,每个中转站的转运量不会超过,16 kg,，,可以规定,T,1,，,T,2,的产量和销量均为,16 kg,。,由于实际的转运量：,这里,s,i,表示,i,点的流出量，,d,j,表示,j,点的流入量，对中转点来说，因此,s,i,=,d,j,=16,。,这样可以在每个约束条件中增加一个松弛变量,x,ii,，,x,ii,相当于一个虚构的中转站，其意义就是自己运给自己。,(16-,x,ii,),就是每个中转站的实际转运量，,x,ii,的对应运价,c,ii,=0,；,扩大了的运输问题中原来的产地与销地由于也具有转运作用，所以同样在原来的产量与销量的数字上加上,16 kg,，,即两个分厂的产量改为,23,、,25 kg,，,销量均为,16 kg,；,三个销地,的每天销量改为,20,、,23,、,21 kg,，,产量均为,16 kg,，,同时引进,x,ii,为松弛变量。,于是得到带有中转运输的产销平衡运输表,产 地,中转站,销 地,产量,A,1,A,2,T,1,T,2,B,1,B,2,B,3,产地,A,1,0,1,2,1,3,11,3,23,A,2,1,0,3,5,1,9,2,25,中转,T,1,2,3,0,1,2,8,4,16,T,2,1,5,1,0,4,5,2,16,销,地,B,1,3,1,2,4,0,1,4,16,B,2,11,9,8,5,1,0,2,16,B,3,3,2,4,2,4,2,0,16,需求量,16,16,16,16,20,23,21,128,带有中转站的产销平衡运输表,发送,接受,产 地,中转站,销 地,产量,A,1,A,2,T,1,T,2,B,1,B,2,B,3,产地,A,1,1,2,1,3,11,3,7,A,2,1,3,5,1,9,2,9,中转,T,1,2,3,1,2,8,4,T,2,1,5,1,4,5,2,销,地,B,1,3,1,2,4,1,4,B,2,11,9,8,5,1,2,B,3,3,2,4,2,4,2,需求量,4,7,5,使用,生产,B1,B2,B3,生产量,A1,2,4,3,6a,1,11,A2,1,5,6,a,2,=7,A3,3,2,4,a,3,4,使用量,10,4,6,例,2,：产地,A1,至少发出,6,个单位物品，最多能生产,11,单位物品；,A2,必须发出,7,个单位物品；,A3,至少发出,4,个单位物品；确定最优方案。,使用,生产,B1,B2,B3,B4,（,虚拟）,生产量,A1,2,4,3,M,6,（必须发出的）,A1,2,4,3,0,5,A2,1,5,6,M,7,（必须发出的）,A3,3,2,4,M,4,（必须发出的）,A3,3,2,4,0,3,使用量,10,4,6,5,解：当,A1,的产量,a,1,=6,（,min),，,A1,A2,的产量之和,=13,，总需求量为,20,，所以在产销平衡的情况下,A3,的产量最大为,7,；,如果,A1,A3,的产量均取最大,11,，,7,，则总产量大于总需求,20,，此时应增加一个虚销地,B4,需求量为,5,。,例,3,：某公司承担,4,条航线运输任务，已知（,1,）各条航线的起点和终点以及每天的航班数；各个城市之间的航行时间；每次装船、卸船时间均为,1,天；问题：公司至少需要配备多少条船才能满足需要？,航线,起点城市,终点城市,每天航班数量,1,2,3,4,E,B,A,D,D,C,F,B,3,2,1,1,从 至,A,B,C,D,E,F,A,B,C,D,E,F,0,1,2,14,7,7,1,0,3,13,8,8,2,3,0,15,5,5,14,13,15,0,17,20,7,8,5,17,0,3,7,8,5,20,3,0,航线,装船（天）,卸船（天）,航行（天）,小记（天）,航班数量,所需船数,1,2,3,4,1,1,1,1,1,1,1,1,17,3,7,13,19,5,9,15,3,2,1,1,57,10,9,15,所需要船只共,91,条船。,城市,A,B,C,D,E,F,每天到达,每天需要,余缺数,0,1,-1,1,2,-1,2,0,2,3,1,2,0,3,-3,1,0,1,各个港口之间调度。每天到达某一个港口的船只数量与它所需要发出船只数量不相等而产生的。将多余船只调往需要的港口，应采用合理的运输方案，单位运价为一对港口城市之间的航行时间。,至,由,A,B,E,多余船只,C,2,3,5,2,D,14,13,17,2,F,7,8,3,1,缺少船只,1,1,3,5,用,表上作业方法求解运输问题，得到最优解,按照这两个方案调运船只，其目标函数等于,40,。，说明各个港口之间调度所需要船只至少,40,艘。,所以，总的需求：,91+40=131,有,m,个产地,A,1,A,2,A,m,和,n,个目的地,B,1,B,2,B,3,B,n,都可以作为中间转运站使用，因此，发送和接受物品的地点有,m+n,个。,a,i,:,第,i,个产地的产量,b,j,:,第,j,个目的地的需求量,x,ij,:,第,i,个产地运到第,j,个目的地数量,C,ij,：第,i,个产地运到第,j,个目的地的单位运价,C,i,：第,i,个,地点转运单位物品的费用,t,i,:,第,i,个地点转运物品的数量,产地与目的地统一编号，产地在前，目的地在后,4,个约束条件两边均加上,Q;,令,x,ii,=Q-,t,i,x,jj,=Q-,t,j,x,ij,0(i,j=1,2,m+n,),说明,:,当,i=j,时,所有的,c,ij,=-,c,i,产地,销地,发送量,1 .m,m+1.m+n,产地,1,.,m,x,11.,x,1m,.,X,m1.,x,mm,X,1,m+1.,x,1,m+n,.,X,m,m+1,x,m,m+n,Q+a1,Q+am,目的地,m+1,.,m+n,x,m+1,1,x,m+1,m,.,X,m+n,1,x,m+n,m,X,m+1,m+1.,x,m+1,m+n,.,X,m+n,m+1.,x,m+n,m+n,Q,Q,接受量,Q Q,Q+b,m+1,.Q+b,m+n,发送,接受,接受,发送,产地,销地,发送量,1.m,m+1.m+n,产地,1,.,m,-c,1.,c,1m,.,c,m1.,-c,m,c,1,m+1.,c,1,m+n,.,c,m,m+1,c,m,m+n,Q+a1,Q+am,目的地,m+1,.,m+n,c,m+1,1,c,m+1,m,.,c,m+n,1,c,m+n,m,-c,m+1.,c,m+1,m+n,.,c,m+n,m+1.-,c,m+n,Q,Q,接受量,Q Q,Q+b,m+1,.Q+b,m+n,1,2,3,4,5,10,40,20,30,5,2,2,5,6,4,3,5,4,3,1,5,3,运输系统，,2,个产地,1,，,2,；一个中间转运站,3,；,2,个目的地,4,，,5,；,产地的产量,a,1,=10,a,2,=40,a,3,=a,4,=a,5,=0;,目的地接受量,b,1,=b,2,=b,3,=0,b,4,=30,b,5,=20,例,4,：,接受,发送,产地,转运,销地,发送量,1,2,3,4,5,产地,1,-4,5,3,2,M,60,2,5,-1,2,M,4,90,转运,3,3,2,-3,5,5,50,销地,4,2,M,5,-3,6,50,5,M,4,5,6,-5,50,接受量,50,50,50,80,70,接受,发送,产地,转运,销地,发送量,1,2,3,4,5,产地,1,50,10,60,2,50,20,20,90,转运,3,50,0,50,销地,4,50,50,5,50,50,接受量,50,50,50,80,70,用,最小元素法求解初始运输方案,接受,发送,产地,转运,销地,发送量,1,2,3,4,5,产地,1,50,10,60,2,50,20,20,90,转运,3,30,20,50,销地,4,50,50,5,50,50,接受量,50,50,50,80,70,经过,2,次迭代得到最优解，其运输方案：由,1,地运输,10,单位物品到,4,地；由,2,地运输,20,单位物品到,5,地；由,2,地运输,20,单位物品到,3,地，再由,3,地转到,4,地；,Z=C14x14+c25x25+c23x23+c3x34+c34x34=2X10+4X20+2X20+3X20+5X20=300,小结,:,产销不平衡的运输问题和有转运的运输问题。,