运输问题表上作业法.pptx

表上作业法表上作业法是一类比较特殊的单纯形法。它必须首先确定一个初始方案，也就是找出一个基可行解，然后根据判别准则来检查这个初始方案是不是最优的，如果不是最优的，那么对初始方案加以改进，直到找出最优方案。表上作业法与单纯形法之间的关系：1、表上作业法中的最小元素法和伏格尔法实质上是在求单纯形表中的初始基可行解；2、表上作业法中的“位势法”实质上是在求单纯形表中的检验数；3、调运方案表中数字格的数实质上就是单纯形法中基变量的值；4、调运方案表上的“闭回路法”实质上是在做单纯形表上的换基迭代。确定初始方案确定初始方案(初初始始基基本本可可行行解解)改进调整改进调整（换基迭代）（换基迭代）否否 判定是否判定是否 最最 优？优？是是结结 束束最优方案最优方案表上作业法求解运输问题思路图表上作业法求解运输问题思路图表上作业法步骤：1、找出初始可行解，用最小元素法、西北角法与伏格尔法。2、求出各非基变量的检验数，判别是否达到最优解。如果是停止计算，否则转入下一步。3、改进当前的基本可行解(确定换入、换出变量)，用闭合回路法与位势法调整;4、重复2、3步骤，直到找到最优解为止。1 1、分别、分别使用最小元素法和西北角法求出初始方案。使用最小元素法和西北角法求出初始方案。&最小元素法的基本思想是“就近供应”；&西北角法则不考虑运距（或运价），每次都选剩余表格的左上角（即西北角）元素作为基变量，其它过程与最小元素法相同；&伏格法尔法每次从当前运价表上，计算各行各列中两个最小运价之差值（行差值hi，列差值kj），优先取最大差值的行或列中最小的格来确定运输关系，直到求出初始方案；1、找出最小运价，确定供求关系，最大量的供应；2、划掉已满足要求的行或(和)列，如果需要同时划去行和列，必须要在该行或列的任意位置填个“0”；3、在剩余的运价表中重复1、2两步，直到得到初始基可行解。最小最小元素法的基本步骤元素法的基本步骤B1B2B3B4产量（产量（ai）A13113107A219284A3741059销量（销量（bj）3656例：例：B1B2B3B4产量（产量（ai）A13113107A219284A3741059销量（销量（bj）3656从表中找出最小运价“1”，最小运价所确定的供应关系为（A2，B1），在（A2，B1）的交叉格处填上“3”，并同时划去B1这一列。3B1B2B3B4产量（产量（ai）A13113107A219284A3741059销量（销量（bj）3656在表的未被划掉的元素中再找出最小运价“2”，最小运价所确定的供应关系为（A2，B3），即将A2余下的1个单位产品供应给B3，划去A2行的运价，划去A2行表明A2所生产的产品已全部运出。31B1B2B3B4产量（产量（ai）A13113 410 37A21 392 18 4A374 6105 39销量（销量（bj）3 3656这样一步步地进行下去，直到单位运价表上的所有元素均被划去为止。得到最终方案，见下表。最终方案：13+46+34+21+103+53=86|最后在产销平衡表上得到一个调运方案，这一方案的总运费为86个单位。|最小元素法各步在运价表中划掉的行或列是需求得到满足的列或产品被调空的行。一般情况下，每填入一个数相应地划掉一行或一列，这样最终将得到一个具有m+n-1个数字格（基变量）的初始基可行解。在供需关系格（i，j）处填入一数字，刚好使第 i个产地的产品调空，同时也使第j个销地的需求得到满足。填入一数字同时划去了一行和一列，那么最终必然无法得到一个具有m+n-1个数字格（基变量）的初始基可行解。应应注意的问题注意的问题 为了使在产销平衡表上有m+n-1个数字格，这时需要在第行或第列此前未被划掉的任意一个空格上填一个“0”。填“0”格虽然所反映的运输量同空格没有什么不同；但它所对应的变量却是基变量，而空格所对应的变量是非基变量。调 销地 运 量产地 B1 B2 B3 产 量 A1 90 X11 70 X12 100 X13 200 A2 80 X21 65 X22 75 X23 250 销 量 100 150 200 450 用西北角法确定初始调运方案用西北角法确定初始调运方案 100100100 50 50200200 得到初始调运方案为：得到初始调运方案为：x11=100，x12=100，x22=50，x23=200 伏格尔法的基本步骤：伏格尔法的基本步骤：伏格尔法伏格尔法1.计算每行、列两个最小运价的差；2.找出最大差所在的行或列；3.找出该行或列的最小运价，确定供求关系，最大量的供应；4.划掉已满足要求的行或(和)列，如果需要同时划去行和列，必须要在该行或列的任意位置填个“0”；5.在剩余的运价表中重复14步，直到得到初始基可行解。表表4-1B1B2B3B4产量（产量（ai）A13113107A219284A3741059销量（销量（b bj j）3656计算各行各列的两最小元素差。计算各行各列的两最小元素差。B1B2B3B4两最小元素之差两最小元素之差(R1)A1311310A21928A374105两最小元素之差两最小元素之差(C1)1301125选出差额的最大值选出差额的最大值5 5，选择它所在，选择它所在B2B2中最小元素中最小元素4 4，可确定，可确定A3A3的产品先供应给的产品先供应给B2B2，及把及把B2B2的销量的销量6 6全部给全部给A3B2A3B2。同时将运价表。同时将运价表B2B2列数字划去。列数字划去。B1B1B2B2B3B3B4B4产量产量R1R1A1A13 311113 310107 70 0A2A21 19 92 28 84 41 1A3A37 74 410105 59 91 1销量销量3 36 65 56 6C1C12 25 51 13 36分别计算出各行和各列的最小元素和次最小元素的差额,并填入该表的最右列(R2)和最下行(C2),其中最大者为3，所在的列B4，而列B4中A3为最小元素，A3的总产量为9，因上面已经给B2分配了6，所以B4分配3，即A3B4=（5*3）,把A3列划去。(注意：A3的产量是9，B2只分配了6，没分完，继续分给B4的3)B1B1B2B2B3B3B4B4产量产量R1R1R2R2A1A13 311113 310107 70 00A2A21 19 92 28 84 41 11A3A37 74 410105 59 91 12销量销量3 36 65 56 6C1C12 25 51 13 3C2201363按照以上的方法，可得出最终方案。按照以上的方法，可得出最终方案。B1B1B2B2B3B3B4B4产量产量R1R1R2R2R3R3R4R4A1A13 311113 310107 70 0007A2A21 19 92 28 84 41 1116A3A37 74 410105 59 91 12-销量销量3 36 65 56 6C1C12 25 51 13 3C22-13C32-12C4-12633521（4*6）+（5*3）+（1*3）+（3*5）+(10*2)+(8*1)=85对于每一个非基变量（空格）都对应一个检验数，对于每一个非基变量（空格）都对应一个检验数，则有以下最优性准则：则有以下最优性准则：为了说明如何在表上作业法的过程中求出非基变量为了说明如何在表上作业法的过程中求出非基变量的检验数，下面介绍闭回路的概念。的检验数，下面介绍闭回路的概念。2 2、求、求检验数、最优性判别检验数、最优性判别例例 某种物资有某种物资有3 3个产地、个产地、4 4个销地，各产地的产量、销地的销量个销地，各产地的产量、销地的销量以及各产销地之间的运价如表以及各产销地之间的运价如表2-12-1，求最优的调运方案。，求最优的调运方案。表表 运输问题的平衡表与运价表运输问题的平衡表与运价表表中表中,有数字的格子有数字的格子(包括包括0)0)对应的是基变量对应的是基变量,空格所对应的空格所对应的变量是非基变量。变量是非基变量。平衡表运价表B1B2B3B4发量B1B2B3B4A13146534A22464475A30337658收量243413检验数检验数闭回路：闭回路：在调运方案中，从一个空格出发，沿水平或垂直方在调运方案中，从一个空格出发，沿水平或垂直方向前进，遇到一个适当的有数字的格子，则转向向前进，遇到一个适当的有数字的格子，则转向9090前进，前进，这样必会又遇到一个适当的有数字的格子，同样再转向这样必会又遇到一个适当的有数字的格子，同样再转向9090前进；经若干次后，必然会回到出发的那个空格，这样就形前进；经若干次后，必然会回到出发的那个空格，这样就形成一条由水平与垂直线构成的封闭折线，我们称这样的封闭成一条由水平与垂直线构成的封闭折线，我们称这样的封闭折线为该空格的闭回路。该空格（非基变量）对应的检验数折线为该空格的闭回路。该空格（非基变量）对应的检验数就等于该闭回路上所有偶次拐点的运价之和减去所有奇次拐就等于该闭回路上所有偶次拐点的运价之和减去所有奇次拐点的运价之和。点的运价之和。闭回路闭回路:闭回路闭回路:检验数检验数在例在例1 1中：中：闭回路闭回路:检验数检验数闭回路闭回路:检验数检验数闭回路闭回路:检验数检验数闭回路闭回路:检验数检验数我们我们也可以用位势法来求检验数。也可以用位势法来求检验数。位势法：位势法：将运价表中将运价表中基变量基变量所对应的运价打所对应的运价打“*”“*”号号或者将数字画圈或者将数字画圈“”“”，然后对运价表每一行、每，然后对运价表每一行、每一列同时加上或减去同一个数，当基变量对应的检一列同时加上或减去同一个数，当基变量对应的检验数（打验数（打“*”“*”号的或画圈号的或画圈“”“”的）的）等于零等于零，其余，其余各数就是各个非基变量所对应的检验数。各数就是各个非基变量所对应的检验数。对例对例1 1，采用位势法求检验数过程如下，采用位势法求检验数过程如下最后的数阵中没有标记最后的数阵中没有标记*的数字就是的数字就是非基变量的检验数。非基变量的检验数。从一个可行方案调整到另一个可行方案从一个可行方案调整到另一个可行方案,也就是从一个基也就是从一个基可行解换基迭代到另一个基可行解可行解换基迭代到另一个基可行解,且使目标函数值不断且使目标函数值不断下降。运输问题表上作业法的换基迭代实际上是在调运表下降。运输问题表上作业法的换基迭代实际上是在调运表上上负检验数对应的空格负检验数对应的空格所在的闭回路上进行的所在的闭回路上进行的.3 3、求、求出调整量、在闭回路上进行调整出调整量、在闭回路上进行调整调整量调整量：该闭回路上所有奇次拐点调运量的最小值。：该闭回路上所有奇次拐点调运量的最小值。调整方法：调整方法：闭回路上每个闭回路上每个奇次奇次拐点拐点的调运量的调运量都减去调整量都减去调整量 (其中有一个且其中有一个且仅允许有一个仅允许有一个调运量为调运量为0 0变为变为空格空格成为非基变成为非基变量，其他变为量，其他变为0 0的仍然要填上的仍然要填上0)0)，各偶次拐点的调运量均加，各偶次拐点的调运量均加上调整量，其中有一个由非基变量上调整量，其中有一个由非基变量(空格空格)变为基变量。变为基变量。对例对例1，取，取表表2-3 2-3 运输问题调运方案调整表运输问题调运方案调整表B1B2B3B4发量B1B2B3B4A131431A224-3+36213A30+33-333收量243413使用位势法求检验数，过程如下：使用位势法求检验数，过程如下：有检验数有检验数l l33 33=-10,=-10,继续调整继续调整,取取表表2-4 2-4 运输问题调运方案调整表运输问题调运方案调整表B1B2B3B4发量B1B2B3B4A13-3 1+3 44A221+3 3-36240A33-3+3 303收量243413注意注意：这里经调整以后，有：这里经调整以后，有3 3个基变量个基变量x x1313,x x2424,x x3131同时变为同时变为零！但零！但只能有一个只能有一个x x1313成为非基变量成为非基变量(空格空格)，另外两个，另外两个x x2424,x x3131仍为基变量，其对应的调运量等于仍为基变量，其对应的调运量等于0 0。继续求检验数：继续求检验数：此时所有检验数全部非负，因此对应的调运方案是最优的。此时所有检验数全部非负，因此对应的调运方案是最优的。min Z=44+24+44+35=55。使用表上作业法，有以下特殊情况需要注意使用表上作业法，有以下特殊情况需要注意在用最小元素法作初始调运方案时，在用最小元素法作初始调运方案时，当出现供需相等时，当出现供需相等时，这时可以这时可以(也只能也只能)满足一家！另一家供满足一家！另一家供(需需)量相应地改为量相应地改为0 0；在下一次供应时，在下一次供应时，0 0也要进行供应或需求也要进行供应或需求(如例如例1 1用最小元素用最小元素法作初始调运方案法作初始调运方案)。在方案的调整过程中，在方案的调整过程中，若奇次拐点的调运量有不止一个等若奇次拐点的调运量有不止一个等于调整量，调整以后，有几个同时变为于调整量，调整以后，有几个同时变为0 0，这时只允许一个，这时只允许一个变为空格成为非基变量，其余的仍为基变量，对应的调运量变为空格成为非基变量，其余的仍为基变量，对应的调运量等于等于0 0，不能是空格。，不能是空格。（如例（如例1 1，方案的调整），方案的调整）在方案的调整过程中在方案的调整过程中，如果调整量等于如果调整量等于0 0，这时也要作形，这时也要作形式上的调整，只是式上的调整，只是0 0与空格的位置互换与空格的位置互换罢了。罢了。谢谢观赏