《表上作业法.PPT》由会员分享，可在线阅读，更多相关《表上作业法.PPT（30页珍藏版）》请在金锄头文库上搜索。
1、管理工程学院运筹学运筹学1第二节第二节 表上作业法表上作业法一、表上作业法一、表上作业法(其其实质就是单纯形法实质就是单纯形法)步骤：步骤：确定初始方案确定初始方案判断是否最优判断是否最优调整改进方案调整改进方案否输出最优方案是1管理工程学院运筹学运筹学2二、初始方案的确定二、初始方案的确定确定方法要求：方法简单易行、并能给出较确定方法要求：方法简单易行、并能给出较好的方案，减少迭代次数。好的方案，减少迭代次数。1.西北角法：西北角法：此方法是从表的西北角上开始，此方法是从表的西北角上开始，即首先尽量把产地即首先尽量把产地1的物资满足销地的物资满足销地1的要求，的要求，42管理工程学院运筹学运
2、筹学3若产地若产地1有剩余再供应销地有剩余再供应销地2；若销地；若销地1得不得不到满足，则不足的部分由产地到满足，则不足的部分由产地2来供应。以来供应。以后依次类似。这种方法比较简单，但没有考后依次类似。这种方法比较简单，但没有考虑使运价最少的问题。虑使运价最少的问题。2.最小元素法：最小元素法：基本思想是就近供应。即从基本思想是就近供应。即从单位运价表中最小的运价处开始确定供销关单位运价表中最小的运价处开始确定供销关系，依此类推，一直到给出全部方案为止。系，依此类推，一直到给出全部方案为止。53管理工程学院运筹学运筹学4 销地销地产地产地 B1 B2 产量产量 A1 1 6 1 A2 2 2
3、0 1 销量销量 1 194管理工程学院运筹学运筹学5 销地产地 B1B2B3B4产量 A1 437 A2 314 A3 639销量3656349111023581071不能填不能填4，要，要满足销量要求满足销量要求3+1=4m+n-1=3+4-1=6个数字个数字5管理工程学院运筹学运筹学6为一个初始调运方案，总运费为为一个初始调运方案，总运费为86元。元。注注1. 调运方案中，称填写数字处为调运方案中，称填写数字处为数字格数字格，它对应运输问题解中的基变量取值；称不填它对应运输问题解中的基变量取值；称不填数字处为数字处为空格空格，它对应解中非基变量。，它对应解中非基变量。注注2. 运输问题中
4、基变量数一般为运输问题中基变量数一般为(m+n-1)个，个，故调运方案中有数字的格也为故调运方案中有数字的格也为(m+n-1)个。个。6管理工程学院运筹学运筹学7 销地产地 B1B2B3B4产量 A1 437 A2 33 A3 639销量364634911102358107107管理工程学院运筹学运筹学8注注3. 当选定最小元素后，发现该元素所在行当选定最小元素后，发现该元素所在行的产地现有产量等于所在列的销地销量，要的产地现有产量等于所在列的销地销量，要在同时划去的该行和该列的任一空格处在同时划去的该行和该列的任一空格处补填补填一个一个“0” 。即每划一下填一数字，即每划一下填一数字，不要漏
5、掉不要漏掉基变量基变量“0”。8管理工程学院运筹学运筹学93. Vogel法法(元素差额法元素差额法)。用最小元素法给定用最小元素法给定初始方案只能从局部观点考虑就近供应，划初始方案只能从局部观点考虑就近供应，划去的行或列可能存在次小元素，从而造成总去的行或列可能存在次小元素，从而造成总体的不合理。体的不合理。Vogel法是从运价表中各行和法是从运价表中各行和各列最小和次小元素之差来确定产销关系。各列最小和次小元素之差来确定产销关系。49管理工程学院运筹学运筹学10Vogel法步骤：法步骤： 在运价表上写出每行和每列运价中最小元素和次在运价表上写出每行和每列运价中最小元素和次小元素之差。小元素
6、之差。 从所有行差额和列差额中选取差额最大的一行或从所有行差额和列差额中选取差额最大的一行或一列进行分配，并对该行一列进行分配，并对该行(或列或列)最小元素格填数，。最小元素格填数，。 重新计算差额，重复上述手续。重新计算差额，重复上述手续。 剩最后一行或一列按余额分配，只填数即可，确剩最后一行或一列按余额分配，只填数即可，确保有数字个数为保有数字个数为m+n-1个。个。10管理工程学院运筹学运筹学11 销地产地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 2
7、销地产地 B1 B2 B3 B4产量 A1 A2 A3 5 23 1 6 3749销量3 6 5 611管理工程学院运筹学运筹学12三、最优性检验与方案的调整三、最优性检验与方案的调整1.闭回路法。最优性检验：闭回路法。最优性检验：运输问题运输问题 中的中的闭闭回路回路是指调运方案中由一个是指调运方案中由一个空格空格和若干个和若干个有有数字格数字格的水平和垂直连线包围成的封闭回路。的水平和垂直连线包围成的封闭回路。 构建闭回路来计算解中各非基变量构建闭回路来计算解中各非基变量(对应空格对应空格)的检验数。的检验数。12管理工程学院运筹学运筹学13 修正量6563 销 量9 A34 A27 A1
8、 修正量产量B4B3B2B1产地产地销地销地31131019287410530 3,40 60 11,4 30 3 3 0 3, 0 0 13管理工程学院运筹学运筹学14（a） （b） （c） （d） （e）1414管理工程学院运筹学运筹学15 销地产地 B1B2B3B4产量 A1 437 A2 314 A3 639销量3656349111023581071+-+-11= c11- c13+ c23-c21 = 3-3+2-1=131= c31- c21+ c23-c31 + c14-c34 = 1015管理工程学院运筹学运筹学16 销地产地B1 B2 B3 B4 A1 A2 A31 2 1
9、-110 1211=1；12=2； 22=1； 24=-1； 31=10； 33=12如何根据检验数的经济意义，判断何时为最优解？16管理工程学院运筹学运筹学172.2.位势法（对偶变量法）位势法（对偶变量法）3. 当一个运输问题的产地和销地数很多时，用闭回路法计算检验数计算量很大。位势法是一种比较简单的求检验数的方法。17管理工程学院运筹学运筹学18运输问题（m+n）个约束条件对于（m+n）个对偶变量，设为Y=(u1, , um,v1, , vn) T ，xij的检验数为 18管理工程学院运筹学运筹学19步骤：步骤：单位运价表中，单位运价用cij表示求行位势ui和列位势vj ，cij= ui
10、+ vj计算检验数ij=cij-(ui+vj)19管理工程学院运筹学运筹学20 A3 A2 A1B4B3B2B1产地产地销地销地311310192874105346133 20管理工程学院运筹学运筹学213 3 方案的调整方案的调整闭回路法调整法步骤：闭回路法调整法步骤：1.找到mn =minij |ij 0对应的空格2.找到该空格的闭回路，并从空格开始正、负相3.间地编号3.找到标负号处的最小运量4.在该闭回路的运量上，标正号处加 ，标负号处减21管理工程学院运筹学运筹学22 销地产地 B1B2B3B4产量 A1 437 A2 314 A3 639销量3656349111023581071+
11、-+-22管理工程学院运筹学运筹学23 销地产地 B1B2B3B4产量 A1 527 A2 3 14 A3 639销量3656 34911102358107123管理工程学院运筹学运筹学241.1.注意：闭回路调整中的问题注意：闭回路调整中的问题比如比如+-+-232=205205224管理工程学院运筹学运筹学25比如比如+-+-032=023025管理工程学院运筹学运筹学26四、表上作业法求解运输问题的步骤框图四、表上作业法求解运输问题的步骤框图分析实际问题列出分析实际问题列出产销平衡表及单位运价表产销平衡表及单位运价表确定初始调运方案确定初始调运方案(最小元素法或最小元素法或Vogel法法
12、)求检验数求检验数(闭回路法或位势法闭回路法或位势法)所有检验数所有检验数0否否找出绝对值最大的负检验数找出绝对值最大的负检验数再用闭回路调整，再用闭回路调整，得出新的调运方案得出新的调运方案是是得到最优方案得到最优方案得出总的运价得出总的运价图图3-1 表上作业法表上作业法计算步骤框图计算步骤框图26管理工程学院运筹学运筹学27例例1 解：解：步步1，用最小元素法求出初始方案如下表所示：，用最小元素法求出初始方案如下表所示： 修正量6563 销 量9 A34 A27 A1 修正量产量B4B3B2B1产地产地销地销地31131019287410530 3,40 60 11,4 30 3 3 0
13、 3, 0 0 27管理工程学院运筹学运筹学28步步2，用位势法求出上述方案的检验数如下表所示：，用位势法求出上述方案的检验数如下表所示： A3 A2 A1B4B3B2B1产地产地销地销地311310192874105346133 28管理工程学院运筹学运筹学29步步3，用闭回路调整方案得到新的方案，并用位势法求检验，用闭回路调整方案得到新的方案，并用位势法求检验数如下表：数如下表：144 A3 A2 A1B4B3B2B1产地产地销地销地311310928710536133 4-230310-591250221912由表中可知所有非基变量的检验数都大于由表中可知所有非基变量的检验数都大于0，所以表中方案，所以表中方案就是最优方案，即：就是最优方案，即：(把最优方案和最小运费写出把最优方案和最小运费写出)29管理工程学院运筹学运筹学301 A3 A2 A1B4B3B2B1产地产地销地销地3113101928741053632 2051192031五五. .如何找多个最优方案如何找多个最优方案 30
