第3章 运输问题 第2节

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第,2,节 表上作业法,表上作业法实质是单纯形法。可归纳为：,(1),找出初始基可行解。即在,(,m,n,),产销平衡表上,用西北角法或最小元素法，,Vogel,法给出,m,+,n,-1,个数字，称为数字格。它们就是初始基变量的取值。,(2),求各非基变量的检验数，即在表上计算空格的检验数，判别是否达到最优解。如已是最优解，则停止计算，否则转到下一步。,(3),确定换入变量和换出变量，找出新的基可行解。在表上用闭回路法调整。,(4),重复,(2),，,(3),直到得到最优解为止。,例,1,某公司经销甲产品。它下设三个加工厂。每日的产量分别是：,A,1,为,7,吨，,A,2,为,4,吨，,A,3,为,9,吨。该公司把这些产品分别运往四个销售点。各销售点每日销量为：,B,1,为,3,吨，,B,2,为,6,吨，,B,3,为,5,吨，,B,4,为,6,吨。已知从各工厂到各销售点的单位产品的运价为表,3-3,所示。问该公司应如何调运产品，在满足各销点的需要量的前提下，使总运费为最少。,表,3-3,单位运价表,表,3-4,产销平衡表,确定初始基可行解的方法很多，有最小元素法和伏格尔,(Vogel),法。一般希望的方法是既简便，又尽可能接近最优解。下面介绍两种方法：,1.,最小元素法,基本思想是就近供应，即从单位运价表中最小的运价开始确定供销关系，然后次小。一直到给出初始基可行解为止。以例,1,进行讨论。,第一步：从表,3-3,中找出最小运价为,1,，这表示先将,A,2,的产品供应给,B,1,。因,a,2,b,1,，,A,2,除满足,B,1,的全部需要外，还可多余,1,吨产品。在表,3-4,的,(,A,2,，,B,1),的交叉格处填上,3,。得表,3-5,。并将表,3-3,的,B,1,列运价划去。得表,3-6,。,2.1,确定初始基可行解,表,3-5,和表,3-6,确定初始调运方案（最小元素法）,运价表 产销平衡表,B1,B2,B3,B4,A1,3,11,3,10,A2,1,9,2,8,A3,7,4,10,5,B1,B2,B3,B4,A1,4,3,7,A2,3,1,4,A3,6,3,9,3,6,5,6,2.1,确定初始基可行解,第三步：在表,3-8,未划去的元素中再找出最小运价,3,；这样一步步地进行下去，直到单位运价表上的所有元素划去为止，最后在产销平衡表上得到一个调运方案，见表,3-9,。这方案的总运费为,86,元。,2.1,确定初始基可行解,2.,伏格尔法,最小元素法的缺点是：为了节省一处的费用，有时造成在其他处要多花几倍的运费。伏格尔法考虑到，一产地的产品假如不能按最小运费就近供应，就考虑次小运费，这就有一个差额。差额越大，说明不能按最小运费调运时，运费增加越多。因而对差额最大处，就应当采用最小运费调运。,伏格尔法的步骤是：,第一步,：分别计算出各行和各列的最小运费和次最小运费的差额，并填入该表的最右列和最下行。,第二步,：从行或列差额中选出最大者，选择它所在行或列中的最小元素，确定调运关系，划去单位运价表中相关的行或列。,第三步,：对未划去的元素再分别计算出各行、各列的最小运费和次最小运费的差额，并填入该表的最右列和最下行。重复第一、二步。直到给出初始解为止。,确定初始调运方案（,伏格尔法,）,B1,B2,B3,B4,产量,行罚数,行罚数,行罚数,行罚数,A1,3,11,3,（,5,）,10,（,2,）,7,0,0,0,7,A2,1,（,3,）,9,2,8,（,1,）,4,1,1,1,6,A3,7,4,（,6,）,10,5,（,3,）,9,1,2,销量,3,6,5,6,列罚数,2,5,1,3,列罚数,2,1,3,列罚数,2,1,2,列罚数,1,2,2.1,确定初始基可行解,用此法给出例,1,的初始解列于表,3-13,。,这方案的总运费,=3*1+6*4+5*3+2*10+1*8+3*5=,85,元。,伏格尔法给出的初始解比用最小元素法给出的初始解更接近最优解。,2.2,最优解的判别,判别的方法是计算空格,(,非基变量,),的检验数,c,ij,-C,B,B,-1,P,ij,，,i,j,N,。因运输问题的目标函数是要求实现最小化，故当所有的,c,ij,-C,B,B,-1,P,ij,0,时，为最优解,1.,闭回路法,在给出调运方案的计算表上，从每一空格,(,非基格,),出发，用水平或垂直线向前划，当碰到一数字格,(,基格,),时转,90,后，继续前进，直到回到起始空格为止。闭回路如图所示。,从每一空格出发一定存在和可以找到唯一的闭回路。,2.2,最优解的判别,1.,闭回路法,由各封闭回路可以计算各空格的检验数。它等于其闭回路上奇数点运价与偶数点运价之负值的和,1.,闭回路法,B1,B2,B3,B4,A1,3,11,3,10,A2,1,9,2,8,A3,7,4,10,5,B1,B2,B3,B4,A1,4,3,7,A2,3,1,4,A3,6,3,9,3,6,5,6,运价表 产销平衡表,1.,闭回路法,B1,B2,B3,B4,A1,3,11,3,10,A2,1,9,2,8,A3,7,4,10,5,B1,B2,B3,B4,A1,4,3,7,A2,3,1,4,A3,6,3,9,3,6,5,6,运价表 产销平衡表,1.,闭回路法,B1,B2,B3,B4,A1,3,11,3,10,A2,1,9,2,8,A3,7,4,10,5,B1,B2,B3,B4,A1,4,3,7,A2,3,1,4,A3,6,3,9,3,6,5,6,运价表 产销平衡表,1.,闭回路法,B1,B2,B3,B4,A1,3,11,3,10,A2,1,9,2,8,A3,7,4,10,5,B1,B2,B3,B4,A1,4,3,7,A2,3,1,4,A3,6,3,9,3,6,5,6,运价表 产销平衡表,1.,闭回路法,B1,B2,B3,B4,A1,3,11,3,10,A2,1,9,2,8,A3,7,4,10,5,B1,B2,B3,B4,A1,4,3,7,A2,3,1,4,A3,6,3,9,3,6,5,6,运价表 产销平衡表,1.,闭回路法,B1,B2,B3,B4,A1,3,11,3,10,A2,1,9,2,8,A3,7,4,10,5,B1,B2,B3,B4,A1,4,3,7,A2,3,1,4,A3,6,3,9,3,6,5,6,运价表 产销平衡表,1.,闭回路法,当所有空格检验数 则当前方案是最优的，若,尚有空格检验数小于零，表明当前方案尚有待调整。,具有确切的经济意义，它表示由,Ai,往,Bj,增运,1,单位时，引起的总运输成本的变化数。若所有的空格检验数都大于等于零，表明任何一个空格处调运,1,单位都会引起总成本的上升，这表明当前方案不能再改进，即定为最优方案。,B1,B2,B3,B4,A1,1,2,A2,1,-1,A3,10,12,2.3,改进的方法,闭回路调整法,选则负检验数中最小的检验数,，,（有多个负检验数时，选择绝对值大的一个）,以其对应的空格,(,非基格,),为调入格，相应的非基变量为换入变量,步骤：,第一步，以,x,ij,为换入变量，找到运输表中的闭回路,第二步，以非基格,(,A,i,B,j,),为第一个奇数顶点，沿闭回路对其,顶点依次编号,第三步，闭回路所有偶数顶点中，找出运输量最小的顶点，,该最小运输量为调整量,，该顶点对应的变量为换,出变量,第四步，闭回路所有奇数顶点都加上调整量,，所有偶数顶,点都减去调整量,，得出新的运输方案,上表是例,1,最小元素法得到的初始方案经调整后的结果,B1,B2,B3,B4,A1,3,11,3,10,A2,1,9,2,8,A3,7,4,10,5,B1,B2,B3,B4,A1,5,2,7,A2,3,1,4,A3,6,3,9,3,6,5,6,运价表 产销平衡表,11,=0;,12,=2;,22,=2;,23,=1;,31,=11;,33,=12,2.2,最优解的判别,2.,位势法,用闭回路法求检验数时，需给每一空格找一条闭回路。当产销点很多时，这种计算很繁。下面介绍较为简便的方法,位势法。,（,1,）在有数格上填上相应的运价,2.2,最优解的判别,B1,B2,B3,B4,A1,3,10,A2,1,2,A3,4,5,B1,B2,B3,B4,A1,4,3,7,A2,3,1,4,A3,6,3,9,3,6,5,6,运价表 产销平衡表,2.,位势法,B1,B2,B3,B4,A1,3,10,U1,A2,1,2,U2,A3,4,5,U3,V1,V2,V3,V4,2.,位势法,2.2,最优解的判别,2.2,最优解的判别,（,2,）设,u1=0,然后根据,cij,=,ui+vj,(,有数格,),，依次求得,ui,和,vj,值，并填在相应的位置上。,B1,B2,B3,B4,A1,3,10,U1,0,A2,1,2,U2,-1,A3,4,5,U3,-5,V1,V2,V3,V4,2,9,3,10,2.,位势法,2.2,最优解的判别,计算,ui+vj,表，把,ui+vj,位势和值填在表中相应位置上，并将有数格位置的,ui+vj,值加上括号以示区别。,B1,B2,B3,B4,A1,2,9,（,3,）,（,10,）,U1,0,A2,（,1,）,8,（,2,）,9,U2,-1,A3,-3,（,4,）,-2,（,5,）,U3,-5,V1,V2,V3,V4,2,9,3,10,2.,位势法,（,3,）计算检验数表,B1,B2,B3,B4,A1,3,11,3,10,A2,1,9,2,8,A3,7,4,10,5,运价表,(,C,ij,),（,ui+vj,）表,B1,B2,B3,B4,A1,2,9,（,3,）,（,10,）,U1,0,A2,（,1,）,8,（,2,）,9,U2,-1,A3,-3,（,4,）,-2,（,5,）,U3,-5,V1,V2,V3,V4,2,9,3,10,检验数表,B1,B2,B3,B4,A1,1,2,A2,1,-1,A3,10,12,2.2,最优解的判别,调整方案：若在检验数表上有某空格的检验数为负，则应改进方案，降低成本。调整的方法是从具有负检验数的空格出发（有多个负检验数时，选择绝对值大的一个），沿它的闭回路进行调整，即在方案可行的条件下，尽量增加空格上的运量。,一般说来，调整量为闭回路上偶数顶点格上运量最小数,2.,位势法,检验数表,B1,B2,B3,B4,A1,4,3,7,A2,3,1,4,A3,6,3,9,3,6,5,6,B1,B2,B3,B4,A1,1,2,A2,1,-1,A3,10,12,初始调运方案（最小元素法）,调整后的结果为：,B1,B2,B3,B4,A1,5,2,7,A2,3,0,1,4,A3,6,3,9,3,6,5,6,（,ui+vj,）表,B1,B2,B3,B4,A1,3,9,（,3,）,（,10,）,U1,0,A2,（,1,）,7,1,(8),U2,-2,A3,-2,（,4,）,-2,（,5,）,U3,-5,V1,V2,V3,V4,3,9,3,10,（,ui+vj,）表,B1,B2,B3,B4,A1,3,9,（,3,）,（,10,）,U1,0,A2,（,1,）,7,1,(8),U2,-2,A3,-2,（,4,）,-2,（,5,）,U3,-5,V1,V2,V3,V4,3,9,3,10,运价表,B1,B2,B3,B4,A1,3,11,3,10,A2,1,9,2,8,A3,7,4,10,5,检验数表,B1,B2,B3,B4,A1,0,2,A2,2,1,A3,9,12,2.4,表上作业法计算中的问题,无穷多最优解,在本章,2.1,节中提到，产销平衡的运输问题必定存在最优解。那么有唯一最优解还是无穷多最优解,?,所有变量检验数,0,，某个非基变量,(,非基格,),检验数,=0;,该问题有无穷多最优解。,比如，例,1,最优解，,x,11,检验数为,0,，,可在表中以,(1,，,1),为调入格，作闭回路,确定,=min(2,3)=2,。经调整后得到