资源描述
单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,本章重点,第三章,货,货物运输,方,方案的优化,方,方法,产销平衡运,输,输问题的数,学,学模型,产销平衡运,输,输问题的表上作业法,本章内容,运输问题的,数,数学模型,表上作业法,运输问题的,扩,扩展,1 货物,运,运输问题,b,n,b,2,b,1,需求量,B,n,B,2,B,1,需方,供方,A,m,A,2,A,1,a,m,a,2,a,1,供应量,供需平衡,运价,b,n,b,2,b,1,需求量,B,n,B,2,B,1,需方,供方,A,m,A,2,A,1,a,m,a,2,a,1,供应量,c,mn,c,m2,c,m1,c,2n,c,22,c,21,c,1n,c,12,c,11,如何建立供,需,需搭配，使,总,总的运输费,用,用最小？,供,需,平,衡,表,数学模型,设从,A,i,到,B,j,的物资运量,为,为,x,ij,，,产销平衡运输问题的,数,数学模型。,A,i,的产品全部,供,供应出去,B,j,的需求全部,得,得到满足,m,n,平衡表、运,价,价表和二为,一,一：,约束条件或,解,解可用产销,平,平衡表表示:,u,i,v,j,无约束,（,i=1,2, ,m;j=1,2, ,n),u,i,v,j,设,u,i,v,j,为对偶变量,，,，对偶问题,模,模型为,m,个,n,个,2,初,初始调运方,案,案的编制,计算步骤：,(1),找,找出初始调,运,运方案。即,在,在(,m,n),产销平衡表,上,上给出,m+n,-,1,个数字格。(最小元素,法,法或差值法,）,）,(2),求,求检验数。,（,（闭回路法,或,或位势法）,判,判别是否,达,达到最优解,。,。如已是最,优,优解，则停,止,止计算，否,则,则转到下一,步,步。,(3),对,对方案进行,改,改善，找出,新,新的调运方,案,案。（表上,闭,闭回路法调,整,整）,确定,m+n-1,个基变量,(4) 重,复,复（2）、,（,（3），直,到,到求得最优,调,调运方案。,空格,例 运输,问,问题供需平,衡,衡表和运价,表,表如下，求,最,最优调运方,案,案。,供,需,B,1,B,2,B,3,B,4,供应量（,T）,A,1,3,11,3,10,7,A,2,1,9,2,8,4,A,3,7,4,10,5,9,需求量（,T）,3,6,5,6,最小元素,法,法,3,1,4,6,3,3,Z=43+310+31+12+64+35=86,该方案总运费：,.,差额法,分别计算各,行,行、各列次,小,小、最小运,价,价的差额，,优,优先在最大,差,差额处进行,供,供需搭配。,步骤：,1,0,计算未划去,行,行、列的差,额,额；,2,0,找出最大差,额,额对应的最,小,小元素,c,ij,进行供需分,配,配；,3,0,在未被划去,的,的行、列重,新,新计算差额,。,。,销,产,B,1,B,2,B,3,B,4,供量,A,1,7,A,2,4,A,3,9,销量,3,6,5,6,6,B,1,B,2,B,3,B,4,行差额,A,1,3,11,3,10,0,A,2,1,9,2,8,1,A,3,7,4,10,5,1,列差额,2,5,1,3,销,产,B,1,B,2,B,3,B,4,供量,A,1,7,A,2,4,A,3,9,销量,3,6,5,6,6,B,1,B,2,B,3,B,4,行差额,A,1,3,11,3,10,0,A,2,1,9,2,8,1,A,3,7,4,10,5,2,列差额,2,1,3,3,销,产,B,1,B,2,B,3,B,4,供量,A,1,7,A,2,4,A,3,9,销量,3,6,5,6,6,B,1,B,2,B,3,B,4,行差额,A,1,3,11,3,10,0,A,2,1,9,2,8,1,A,3,7,4,10,5,列差额,2,1,2,3,3,销,产,B,1,B,2,B,3,B,4,供量,A,1,7,A,2,4,A,3,3,9,销量,3,6,5,6,6,B,1,B,2,B,3,B,4,差额,A,1,3,11,3,10,7,A,2,1,9,2,8,6,A,3,7,4,10,5,差额,1,2,3,5,1,2,3,调,调运方案的,改,改进,闭回路法,闭回路：从,空,空格出发顺,时,时针(或逆,时,时针)画水(或垂直),直,直线，遇到,填,填有运量的,方,方格可转90，然后继续,前,前进，直到,到,到达出发的,空,空格所形成,的,的闭合回路,。,。,调运方案的,任,任意空格存,在,在唯一闭回,路,路。,销,产,B,1,B,2,B,3,B,4,供量,A,1,5,2,7,A,2,3,1,4,A,3,6,3,9,销量,3,6,5,6,差额法方案,一、最优调,运,运方案的判,定,定,闭回路法,闭回路：从,空,空格出发顺,时,时针(或逆,时,时针)画水,平,平(或垂直)直线，遇,到,到填有运量,的,的方格可转90，然,后,后继续前进,，,，直到到达,出,出发的空格,所,所形成的闭,合,合回路。,调运方案的,任,任意空格存,在,在唯一闭回,路,路。,销,产,B,1,B,2,B,3,B,4,供量,A,1,5,2,7,A,2,3,1,4,A,3,6,3,9,销量,3,6,5,6,3,1,4,6,3,3,最小,元,元素,法,法,+,-,+,-,x,11,为换,入,入变,量,量，,x,11,增加1，,运,运费,的,的变,化,化为3,-,1+2,-,3=1。,这,这个,变,变化,就,就是,x,11,的检,验,验数,，,，故,11,=1,基变,量,量的,检,检验,数,数为,零,零(,基变,量,量,x,ij,)，,ij,=c,ij,-(u,i,+v,j,),u,i,v,j,自由,变,变量,.,位势,法,法,标准,型,型运,输,输问,题,题的,对,对偶,问,问题,是,是：,X,B,X,N,X,S,0,C,N,-C,B,B,-1,N,-,C,B,B,-1,-,Y,S1,-,Y,S2,-,Y,检验,数,数,得,m+n,-,1,个方,程,程，,令,令某,个,个,u,i,(,或,v,j,)=0，,可解,出,出,m+n,个,u,i,和,v,j,；,由此,得,得非,基,基变,量,量的,检,检验,数,数。,对偶,变,变量,值,值等,于,于原,问,问题,的,的检,验,验数,松弛,变,变量,3,1,4,6,3,3,位势,法,法,令,v,1,=0,由,c,21,=3=u,2,+v,1,，,得,u,2,=3,0,1,1,2,0,1,1,2,8,-3,7,位势,表,表,2,9,8,9,-3,-2,检验数,0,1,1,2,8,-3,7,检验,数,数表,1,2,1,-1,10,12,24,=-10，,当,当前,方,方案,不,不,是,是最,优,优方,案,案。,二、 调运方案的调整,pq,ij,j,i,),(,min,=,0,x,pq,为换入变量,从(,p,q),空格,开,开始,画,画闭,回,回路,，,，其,它,它转,角,角点,都,都是,填,填有,运,运量,的,的方,格,格，,并,并从(,p,q),空格,开,开始,给,给闭,回,回路,上,上的,点,点按+1,，,，-1，+1,，,，-1编,号,号，-1,格,格的,最,最小,运,运量为调,整,整量,。,。,换出,变,变量,运价,新的,调,调运,方,方案,为,为：,B,1,B,2,B,3,B,4,产量,A,1,5,2,7,A,2,3,1,4,A,3,6,3,9,销量,3,6,5,6,需,供,B,1,B,2,B,3,B,4,u,i,A,1,0,2,10,A,2,2,1,8,A,3,9,12,5,V,j,-7,-1,-7,0,7,1,3,4,9,11,10,2,3,10,8,5,
展开阅读全文