单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,第5章 运输模型,*,第5章 运输模型,Transportation Model,TM,1,第5章 运输模型,第5章 运输模型Transportation Mod,5.1 运输问题及其数学模型,5.2 表上作业法,5.3 运输模型的应用,第5章 运输模型,2,第5章 运输模型,5.1 运输问题及其数学模型第5章 运输模型2第5章,5.1 运输问题及其数学模型,问题的提出,运输问题：产地、销地、产量、销量,例1,有A,1,，A,2,，A,3,三座铁矿，每天要把生产,的铁矿石运往B,1,，B,2,，B,3,，B,4,四个炼铁厂。各矿的,产量、各厂的销量以及各厂矿间的运价如下表所示。,问应如何组织调运才能使运费最少？,3,第5章 运输模型,5.1 运输问题及其数学模型问题的提出3第5章,5.1 运输问题及其数学模型,B,1,B,2,B,3,B,4,产量,A,1,A,2,A,3,6 3 2 5,7 5 8 4,3 2 9 7,5,2,3,销量,2 3 1 4,(,百元,/,百吨,),x,ij,A,i,运给B,j,的铁矿石数量（百吨）,z,总运费（百元）,4,第5章 运输模型,5.1 运输问题及其数学模型B1 B,5.1 运输问题及其数学模型,B,1,B,2,B,3,B,4,产量,A,1,6,3,2,5,5,A,2,7,5,8,4,2,A,3,3,2,9,7,3,销量,2,3,1,4,(,百元,/,百吨,),x,11,x,12,x,13,x,14,x,21,x,22,x,23,x,24,x,31,x,32,x,33,x,34,5,第5章 运输模型,5.1 运输问题及其数学模型B1B2B3B4产量A1632,5.1 运输问题及其数学模型,数学模型为:,min z=6,x,11,+3,x,12,+2,x,13,+5,x,14,+7,x,21,+5,x,22,+8,x,23,+4,x,24,+3,x,31,+2,x,32,+9,x,33,+7,x,34,x,11,+,x,12,+,x,13,+,x,14,=5 ,x,21,+,x,22,+,x,23,+,x,24,=2 ,x,31,+,x,32,+,x,33,+,x,34,=3 ,x,11,+,x,21,+,x,31,=2 ,x,12,+,x,22,+,x,32,=3 ,x,13,+,x,23,+,x,33,=1 ,x,14,+,x,24,+,x,34,=4,x,ij,0 (,i=1,2,3;j=1,2,3,4,),s.t.,6,第5章 运输模型,5.1 运输问题及其数学模型 数学模型为:s.t.6,5.1 运输问题及其数学模型,表式,模型,产销平衡,的运输问题:,a,i,=,b,j,产大于销,的运输问题:,a,i,b,j,产小于销,的运输问题:,a,i,b,j,B,1,B,2,B,n,产量,A,1,c,11,x,11,c,12,x,12,c,1n,x,1n,a,1,A,2,c,21,x,21,c,22,x,22,c,2n,x,2n,a,2,A,m,c,m1,x,m1,c,m2,x,m2,c,mn,x,m,n,a,m,销量,b,1,b,2,b,n,a,i,b,j,7,第5章 运输模型,5.1 运输问题及其数学模型表式模型 产销平衡的运输问题,5.1 运输问题及其数学模型,x,ij,0,x,ij,=,a,i,i=1,2,，m,j=1,n,x,ij,=,b,j,j=1,2,，n,i=1,n,s.t.,min z,=,i=1,n,j=1,n,c,ij,x,ij,LP式,产销平衡,模型,8,第5章 运输模型,5.1 运输问题及其数学模型xij 0 xij=,LP,式,产大于销,模型,5.1 运输问题及其数学模型,x,ij,0,x,ij,a,i,i=1,2,，m,j=1,n,x,ij,=,b,j,j=1,2,，n,i=1,n,s.t.,min z,=,i=1,n,j=1,n,c,ij,x,ij,9,第5章 运输模型,LP式 产大于销,5.1 运输问题及其数学模型,x,ij,0,x,ij,=,a,i,i=1,2,，m,j=1,n,x,ij,b,j,j=1,2,，n,i=1,n,s.t.,min z,=,i=1,n,j=1,n,c,ij,x,ij,LP,式,产小于销,模型,10,第5章 运输模型,5.1 运输问题及其数学模型xij 0 xij =,5.1 运输问题及其数学模型,运输模型有两个特点：,(1)它有,m,n,个变量，,m,+,n,个约束方程,(2)其系数阵具有特殊的结构,m=3行,n=4行,A,=,1 1 1 1,1 1 1 1,1 1 1 1,1 1 1,1 1 1,1 1 1,1 1 1,11,第5章 运输模型,5.1 运输问题及其数学模型 运输模型有两个特点：,5.2 表上作业法,基本步骤,(1),确定初始方案,；,(2),进行最优性检验,；,(3),调整、改进非最优方案,。,12,第5章 运输模型,5.2 表上作业法12第5章 运输模型,5.2 表上作业法,5.2.1,初始方案的确定,一,、,最小元素法,所谓,最小元素,，是指作业表中,最小运价,c,ij,。即先给最小运价那格安排,运量，然后划去该运价所在行或列；直到求出初始方案为止。,1,4,3,0,0,2,2,2,2,2,B,1,B,2,B,3,B,4,产量,A,1,6,3,2,5,5,A,2,7,5,8,4,2,A,3,3,2,9,7,3,销量,2,3,1,4,13,第5章 运输模型,5.2 表上作业法 5.2.1 初始方案的确定14,为了保证,画圈数字为,m,+,n,-,1,个,，最小元素法有以下,三条原则:,(1)在确定了某一基变量,x,lk,及其数值并画圈以后，,若它所在的A,l,行或B,k,列中其余变量均应取 0 值,也,不能,同时把,A,l,行和,B,k,列都划去,，而只能划去其中之一。,(2)在确定为,最小元素的,某一,空格,上，若该变量,x,ij,=,min a,i,b,j,=,0,此时,也不能保留该空格,，而必须把 0 填上并画圈。,(3),最后一个空格必须画圈,，即便该格的,x,ij,=,0也要,填上0并画圈。,5.2 表上作业法,14,第5章 运输模型,5.2 表上作业法14第5章 运输,5.2 表上作业法,(1)为了保证,画圈个数为,m,+,n,-,1,个,，,每画1个圈,只许划去1行/列，即，行列总数减少1；,因为行列总数为,m,+,n；,(2),再如，当只剩下最后,1,行/列时:,当画了,m,+,n,-,2,个,圈时，未划去的行列总数为,2,，,即只剩下,1,个空格，只能再画1个圈，这样，,画圈个数,恰为,m,+,n,-,1,。,2,2,2,不仅划去,1,行,，同时也划去了所有的列，,不可！,15,第5章 运输模型,5.2 表上作业法 m+n；(2)再如，当只剩下,5.2 表上作业法,“,最小元素法,”和“,最大差额法,”所确定的,初始方案,满足以下条件：,(1)画圈数字的个数恰好等于线性无关的约束,个数，即,m,+,n,-,1,个。,(2),可行,：满足所有约束条件。,(3)表中不存在,“,以画圈数字为顶点的闭回路,”。,16,第5章 运输模型,5.2 表上作业法16第5章 运输模型,5.2 表上作业法,画圈数字为顶点的闭回路,B,1,B,2,B,3,B,4,产量,A,1,6,3,2,5,5,A,2,7,5,8,4,2,A,3,3,2,9,7,3,销量,2,3,1,4,1,1,3,2,2,1,17,第5章 运输模型,5.2 表上作业法画圈数字为顶点的闭回路B1B2B3,5.2 表上作业法,二、最大差额法,步骤,如下：,1,对每行每列的运价c,ij,分别计算,两最小元素之差,(,取正值,),，将“行差”,记于表右侧，“列差”记于表下端。,2,在所有行差、列差中选一,最大差额,，若有几个同时最大，则可任选其中,之一。,3,在最大差额所在行,(,列,),中选一,最小运价,，若有几个同时最小，则可,任选其一。,4,在所确定的最小运价格内，确定基变量数值并画圈，然后划去其所在行,或列，具体做法同最小元素法。,5,对剩余未划去的行列重复上述步骤，但当,只剩下最后一行,(,列,),时，,不再,计算行,(,列,),差，而,直接按最小元素法,分配运量并划去相应的行或列。,18,第5章 运输模型,5.2 表上作业法二、最大差额法 4在所确定的最小,5.2 表上作业法,B,1,B,2,B,3,B,4,产量,A,1,6,3,2,5,5,A,2,7,5,8,4,2,A,3,3,2,9,7,3,销量,2,3,1,4,行 差,列,差,1,1,1,3,1,6,1,6,3,1,4,2,1,1,2,1,2,1,5,5,2,1,2,2,2,1,2,2,2,2,19,第5章 运输模型,5.2 表上作业法B1B2B3B4产量A163255,5.2 表上作业法,5.2.2,最优性检验,一、位势法,在初始方案表中,可将基变量所在格的运价,c,ij,分解为两部分,u,i,+,v,j,=,c,ij,其中,u,i,代表产地A,i,所在行的,行位势量,，,v,j,代表销地B,j,所在列,的,列位势量,，,c,ij,为,画圈数字,所在格的,运价,。,所有u,i,，v,j,的值确定以后，可以证明，,ij,可按下式计算：,ij,=,c,ij,u,i,v,j,基变量对应的检验数显然全都为0，因此，只需计算非基,变量的检验数。这种计算检验数的方法就是,位势法,。,20,第5章 运输模型,5.2 表上作业法 5.2.2 最优性检验20第,5.2 表上作业法,1,3,0,2,2,2,u,i,v,j,0,6,2,5,-,3,5,-,1,-,2,2,1,7,10,5,21,第5章 运输模型,5.2 表上作业法 130222uivj0625-3,5.2 表上作业法,二、闭回路法,闭回路,是指以一个非基变量的格子为始点和终点，而其,余顶点均为画圈数字的一条封闭回路。,符号,+,表示始点（非基变量），它及其闭,回路上标,“,+,”,号的顶点称为,偶点,，而标“,”号的顶点称为,奇点,。,奇偶点的确定,：,的某一行进方向交错地标记奇偶符号。则,标 号，,始点,（非基变量）必为,偶点,，,+,ij,=,c,ij,c,ij,+,-,然后沿着闭回路,检验数,等于,闭回路,上,偶点,的,运价总和,减去,奇点,的,运价总和,。,即,22,第5章 运输模型,5.2 表上作业法 二、闭回路法符号 +表示始,5.2 表上作业法,B,1,B,2,B,3,B,4,产量,A,1,6,3,2,5,5,A,2,7,5,8,4,2,A,3,3,2,9,7,3,销量,2,3,1,4,1,2,1,2,2,2,+,-,-,-,+,+,4,2,3,7,8,3,补表,以,最大差额法,所确定,方案,及其,闭回路,为例,x,21,的闭回路,。,21,=,7-4+5-3+2-3,=,4,23,第5章 运输模型,5.2 表上作业法B1B2B3B4产量A163255,5.2 表上作业法,5.2.3,非优方案的调整,在,进基变量的闭回路,上的所有,奇点,中,选择数值最小的那个作为离基变量,并且取它的值作为,调整量,。,1,3,0,2,2,2,u,i,v,j,0,6,2,5,-,3,5,-,1,-,2,2,1,7,10,5,+,-,-,+,24,第5章 运输模型,5.2 表上作业法 5.2.3 非优方案的调整13,5.2 表上作业法,1,3,0,2,2,u,i,v,j,0,6,2,5,-,3,5,-,1,-,2,2,1,7,10,5,+,-,-,+,2,调整之，,t=2,2,2,1,25,第5章 运输模型,5.2 表上作业法 13022uivj0625-35,5.2 表上作业法,1,2,2,1,2,2,u,i,v,j,0,4,2,5,-,1,3,-,1,2,4,3,7,8,3,为,最优方案,，,对所得新方案用,位势法,检验：,与,最大差