位势法

---

检验物资调运方案是否最优的一般公式法。

将初始调运方案中填有运量方格的运费C_ij分解成C_ij= U_i+V_j，称U_i、V_j为该方格对应于i行和j列的位势，m个供应点、n个需求点，共有m+n个位势，但调运方案仅有m+n－1个填有运量的方格，这样由m+n－1个C_ij解出m+n个位势，可先任意给定一个位势，然后推导其它位势。仍以前述问题为例，建表求位势。根据C₂₁=U₂+V₁=1，先令V₁=1，得U₂=0，再由C₂₃=U₂+V₃=2，得V₃=2，依此继续下去，可得V₂=8，V4=9，U₁=1，U₃=－4。

任一空格的位势为U_i+V_j，则检验数为λ_ij=C_ij－(U_i+V_j)，当检验数全部非负时为最优调运方案，否则按闭回路法进行调整。

新调运方案