运输问题表上作业法补零规则的改进

林磊

【摘 要】本文对运输问题表上作业法过程中，检验数计算出现负值，而方案却已经达到最优这种情况进行了分析，指出了其原因在于问题出现退化时进行补零操作的规则不明确。本文进一步给出了一种改进的补零规则以减少这种情况出现。

【关键词】表上作业法；检验数；退化解

运输问题是运筹学的一个重要分支线性规划问题的特例[1]。对于一般线性规划问题，可以使用单纯形法来解决。而运输问题由于其約束条件变量的系数矩阵的特殊性，可以使用比单纯形法更为简单的方式来处理，然而，有时，虽然检验数出现了负值，调运方案却已达到了最优。本文就这种情况形成的原因进行了分析，发现这是由于问题出现退化时进行补零操作的规则不明确而导致的。故而，本文设计了一种改进的补零规则减少此种情况的出现。

1问题引入与分析

这一节将详细地描述本文所要解决的问题。为了便于理解，下面将结合具体的实例来引出问题。

例子1：已知运输问题的产销地的供需量与单位运价表如表1所示，用表上作业法求解其最优解。

解：这是一个产销平衡的运输问题，文中单位运价用符号表示，从地销往地的运量用符号表示，检验数用符号表示。第一步通过Vogel法寻找初始调运方案。在第一轮计算行列最大差时，出现第一行和第一列的最低和次低运费的差值都为8，是最大的运费差，所以按照Vogel法的规则，可选择划掉第一列，设置。由于所在行的产量等于其所在列的销量，还要同时划掉第三行，并可以设置第三行或是第一列除去的某一格运量为0，并将此格所代表的变量视为基变量。假设设置，继续使用Vogel法，得到初始调运方案如表2所示。

表2中括号里面的数字代表对应的行产地运往列销地的运量。接下来计算空格变量的检验数。使用闭回路法算出检验数为：

σ13=16，σ21=-3，σ24=4，σ32=14，σ33=20，σ34=15.

可以看出，检验数当中有负值，根据表上作业法该方案没有达到最优，需要调整。从所对应的空格出发，做一条除该空格外其余顶点都为有数字格的闭回路，如表3所示。由于这条闭回路上最大的调整值为0，所以调整之后的总运费是不会改变的。换句话说，调整后的方案和原方案所对应的目标函数值是一样的。对这个闭回路，调整后，只有和有变化，从基变量0变成了非基变量0，而从非基变量0变成了基变量0。对新的方案，计算检验数，原来为正的检验数依然为正的，新的非基变量的检验数此时也为正，且刚好是原非基变量检验数的相反数。因此，由于所有非基变量的检验数都为正，新方案已达到最优。

显然，初始方案与新的方案的目标函数值是相等的。由于新的方案达到了最优，所以初始方案也达到了最优。然而初始方案的检验数却有负数值。为什么会出现这种现象？原因在于，求初始方案的时候出现要同时划去一行和一列的情况（称为退化），在这个时候为了使基变量的个数不减少，需要在划去的行列中随机选择一格赋值0作为基变量。选择哪一格补0按传统的规则是随机挑选的，这种规则会导致表上作业法出现以上的漏洞。因为，选任何一格补0最后得到的调运方案所计算的总运费是一样的。

2改进的补零规则

回顾上一节的例子，可以看出，如果一个方案已经达到最优，此时出现了退化。传统的补零规则是随机选取同时划去的行列中除最小运费之外的任意格做为基变量。假设补零的时候选取某一格为基变量，利用闭回路算法计算检验数时这一格的检验数恰好却出现了负值。那么就会出现检验数为负值，方案却已达到最优这种情况。为了减少这种情况出现的次数，本文给出了一种改进的补零规则，如下所示。

补零规则对运输问题进行表上作业法碰到退化解时，选择同时划去的行列中未添供销量格中运费最小的格补上0。

规则解释：不失一般性，假设需要同时划去的行列中未添供销量格子中最小运费格为。计算被划去行列中这些非基变量的检验数时，某些非基变量格的闭回路会以格做为其回路顶点。对这些非基变量格计算检验数时，可以分为两种情况分析。一种是计算检验数时需要加上格的运费，这种情况下格贡献的是正数，不会导致检验数为负；另一种是计算检验数时需要减去格的运费，这种情况下格贡献的是负数，但由于所要计算检验数的非基变量格的运费按改进的规则是大于等于，两者相减得数非负，故也不会导致检验数为负。

3结论

本文对运筹学中运输问题的表上作业法出现检验数为0方案却已最优的情况进行了分析，指出其原因是在同时划去行列时的补零操作过于随机。为了减少这种情况的发生，本文给出了一种改进的补零规则。

参考文献：

[1]胡运权等.《运筹学基础及应用》[M].高等教育出版社，2015endprint