运输问题表上作业法PPT课件

表上作业法,1,-,表上作业法是一类比较特殊的单纯形法。它必须首先确定一个初始方案，也就是找出一个基可行解，然后根据判别准则来检查这个初始方案是不是最优的，如果不是最优的，那么对初始方案加以改进，直到找出最优方案。,表上作业法与单纯形法之间的关系：1、表上作业法中的最小元素法和伏格尔法实质上是在求单纯形表中的初始基可行解；2、表上作业法中的“位势法”实质上是在求单纯形表中的检验数；3、调运方案表中数字格的数实质上就是单纯形法中基变量的值；4、调运方案表上的“闭回路法”实质上是在做单纯形表上的换基迭代。,2,-,表上作业法求解运输问题思路图,3,-,表上作业法步骤：1、找出初始可行解，用最小元素法、西北角法与伏格尔法。2、求出各非基变量的检验数，判别是否达到最优解。如果是停止计算，否则转入下一步。3、改进当前的基本可行解(确定换入、换出变量)，用闭合回路法与位势法调整;4、重复2、3步骤，直到找到最优解为止。,4,-,1、分别使用最小元素法和西北角法求出初始方案。&最小元素法的基本思想是“就近供应”；&西北角法则不考虑运距（或运价），每次都选剩余表格的左上角（即西北角）元素作为基变量，其它过程与最小元素法相同；&伏格法尔法每次从当前运价表上，计算各行各列中两个最小运价之差值（行差值hi，列差值kj），优先取最大差值的行或列中最小的格来确定运输关系，直到求出初始方案；,5,-,1、找出最小运价，确定供求关系，最大量的供应；2、划掉已满足要求的行或(和)列，如果需要同时划去行和列，必须要在该行或列的任意位置填个“0”；3、在剩余的运价表中重复1、2两步，直到得到初始基可行解。,最小元素法的基本步骤,6,-,例：,7,-,从表中找出最小运价“1”，最小运价所确定的供应关系为（A2，B1），在（A2，B1）的交叉格处填上“3”，并同时划去B1这一列。,3,8,-,在表的未被划掉的元素中再找出最小运价“2”，最小运价所确定的供应关系为（A2，B3），即将A2余下的1个单位产品供应给B3，划去A2行的运价，划去A2行表明A2所生产的产品已全部运出。,3,1,9,-,这样一步步地进行下去，直到单位运价表上的所有元素均被划去为止。得到最终方案，见下表。,10,-,最后在产销平衡表上得到一个调运方案，这一方案的总运费为86个单位。,最小元素法各步在运价表中划掉的行或列是需求得到满足的列或产品被调空的行。一般情况下，每填入一个数相应地划掉一行或一列，这样最终将得到一个具有m+n-1个数字格（基变量）的初始基可行解。,11,-,在供需关系格（i，j）处填入一数字，刚好使第i个产地的产品调空，同时也使第j个销地的需求得到满足。填入一数字同时划去了一行和一列，那么最终必然无法得到一个具有m+n-1个数字格（基变量）的初始基可行解。,应注意的问题,为了使在产销平衡表上有m+n-1个数字格，这时需要在第行或第列此前未被划掉的任意一个空格上填一个“0”。填“0”格虽然所反映的运输量同空格没有什么不同；但它所对应的变量却是基变量，而空格所对应的变量是非基变量。,12,-,用西北角法确定初始调运方案,100,100,100,50,50,200,200,13,-,得到初始调运方案为：x11=100，x12=100，x22=50，x23=200,14,-,伏格尔法的基本步骤：,伏格尔法,1.计算每行、列两个最小运价的差；2.找出最大差所在的行或列；3.找出该行或列的最小运价，确定供求关系，最大量的供应；4.划掉已满足要求的行或(和)列，如果需要同时划去行和列，必须要在该行或列的任意位置填个“0”；5.在剩余的运价表中重复14步，直到得到初始基可行解。,15,-,表4-1,计算各行各列的两最小元素差。,1,3,0,1,1,2,5,16,-,选出差额的最大值5，选择它所在B2中最小元素4，可确定A3的产品先供应给B2，及把B2的销量6全部给A3B2。同时将运价表B2列数字划去。,6,17,-,分别计算出各行和各列的最小元素和次最小元素的差额,并填入该表的最右列(R2)和最下行(C2),其中最大者为3，所在的列B4，而列B4中A3为最小元素，A3的总产量为9，因上面已经给B2分配了6，所以B4分配3，即A3B4=（5*3）,把A3列划去。(注意：A3的产量是9，B2只分配了6，没分完，继续分给B4的3),6,3,18,-,按照以上的方法，可得出最终方案。,6,3,3,5,2,1,（4*6）+（5*3）+（1*3）+（3*5）+(10*2)+(8*1)=85,19,-,对于每一个非基变量（空格）都对应一个检验数，则有以下最优性准则：,为了说明如何在表上作业法的过程中求出非基变量的检验数，下面介绍闭回路的概念。,2、求检验数、最优性判别,20,-,例某种物资有3个产地、4个销地，各产地的产量、销地的销量以及各产销地之间的运价如表2-1，求最优的调运方案。,表运输问题的平衡表与运价表,表中,有数字的格子(包括0)对应的是基变量,空格所对应的变量是非基变量。,21,-,检验数,闭回路：在调运方案中，从一个空格出发，沿水平或垂直方向前进，遇到一个适当的有数字的格子，则转向90前进，这样必会又遇到一个适当的有数字的格子，同样再转向90前进；经若干次后，必然会回到出发的那个空格，这样就形成一条由水平与垂直线构成的封闭折线，我们称这样的封闭折线为该空格的闭回路。该空格（非基变量）对应的检验数就等于该闭回路上所有偶次拐点的运价之和减去所有奇次拐点的运价之和。,闭回路:,闭回路:,检验数,在例1中：,22,-,闭回路:,检验数,闭回路:,检验数,闭回路:,检验数,闭回路:,检验数,我们也可以用位势法来求检验数。,23,-,位势法：将运价表中基变量所对应的运价打“*”号或者将数字画圈“”，然后对运价表每一行、每一列同时加上或减去同一个数，当基变量对应的检验数（打“*”号的或画圈“”的）等于零，其余各数就是各个非基变量所对应的检验数。,对例1，采用位势法求检验数过程如下,最后的数阵中没有标记*的数字就是非基变量的检验数。,24,-,从一个可行方案调整到另一个可行方案,也就是从一个基可行解换基迭代到另一个基可行解,且使目标函数值不断下降。运输问题表上作业法的换基迭代实际上是在调运表上负检验数对应的空格所在的闭回路上进行的.,3、求出调整量、在闭回路上进行调整,调整量：该闭回路上所有奇次拐点调运量的最小值。,25,-,调整方法：闭回路上每个奇次拐点的调运量都减去调整量(其中有一个且仅允许有一个调运量为0变为空格成为非基变量，其他变为0的仍然要填上0)，各偶次拐点的调运量均加上调整量，其中有一个由非基变量(空格)变为基变量。,对例1，取,表2-3运输问题调运方案调整表,26,-,使用位势法求检验数，过程如下：,有检验数l33=-10,继续调整,取,表2-4运输问题调运方案调整表,27,-,注意：这里经调整以后，有3个基变量x13,x24,x31同时变为零！但只能有一个x13成为非基变量(空格)，另外两个x24,x31仍为基变量，其对应的调运量等于0。,继续求检验数：,此时所有检验数全部非负，因此对应的调运方案是最优的。,minZ=44+24+44+35=55。,28,-,使用表上作业法，有以下特殊情况需要注意,在用最小元素法作初始调运方案时，当出现供需相等时，这时可以(也只能)满足一家！另一家供(需)量相应地改为0；在下一次供应时，0也要进行供应或需求(如例1用最小元素法作初始调运方案