运筹学 04 运输问题.ppt

单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,运输模型,Transport Model,运输问题的表上作业法,Table Method of TP,运输问题的进一步讨论,Further Discussion of TP,运输问题的思考题及练习题,Questions and Exercises for TP,运输问题,Transportation Problem,1,运输模型,一般的运输问题就是要解决把某种产品从若干个产地,A,i,(i,=1,2,m),调运到若干个销地,B,j,(j,=1,2,n),，在每个产地的供应量,a,i,(i,=1,2,m),、每个销地的需求量,b,j,(j,=1,2,n),、,A,i,运输到,B,j,的单位运价,c,ij,已知的前提下，如何确定一个运输方案，使总运价最低。,设,x,ij,为从,A,i,运输到,B,j,的产品数量，若,a,i,=,b,j,，则称为产销平衡的运输规划问题，数学模型为,min f=c,11,x,11,+c,1n,x,1n,+c,21,x,21,+,c,mn,x,mn,x,i1,+x,i2,+,x,in,=,a,i,(i=1,2,m),x,1j,+x,2j,+,x,mj,=,b,j,(j=1,2,n),x,ij,0 (i=1,2,m;j,=1,2,n),有时运输问题的一般模型会有一些变化，如,求目标函数的最大值,某些运输线路的运输能力有一定限制,生产地产量有所限制,销售地销量有所限制,总产量不等于总销量，即产销不平衡,某些地方只是中转站,这些问题也可以转化为平衡运输问题,对产销平衡运输问题，若用,u,1,u,2,u,m,分别表示前,m,个约束等式相应的对偶变量，用,v,1,v,2,v,n,分别表示后,n,个约束等式相应的对偶变量，即对偶变量为,Y=(u,1,u,2,u,m,v,1,v,2,v,n,),T,运输问题的对偶问题可以写成,max f=a,1,u,1,+a,m,u,m,+b,1,v,1,+,b,n,v,n,u,i,+v,j,c,ij,(i=1,2,m;j,=1,2,n),u,i,v,j,任意,原问题变量,x,j,的检验数,j,=,c,j,-z,j,=c,j,-C,B,B,-1,P,j,=,c,j,-YP,j,变量,x,ij,的检验数,ij,=,c,ij,-z,ij,=,c,ij,-YP,ij,=c,ij,-(u,1,u,2,u,m,v,1,v,2,v,n,)P,ij,=,c,ij,-(u,i,+v,j,),2,运输问题的表上作业法,运输问题的数学模型及其约束方程组的系数矩阵结构具有特殊性，使用表上作业法解决运输问题，比单纯形法更为简便。,表上作业法的步骤：,第,1,步：确定初始基可行解,第,2,步：解的最优性检验,第,3,步：解的调整，转第,2,步,例,1,：某集团公司,3,个工厂,A,1,、,A,2,、,A,3,生产同一产品的产量、,4,个销售点,B,1,、,B,2,、,B,3,、,B,4,的销量及单位产品的运价如下表。试确定使总运费最低的运输方案。,工厂,B,1,B,2,B,3,B,4,产量,A,1,4,12,4,11,16,A,2,2,10,3,9,10,A,3,8,5,11,6,22,销量,8,14,12,14,第,1,步：确定初始基可行解,最小元素法,(,最低运价法,),步骤：,运价表中找出一个最低运价,(,即最小元素,),c,ij,在该处确定运量,x,ij,=,min(a,i,b,j,),计算剩余产量,a,i,=,a,i,-x,ij,和剩余销量,b,j,=,b,j,-x,ij,，则出现,(1)a,i,=0,，,b,j,0,划去第,i,行运价；,(2)a,i,0,，,b,j,=0,划去第,j,列运价；,(3)a,i,=0,，,b,j,=0,划去第,i,行或第,j,列运价,重复上述，直到获得,(m+n-1),个运输数量,工厂,B,1,B,2,B,3,B,4,产量,A,1,4,12,4,11,16,A,2,2,10,3,9,10,A,3,8,5,11,6,22,销量,8,14,12,14,工厂,B,1,B,2,B,3,B,4,产量,A,1,10,6,16,A,2,8,2,10,A,3,14,8,22,销量,8,14,12,14,(1),(2),(3),最低运价,2,3,4,运价标号,c,21,c,23,c,13,线路,x,21,x,23,x,13,数量比较,8,10,2,12,16,10,运输数量,8,2,10,新产量,a,2,=2,a,2,=0,a,1,=6,新销量,b,1,=0,b,3,=10,b,3,=0,划去,第,1,列,第,2,行,第,3,列,西北角法步骤,运价表中找出西北角,(,左上角,),运价,c,ij,在该处确定运量,x,ij,=,min(a,i,b,j,),计算剩余产量,a,i,=,a,i,-x,ij,和剩余销量,b,j,=,b,j,-x,ij,，则出现,(1)a,i,=0,，,b,j,0,划去第,i,行运价；,(2)a,i,0,，,b,j,=0,划去第,j,列运价；,(3)a,i,=0,，,b,j,=0,划去第,i,行或第,j,列运价,重复上述，直到获得,(m+n-1),个运输数量,伏格尔法步骤,运价表中计算每行和每列最小和次小运价之差，从差值最大的行或列中找出最小运价,c,ij,在该处确定运量,x,ij,=,min(a,i,b,j,),计算剩余产量,a,i,=,a,i,-x,ij,和剩余销量,b,j,=,b,j,-x,ij,，则出现,(1)a,i,=0,，,b,j,0,划去第,i,行运价；,(2)a,i,0,，,b,j,=0,划去第,j,列运价；,(3)a,i,=0,，,b,j,=0,划去第,i,行或第,j,列运价,重复上述，直到获得,(m+n-1),个运输数量,罗素法步骤,运价表中找出每行和每列的最大值,u,i,和,v,j,，每个单元格计算,ij,=,c,ij,-u,i,-v,j,，找到最小值,ij,在该处确定运量,x,ij,=,min(a,i,b,j,),计算剩余产量,a,i,=,a,i,-x,ij,和剩余销量,b,j,=,b,j,-x,ij,，则出现,(1)a,i,=0,，,b,j,0,划去第,i,行运价；,(2)a,i,0,，,b,j,=0,划去第,j,列运价；,(3)a,i,=0,，,b,j,=0,划去第,i,行或第,j,列运价,重复上述，直到获得,(m+n-1),个运输数量,任意方法也能获得初始运输方案，自己思考,第,2,步：解的最优性检验,运输问题是否达到最优，可以这样考虑：在现有运输方案基础上作一点点调整，看看总成本作如何改变。如，某运输线路上原先没有运输数量，现在增加一个单位的运输数量，成本该如何改变？为了保证数量平衡，这就要用到闭合回路思路了。,闭回路法思路,选定一个空格,(,非基变量,),，顺次从垂直和水平两个方向交替寻找闭合回路,(,该空格和大于零的数字构成封闭多边形，只有横直线,),从空格开始，把对应运价交替相加和相减，得到的结果填入该空格，即为检验数,检验数,0,，方案不能调整；检验数,0,，方案不能调整；检验数,总销量，属于产大于销的产销不平衡运输问题。增加一个销地，销量,b,5,=22-18=4,；运价为,0,。得到产销平衡表如左表。表上作业法结果见右表。,产地,B,1,B,2,B,3,B,4,B,5,产量,产地,B,1,B,2,B,3,B,4,B,5,产量,A,1,4,12,4,11,0,8,A,1,1,-,4,0,4,8,A,2,2,10,3,9,0,5,A,2,4,-,1,-,1,5,A,3,8,5,11,6,0,9,A,3,10,3,9,6,5,9,销量,4,3,5,6,4,销量,4,3,5,6,4,例,3,：设,3,个化肥厂供应,4,个地区的农用化肥。各化肥厂年产量,(,万吨,),、各地区年需求量,(,万吨,),以及各化肥厂到各地区单位运价,(,万元,/,万吨,),见表。试求总运费最低的化肥调拨方案。,产地,产量,A,16,13,22,17,50,B,14,13,19,15,60,C,19,20,23,M,50,最低需求,30,70,0,10,最高需求,50,70,30,解答,总产量,=50+60+50=160(,万吨,),；最低需求量,=30+70+0+10=110(,万吨,),，最高需求,=,。根据现有产量，地区,最多需求数量,=160-110+10=60(,万吨,),，这样最高需求,=50+70+30+60=210(,万吨,),，大于总产量，产销不平衡。,假定有一家化肥厂,D,生产化肥，产量,=210-160=50(,万吨,),。地区,最低需求,30,万吨，不能由,D,提供，运价设定为,M,；类似，所有地区最低需求都不能由,D,提供。而超过最低需求的部分可以由,D,提供，这时表明所需数量不能满足，设定运价为,0,。这样得到产销平衡的运输问题,(,如上表,),，并求得其最优解,(,如下表,),。,产地,产量,A,16,16,13,22,17,17,50,B,14,14,13,19,15,15,60,C,19,19,20,23,M,M,50,D,M,0,M,0,M,0,50,销量,30,20,70,30,10,50,产地,产量,A,50,50,B,20,10,30,60,C,30,20,0,50,D,30,20,50,销量,30,20,70,30,10,50,有存储费用的运输问题,例,4,：对下表所示的运输问题，若产地有一个单位物资没运出就发生存储费用，假设,3,个产地单位物资存储费用分别为,4,、,4,、,3,；又假设产地,2,的物资最多运出,35,，产地,3,的物资最少运出,28,。试求最优运输方案。,产地,1,2,3,产量,1,1,2,2,20,2,1,4,5,40,3,2,3,3,30,销量,30,20,20,产地,1,2,3,1,2,3,产量,1,1,2,2,4,M,M,20,2,1,4,5,M,4,M,40,3,2,3,3,M,M,3,30,销量,30,20,20,13,5,2,产地,1,2,3,1,2,3,产量,1,8,12,0,20,2,22,18,40,3,20,8,2,30,销量,30,20,20,13,5,2,216,目标函数求最大值的运输问题,例,5,：某农场有土地,900,亩，分为,3,类,(A,1,A,2,A,3,),，,计划种植,3,种作物,(B,1,B,2,B,3,),，各类型土地面积、各作物所需面积、每种作物单位产值如表。求使农作物总产值最多的布局方案。,土地类型,B,1,B,2,B,3,供给量,A,1,700,500,480,100,A,2,850,700,600,400,A,3,400,300,500,400,需求量,300,200,400,土地类型,B,1,B,2,B,3,供给量,A,1,700,500,480,100,A,2,850,700,600,400,A,3,400,300,500,400,需求量,300,200,400,土地类型,B,1,B,2,B,3,供给量,A,1,50,100,0,100,A,2,300,100,-,400,A,3,-270,-220,400,400,需求量,300,200,400,575000,土地类型,B,1,B,2,B,3,供给量,A,1,700,500,480,100,A,2,850,700,600,400,A,3,400,300,500,400,需求量,300,200,400,土地类型,B,1,B,2,B,3,供给量,A,1,100,-40,0,100,A,2,200,200,-30,400,A,3,-420,-270,400,400,需求量,300,200,400,580000,有转运的运输问题,中转站,运输问题存在中途临时储存的设施，即中转站。这类运输问题称为转运问题,(Transshipment problem),。,建模思路,从发送及接受角度考虑,产地只有发送而无接受,销地只有接受而无发送,中转站既有发送又有接受，且发送和接受数量相等,此路不通者运价为无穷大,(,大,M,表示,),4,运输问题的思考题及练习题,判断题,(,概念,),1、运输问题是一种,LP,问题，其求解结果有四种情况。,2、在运输问题中，只要给出一组含,(m+n-1),个非零的,x,ij,，且满足,x,ij,=,a,i,(i,=1,2,n),，,x,ij,=,b,j,(j,=1,2,n),，就可以作为一个初始基可行解。,3、按最小元素法,(,或伏格尔法,),给出的初始基可行解，从每一空格出发可以找出而且仅能找出唯一的闭回路。,4、当所有产地产量和销地销量均为整数值，运输问题的最优解也为整数值。,5、如果运输问题单位运价表的某一行,(,或某一列,),元素分别加上一个常数,k，,最优调运方案将不会发生变化。,6、如果运输问题单位运价表的某一个,(,或某一列,),元素分别,乘,上一个常数,k,，最优调运方案将不会发生变化。,运输问题的对偶问题,某运输问题可以叙述如下：有,n,个地区需要某种物资，需要量分别为,b,1,b,2,b,n,，这些物资均由某公司分设在,m,个地区的工厂供应，各工厂的产量分别为,a,1,a,2,a,m,，已知从,i,地区工厂至第,j,个需要地区单位物资的运价为,c,ij,，又供需平衡,(,即,a,1,+a,m,=b,1,+,b,n,),。如何调运物资使总运输费用最低？,阐述其对偶问题，并解释对偶变量的经济意义。,运输问题的灵敏度分析,已知某运输问题的产量、销量及单位运价如下表。,要求：,(1),用表上作业法找出最优调运方案。,(,2,),分别讨论,c,11,和,c,23,使最优方案不变的变化范围。,产地,B,1,B,2,B,3,产量,A,1,4,2,5,8,A,2,3,5,3,7,A,3,1,3,2,4,销量,4,8,5,可转化为运输问题来求解,求解下列线性规划问题,min,z=100 x,11,+140 x,12,+110 x,13,+180 x,21,+150 x,22,+160 x,23,x,11,+x,12,+x,13,=30,x,21,+x,22,+x,23,=20,x,11,+x,21,=10,x,12,+x,22,=15,x,13,+x,23,=25,x,11,x,12,x,13,x,21,x,22,x,23,0,下表给出一个运输问题及它的一个解,(,左边运量，右边运价,),。试问：,(1),表中给出的解是否为最优解？,(2),若,c,24,由1变为3，最优解是否改变？如何改变？,(3),若所有运价均增加1，最优解是否改变？为什么？,(4),若所有运价均减去1，最优解是否改变？为什么？,(5),写出该问题的对偶问题，并给出其最优解。,产地,B,1,B,2,B,3,B,4,产量,A,1,4,5,1,3,4,6,8,A,2,8,1,2,6,2,1,10,A,3,3,7,3,5,1,1,4,销量,8,5,6,3,