表 3-25

1. 位势法

用闭回路法求检验数时，需给每一个空格找一条闭回路。当产销地很多时，这种计算就变得很繁。下面我们介绍一种较为简便的求检验数方法—— 位势法。

设 u1，u2，⋯，um；v1，v2，⋯，vn 是对应运输问题的 m+n 个约束条件的对偶变量。B 是含有一个人工变量 xa 的（m+n)×（m+n)阶初始基矩阵。人工变量 xa 在目标函数中的系数 ca=0，由线性规划的对偶理论可知

CBB^-1=[u1，u2，⋯，um；v1，v2，⋯，vn] （2)

而每一个决策变量 xij 的系数向量 Pij=ei+em+j，所以 CBB^-1Pij=ui+vj。于是检验数为

σij=Cij-CBB^-1Pij=Cij-（ui+vj) （3) 由单纯形法知所有基变量的检验数等于 0，即

Cij-（ui+vj)=0 i，j∈B （4)

譬如，在例 3 由最小元素法得到的初始解中，x24，x34，x21，x32，x13， x14 是基变量。xa 为人工变量，这时对应的检验数是

基变量 检验数

xa ca-u1=0 因为 ca=0，所以 u1=0

x24 c24-（u2+v4)=0 即 8-（u2+v4)=0

x34 c34-（u3+v4)=0 即 5-（u3+v4)=0

x21 c21-（u2+v1)=0 即 1-（u2+v1)=0

x32 c32-（u3+v2)=0 即 4-（u3+v2)=0

x13 c13-（u1+v3)=0 即 3-（u1+v3)=0

x14 c14-（u1+v4)=0 即 10-（u1+v4)=0

从以上 7 个方程中可求得：u1=0，u2=-1，u3=-5，v1=2，v2=9，v3=3，v4=10

对于非基变量的检验数

σij=Cij-（ui+vj)i，j∈N （5)

可以由已知的 ui，vj 求得。所有这些计算均可以在表中进行，以下我们以例 3 说明之。

第一步：按最小元素法给出表 3-19 的初始基可行解，作表 3-26。在对

应表 3-19 的数字格处填入单位运价，见表 3—26。