判断最优解的方法与检验数

判别最优解的方法是计算空格（非基变量）的检验数cij-CBB-1Pij（i，j∈N）。因运输问题的目标函数是要求实现最小化，故当所有的cij-CBB-1Pij≥0时，为最优解。下面介绍两种求空格检验数的方法。

1.闭回路法

在给出调运方案的计算表上，如表3-13，从每一空格出发找一条闭回路。它是以某空格为起点，用水平或垂直线向前划，当碰到一数字格时可以转90°，之后继续前进，直到回到起始空格为止。闭回路如图3-1的（a），（b），（c）等所示。

图3-1

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

其中 Pik，Plk，Pls，Pus，Puj∈B。而这些向量构成了闭回路（见图3-2）。

用闭回路法计算检验数的经济解释为：在已给出初始解的表3-9中，可从任一空格出发，如（A1，B1），若让 A1的产品调运1 t 给 B1，为了保持产销平衡，就要依次作调整：在（A1，B3）处减少1 t，（A2，B3）处增加1 t，（A2，B1）处减少1 t，即构成了以（A1，B1）空格为起点，其他为数字格的闭回路，如表3-14中的虚线所示。在此表中闭回路各顶点所在格的右上角数字是单位运价。

图3-2　闭回路示意

表3-14

可见，经过调整的方案使运费增加

这表明，若这样调整运量将增加运费。将“1”这个数填入（A1，B1）格，就是检验数。按以上所述，可找出所有空格的检验数，如表3-15 所示。

表3-15

当检验数还存在负数时，说明原方案不是最优解，改进方法见3.2.3 小节。

2.位势法

用闭回路法求检验数时，需给每一空格找一条闭回路，当产销点很多时，这种计算很烦琐。下面介绍一种较为简便的方法：位势法。

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

而每个决策变量 xij的系数向量 Pij=ei+em+j，所以CBB-1Pij=ui+vj。于是检验数(www.xing528.com)

由单纯形法得知所有基变量的检验数等于0。即

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

表3-16

从以上七个方程中由 u1=0可求得

因非基变量的检验数

这就可以从已知的ui，vj值中求得。这些计算可在表格中进行，下面以例3-1 来说明。

第一步：按最小元素法给出表3-9的初始解，作表3-17。在对应表3-9的数字格处填入单位运价，如表3-17 所示。

表3-17

第二步：在表3-17 上增加一行一列，在列中填入 ui，在行中填入 vj，得表3-18。

表3-18

先令 u1=0，然后按ui+vj=cij，i，j ∈N 相继地确定 ui，vj。由表3-18 可见，当 u1=0时，由 u1+v3=3可得 v3=3，由 u1+v4=10可得 v4=10；当 v4=10时，由 u3+v4=5可得 u3=-5 。以此类推，可确定所有的ui，vj的数值。

第三步：按σij=cij-（ui+vj），i，j ∈N 计算所有空格的检验数。如

这些计算可直接在表3-18 上进行。为了方便，特设计计算表，如表3-19 所示。

表3-19

在表3-19中还有负检验数，说明未得最优解，还可以改进。