企业运筹学管理运输问题讲义

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,运筹学,运输问题,物资运输问题,某种物资有,m,个产地,A,i,，,i,=1,2,.,m，,产量分别为,a,i,个单位；有,n,个销地,B,j,，,销量分别为,b,j,个单位，,j,=1,2,.n，,A,i,与,B,j,之间的单位运价为,C,ij,，,问应如何安排运输方案，才能使总运费最少？,设从产地,A,i,，,运往销地,B,j,的销量为,X,ij,，,则目标为总运费最小,物资运输问题,产地约束条件,销地约束条件,非负约束,物资运输问题,物资运输问题,产销平衡的运输问题,物资运输问题,求一个初始基本可行解,是,判断基本可行解是否最优 结 束,不是,求使目标得到改善的基本可行解,约束方程系数矩阵结构,约束方程系数矩阵结构,约束方程系数矩阵结构,基变量个数,m+n-1,A,的增广矩阵的秩小于,m+n,基,变,变,量,量,个,个,数,数,m+n-1,A,的,增,增,广,广,矩,矩,阵,阵,的,的,秩,秩,等,等,于,于,m+n-1,基,变,变,量,量,的,的,构,构,成,成,闭,回,回,路,路,其,中,中,，,，,i,1,i,2,.,i,s,互,不,不,相,相,同,同,，,，,j,1,j,2,.,j,s,互,不,不,相,相,同,同,）,）,上,述,述,形,形,式,式,的,的,变,变,量,量,的,的,集,集,合,合,称,称,为,为,一,一,个,个,闭,闭,回,回,路,路,其,中,中,的,的,变,变,量,量,称,称,为,为,闭,闭,回,回,路,路,的,的,顶,顶,点,点,闭,回,回,路,路,的,的,特,特,点,点,：,：,封,封,闭,闭,、,、,每,每,行,行,每,每,列,列,至,至,多,多,两,两,个,个,顶,顶,点,点,基,变,变,量,量,的,的,构,构,成,成,闭,回,回,路,路,基,变,变,量,量,的,的,构,构,成,成,对,于,于,闭,闭,回,回,路,路,线,性,性,相,相,关,关,其,对,对,应,应,的,的,列,列,向,向,量,量,基,变,变,量,量,的,的,构,构,成,成,若,变,变,量,量,组,组,中,中,有,有,一,一,部,部,分,分,构,构,成,成,闭,闭,回,回,路,路,，,，,则,则,变,变,量,量,组,组,线,线,性,性,相,相,关,关,。,。,不,包,包,含,含,任,任,何,何,闭,闭,回,回,路,路,的,的,变,变,量,量,组,组,中,中,必,必,有,有,孤,孤,立,立,点,点,。,。,孤,立,立,点,点,是,其,其,所,所,在,在,行,行,和,和,所,所,在,在,列,列,中,中,包,包,含,含,在,在,该,该,变,变,量,量,组,组,中,中,的,的,唯,唯,一,一,向,向,量,量,。,。,定,理,理,：,：,r,个,变,变,量,量,对,对,应,应,的,的,系,系,数,数,列,列,向,向,量,量,线,线,性,性,无,无,关,关,的,的,充,充,要,要,条,条,件,件,是,是,变,变,量,量,组,组,不,不,包,包,含,含,闭,闭,回,回,路,路,。,。,推,论,论,：,：,m,+,n,-1,个,变,变,量,量,构,构,成,成,基,基,变,变,量,量,的,的,充,充,要,要,条,条,件,件,是,是,不,不,含,含,闭,闭,回,回,路,路,。,。,运,输,输,问,问,题,题,求,求,解,解,初,始,始,基,基,本,本,可,可,行,行,解,解,的,的,确,确,定,定,在,供,供,需,需,表,表,中,中,任,任,选,选,一,一,个,个,单,单,元,元,x,ij,，,尽,量,量,匹,匹,配,配,产,产,销,销,，,，,使,使,一,一,个,个,约,约,束,束,方,方,程,程,得,得,以,以,满,满,足,足,，,，,填,填,入,入,相,相,应,应,位,位,置,置,；,；,调,调,整,整,A,i,的,拥,拥,有,有,量,量,及,及,B,j,的,需,需,求,求,量,量,，,，,分,分,别,别,减,减,去,去,x,ij,，,得,得,到,到,调,调,整,整,后,后,的,的,拥,拥,有,有,量,量,a,i,和,需,需,求,求,量,量,b,j,；,若,a,i,=0,，,则划去,对,对应的,行,行（拥,有,有的量,全,全部运,走,走），,若,若,b,j,=0,则划去,对,对应的,列,列（需,求,求的量,全,全部运,来,来），,且,且每次,只,只划去,一,一行或,一,一列（,每,每次只,去,去掉一,个,个约束,）；,若平,衡,衡表中,所,所有的,行,行或列,均,均被划,去,去，则,结,结束。,否则，,在,在剩下,的,的平衡,表,表中选,下,下一个,变,变量，,转,转,运输问,题,题求解,B,1,B,j,B,n,A,1,:,A,i,x,ij,a,i,a,i,:,A,m,b,j,b,j,b,j,=b,j,-x,ij,a,i,=a,i,-x,ij,基变量,的,的构成,按照上,述,述方法,所,所产生,的,的一组,变,变量的,取,取值将,满,满足下,面,面条件,：,：,a,所得的,变,变量均,为,为非负,，,，且变,量,量总数,恰,恰好为,m,+,n,-1,个；,b,所有的,约,约束条,件,件均得,到,到满足,；,；,c,所得的,变,变量不,构,构成闭,回,回路。,因此所,得,得的解,一,一定是,运,运输问,题,题的基,本,本可行,解,解。,在上面,的,的方法,中,中，,x,ij,的选取,方,方法并,没,没有加,以,以限定,，,，如果,采,采取一,定,定的规,则,则来选,取,取，则,会,会产生,不,不同的,方,方法，,若,若每次,在,在调整,后,后的供,需,需表中,选,选取最,左,左上角,的,的元素,，,，则称,为,为左上,角,角方法,（,（或称,西,西北角,法,法），,若,若每次,在,在调整,后,后的供,需,需表中,选,选取对,应,应单位,运,运费最,小,小的元,素,素，则,称,称为最,小,小费用,法,法。,西北角,法,法,运输问,题,题,某地区,有,有两个,煤,煤矿,A,1,A,2,，,所产的,煤,煤要运,往,往三个,城,城市,B,1,B,2,B,3,，,各产地,的,的产量,、,、销地,的,的销量,以,以及各,产,产地到,各,各销地,的,的单位,运,运费见,下,下表，,求,求使总,运,运费最,小,小的运,输,输方案,B,1,B,2,B,3,产量,A,1,90,70,95,200,A,2,80,65,75,230,销量,100,150,180,西北角,法,法,B,1,B,2,B,3,产量,A,1,x,11,x,12,x,13,200,A,2,x,21,x,22,x,23,230,销量,100,150,180,调整量,100,100,调整量,0,调整量,100,0,调整量,0,50,调整量,50,180,调整量,0,0,调整量,180,0,调整量,0,最小费,用,用法,B,1,B,2,B,3,产量,A,1,x,11,x,12,x,13,200,A,2,x,21,x,22,x,23,230,销量,100,150,180,调整量,150,80,调整量,0,调整量,80,0,调整量,100,调整量,100,100,调整量,0,调整量,100,0,调整量,0,90,70,95,80,65,75,+,-,+,-,B,1,B,2,B,3,产量,A,1,x,11,x,12,x,13,200,A,2,x,21,x,22,x,23,230,销量,100,150,180,90,70,95,80,65,75,100,100,50,180,最优性,检,检验,21,=,C,21,-C,11,+C,12,-C,22,=80-90+70-65=-5,13,=,C,13,-C,23,+C,22,-C,12,=95-75+65-70=15,最优性,检,检验：,闭,闭回路,法,法,闭回路,方,方法,原理是,通,通过寻,找,找闭回,路,路来找,到,到非基,变,变量的,检,检验数,。,。,可以证,明,明，如,果,果对闭,回,回路的,方,方向不,加,加区别,，,，那么,以,以每一,个,个非基,变,变量为,起,起始顶,点,点，以,基,基变量,为,为其它,顶,顶点的,闭,闭回路,就,就存在,而,而且唯,一,一。,如果规,定,定作为,起,起始顶,点,点的非,基,基变量,为,为偶数,次,次顶点,，,，闭回,路,路的其,他,他顶点,依,依次为,第,第一个,顶,顶点、,第,第二个,顶,顶点,，那,么,么就有,检验数=偶数,点,点单位,运,运费之,和,和奇,数,数点单,位,位运费,之,之和,若所有,非,非基变,量,量检验,数,数0,，,，则最,优,优。,最优性,检,检验：,位,位势法,位势法,其原理,是,是利用,约,约束条,件,件的特,殊,殊性来,找,找到非,基,基变量,的,的检验,数,数。,从约束,条,条件中,解,解出基,变,变量（,用,用非基,变,变量表,示,示基变,量,量），,代,代入目,标,标后消,去,去目标,中,中的基,变,变量，,得,得到的,非,非基变,量,量的系,数,数就是,检,检验数,。,。,这一过,程,程若用,消,消元的,方,方法加,以,以实现,，,，则回,产,产生位,势,势法。,若所有,非,非基变,量,量检验,数,数0,，,，则最,优,优。,最优性,检,检验：,位,位势法,位势法,最优性,检,检验：,位,位势法,位势法,最优性,检,检验：,位,位势法,B,1,B,2,B,3,产量,A,1,x,11,x,12,x,13,200,A,2,x,21,x,22,x,23,230,销量,100,150,180,最优性,检,检验：,位,位势法,（90）,（70）,95,80,（65）,（75）,B,1,B,2,B,3,产量,A,1,x,11,x,12,x,13,200,A,2,x,21,x,22,x,23,230,销量,100,150,180,最优性,检,检验：,位,位势法,（90）,（70）,95,80,（65）,（75）,B,1,B,2,B,3,产量,A,1,x,11,x,12,x,13,200,A,2,x,21,x,22,x,23,230,销量,100,150,180,最优性,检,检验：,位,位势法,（0）,（-20）,5,80,（65）,（75）,B,1,B,2,B,3,产量,A,1,x,11,x,12,x,13,200,A,2,x,21,x,22,x,23,230,销量,100,150,180,最优性,检,检验：,位,位势法,（0）,（0）,5,80,（85）,（75）,B,1,B,2,B,3,产量,A,1,x,11,x,12,x,13,200,A,2,x,21,x,22,x,23,230,销量,100,150,180,最优性,检,检验：,位,位势法,（0）,（0）,5,-5,（0）,（-10）,B,1,B,2,B,3,产量,A,1,x,11,x,12,x,13,200,A,2,x,21,x,22,x,23,230,销量,100,150,180,最优性,检,检验：,位,位势法,（0）,（0）,15,-5,（0）,（0）,90,70,95,80,65,75,100,100,50,180,+,-,+,-,B,1,B,2,B,3,产量,A,1,x,11,x,12,x,13,200,A,2,x,21,x,22,x,23,230,销量,100,150,180,调整流,量,量,X,21,进基，,=,minx,11,x,22,=min100,50=50,X,22,出基,调整流,量,量,调运量,的,的调整,步,步骤：,闭回,路,路上的,奇,奇数次,顶,顶点的,调,调运量,减,减去,；,闭,回,回,路,路,上,上,的,的,偶,偶,数,数,次,次,顶,顶,点,点,（,（,包,包,括,括,起,起,始,始,变,变,量,量,）,）,的,的,调,调,运,运,量,量,加,加,上,上,；,；,非,闭,闭,回,回,路,路,顶,顶,点,点,的,的,其,其,他,他,变,变,量,量,调,调,运,运,量,量,不,不,变