运输问题出现退化解时0元添加的改进方法

摘要： 运输问题表上作业法确定初始基可行解时，可能出现退化解，此时应当在适当的位置添加一个0元。本文探讨了这种情况下，如何恰当选取0元添加的位置，以减少表上作业法调整的工作量，最后提出了0元添加的改进方法。

Abstract： When the table dispatching method of transportation problems determines initial basic feasible solution， degenerate solution may appear， at this time， a "0" should be added in appropriate position. This paper discussed how to properly select the addition position of the "0" in this situation so as to reduce the workload of table dispatching method adjustment， and finally proposes improvement methods for "0" addition.

关键词： 运输问题；退化解；闭回路；初始基可行解；最优解

Key words： transportation problems；degenerate solution；closed loop；initial basic feasible solution；optimal solution

中图分类号：O223 文献标识码：A 文章编号：1006-4311（2014）02-0059-02

0 引言

运输问题及其数学模型：

有m个产地Ai可供应某物资量分别为ai（i=1、2、…m）

有n个销地Bj其需求量分别bj（j=1、2、…n）

从Ai到Bj运输单位物资的运输单价为Cij，将此信息汇总于表1和表2。

若用Xij表示Ai到Bj运量（如上表），则在产量平衡条件下，数学模型为

minz=■■CijXij ■Xij=bj，j=1，2，…n■Xij=ai，i=1，2，…mXij？叟0

由于产销不平衡问题易转化为产销平衡问题，故本仅探讨产销平衡类运输问题。求解此类问题用表上作业法比较简便，其实质是单纯形法的一种简化方法，但其在检验数计算和调整过程中，计算量会比较大，特别是在确定初始基可行解出现退化解时，如果0元的添加位置选取不当，会导致后面调整工作量增大，甚至得不到最优解。如何有效选取0元的添加位置，使初始基可行解与最优解更接近，以减少调整工作量。本文提出了一种全新的有效方案。

1 确定初始基可行解的方法及其改进

1.1 确定初始基可行解

确定初始基可行解方法很多，一般比较简单便于求得最优解的方法包括最小元素法和伏格尔法。而其中，最小元素法往往会为了节省一处的费用而造成其他某处要多花几倍的费用。伏格尔法考虑到一产地产品若不能按最小运费就近供应，就考虑次小运费，其从整体费用的角度出发，克服了最小元素法仅考虑就近的，局部的利益的缺点，往往得出的初始可行解与最优解更相近，甚至直接得到最优方案。

用伏格尔法确定初始基可行解的一般步骤：

①算出单位运价表中各行各列的最小运费和次小运费之差，找出最大差额；

②若同时有几个相等最大差额，则应选取单位运价最小的那行或那列；

③在选取的最大差额最小元素上填上尽可能大的运量，同时划去已满足的行或列；

④若在表格（i，j）填入某一数后，出现Ai处的余量和Bj处的需量相等，这时在产销平衡表上（i，j）处填一个数，在单位运价表中相应的划去该行和该列，并且在对应的那行或那列的任一不构成闭合回路的空格处添加0元；

⑤重复上述步骤直至给出初始基可行解。

1.2 确定初始基可行解的改进方法

在上述用伏格尔法确定初始基可行解的一般方法中，有些文献认为0元的添加比较随意，甚至都没有给出“0元的添加应当不能在表中构成闭合回路”这一要求（否则在用位势位法检验时，某些空格可能找不到闭合回路）。如《运筹学》教材编写组编一3版中关于0元的添加定义比较随意，好在由唐文广等学者给出了这一明确的要求。但是这种0元位置的选取方法某些时候仍然得不到最优的初始基可行解，依然会导致后面的调整工作量比较大，甚至得不到最优解。下面举一实例分别说明无法得到最优解和导致调整量比较大的情况。

1.2.1 选取的0元位置不当导致无法得到最优解

如表3所示产销平衡问题，表中“―”表示无此运输线路，用伏格尔法计算差额如表4。

若在空格（2，4）处填入10后，出现了退化现象，需添加一个0元，若此时仅仅满足上文中“用伏格尔法确定初始基可行解的一般步骤”中的步骤④的要求，把0元添加到如表5所示位置（4，4）处，则在用位势法计算检验数时，会导致很多空格处的检验数位负，如上表6用位势法算取的某些空格处检验数都为负，且后面无论怎么调整都得不到最优解。

1.2.2 选取的0元位置不当导致调整工作量增大

同样取上例，若在确定X24=10时，把0元选择填入方格（2，3），如表7。继续在空格（3，2）处填入20后，又出现了退化现象，需添加0元，若仅满足步骤④要求，将0元随意添至（3，1）格，如下表7。通过计算表7空格检验数，知δ33=-11

通过计算上表8中空格检验数，易知δ34=-5

用位势法计算表9空格中检验数，结果如上表10，可知所有检验数已满足非负，表9即为一最优解，且该问题有无穷最优解。

纵观以上解题过程，不难发现关于0元的添加是比较随意，且改进的过程调整了两次，每次都需要把所有空格检验数都计算一遍，这仍然是比较麻烦的。有没有一种更加科学的方法使得到的初始基可行解可以更加接近最优解或直接得到最优解呢？下面就是给出的改进方法：

将步骤④加以改进：

④’：若在表格（i，j）处填入某一数后，出现Ai的余量和Bj处的需量相等，这时在产销平衡表上（i，j）处填上一个数，在单位运价表中相应的划去该行和该列，并且在对应的那行的或那列不构成闭合回路且对应单价运价最小的空格处添加0元。

1.2.3 用改进方法计算初始基可行解

当确定基变量X24=10时，出现退化现象，需添加0元，根据结论④’，可确定0元填入（2，5）格；同理当确定X32=20时，0元填入（1，2）格，得初始基可行解如表11。

用位势法计算空格处的检验数得上表12，因表12中所有空格处检验数均非负，所以初始基可行解就是最优解。由此可见，上文同一例子，使用本文改进后的计算方法可以有效的降低表上作业法调整的计算量。结论④’是有效可行的，一般得到的初始基可行解就为最优解，避免因多次调整带来的大量计算，有效的降低了表上作业法的计算量，可操作性强。

结论：运输问题表上作业法出现退化解时，应该在对应的那行或那列不构成闭合回路且对应单位运价最小的空格处添加0元。

2 结语

求解运输问题，表上作业法相对单纯形法来说是一种比较简单的算法，但若初始基可行解中0元的位置选取不当，会使调整次数增多。若用本文结论确定初始基可行解，一般情况下可直接得到最优解，进而显著的降低了运输问题表上作业法的计算量。

参考文献：

[1]唐文广等.运输问题的退化解及表解中0元的添加[J].数学的实践与认识，2009.

[2]《运筹学》教材编写组.运筹学（第三版）[M].北京：清华大学出版社，2005：78-89.

[3]刘大为等.运输问题表上作业法的改进[J].科技资讯，2008.