表 3-23

（二)最优解的判别

要判别一个基可行解是否最优解，就需要计算非基变量（空格)的检验数Cij-CBB^-1Pij（i，j∈N)。因为运输问题的目标函数是求最小值，故当所有的Cij-CBB^-1Pij≥0 时，为最优解。下面，我们将介绍两种求空格检验数的方法。

1. 闭回路法在给出调运方案的计算表上，如表 3-19，从每一空格出发找一条闭回路，它是以某一空格为起点，用水平或垂直线向前划，每碰到一数字格转 90°后，继续前进，直到回到起始空格为止。闭回路如图 3-2 的（a)，

（b)，（c)等所示。

可以证明，从每一个空格出发一定存在并且可以找到唯一的闭回路。因为 m+n-1 个数字格（基变量)对应的系数向量是一个基，任一空格（非基变量) 对应的系数向量是这个基的线性组合。譬如，Pij（i，j∈N)可表示为：

Pij=ei+em+j

=ei+em+k-em+k+el-el+em+s-em+s+eu-eu+em+j

=(ei+em+k)-(el+em+k)+(el+em+s)-(eu+em+s)+(eu+em+j)

=Pik-Plk+Pls-Pus+Puj （1)

在（1)式中，Pik，Plk，Pls ，Puj∈B，而这些向量构成了闭回路（见图3-3)。

闭回路法计算检验数的经济解释为：在已给出初始基可行解的表 3-19 中，可从任一空格出发，如（A1，B1)，若让 A1 的产品调运 1 吨给 B1，为了保持产销平衡，就要依次进行调整：在（A1，B3)处减少 1 吨，在（A2，B3)

处增加 1 吨，（A2，B1)处减少 1 吨，即构成了以（A1，B1)空格为起点，其它

为数字格的闭回路，如表 3-24 中的虚线所示。在这个表中，闭回路各顶点所在格的右上角数字是单位运价。

调整的方案使运费增加

（+1)×3+（-1)×3+（+1)×2+（-1)×1=1（元)

这表明若作这样的运量调整，将会使运费增加 1 元。将“1”填（A1，B1) 格中，这就是检验数。按照上述办法，可找出所有空格的检验数，见表 3-25。当检验数还存在负数时，说明原方案不是最优解，还需要对原方案进行改进。