4.2表上作业法

1、 4.1 运输问题的数学模型运输问题的数学模型 4.2 表上作业法表上作业法 4.3 产销不平衡的运输问题及其求解方法产销不平衡的运输问题及其求解方法 4.4 应用举例应用举例Page 3Page 4 表上作业法是一种求解运输问题的特殊方法，其实质是单纯形法。可归纳为：步骤描述方法第一步求初始基可行解（初始调运方案），即在产销平衡表中给出m+n-1m+n-1个数字格。最小元素法元素差额法第二步求非基变量（空格）的检验数并判断是否得到最优解。若已得最优解，停止计算，否则转第三步。闭回路法位势法第三步换基，对原运量进行调整得到新的基可行解，转入第二步闭回路法4.2 表上作业法表上作业法Page 5

2、例4.2 某公司经销甲产品，运输资料如下表所示：单位 销地 运价 产地产量3 311113 310107 71 19 92 28 84 47 74 410105 59 9销量3 36 65 56 64321 BBBB321AAA问：在满足各销售点的需要量的前提下，应如何调运可使总运输费用最小？4.2 表上作业法表上作业法Page 6方法方法1：最小元素法：最小元素法 基本思想是就近供应，即从运价最小的地方开始调运，基本思想是就近供应，即从运价最小的地方开始调运，然后次小，直到最后供完为止。然后次小，直到最后供完为止。B1B2B3B4产量A17A2 4A39销量36563113101927410

3、583416334.2 表上作业法表上作业法Page 7总运输费总运输费(3(31)+(61)+(64)+(44)+(43)+(13)+(12)+(32)+(310)+(310)+(35)5) =86 =86元元方法方法2 2：VogelVogel法法( (伏格尔法伏格尔法) )或元素差额法或元素差额法 元素差额法对最小元素法进行了改进，考虑到产地到销元素差额法对最小元素法进行了改进，考虑到产地到销地的最小运价和次小运价之间的差额，如果差额很大，就选地的最小运价和次小运价之间的差额，如果差额很大，就选最小运价先调运，否则会增加总运费。例如下面两种运输方最小运价先调运，否则会增加总运费。例如下面

4、两种运输方案。案。85102120151515510总运费总运费=108+52+151=105最小元素法：最小元素法：4.2 表上作业法表上作业法Page 885102120151551510总运费总运费=105+152+51=85后一种方案考虑到后一种方案考虑到C1111与与C2121之间的之间的差额是差额是82=6，如果不先调运如果不先调运x21，就有可能就有可能x111100，这样会使总运费这样会使总运费增加较大，从而先调运增加较大，从而先调运x2121，再是再是x2222，其次是其次是x1212伏格尔法给出的初始解比用最小元素法给出伏格尔法给出的初始解比用最小元素法给出的初始解更接近最

5、优解。的初始解更接近最优解。4.2 表上作业法表上作业法Page 9（1 1）从运价表中分别计算出各行和各列的最小运费和次最小）从运价表中分别计算出各行和各列的最小运费和次最小运费的差额，并填入该表的最右列和最下行。运费的差额，并填入该表的最右列和最下行。4.2 表上作业法表上作业法单位 销地 运价 产地A1A2A3A4产量产量行差额行差额B1311 31070B21 9 2 841B37 410 591销量销量3656列差额列差额2513Page 10（2 2）再从行或列差额中选出最大的行或列，找出最小运价）再从行或列差额中选出最大的行或列，找出最小运价确定供需数量。当产地或销地中有一方数量

6、供应完或得到确定供需数量。当产地或销地中有一方数量供应完或得到满足时，划去运价表中对应的行或列。重复（满足时，划去运价表中对应的行或列。重复（1)1)和（和（2)2)，直到找出初始解为至。直到找出初始解为至。4.2 表上作业法表上作业法Page 11单位 销地 运价 产地产量行差额311 31071 9 2 847 410 59销量3656列差额4321 BBBB321AAA011352164.2 表上作业法表上作业法Page 12单位 销地 运价 产地产量行差额311310719284741059销量3656列差额4321 BBBB321AAA023121634.2 表上作业法表上作业法Pa

7、ge 13单位 销地 运价 产地产量行差额311310719284741059销量3656列差额4321 BBBB321AAA022136314.2 表上作业法表上作业法Page 14单位 销地 运价 产地产量行差额311 31071 9 2847 41059销量3656列差额4321 BBBB321AAA7263631521该方案的总运费该方案的总运费:(1:(13)3)(4(46)6)(3(35)5)(2(210)10)(1(18)8)(3(35)5)8585元元4.2 表上作业法表上作业法Page 15方法方法3：西北角法：西北角法 从表的西北角（左上角）格开始，在格的右下角标上允许从表

8、的西北角（左上角）格开始，在格的右下角标上允许取得的最大数；然后按行（列）标下一格的数；若某行（列）取得的最大数；然后按行（列）标下一格的数；若某行（列）的产量（销量）已满足，则把该行（列）的其他格划去；如的产量（销量）已满足，则把该行（列）的其他格划去；如此进行下去，得到初始基可行解。此进行下去，得到初始基可行解。B1B2B3B4产量A17A2 4A39销量36563113101927410583422634.2 表上作业法表上作业法Page 16求出一组基可行解后，判断是否为最优解，仍然是用检求出一组基可行解后，判断是否为最优解，仍然是用检验数来判断，记验数来判断，记xij的检验数为的检验

9、数为ij由第一章知，求最小值的运由第一章知，求最小值的运输问题的最优判别准则是：输问题的最优判别准则是：所有非基变量的检验数都非负，则运输方案最优所有非基变量的检验数都非负，则运输方案最优求检验数的方法有两种：求检验数的方法有两种： 1 1 闭回路法闭回路法 2 2 位势法位势法4.2 表上作业法表上作业法Page 171. 闭回路法闭回路法为闭回路为闭回路 ，集合中的变量称为回路的顶点，相邻两个顶点，集合中的变量称为回路的顶点，相邻两个顶点的连线为闭回路的边。的连线为闭回路的边。闭回路：它是以某空格为起点。用水平或垂直线向前划，当闭回路：它是以某空格为起点。用水平或垂直线向前划，当碰到一数字

10、格时可以转碰到一数字格时可以转9090后，继续前进，直到回到起始空格后，继续前进，直到回到起始空格为止。闭回路如下图的为止。闭回路如下图的(a),(b),(c)(a),(b),(c)等所示。等所示。 4.2 表上作业法表上作业法 一条回路中的顶点数一定是偶数，回路遇到顶点必须一条回路中的顶点数一定是偶数，回路遇到顶点必须转转9090与另一顶点连接。与另一顶点连接。 Page 18 闭回路B1B2B3A1x11x12A2A3x32x33A4x41x43而而 不能构成一条闭回路，但不能构成一条闭回路，但A A中包含有中包含有闭回路闭回路 。 中顶点数是奇数，显然不是闭回路，也中顶点数是奇数，显然不

11、是闭回路，也不含有闭回路。不含有闭回路。 114143333212,xxxxxx212535311112,xxxxxx21253531,xxxx3332121121,xxxxx4.2 表上作业法表上作业法Page 19从每一空格出发一定存在和可以找到唯一的闭回路。（为什从每一空格出发一定存在和可以找到唯一的闭回路。（为什么？）因么？）因(m+n-1)(m+n-1)个数字格个数字格( (基变量基变量) )对应的系数向量是一个基。对应的系数向量是一个基。任一空格任一空格( (非基变量非基变量) )对应的系数向量是这个基的线性组合。对应的系数向量是这个基的线性组合。如如Pij, i,jN可表示为可表

12、示为()()()()()ijimjim km kllm sm suumjim klm klm sum sumjiklklsusujPeeeeeeeeeeeeeeeeeeeeeePPPPP 4.2 表上作业法表上作业法Page 20其中其中Pik,Plk,Pls,Pus,PujB。这些向量构成了闭回路。这些向量构成了闭回路。4.2 表上作业法表上作业法PujPus Plk PlsPij PikPage 21B1B2B3B4产量A1（+1）（-1）7A2（-1） （+1）4A39销量3656311310192741058341633 闭回路法计算检验数的经济解释：在已给出初始解的表闭回路法计算检验

13、数的经济解释：在已给出初始解的表中，可从任一空格如中，可从任一空格如(A1(A1，B1)B1)出发，若出发，若A1A1的产品调运的产品调运1 1吨给吨给B1B1。为了保持产销平衡，就要依次调整：。为了保持产销平衡，就要依次调整：(A1(A1，B3)B3)处减少处减少1 1吨，吨，(A2(A2，B3)B3)处增加处增加1 1吨，吨，(A2(A2，B1)B1)处减少处减少1 1吨，即构成了以吨，即构成了以空格为起点，其他为数字格的闭回路。空格为起点，其他为数字格的闭回路。 4.2 表上作业法表上作业法Page 22可见调整的方案使运费增加可见调整的方案使运费增加(+1)(+1)3+(-1)3+(-

14、1)3+(+1)3+(+1)2+(-1)2+(-1)=1(=1(元元) )，“1”1”这个数这个数这就是这就是(A1(A1，B1)B1)的检验数。的检验数。空格 闭 回 路 检验数 (11) (12) (22) (24) (31) (33) (11)-(13)-(23)-(21)-(11) (12)-(14)-(34)-(32)-(12) (22)-(23)-(13)-(14)-(34)-(32)-(22) (24)-(23)-(13)-(14)-(24) (31)-(34)-(14)-(13)-(23)-(21)-(31) (33)-(34)-(14)-(13)-(33) 1 2 1 -1

15、10 12 当检验数还存在负数时，说明原方案不是最优解，要继续改进。当检验数还存在负数时，说明原方案不是最优解，要继续改进。 故检验数为闭回路上奇数顶点的运价之和减去故检验数为闭回路上奇数顶点的运价之和减去偶数顶点的运价之和。偶数顶点的运价之和。4.2 表上作业法表上作业法Page 232.位势法位势法1 21 21iju (i, ,m),v ( j, ,n)mn-设设是是对对应应运运输输问问题题的的个个约约束束条条件件的的对对偶偶变变量量，1ijijBijijijcC B Pc(uv ) ijijimjxPee 系系数数列列向向量量，01ijijijc(uv )( ) 基基变变量量2ijij

16、ijcuv() 非非基基变变量量4.2 表上作业法表上作业法11212BmnC B(u ,u ,u ;v ,v ,v ) ，由（由（1 1）式，令）式，令 便可求出所有的便可求出所有的 和和 值。再由公式值。再由公式（2 2），便可以计算出所有非基变量的检验数。），便可以计算出所有非基变量的检验数。10u iujvPage 24B1B2B3B4UiA1A2A3Vj311310192741058436313当存在非基当存在非基变量的检验变量的检验数数 kl 0，说，说明现行方案明现行方案为最优方案，为最优方案，否则目标成否则目标成本还可以进本还可以进一步减小。一步减小。4.2 表上作业法表上作业

17、法Page 254.2 表上作业法表上作业法以进基变量以进基变量x xikik为起点的闭回路中，标有负号的最小运量作为起点的闭回路中，标有负号的最小运量作为调整量为调整量，对应的基变量为出基变量，并打上对应的基变量为出基变量，并打上“”以示换出作为非基变量以示换出作为非基变量。确定换入基的变量确定换入基的变量确定换出基的变量确定换出基的变量当在表中空格处出现负检验数时，表明未得最优解。当在表中空格处出现负检验数时，表明未得最优解。若有两个和两个以上的负检验数时，一般选若有两个和两个以上的负检验数时，一般选其中最小的负检其中最小的负检验数验数，以它对应的空格为调入格以它对应的空格为调入格。即以它

18、对应的非基变量为。即以它对应的非基变量为换入量换入量。Page 264.2 表上作业法表上作业法(2(2，4)4)为调入格。以此格为出发点，作一闭回路，为调入格。以此格为出发点，作一闭回路，(2(2，4)4)格的调入量格的调入量是选择闭回路上具有是选择闭回路上具有(-1)(-1)的数字格中的最小的数字格中的最小者。即者。即=min(1,3)=1(=min(1,3)=1(其原理与单纯形法中按其原理与单纯形法中按规划来确规划来确定换出变量相同定换出变量相同) )。B1B2B3B4产量A14（+1）3 （-1）7A231（-1） （+1）4A3639销量3656Page 27B1B2B3B4产量A1

19、527A23 14A3639销量3656调整步骤为：调整步骤为：在进基变量的闭回路中标有正号的变量加上调整量在进基变量的闭回路中标有正号的变量加上调整量，标有负号的变量减去调整量，标有负号的变量减去调整量，其余变量不变，得到一组新的，其余变量不变，得到一组新的基可行解。然后求所有非基变量的检验数重新检验。基可行解。然后求所有非基变量的检验数重新检验。4.2 表上作业法表上作业法Page 28再用闭回路法或位势法求各空格的检验数，表中的所有检验再用闭回路法或位势法求各空格的检验数，表中的所有检验数都非负，则当前方案为最优方案，此时最小总运费：数都非负，则当前方案为最优方案，此时最小总运费：Z =

20、(13)(46)(35)(210)(18)(35)85元元B1B2B3B4UiA1A2A3Vj3113101927410585363124.2 表上作业法表上作业法Page 29 表上作业法的计算步骤：表上作业法的计算步骤：分析实际问题列出产销平分析实际问题列出产销平衡表及单位运价表衡表及单位运价表确定初始调运方案（最小确定初始调运方案（最小元素法或元素法或Vogel法）法）求检验数（位势法）求检验数（位势法）所有检验数所有检验数0找出绝对值最大的负检验数，用闭合找出绝对值最大的负检验数，用闭合回路调整，得到新的调运方案回路调整，得到新的调运方案得到最优方案，得到最优方案，算出总运价算出总运价

21、4.2 表上作业法表上作业法Page 30（1）若运输问题的某一基可行解有多个非基变量的检验数）若运输问题的某一基可行解有多个非基变量的检验数为负，在继续迭代时，取它们中任一变量为换入变量均可使为负，在继续迭代时，取它们中任一变量为换入变量均可使目标函数值得到改善，但通常取目标函数值得到改善，但通常取ij0中最小者对应的变量为中最小者对应的变量为换入变量。换入变量。（2）无穷多最优解）无穷多最优解产销平衡的运输问题必定存最优解。如果非基变量的产销平衡的运输问题必定存最优解。如果非基变量的ij0，则该问题有无穷多最优解。，则该问题有无穷多最优解。4.2 表上作业法表上作业法Page 31 退化解：退化解： 表格中一般要有表格中一般要有(m+