第二节表上作业法

1、管理工程学院运筹学运筹学11第二节第二节 表上作业法表上作业法一、表上作业法一、表上作业法(其其实质就是单纯形法实质就是单纯形法)步骤：步骤：确定初始方案确定初始方案判断是否最优判断是否最优调整改进方案调整改进方案否输出最优方案是管理工程学院运筹学运筹学22二、初始方案的确定二、初始方案的确定确定方法要求：方法简单易行、并能给出较确定方法要求：方法简单易行、并能给出较好的方案，减少迭代次数。好的方案，减少迭代次数。1.西北角法：西北角法：此方法是从表的西北角上开始，此方法是从表的西北角上开始，即首先尽量把产地即首先尽量把产地1的物资满足销地的物资满足销地1的要求，的要求，4管理工程学院运筹学运

2、筹学33若产地若产地1有剩余再供应销地有剩余再供应销地2；若销地；若销地1得不得不到满足，则不足的部分由产地到满足，则不足的部分由产地2来供应。以来供应。以后依次类似。这种方法比较简单，但没有考后依次类似。这种方法比较简单，但没有考虑使运价最少的问题。虑使运价最少的问题。2.最小元素法：最小元素法：基本思想是就近供应。即从基本思想是就近供应。即从单位运价表中最小的运价处开始确定供销关单位运价表中最小的运价处开始确定供销关系，依此类推，一直到给出全部方案为止。系，依此类推，一直到给出全部方案为止。5管理工程学院运筹学运筹学44 销地销地产地产地 B1 B2 产量产量 A1 1 6 1 A2 2

3、20 1 销量销量 1 19管理工程学院运筹学运筹学55 销地产地 B1B2B3B4产量 A1 437 A2 314 A3 639销量3656349111023581071不能填不能填4，要，要满足销量要求满足销量要求3+1=4m+n-1=3+4-1=6个数字个数字管理工程学院运筹学运筹学66为一个初始调运方案，总运费为为一个初始调运方案，总运费为86元。元。注注1. 调运方案中，称填写数字处为调运方案中，称填写数字处为数字格数字格，它对应运输问题解中的基变量取值；称不填它对应运输问题解中的基变量取值；称不填数字处为数字处为空格空格，它对应解中非基变量。，它对应解中非基变量。注注2. 运输问题

4、中基变量数一般为运输问题中基变量数一般为(m+n-1)个，个，故调运方案中有数字的格也为故调运方案中有数字的格也为(m+n-1)个。个。管理工程学院运筹学运筹学77 销地产地 B1B2B3B4产量 A1 437 A2 33 A3 639销量36463491110235810710管理工程学院运筹学运筹学88注注3. 当选定最小元素后，发现该元素所在行当选定最小元素后，发现该元素所在行的产地现有产量等于所在列的销地销量，要的产地现有产量等于所在列的销地销量，要在同时划去的该行和该列的任一空格处在同时划去的该行和该列的任一空格处补填补填一个一个“0” 。即每划一下填一数字，即每划一下填一数字，不要

5、漏不要漏掉基变量掉基变量“0”。管理工程学院运筹学运筹学993. Vogel法法(元素差额法元素差额法)。用最小元素法给定用最小元素法给定初始方案只能从局部观点考虑就近供应，划初始方案只能从局部观点考虑就近供应，划去的行或列可能存在次小元素，从而造成总去的行或列可能存在次小元素，从而造成总体的不合理。体的不合理。Vogel法是从运价表中各行和法是从运价表中各行和各列最小和次小元素之差来确定产销关系。各列最小和次小元素之差来确定产销关系。4管理工程学院运筹学运筹学1010Vogel法步骤：法步骤： 在运价表上写出每行和每列运价中最小元素和次在运价表上写出每行和每列运价中最小元素和次小元素之差。小

6、元素之差。 从所有行差额和列差额中选取差额最大的一行或从所有行差额和列差额中选取差额最大的一行或一列进行分配，并对该行一列进行分配，并对该行(或列或列)最小元素格填数，。最小元素格填数，。 重新计算差额，重复上述手续。重新计算差额，重复上述手续。 剩最后一行或一列按余额分配，只填数即可，确剩最后一行或一列按余额分配，只填数即可，确保有数字个数为保有数字个数为m+n-1个。个。管理工程学院运筹学运筹学1111 销地产地B1 B2 B3 B4两个最小元素之差A1A2A33 11 3 101 9 2 87 4 10 5两个最小元素之差0112 5 1 3 0122 1 3 012 1 2 76 1

7、2 销地产地 B1 B2 B3 B4产量 A1 A2 A3 5 23 1 6 3749销量3 6 5 6管理工程学院运筹学运筹学1212三、最优性检验与方案的调整三、最优性检验与方案的调整1.闭回路法。最优性检验：闭回路法。最优性检验：运输问题运输问题 中的中的闭闭回路回路是指调运方案中由一个是指调运方案中由一个空格空格和若干个和若干个有有数字格数字格的水平和垂直连线包围成的封闭回路。的水平和垂直连线包围成的封闭回路。 构建闭回路来计算解中各非基变量构建闭回路来计算解中各非基变量(对应空格对应空格)的检验数。的检验数。管理工程学院运筹学运筹学1313 修正量6563 销 量9 A34 A27

8、A1 修正量产量B4B3B2B1产地产地销地销地31131019287410530 3,40 60 11,4 30 3 3 0 3, 0 0 管理工程学院运筹学运筹学1414（a） （b） （c） （d） （e）14管理工程学院运筹学运筹学1515 销地产地 B1B2B3B4产量 A1 437 A2 314 A3 639销量3656349111023581071+-+-11= c11- c13+ c23-c21 = 3-3+2-1=131= c31- c21+ c23-c31 + c14-c34 = 10管理工程学院运筹学运筹学1616 销地产地B1 B2 B3 B4 A1 A2 A31 2

9、1 -110 1211=1；12=2； 22=1； 24=-1； 31=10； 33=12如何根据检验数的经济意义，判断何时为最优解？管理工程学院运筹学运筹学1717 位势法（对偶变量法）位势法（对偶变量法） 当一个运输问题的产地和销地数很多时，用闭回路法计算检验数计算量很大。位势法是一种比较简单的求检验数的方法。管理工程学院运筹学运筹学1818运输问题（m+n）个约束条件对于（m+n）个对偶变量，设为Y=(u1, , um,v1, , vn) T ，xij的检验数为 )()(,(111jiijjminmijijTijijBijijijijvuceeuvuucPYcPBCczc管理工程学院运筹

10、学运筹学1919步骤：步骤： 单位运价表中，单位运价用cij表示 求行位势ui和列位势vj ，cij= ui+ vj计算检验数ij=cij-(ui+vj)管理工程学院运筹学运筹学202013c21c14c34c A3 A2 A1B4B3B2B1产地产地销地销地311310192874105346133 iujv031 2105 932c23c1211 1012管理工程学院运筹学运筹学21213 3 方案的调整方案的调整闭回路法调整法步骤：闭回路法调整法步骤： 找到mn =minij |ij 0对应的空格找到该空格的闭回路，并从空格开始正、负相间地编号找到标负号处的最小运量1. 在该闭回路的运量

11、上，标正号处加 ，标负号处减管理工程学院运筹学运筹学2222 销地产地 B1B2B3B4产量 A1 437 A2 314 A3 639销量3656349111023581071+-+-管理工程学院运筹学运筹学2323 销地产地 B1B2B3B4产量 A1 527 A2 3 14 A3 639销量3656 349111023581071管理工程学院运筹学运筹学2424 注意：闭回路调整中的问题注意：闭回路调整中的问题 比如比如+-+-232=2052052管理工程学院运筹学运筹学2525 比如比如+-+-032=0230管理工程学院运筹学运筹学2626四、表上作业法求解运输问题的步骤框图四、表上

12、作业法求解运输问题的步骤框图分析实际问题列出分析实际问题列出产销平衡表及单位运价表产销平衡表及单位运价表确定初始调运方案确定初始调运方案(最小元素法或最小元素法或Vogel法法)求检验数求检验数(闭回路法或位势法闭回路法或位势法)所有检验数所有检验数0否否找出绝对值最大的负检验数找出绝对值最大的负检验数再用闭回路调整，再用闭回路调整，得出新的调运方案得出新的调运方案是是得到最优方案得到最优方案得出总的运价得出总的运价图图3-1 表上作业法表上作业法计算步骤框图计算步骤框图管理工程学院运筹学运筹学2727例例1 解：解：步步1，用最小元素法求出初始方案如下表所示：，用最小元素法求出初始方案如下表

13、所示： 修正量6563 销 量9 A34 A27 A1 修正量产量B4B3B2B1产地产地销地销地31131019287410530 3,40 60 11,4 30 3 3 0 3, 0 0 管理工程学院运筹学运筹学2828步步2，用位势法求出上述方案的检验数如下表所示：，用位势法求出上述方案的检验数如下表所示：13c21c14c34c A3 A2 A1B4B3B2B1产地产地销地销地311310192874105346133 iujv031 2105 932c23c1211 1012管理工程学院运筹学运筹学2929步步3，用闭回路调整方案得到新的方案，并用位势法求检验，用闭回路调整方案得到新的方案，并用位势法求检验数如下表：数如下表：1441 A3 A2 A1B4B3B2B1产地产地销地销地311310928710536133 iujv031 2105 9121 10124-230310