单纯形法是计算出机会费用zj以后，直接计算检验数的代数式cj-zj 或zj-cj，而运输问题的表上作业法是间接计算检验数的代数式cj-zj，即通过闭回路法或位势法来求检验数。

由单纯形法可知，基变量的检验数均为 0，所以在表上作业法中只计算非基变量的检验数即可，即计算综合表中打“×”位置所对应的非基变量的检验数。下面分别介绍运输问题中求检验数的闭回路法和位势法。

1.闭回路法

为了利用闭回路法求检验数，下面给出一个定理。

定理5.4　运输问题的表上作业法中，任意一个非基变量都能和若干个基变量构成一个唯一的闭回路。（证略）

用闭回路法求运输问题检验数的具体步骤是：

第一步：以非基变量xij为起点，利用定义5.1闭回路的概念及定理5.4，寻找存在的唯一的闭回路。

第二步：闭回路上非基变量xij对应的检验数λij等于闭回路上所有奇数顶点对应的单位运价之和减去所有偶数顶点对应的单位运价之和。

第三步：将求出的检验数填到综合表中对应的非基变量xij的位置。

第四步：返回到第一步，直到求出所有非基变量的检验数为止。

如图5.2所示，顶点（1）处非基变量的检验数等于该闭回路上奇数顶点（1）、（3）、（5）对应的单位运价之和减去偶数顶点（2）、（4）、（6）对应的单位运价之和。

图5.2

以最小元素法求基本解的表5.15为例，说明用闭回路法求非基变量检验数的过程。

解　以非基变量x22为起点，寻找存在的唯一闭回路，如表 5.21所示：

依据表5.21中的闭回路，可得出非基变量x22的检验数：

表5.21　例5.1的综合表

λ22=(c22+c13+c34)－(c23+c14+c32)=(9+3+5)－(2+10+4)=17-16=1

将此检验数λ22填入到表中非基变量x22的位置，如表5.22所示：

表5.22　例5.1的综合表

用同样的方法求出其他所有非基变量的检验数（过程省略），最后得到表5.23：

表5.23　例5.1的综合表

从表5.23可以看出，有负的检验数存在，而此运输问题的目标函数又是min型，这说明目前的基本可行解不是最优解。

现在从运量分配的角度作如下分析：

把运量分配给x11一个单位，看看会对目标函数产生什么影响，即目标函数值是增加还是减少。当前，非基变量x11=0，如果给x11分配1个单位的运量，将增加3×1个单位的运费，由于表上作业法中表的每列分配的运量之和是一个常数，即等于对应销售地的销量，所以当x11增加1个单位的运量时，为保持销量平衡，x21就应该减少1个单位的运量，这样将减少1×1个单位的运费。与此同时，由于表上作业法中表的每行分配的运量之和也是一个常数，即等于对应产地的产量，为保持产量平衡，对应的x23就应该增加一个单位的运量，这样将增加2×1个单位的运费。同理可知，对应的x13处也应该减少一个单位的运量，进而减少3×1个单位的运费。

综上所述，运费的目标函数值共增加了3+2，同时又减少了1+3，所以目标函数值的总变化量为(3+2)－(1+3)=1。这就是说，每给x11分配一个单位的运量，目标函数值（总运费）将增加一个单位。这也说明，当所有非基变量的检验数都大于零时，再进行任何形式的运量调整只能使目标函数值增加，所以算法终止，此时的解就是最优解。反之，若对检验数小于零的非基变量进行运量分配，可以把非基变量调整为基变量，同时也会使目标函数值减少，从而得到更有利的方案。

用闭回路法求检验数，需要对表上每一个打“×”的非基变量寻找闭回路，然后再求检验数，而当一个运输问题的产地和销售地很多时，这种方法的计算工作量很大，另外，寻找闭回路本身就不容易。因此，下面介绍求检验数相对简便的位势法。

2.位势法(www.daowen.com)

简单地说，位势法就是基于基变量对应的单位运价，把各行和各列所对应的位势先设成未知数，通过解方程组的方式求出这些未知数，再利用这些求出的未知数把非基变量检验数计算出来。这种方法的合理性来自于线性规划问题的对偶理论。

为了利用位势法求检验数，下面给出一个定理。

定理5.5　针对运输问题求出的基变量xij，设定两个未知数ui和vj，据此建立方程

ui+vj=cij

那么对于非基变量xij的检验数λij，就有λij=cij－ui－vj。

证明　这里利用闭回路法的思路进行证明，不妨设有一闭回路如图5.3所示：

图5.3

因为xi j′、xi′j′、xi′j是基变量，由已知条件有以下方程：

根据闭回路法，非基变量xij的检验数为

位势法的具体步骤是：

第一步：针对基变量xij，设定未知数ui和vj，建立方程组

ui+vj=cij

已知运输问题的基变量有m+n-1个，所以设定的未知数ui和vj的个数分别为m+n-1个，那么方程组的个数也为m+n-1个，解方程组即可求出ui和vj。

第二步：将求出的ui写在综合表最左一列第i个产地标号的左边，将求出的vj写在综合表最上一行第j个销售地标号的上边。

第三步：利用定理5.5计算出所有非基变量的检验数。

第四步：将求出的检验数填到综合表中对应的非基变量xij所在的位置。

以最小元素法求基本解的表5.15为例，说明用位势法求非基变量检验数的过程。

解　在表5.15中，x13、x14、x21、x23、x32、x34为基变量，因此有如下方程组：

每一个基变量都有ui+vj=cij的关系式，所以求解此方程组的技巧是先令u1=0，进而很方便的求出其他的u值和v值。这样在使用位势法时，可以不必列出方程组，而直接在综合表上计算即可。

如前所述，对以上方程组，令u1=0，那么v3=3，v4=10。再由v3=3，得u2=-1；由v4=10，得u3=-5。同样有v2=9，v1=2。将这些值按照位势法的步骤写入表5.15后，得表5.24：

表5.24　例5.1的综合表

再利用定理5.5，计算出所有非基变量的检验数，并将求出的检验数填到综合表中对应的非基变量xij的位置，如表5.25所示：

表5.25　例5.1的综合表

可以看出，表5.25中的检验数和表5.23中用闭回路法求得的检验数是一样的。