求解思路与方法

1.求解思路

求解运输问题的表上作业法的思路与单纯形法一致，所有运算均可以在表上完成，但是具体做法仍然具有一些特殊性。具体步骤如下：

（1）寻找一个初始基本可行解（基可行解），对应一个初始的调运方案，即在（m×n）产销平衡表上给出m+n-1个数字格。

（2）求得各非基变量的检验数，即在表上计算空格的检验数，判断是否达到最优解。如果已是最优解，则停止计算；否则继续进行下一步。

（3）确定换入变量和换出变量，在表上用闭回路法调整，找出一个新的基本可行解。

（4）重复第二步、第三步的内容，直到求得最优解为止。

表上作业法是单纯形法在求解运输问题时的一种变形方法，实质上仍然是单纯形法，只是外在表现方式和具体术语有所区别。与一般线性规划问题类似，Excel、 MPL、 CPLEX、 LING、LIDO等均可以用来建立和求解运输问题，其求解方法非常丰富。

2.求解方法

对于表上作业法各个步骤而言，存在可选的各种具体方法，我们简单介绍如下：

（1）西北角法：从运输问题单纯形表（调运表）的西北角开始，即首先选择x11，因此西北角法又称左上角法，或阶梯法。根据约束条件所允许的、尽可能大的运输数量，即令x11 =min（a1，b1）。接下来，继续选取下一个西北角变量作为基变量，这样顺次由西北角往东南角移动。由此逐步推演下去，就得到了一个初始调运方案，也是初始基本可行解。

（2）最小元素法：从运输问题单位运价表中选择最小的单位运价开始，确定运输关系，相应地划去该单位运价所在行或列；然后选择剩余单位运价中最小的，一直到给出初始基可行解，求出初始方案为止。此时单位运价表上所有的元素都被划去了，相应地在产销平衡表上填写了m+n-1个数字，给出了运输问题m+n-1个基变量的取值。

（3）伏格尔法：对需要考虑的行和列计算罚数，罚数是指运输表中每一行、每一列的次小单位运价和最小单位运价之间的差值。在这些罚数中选择最大者，对应的列或行与最小元素法一样进行处理。在尚未划去的各行和各列中如上重新计算各行罚数和列罚数，用上述方法继续做下去，依次算出每次迭代的行罚数和列罚数，根据其最大罚数值的位置在运输表中的适当格中填入一个尽可能大的运输量，并划去对应的一行或一列。用这种方法可以得到一个初始基可行解。

西北角法和最小元素法最主要的优点是简单易行，但所得初始调运方案常常远离最优调运方案。伏格尔法虽然并未将总的成本考虑全面，但给出的初始调运方案一般较为高效。当然，考虑到人工计算和计算机应用的因素，各方法的取舍仍有一定的可选性。

例3-2某公司生产某种产品，下设三个加工厂。公司把这些产品分别运往四个销售点。 已知从各个工厂到各销售点的单位产品的运价如表3-3所示。 问该公司应该如何调运产品，在满足各个销售点需求的前提下，使总的运输成本最小。

表3-3　产销量及单位运价表

解：利用伏格尔法求得初始调运方案，如表3-4至3-8所示。

表　3-4

表　3-5

表　3-6

表　3-7

表　3-8

（5）闭回路方法：当某一运输方案有负检验数时，需要将绝对值最大的负检验数对应的非基变量作为换入变量，变成基变量。从换入变量xij出发，遇到某个基变量则选一个方向拐角或穿过，直至回到起点形成闭回路。按此法从换入变量出发作闭合回路运转，其四周顶点除换入变量以外，其余都是基变量。选定格的调入量θ是选择闭回路上具有（-1）标号的数字格中的最小者，其原理与单纯形法中按θ规划来确定换出变量一致。按闭回路上的正、负号，加入和减去此值，得到新的调整方案。

例3-3通过例3-2讨论运输问题求解的表上作业法。

首先初始化，目标是获得初始基可行解。

对于运输问题而言，约束条件都是等式。在所有的m+n个等式中，存在一个冗余的重复约束，删除其并不影响可行域，对具有m个产地和n个销地的运输问题，基变量的数量为m+n-1。

利用最小元素法求得例3-2的初始调运方案，如表3-9所示。

表3-9　初始方案

其次，利用位势法进行最优解的判断，如表3-10所示。

表3-10　位势法求解

表3-11　最佳方案

该调运方案满足最优解检验条件，且为最优解，最小总运费为98。