表上作业法-a.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,精品课程,运筹学,2.1,表上作业法,精品课程,运筹学,表上作业法,:,建立在运输费用矩阵的求解运输问题的方法。,表上作业法求解运输问题的思想和单纯形法完全类似：,确定一个初始基本可行解,根据最优性判别准则来检查这个基本可行解是不是最优的？,如果是，则计算结束；,如果不是，则进行换基。,直至求出最优解为止。,精品课程,运筹学,一、初始基本可行解的确定,根据上面的讨论，要求得运输问题的初始基本可行解，必须保证找到,m,+,n,1,个不构成闭回路的基变量。,一般的方法步骤如下：,精品课程,运筹学,(1),在运输问题求解作业数据表中任选一个单元格,x,ij,(,A,i,行,B,j,列交叉位置上的格,),令,x,ij,=min,a,i,b,j,即从,A,i,向,B,j,运最大量,(,使行或列在允许的范围内尽量饱和，即使一个约束方程得以满足,),填入,x,ij,的相应位置；,精品课程,运筹学,(2),从,a,i,和,b,j,中分别减去,x,ij,的值，修正为新的,a,i,和,b,j,，,即调整,A,i,的拥有量及,B,j,的需求量；,(3),若,a,i,=0,，,则划去对应的行（已经把拥有的量全部运走），若,b,j,=0,则划去对应的列（已经把需要的量全部运来），且每次只划去一行或一列（即每次要去掉且只去掉一个约束）；,精品课程,运筹学,(4),当最终的运输量选定时，其所在行、列同时满足，此时要同时划去一行和一列。这样，运输平衡表中所有的行与列均被划去，则得到了一个初始基本可行解。,否则在剩下的运输平衡表中选下一个变量，返回,(1),。,精品课程,运筹学,上述计算过程可用流程图描述如下,取未划去的单元格,x,ij,令,x,ij,=min,a,i,b,j,a,i,=,a,i,-,x,ij,b,j,=,b,j,-,x,ij,a,i,=,0?,划去第,i,行,划去第,j,列,是,否,b,j,=0,否,所有行列是,否均被划去,是,找到初始基,本可行解,求运输问题的初始基本可行解过程,注：为了方便，这里总记剩余的产量和销量为,a,i,b,j,精品课程,运筹学,按照上述方法所产生的一组变量的,取值将满足下面条件：,(1),所得的变量均为非负，且变量总,数恰好为,m,+,n,1,个；,(2),所有的约束条件均得到满足；,(3),所得的变量不构成闭回路。,精品课程,运筹学,因此，根据定理及其推论，所得的解一定是运输问题的基本可行解。,在上面的方法中，,x,ij,的选取方法并没有给予限制，若采取不同的规则来选取,x,ij,，,则得到不同的方法，较常用的方法有西北角法和最小元素法。下面分别举例予以说明。,精品课程,运筹学,1,、初始基本可行解的确定,（,1,）,西北角法：,从西北角（左上角）格开始，在格内的右下角标上允许取得的最大数。然后按行（列）标下一格的数。若某行（列）的产量（销量）已满足，则把该行（列）的其他格划去。如此进行下去，直至得到一个基本可行解,。,精品课程,运筹学,（,2,）,最小元素法：,从运价最小的格开始，在格内的右下角标上允许取得的最大数。然后按运价从小到大顺序填数。若某行（列）的产量（销量）已满足，则把该行（列）的其他格划去。如此进行下去，直至得到一个基本可行解。,精品课程,运筹学,注,:,应用西北角法和最小元素法，每次填完数，都只划去一行或一列，只有最后一个元例外（同时划去一行和一列）。当填上一个数后行、列同时饱和时，也应任意划去一行（列），在保留的列（行）中没被划去的格内标一个,0,。,精品课程,运筹学,精品课程,运筹学,精品课程,运筹学,精品课程,运筹学,最优性检验就是检查所得到的方案是不是最优方案。检查的方法与单纯形方法中的原理相同，即计算检验数。由于目标要求极小，因此，当所有的检验数都大于或等于零时该调运方案就是最优方案；否则就不是最优，需要进行调整。下面介绍两种求检验数的方法。,二、基本可行解的最优性检验,精品课程,运筹学,1,、闭回路法,为了方便，我们以上表给出的初始基本可行解方案为例，考察初始方案的任意一个非基变量，比如,x,24,。,根据初始方案，产地,A,2,的产品是不运往销地,B,4,的。如果现在改变初始方案，把,A,2,的产品运送,1,个单位给,B,4,，,那么为了保持产销平衡，就必须使,x,14,或,x,34,减少,1,个单位；而如果,x,14,减少,1,个单位，第,1,行的运输量就必须增加,1,个单位，例如,x,13,增加,1,个单位，那么为了保持产销平衡，就必须使,x,23,减少,1,个单位。,精品课程,运筹学,这个过程就是寻找一个以非基变量,x,24,为起始顶点的闭回路,x,24,，,x,14,，,x,13,，,x,23,，,这个闭回路的其他顶点均为基变量,(,对应着填上数字的格,),。容易计算出上述调整使总的运输费用发生的变化为,8 10+3 2,-1,，即总的运费减少,1,个单位，这就说明原始方案不是最优方案，可以进行调整以得到更好的方案。,精品课程,运筹学,可以证明，如果对闭回路的方向不加区别（即只要起点及其他所有顶点完全相同，而不区别行进方向），那么以每一个非基量为起始顶点的闭回路就存在而且唯一。因此，对每一个非基变量可以找到而且只能找到唯一的一个闭回路。,下表中用虚线画出以非基变量,x,22,为起始顶点的闭回路。,精品课程,运筹学,销地,产地,B,1,B,2,B,3,B,4,产量,3,11,3,4,10,3,7,1,3,9,2,1,8,4,7,4,6,10,5,3,9,销量,3,6,5,6,20(,产销平衡,),A,1,A,2,A,3,精品课程,运筹学,可以计算出以非基变量,x,22,为起始顶点的闭回路调整使总的运输费用发生的变化为,9 2+3 10+5 4,1,即总的运费增加,1,个单位，这就说明这个调整不能改善目标值。,从上面的讨论可以看出，当某个非基变量增加一个单位时，有若干个基变量的取值受其影响。,精品课程,运筹学,这样，利用单位产品变化（运输的单位费用）可计算出它们对目标函数的综合影响，其作用与线性规划单纯形方法中的检验数完全相同。故也称这个综合影响为该非基变量对应的检验数。上面计算的两个非基变量的检验数为,24,=-1,，,22,=1,。闭回路方法原理就是通过寻找闭回路来找到非基变量的检验数。,精品课程,运筹学,如果规定作为起始顶点的非基变量为第,1,个顶点，闭回路的其他顶点依次为第,2,个顶点、第,3,个顶点,，那么就有,ij,=(,闭回路上的奇数次顶点单位运费之和,)-(,闭回路上的偶数次顶点单位运费之和,),其中,ij,为非基变量的下角指标。,精品课程,运筹学,按上述作法，可计算出表中的所有非基变量的检验数，把它们填入相应位置的方括号内，如下图所示。,销地,产地,B,1,B,2,B,3,B,4,产量,A,1,3,1,11,2,3,4,10,3,7,A,2,1,3,9,1,2,1,8,-1,4,A,3,7,10,4,6,10,12,5,3,9,销量,3,6,5,6,20(,产销平衡,),初始基本可行解及检验数,精品课程,运筹学,显然，当所有非基变量的检验数均大于或等于零时，现行的调运方案就是最优方案，因为此时对现行方案作任何调整都将导致总的运输费用增加。,闭回路法的主要缺点是：当变量个数较多时，寻找闭回路以及计算两方面都会产生困难。,精品课程,运筹学,当非基变量的检验数出现负值时，则表明当前的基本可行解不是最优解。在这种情况下，应该对基本可行解进行调整，即找到一个新的基本可行解使目标函数值下降，这一过程通常称为换基,(,或主元变换,),过程。,三、求新的基本可行解,精品课程,运筹学,（,1,）选负检验数中最小者,rk,，,那么,x,rk,为主元，作为进基变量（上图中,x,24,）,;,（,2,）,以,x,rk,为起点找一条闭回路，除,x,rk,外其余,顶点必须为基变量格（上页图中的回路）,;,在运输问题的表上作业法中，换基的过程是如下进行：,精品课程,运筹学,（,3,）为闭回路的每一个顶点标号，,x,rk,为,1,，沿一个方向（顺时针或逆时针）依次给各顶点标号；,（,4,）求,=,min,x,ij,x,ij,对应闭回路上的偶数标号格,=,x,pq,那么确定,x,pq,为出基变量，,为调整量；,精品课程,运筹学,（,5,）对闭回路的各奇标号顶点调整为：,x,ij,+,，,对各偶标号顶点 调整为：,x,ij,-,，,特别,x,pq,-,=0,，,x,pq,变为非,基变量。,重复,(2),、,(3),步，直到所有检验数均非负，得到最优解。,精品课程,运筹学,ij,0,，,得到最优解,x,13,=5,x,14,=2,x,21,=3,x,24,=1,x,32,=6,x,34,=3,其余,x,ij,=0;,最优值：,f,*=35+102+13+81+46+53=85,精品课程,运筹学,四、产销不平衡问题的处理,在实际中遇到的运输问题常常不是产销平衡的，而是下列的一般运输问题模型,m,n,min,f,=,c,ij,x,ij,（,1,）,i,=1,j,=1,n,s.t,.,x,ij,s,i,i,=1,2,m,（,2,）,j,=1,m,x,ij,(=,),d,j,j,=1,2,n,(3,）,i,=1,x,ij,0,(,i,=1,2,m,;,j,=1,2,n,),（,4,）,精品课程,运筹学,我们可以通过增加虚设产地或销地（加、减松弛变量）把问题转换成产销平衡问题，下面分别来讨论。,1.,产量大于销量的情况,m,n,考虑,s,i,d,j,的运输问题，得到的数学模,i,=1,j,=1,型为,精品课程,运筹学,m n,min,f,=,c,ij,x,ij,i,=1,j,=1,n,s.t.,x,ij,s,i,i,=1,2,m,j,=1,m,x,ij,=,d,j,j,=1,2,n,i,=1,x,ij,0(,i,=1,2,m,;,j,=1,2,n,),精品课程,运筹学,只要在模型中的产量限制约束（前,m,个不等式约束）中引入,m,个松弛变量,x,i,n,+1,i,=,1,2,m,即可，变为：,n,x,ij,+,x,in,+1,=,s,i,i,=1,2,m,j,=1,然后，需设一个销地,B,n,+1,它的销量为：,m n,b,n,+1,=,s,i,-d,j,i,=1,j,=1,精品课程,运筹学,这里，松弛变量,x,i n,+1,可以视为从产地,A,i,运往销地,B,n,+1,的运输量，由于实际并不运送，它们的运费为,c,i,n,+1,=0,i,=1,2,m,。,于是，这个运输问题就转化成了一个产销平衡的问题。,精品课程,运筹学,例,:,某公司从两个产地,A,1,、,A,2,将物品运往三个销地,B,1,、,B,2,、,B,3,，,各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？,精品课程,运筹学,解：增加一个虚设的销地运输费用为,0,精品课程,运筹学,2.,销量大于产量的情况,m n,考虑,s,i,d,j,的运输问题，得到的数学模型为,i,=1,j,=1,m n,Min,f,=,c,ij,x,ij,i,=1,j,=1,n,s.t,.,x,ij,=,s,i,i,=1,2,m,j,=1,m,x,ij,d,j,j,=1,2,n,i,=1,x,ij,0(,i,=1,2,m,;,j,=1,2,n,),精品课程,运筹学,只要在模型中的产量限制约束（后,n,个不等式约束）中引入,n,个松弛变量,x,m,+1,j,j,=,1,2,n,即可，变为：,m,x,ij,+,x,m,+1j,=,d,j,j,=1,2,m,i,=1,然后，需设一个产地,A,m,+1,它的销量为：,n m,a,m,+1,=,d,j,-,s,i,j,=1,i,=1,精品课程,运筹学,这里，松弛变量,x,m,+1,j,可以视为从产地,A,m,+1,运往销地,B,j,的运输量，由于实际并不运送，它们的运费为,c,m,+1,j,=0,j,=,1,2,n,。,于是，这个运输问题就转化成了一个产销平衡的问题。,精品课程,运筹学,例,:,某公司从两个产地,A,1,、,A,2,将物品运往三个销地,B,1,、,B,2,、,B,3,，,各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？,精品课程,运筹学,解：增加一个虚设的产地运输费用为,0,精品课程,运筹学,