产销不平衡的运输问题及其求解方法.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第,3,节 产销不平衡的运输问题及其求解方法第,4,节 应用举例,运筹学,（第二版）,刁在筠等 编,第,3,章 运输问题,（,继续,）,高等教育出版社,第,3,节 产销不平衡的运输问题及其求解方法,前面所讲表上作业法，都是以产销平衡为前提条件的；但是实际问题中产销往往是不平衡的。就需要把产销不平衡的问题化成产销平衡的问题。,当产大于销,运输问题的数学模型可写成,目标函数：,满足：,由于总的产量大于销量，就要考虑多余的物资在哪一个产地就地储存的问题。设,x,i,n+1,是产地,A,i,的储存量，于是有：,令：当,i=1,，,m,，,j=1,，,n,时,当,i=1,，,m,，,j=n+1,时,将其分别代入，得到,满足：,由于这个模型中,所以这是一个产销平衡的运输问题。,若当产大于销时，,只要增加一个假想的销地,j=n+1(,实际上是储存,),，该销地总需要量为,而在单位运价表中从各产地到假想销地的单位运价为，,就转化成一个产销平衡的运输问题,当销大于产时，可以在产销平衡表中增加一个假想的产地,i=m+1,，,该地产量为,在单位运价表上令从该假想产地到各销地的运价，,同样可以转化为一个产销平衡的运输问题,.,。,例,2,设有三个化肥厂,(,A,，,B,，,C),供应四个地区,(,，,，,，,),的农用化肥。假定等量的化肥在这些地区使用效果相同。各化肥厂年产量，各地区年需要量及从各化肥厂到各地区运送单位化肥的运价如表,3-25,所示。试求出总的运费最节省的化肥调拨方案。表,3-25,解,这是一个产销不平衡的运输问题，总产量为,160,万吨，四个地区的最低需求为,110,万吨，最高需求为无限。根据现有产量，第,个地区每年最多能分配到,60,万吨，这样最高需求为,210,万吨，大于产量。为了求得平衡，在产销平衡表中增加一个假想的化肥厂,D,，,其年产量为,50,万吨。由于各地区的需要量包含两部分，如地区,，其中,30,万吨是最低需求，故不能由假想化肥厂,D,供给，令相应运价为,M(,任意大正数),，而另一部分,20,万吨满足或不满足均可以，因此可以由假想化肥厂,D,供给，按前面讲的，令相应运价为,0,。对凡是需求分两种情况的地区，实际上可按照两个地区看待。这样可以写出这个问题的产销平衡表,(,表,3-26),和单位运价表,(,表,3-27),。,产销平衡表,(,表,3-26),单位运价表,(,表,3-27),根据表上作业法计算，可以求得这个问题的最优方案如表,3-28,所示,第,4,节 应 用 举 例,由于在变量个数相等的情况下，表上作业法的计算远比单纯形法简单得多。所以在解决实际问题时，人们常常尽可能把某些线性规划的问题化为运输问题的数学模型。下面介绍几个典型的例子。,例,3,某厂按合同规定须于当年每个季度末分别提供,10,，,15,，,25,，,20,台同一规格的柴油机。已知该厂各季度的生产能力及生产每台柴油机的成本如表,3-29,所示。又如果生产出来的柴油机当季不交货的，每台每积压一个季度需储存、维护等费用,0.15,万元。要求在完成合同的情况下，作出使该厂全年生产,(,包括储存、维护,),费用最小的决策,表,3-29,解,由于每个季度生产出来的柴油机不一定当季交货，所以设,x,ij,为第,i,季度生产的用于第,j,季度交货的柴油机数。,根据合同要求，必须满足,又每季度生产的用于当季和以后各季交货的柴油机数不可能超过该季度的生产能力，故又有：,第,i,季度生产的用于,j,季度交货的每台柴油机的实际成本,c,ij,应该是该季度单位成本加上储存、维护等费用。,c,ij,的具体数值见 表,3-30,设用,a,i,表示该厂第,i,季度的生产能力，,b,j,表示第,i,季度的合同供应量，则问题可写成：,目标函数：,满足,显然，这是一个产大于销的运输问题模型。注意到这个问题中当,i,j,时，,x,ij,=0,，,所以应令对应的,c,ij,=M,，,再加上一个假想的需求,D,，,就可以把这个问题变成产销平衡的运输模型，并写出产销平衡表和单位运价表,(,合在一起，见表,3-31),。,经用表上作业法求解，可得多个最优方案，表,3-32,中列出最优方案之一。即第,季度生产,25,台，,10,台当季交货，,15,台,季度交货；,季度生产,5,台，用于,季度交货；,季度生产,30,台，其中,20,台于当季交货，,10,台于,季度交货。,季度生产,10,台，于当季交货。按此方案生产，该厂总的生产,(,包括储存、维护,),的费用为,773,万元。,表,3-32,例,4,某航运公司承担六个港口城市,A,、,B,、,C,、,D,、,E,、,F,的四条固定航线的物资运输任务。已知各条航线的起点、终点城市及每天航班数见表,3-33,。,假定各条航线使用相同型号的船只，又各城市间的航程天数见表,3-34,。,又知每条船只每次装卸货的时间各需,1,天，则该航运公司至少应配备多少条船，才能满足所有航线的运货需求,?,解,该公司所需配备船只分两部分。,(1),载货航程需要的周转船只数。例如航线,1,，在港口,E,装货,1,天，,E,D,航程,17,天，在,D,卸货,1,天，总计,19,天。每天,3,航班，故该航线周转船只需,57,条。各条航线周转所需船只数见表,3-35,。,表,3-35,以上累计共需周转船只数,91,条,.,(2),各港口间调度所需船只数。有些港口每天到达船数多于需要船数，例如港口,D,，,每天到达,3,条，需求,1,条；而有些港口到达数少于需求数，例如港口,B,。,各港口每天余缺船只数的计算见 表,3-36,。,为使配备船只数最少，应做到周转的空船数为最少。因此建立以下运输问题，其产销平衡表见表,3-37,。,单位运价表应为相应各港口之间的船只,航程天数,，见表,3-38,。,用表上作业法求出空船的最优调度方案见表,3-39,。,由表,3-39,知最少需周转的空船数为,21+131+51+171+31=40,条。,这样在不考虑维修、储备等情况下，,该公司至少应配备,40+91=131,条船。,例,5,在本章的例,1,中，如果假定,每个工厂生产的产品不一定直接发运到销售点，可以将其中几个产地集中一起运；,运往各销地的产品可以先运给其中几个销地，再转运给其他销地；,除产、销地之外，中间还可以有几个转运站，在产地之间、销地之间或产地与销地间转运。已知各产地、销地、中间转运站及相互之间每吨产品的运价如表,3-40,所示，问在考虑到产销地之间直接运输和非直接运输的各种可能方案的情况下，如何将三个厂每天生产的产品运往销售地，使总的运费最少。,表,3-40,解,从表,3-40,中看出，从,A,1,到,B,2,每吨产品的直接运费为,11,元，如从,A,1,经,A,3,运往,B,2,，,每吨运价为,3+4=7,元，从,A,1,经,T,2,运往,B,2,只需,1+5=6,元，而从,A,1,到,B,2,运费最少的路径是从,A,1,经,A,2,，,B,1,到,B,2,，,每吨产品的运费只需,1+1+1=3,元。可见这个问题中从每个产地到各销地之间的运输方案是很多的。为了把这个问题仍当作一般的运输问题处理，可以这样做：,(1),由于问题中所有产地、中间转运站、销地都可以看作产地，又可看作销地。因此把整个问题当作有,11,个产地和,11,个销地的扩大的运输问题。,(2),对扩大的运输问题建立单位运价表。方法将表,3-40,中不可能的运输方案的运价用任意大的正数,M,代替。,(3),所有中间转运站的产量等于销量。由于运费最少时不可能出现一批物资来回倒运的现象，所以每个转运站的转运数不超过,20,吨。可以规定,T1,，,T2,，,T3,，,T4,的产量和销量均为,20,吨。由于实际的转运量,可以在每个约束条件中增加一个松弛变量,x,ii,，,xii,相当于一个虚构的转运站，意义就是自己运给自己。,(20-,x,ii,),就是每个转运站的实际转运量，,x,ii,的对应运价,c,ii,=0,。,(4),扩大的运输问题中原来的产地与销地因为也有转运站的作用，所以同样在原来产量与销量的数字上加,20,吨，即三个厂每天糖果产量改成,27,，,24,，,29,吨，销量均为,20,吨；四个销售点的每天销量改为,23,，,26,，,25,，,26,吨，产量均为,20,吨，同时引进,x,ii,作为松弛变量。,下面写出扩大运输问题的产销平衡表与单位运价表,(,见表,3-41),，由于这是一个产销平衡的运输问题，所以可以用表上作业法求解,(,计算略,),第,3,章 结束,