摘 要：本文摆脱了传统的通过位势方程介绍位势的束缚，从单纯形法入手解决运输问题，其间引出位势这一概念，并讨论了利用位势确定检验数的原理和方法。 关键词：位势方程组 位势 检验数
位势是解决运输问题过程中的一个重要的概念，然而在一般的文献中对位势都没有做系统的介绍，大多数情况是利用位势方程来定义位势，然后再利用位势来计算运输问题的检验数，其间不加任何说明，初学者往往会丈二和尚摸不着头脑，对以后的学习带来负面影响。本文利用单纯行法解决运输问题，其间引出位势这一概念，让大家深刻地领悟位势的本质，同时也可以很清楚地了解为什么可以用位势计算运输问题的检验数以及如何来计算检验数。
在运筹学中，运输问题是一类非常重要的问题，其中最重要的是平衡运输问题，即总发量等于总销量的运输问题。其它的运输问题都可以转化为平衡的运输问题，因此我们这里只讨论平衡的运输问题。平衡运输问题的一般模型如下：
表一
其中ai是产地A 的产量(i=1，2，…，m)，bj是销地Bj的销量，cij是由Ai运输单位货物到Bi的运价。
从运输问题的模型可以看出，其实运输问题也是线性规划问题，完全可以通过单纯形法来解决运输问题。首先需要确定一组初始可行基，确定初始可行基的方法很多，经常用的有三种：西北角法、最小元素法、Vogel法。（在任何一本运筹学教材里都可以找到这些方法的详细介绍，这里就不再赘述了）确定了初始可行基后，列出初始可行基的单纯行表如下：
表二 表一左边的X是初始基可行解向量，易证运输问题的任何一个基都由m+n-1个变量组成（具体的证明可在参考文献（1）内找），因此，X的分量有m+n-1个。不妨设m=3，n=4，X=（x ， x ， x ， x ， x ， x ）表一变为：
要想从上面的单纯形表中判断当前基可行解是否是最优解，还得把基变量在目标函数z中的系数消为零，如果对单纯形法有足够的认识，理解这点应该没有什么问题，为了帮助读者更好地理解本文，这里对单纯形法的原理做个简单的回顾。
单纯形法的基本思想是：确定一组系数向量线性独立的基可行解，然后令其它的非基可行解取值为零，再在约束方程组里解出基可行解，然后判断由基可行解和取值为零的非基可行解所组成的规划问题的解是否最优，这个过程称之为单纯型迭代。怎么判断当前解是否最优呢？从迭代过程中看到，基变量的取值是由约束方程来确定的我们无法控制，我们能控制的是非基变量的取值，令其为零，要想知道这样做是否合理，我们可以利用约束方程组中的基变量和非基变量的关系在目标函数里消去基变量，只留下非基变量，然后观察非基变量的系数。如果系数都是正的，那么我们令非基变量取值为零就是最合理的，此时的解也是最合理的，就是最优解，如果系数存在负数，那么令系数为负的非基变量为零就不合理了，因为如果非基变量不为零，会给目标函数带来消减，从而优化目标函数。综上所述，判断当前解是否最优的标准其实是将基变量消去后的目标函数中非基变量的系数，所以称它们为检验数。
回到我们的问题当中，在表二中如何将基变量在目标函数中的系数消去呢？比如说我们如何消去目标函数中的基变量x11？观察表二，我们发现在约束方程组里有两个关于11的约束方程（从上往下数第一个和第四个），我们可以借助这两个方程将目标函数里的11消去，具体的做法是：Z-第一个方程×U1+第四个方程×V1，这个做法的本质是高斯消元法，其实再说得简单点就是我们中学里解线性方程组常用的消元法。这样做也不会改变目标函数的最优值，当然也不会改变最优解。此时x11的系数就变成c11-U1- V1只要令它等于零就达到我们的目的了。这样，我们就得到了关系式：
c11=U1+V1 (2)
对其他五个基变量用同样的方法，我们可以得到类似（2）式的等式，将这六个等式联立成一个方程组：
（3）是一个有七个变量而只有六个方程的线性方程组，这就是通常所说的“位势方程组”，U i(i=1，2，3)，Vj(j=1，2，3，4)就是所谓的“位势”。由线性代数方程组理论可知，它有一个自由变量，因此有无数个解，不妨就令这个自由变量是U1、U1取不同的值，就会得到不同的解，最简单的情形是令U1等于零。
在一般的运输问题当中,位势言和组为:
cij=Ui+Vj(cij是基变量在目标函数中的系数)
有了位势以后，怎么求检验数呢？
很简单，我们曾说过，检验数其实是将目标函数中基变量消去后非基变量的系数，前面我们在表二中所做的工作将目标函数中基变量消去，既将基变量的系数消为零的同时，对非基变量的系数也做了相应的变动，设C 是非基变量系数c 变动过后的值，则Cij= cij-Ui-Vj，Cij就是判断当前解是否最优的检验数。
参考文献：
[1]朱求长.运筹学及其应用(修订本)[M].武汉:武汉大学出版社，1997.
[2]宋学锋，魏哓平.运筹学[M].南京:东南大学出版社，2003.
注：“本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文。”
本文为全文原貌 未安装PDF浏览器用户请先下载安装 原版全文