运输问题的简化解法

[摘 要] 本文对运输问题的传统解法(表上作业法)做了改进，提出跳过计算“检验数”，直接采用“闭回路法”和“对角相加法”可以简化运输问题的求解过程。

[关键词] 运输问题 检验数 位势法 闭回路法 对角相加法

多数运筹学或物流管理教科书对运输问题（表上作业法）一般先采用最小元素法找出一个可行解，然后采用闭回路法或位势法计算“检验数”，验证这个可行解是否最优解。如果不是最优解，再用闭回路法调整。调整后还要用闭回路法或位势法计算“检验数”，直到验证表明调整后的方案是最优解才算完成。解法可用如下程序图所示：

注：不平衡的要虚设需方或产地，已有成熟方法，本文对此不加讨论

在上述程序中，“采用闭回路法或位势法计算‘检验数’，验证这个可行解是否最优解”是一个比较复杂的过程。当产地和销地数量较大时，闭回路寻找比较复杂。多数运筹学或物流管理教科书采用位势法计算检验数，这要先分解运价，列出并求解一个联立方程（有时列出的联立方程还可能未知数与方程数不等，还要做技术处理）， 再计算每一个未使用的运价（空格）的检验数，要所有检验数不小于零才表明所得方案是最优解。这个过程有时要重复多次，比较繁琐，能否简化呢？

笔者从后面的闭回路法得到启示，是否可以这么认为：只要还存在可以用闭回路法调整优化的“回路”，原方案就不是最优解，一直到所有的“回路”都不能再调整优化时，该方案就是最优解。并且笔者认为闭回路的寻找也可以从已采用的最大运价开始着手，便于使不合理的运价及时得到调整，这样上述程序图就可修改如下：

在上述程序中，“判断所在运量闭回路是否可调整”可以用一个比较简单的“对角相加法”来加以判断，下面用一个例子来加以说明：设有5个产地A1，A2，A3，A4，A5和4个销地B1，B2，B3，B4的运输问题，它们的供应量与需求量及单位运费表如下：

求解这个问题的第一步:按“最小元素法”根据运价从小到大满足需求得一可行解：

注：在此用“P/M”表示以P运价运输量M，未打“/”的运价暂不采用

第二步：找到所采用的最大运价20，找其所在的“运量闭回路”。所谓的“运量闭回路”应满足以下条件：

(1)“运量闭回路”是由水平线和垂线及其角上元素组成的矩形。

(2)该矩形包含角上的4个元素（运价）。

(3)4个运价中有3个是采用的，一个是暂不采用的。

最大运价20所在的这样的“运量闭回路”有两个：

第三步：任选一个回路，采用“对角相加法”判断：将对角的两个运价相加。针对回路一有：20+1=21，7+5=12；可以看出，两个均采用的对角运价之和大于另外两个对角运价（其中一个暂不采用）之和，20+1＞7+5，说明可以调整优化，采用“闭回路法”调整为：

此时，7+5＜20+1；两个均采用的对角运价之和小于另外两个对角运价（其中一个暂不采用）之和，说明该回路已经优化（不能再调整优化）。并且得到第二个可行解。

然后再找到现方案中的最大运价15，再找相应回路进行判断和调整。这样调整4次以后得到最优解：

最小运费=5×10+9×20+4×30+7×30+0×10+3×30+12×10+5×10=820，可以判断在这个方案中已不存在可以调整优化的回路。该方案确为最优解。

由此可以看出，跳过计算“检验数”，直接采用“闭回路法”和“对角相加法”可以简化运输问题(表上作业法)的求解过程。也许这对于当今使用计算机软件解决该问题帮助不大，但是对于初学者用手工解决问题时是有帮助的。与“位势法”相比，上述“闭回路法”和“对角相加法”都比较容易理解和运用。

参考文献:

[1]王自勤:现代物流管理.电子工业出版社，2007.6

[2]卢向南:应用运筹学.浙江大学出版社，2005.2

[3]韩伯棠:管理运筹学.高等教育出版社，2005.7

[4]李维铮等:运筹学.清华大学出版社，1982.2

推荐访问： 解法 简化 运输