§5.3最优性的检验
预备知识：
对标准形线性规划问题

其对偶问题为

的一个基，作关于基的单纯形表

则关于基的对偶解为，检验数为,其中，即.
又
，
将的约束条件中基变量对应的不等式改为等式，即令（为基变量），
即得关于基的对偶解.
由对偶理论知，对运输问题

引入对偶变量，得对偶问题为

的一个基本格子集，由§5.2知，从中去掉一个多余的行即得的一个基，且关于基的单纯形表为

则关于基的对偶解为，检验数为,其中，即.
由预备知识知，将的对偶问题的约束条件中的的不等式改为等式，即令，即得关于基的对偶解.
是自由变量，可令，解得关于基的对偶解，，即.
定义 称为关于基本格子集的位势（potential）.
由此，得关于基的检验数为
；

小结：求关于基的检验数先求位势：
再求检验数：
图示：

例1设中，，，，试求的一个基本可行解和相应的检验数.
解：利用最小元素法求解：

的一个基本格子集为，相应的基本可行解为，其它.
求位势：

求检验数：
.▍
注：显然，将求位势和求检验数的计算可在同一张运输表上进行.
同单纯形法一样，在运输表中，当求得的一个初始基本可行解和相应的检验数后，若所有检验数均非负，则当前的基本可行解即为最优解；否则，应改进之（转轴），以使之更优.
定义 设，若可将中的诸格子排列为，其中互异，互异，则称是一个闭回路.
闭回路的特点：任意两个相邻的格子的行指标相同时，其列指标必不相同；列指标相同时，其行指标必不相同.即任意两个相邻格子的行（列）指标不能同时相同，也不能同时不同.
如对格子集，令.
易见，可将中的诸格子排列为，是一个闭回路.

显然，闭回路在格子表的同一行（列）上均恰有两个格子.
Lemma设是的一个基本格子集，，则中必存在唯一一个闭回路，且.
证明：从中递归地删去孤立格子，即得一个闭回路.▍
例1（续）求一个闭回路.
解：.
若取，则从中删去孤立格子，即得一个闭回路.

显然，.
若取，则从中递归地删去孤立格子，即得一个闭回路.

显然，.
其它情况略同.▍
Th1设的一个基本格子集为，相应的基本可行解为.
,中的闭回路为.按如下规则将划分为和:
；的处在同一行、列的两个格子应分属和.
令
，
，

则仍是的一个基本格子集，且是相应的基本可行解.▍
注：（1）Th1描述的是类似于单纯形法的转轴过程的运输问题的转轴过程：由非基变量变为基变量，由基变量变为非基变量.
（2）转轴后，新进入基本格子集的格子对应的基变量的值为.
例1（续）解：.
取，则中的一个闭回路为：

将划分为和:

.
修正：
▍