运输问题检验数闭回路法

---

一种评价调运方案最优性的方法。

与单纯形法求解线性规划问题相似，必须对运输问题得到的调运方案中的非基变量(即调运表中的×格)求出相应的检验数，判别是否得到最优解。在表上作业法中，可用闭回路法求检验数。

运输表中，非基变量就是调运量为零的格子，即表中打“×”格。从每一打×格出发，遇到打圈格，转过90°，继续前进，遇到打圈格再转过90°，直到回至原打×格，构成一闭回路(闭回路必须是由一打×格和若干个打圈格为顶点构成)。

检验数求法：在闭回路中，以打×格为始点，沿闭回路(方向任选)，对闭回路顶点相间“+”“－”标号，奇点标“+”号，偶点标“－”号(以打×格为第一顶点)。然后，对各顶点格的单位运价冠以该顶点标号，求其代数和，即为该打×格的检验数。

最优判断标准：

(1)如果所有打×格检验数λ_ij≥0，则调运方案最优。

(2)如果打×格检验数中有λ_ij＜0，则调运方案非优，需调整。

例，对“最小元素法”例中求出的初始调运方案，用闭回路法求检验数。

λ₁₁=3－3+2－1=1

λ₁₂=11－4+5－10=2

λ₂₂=9－4+5－10+3－2=1

λ₂₄=8－10+3－2=－1

λ_3i=7－5+10－3+2－1=10

λ₃₃=10－5+10－3=12