第七章 运输问题之表上作业法

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第七章 运输问题之表上作业法,一、运输问题模型及其求解思路,二、确定初始基本可行解,三、最优性检验,四、方案调整,五、几种特殊情况,一、运输问题模型及其求解思路,1,、问题的提出：,某公司从两个产地,A,1,、,A,2,将物品运往三个销地,B,1,、,B,2,、,B,3,。,各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示。,问：应如何调运可使总运输费用最小？,一、运输问题模型及其求解思路,B,1,B,2,B,3,产量,A,1,6,4,6,200,A,2,6,5,5,300,销量,150,150,200,一、运输问题模型及其求解思路,2,、产销平衡运输问题模型的特点,从模型的建立可知：,列数为,2,（产地数）,3,（销地数）,6,；,行数为,2,（产地数）,+3,（销地数）,5,；,再观察模型的系数矩阵：,一、运输问题模型及其求解思路,1 1 1 0 0 0 200,0 0 0 1 1 1 300,1 0 0 1 0 0 150,0 1 0 0 1 0 150,0 0 1 0 0 1 200,前,2,行之和后,3,行之和,一、运输问题模型及其求解思路,对于产销平衡的运输问题，若产地为,m,个，销地为,n,个，,则变量个数为,mn,个，线性无关的约束条件个数为,m+n-1,，,故基本解中的基变量个数为,m+n-1,。,一、运输问题模型及其求解思路,3,、运输问题求解思路,表上作业法,由于运输规划系数矩阵的特殊性，如果直接使用线性规划单纯形法求解计算，则无法利用这些有利条件。,人们在分析运输规划系数矩阵特征的基础上建立了针对运输问题的,表上作业法,。,一、运输问题模型及其求解思路,B,1,B,2,B,3,产量,A,1,6,x,11,4,x,12,6,x,13,200,A,2,6,x,21,5,x,22,5,x,23,300,销量,150,150,200,我们关心的量均在运价表和运量表中，故将两表和为,作业表,：,一、运输问题模型及其求解思路,表上作业法的总体思路和单纯形法类似：,基本可行解,是否最优解,结束,换基,是,否,每个步骤都充分利用运输表的特点,一、运输问题模型及其求解思路,例：某食品公司下属的,A,1,、,A,2,、,A,3,，,3,个厂生产方便食品，要运输到,B,1,、,B,2,、,B,3,、,B,4,，,4,个销售点，数据如下表，求最优运输方案。,B,1,B,2,B,3,B,4,产量,A,1,3,11,3,10,7,A,2,1,9,2,8,4,A,3,7,4,10,5,9,销量,3,6,5,6,20,二、确定初始基本可行解,1,、西北（左上）角法,每次找最西北角的元素，让其运输量尽可能的满足一个约束条件。,二、确定初始基本可行解,B,1,B,2,B,3,B,4,产量,A,1,3,11,3,10,7,A,2,1,9,2,8,4,A,3,7,4,10,5,9,销量,3,6,5,6,20,3,4,2,2,3,6,二、确定初始基本可行解,这样得到的初始基本可行解为：,x,11,=3, x,12,=4, x,22,=2, x,23,=2, x,33,=3, x,34,=6,，其余均为,0,。对应的总运费为：,33+411+29+22+310+65,135,二、确定初始基本可行解,2,、最小元素法,每次找到剩下的最小运价，让其对应的运输量尽可能的满足一个约束条件。,二、确定初始基本可行解,B,1,B,2,B,3,B,4,产量,A,1,3,11,3,10,7,A,2,1,9,2,8,4,A,3,7,4,10,5,9,销量,3,6,5,6,20,3,4,3,1,6,3,二、确定初始基本可行解,用最小元素法求出的初始基本可行解为：,x,21,=3, x,22,=1, x,13,=4, x,32,=6, x,34,=3, x,14,=3,其余均为,0,。对应的总运费为：,31+12+43+64+35+310,86,二、确定初始基本可行解,为保证基变量的个数有,m+n-1,个，注意：,1,、,每次填完数，只能划去一行或一列，只有最后一个格子例外。,2,、,用最小元素法时，可能会出现基变量个数还差两个以上但只剩下一行或一列的情况，此时不能将剩下行或列按空格划掉，应在剩下的空格中标上,0,。（退化的基本可行解）,二、确定初始基本可行解,B,1,B,2,B,3,B,4,产量,A,1,3,11,3,10,8,A,2,1,9,2,8,3,A,3,7,4,10,5,9,销量,3,6,5,6,20,3,5,3,0,6,3,二、确定初始基本可行解,B,1,B,2,B,3,B,4,产量,A,1,3,11,3,10,4,A,2,1,9,2,8,4,A,3,7,4,10,5,9,销量,3,6,5,3,17,3,4,0,1,6,3,三、最优性检验,检验数的意义：非基变量增加一个单位，使目标函数值增加的数量。,运输问题中目标函数值要求最小化，因此，当所有的检验数都大于或等于零时该调运方案就是最优方案；否则不是。,下面介绍两种计算检验数的方法：,三、最优性检验,1,、闭回路法,闭回路：在已给出基本解的运输表上，从一个非基变量出发，沿水平或竖直方向前进，只有碰到基变量，才能向右或向左转,90,o,(,当然也可以不改变方向）继续前进。,这样继续下去，总能回到出发的那个非基变量，由此路线形成的封闭曲线，叫闭回路。,三、最优性检验,每一个非基变量都有唯一的闭回路,B,1,B,2,B,3,B,4,产量,A,1,3,11,3,4,10,3,7,A,2,1,3,9,2,1,8,4,A,3,7,4,6,10,5,3,9,销量,3,6,5,6,20,三、最优性检验,观察,x,24,的闭回路：,若让第一个顶点非基变量,x,24,的取值变为,1,，为了保持产销平衡，其闭回路上的顶点运量都要调整，基数顶点,+1,，偶数顶点,-1,。,上述调整使总的运输费用发生的变化为,8 10 + 3 2,-1,，这就说明原方案还不是最优方案，需要进行调整。,三、最优性检验,B,1,B,2,B,3,B,4,产量,A,1,3,11,3,4,10,3,7,A,2,1,3,9,2,1,8,4,A,3,7,4,6,10,5,3,9,销量,3,6,5,6,20,若让,x,11,1,，则总运费变化：,33+21,1,。,三、最优性检验,如果规定作为起始顶点的非基变量,x,ij,为第,1,个顶点，其闭回路上的其他顶点依次为第,2,个顶点、第,3,个顶点,，那么就有该非基变量的检验数：,ij,= (,闭回路上的奇数顶点运价之和,) - (,闭回路上的偶数顶点运价之和,),最优标准：所有检验数,0,三、最优性检验,B,1,B,2,B,3,B,4,产量,A,1,3,11,3,4,10,3,7,A,2,1,3,9,2,1,8,4,A,3,7,4,6,10,5,3,9,销量,3,6,5,6,20,检验数计算如下表：,（,1,）,（,2,）,（,1,）,（,-1,）,（,10,）,（,12,）,三、最优性检验,2,、位势法,闭回路法的缺点：当变量个数较多时，寻找闭回路以及计算两方面都容易出错。,位势法：设产地,A,i,对应的位势量为,u,i,，销地,B,j,对应的位势量为,v,j,， 检验数,ij,=,c,ij,u,i,-v,j,。,三、最优性检验,B,1,B,2,B,3,B,4,产量,u,i,A,1,3,11,3,4,10,3,7,u,1,A,2,1,3,9,2,1,8,4,u,2,A,3,7,4,6,10,5,3,9,u,3,销量,3,6,5,6,20,v,j,v,1,v,2,v,3,v,4,三、最优性检验,根据基变量,x,ij,的检验数,ij,=0,，对应基变量的运价,c,ij,可以分解为,u,i,和,v,j,，即,c,ij,=,u,i,+v,j,。,因为位势量,u,i,v,j,的总数为,m + n,个，而限定方程只有,m+n-1,个（基变量个数），所以位势量（,u,i,v,j,）有无穷多组解，其中总有一个自由变量。,故可以任意取一个位势量赋以定值，从而确定其它位势量的值，一般取,u,1,0,。,三、最优性检验,10,3,9,2,v,j,20,6,5,6,3,销量,b,j,-5,9,5,3,10,4,6,7,A,3,-1,4,8,2,1,9,1,3,A,2,0,7,10,3,3,4,11,3,A,1,u,i,产量,a,i,B,4,B,3,B,2,B,1,（,1,）,（,2,）,（,1,）,（,-1,）,（,10,）,（,12,）,检验数计算总结,1,、闭回路法计算式：,ij,= (,闭回路上的奇数顶点运价之和,) - (,闭回路上的偶数顶点运价之和,),2,、位势法计算式：,ij,=,c,ij,- u,i,v,j,四、方案调整,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,-1,+1,-1,四、方案调整,B,1,B,2,B,3,B,4,产量,a,i,A,1,3,11,3,5,10,2,7,A,2,1,3,9,2,8,1,4,A,3,7,4,6,10,5,3,9,销量,b,j,3,6,5,6,20,得到新的基变量：,x,13,= 5, x,14,= 2, x,21,= 3, x,24,= 1, x,32,= 6, x,34,= 3,。重新计算检验数。,（,0,）,（,2,）,（,2,）,（,1,）,（,9,）,（,12,）,四、方案调整,经过一次基变换，所有,ij, 0,，已得到最优解：,x,13,= 5, x,14,= 2, x,21,= 3, x,24,= 1, x,32,= 6, x,34,= 3,，其它为,0,。,最优值：,f* =35+102+13+81+46+53 = 85,四、方案调整,闭回路调整法步骤：,1,、入基变量的确定：选负检验数中最小者,rk,，那么,x,rk,作为进基变量；（使总运费尽快减少）,2,、出基变量的确定：在进基变量,x,rk,的闭回路上，选取偶数顶点上调运量最小的值，将其对应的运量作为出基变量。（刚好有一个基变量出基，其它基变量都为正）,四、方案调整,即求,=,Min,x,ij,闭回路上的偶数顶点的,x,ij,=,x,pq,。,那么确定,x,pq,为出基变量，,为调整量；,3,、换基调整：对闭回路的奇数顶点运量调整为：,x,ij,+,，对各偶数顶点运量调整为：,x,ij,-,，特别,x,pq,-,=0,，,x,pq,变为非基变量。,重复以上步骤，直到所有检验数均非负，即得到最优解。,练习题,已知如下运价表，用表上作业法求解：,产销地,B,1,B,2,B,3,B,4,产量,A,1,6,5,3,4,4,A,2,4,4,7,5,6,A,3,7,6,5,8,3,销量,2,4,3,4,13,初始解对应目标值为,33+41+42+44+83,61,产销地,B,1,B,2,B,3,B,4,产量,u,i,A,1,6,5,3,4,4,A,2,4,4,7,5,6,A,3,7,6,5,8,3,销量,2,4,3,4,13,v,j,3,4,2,1,0,3,0,3,4,1,3,3,4,(3),(2),(3),(0),(-1),(-2),产销地,B,1,B,2,B,3,B,4,产量,u,i,A,1,6,5,3,4,4,A,2,4,4,7,5,6,A,3,7,6,5,8,3,销量,2,4,3,4,13,v,j,4,0,3,0,2,4,0,3,4,1,3,3,2,(3),(2),(3),(2),(1),(2),已达到最优，最优目标值为,44+42+44+53,55,五、运输问题的几种特殊情况,1,、多个最优方案的情况：,若最优表中有非基变量的检验数为,0,，则为多个最优方案的情况。,这种情况下，可将检验数为,0,的非基变量作为进基变量，即可得到另一个最优方案。,五、运输问题的几种特殊情况,B,1,B,2,B,3,B,4,产量,a,i,A,1,3,11,3,5,10,2,7,A,2,1,3,9,2,8,1,4,A,3,7,4,6,10,5,3,9,销量,b,j,3,6,5,6,20,如上例中的最优方案就不唯一：,（,0,）,（,2,）,（,2,）,（,1,）,（,9,）,（,12,）,检验数为,0,者进基,最小偶点为出基变量和调整量,+2,-2,-2,+2,五、运输问题的几种特殊情况,得到另一个最优方案：,x,11,= 2, x,13,= 5, x,21,= 1, x,24,= 3, x,32,= 6, x,34,= 3,其余,x,ij,= 0,；,最优值仍然为,f* = 85,五、运输问题的几种特殊情况,2,、无解情况：,当某个产地,A,i,不能向某个销地,B,j,供应产品时，设相应的运费为,M,（类似于大,M,法），然后求最优解。,在最优解中，若相应,x,ij,的取值为,0,，则此最优解为原问题的最优解；若,x,ij,的取值不为,0,，则原问题无解。,五、运输问题的几种特殊情况,3,、退化情况,一个或多个基变量等于,0,。,思考,：运输问题是否存在无界解情况？,