关于一类退化型运输问题求解的研究

朱 翔

（无锡职业技术学院 基础部，江苏 无锡 214121）

运输问题［1］是运筹学中一类重要的线性规划问题，它的一般模型如下：

由于运输问题模型的特殊性，常用表上作业法［1］来求解该问题。在通过最小元素法确定初始调运方案（初始可行基）时，有时会出现基变量数小于m＋n-1的情况，从而产生退化解（在这里我们称之为退化型运输问题），这给后面用闭回路法和位势法继续迭代带来了困难，下面通过一道实例来说明该类问题的求解方法。

1 实例及求解

已知某运输问题的产销平衡表及单位运价资料（见表1），试确定最优的运输方案。

表1 产销及运价表

利用最小元素法得到如下的初始方案（见表2），我们发现在此题中m＋n-1＝4＋6-1＝9，而数字格只有8个，属于退化情形。

表2 初始调运方案

为了保证基变量个数，此时必须在空格处添加一个“0”。但是0运量添加的位置并不是任意的，有如下命题：

命题1［2］用表上作业法给出运输问题初始方案时，遇到退化解的情形，0运量应添在不与其他数字格构成闭回路的格子里。

故此题中，0运量只能添加在A1行或B2列的空格处，下面讨论两种不同的初始方案。

情况Ⅰ：x11＝0（见表3、表4）

表3 调运方案1.1

表4 空格检验数2.1

由于检验数x45＝-1＜0，故不是最优解，需调整。表3中，x34，x35，x45，x44组成闭回路，取△＝min｛x35，x43｝＝10，则

x34＝9＋△＝19，x35＝10-△＝0（成为非基变量空格），x45＝△＝10，x44＝31-△＝21，调整后的方案如下（见表5、表6）：

表5 调运方案1.2

此时检验数λ22＝-1＜0，同上做法继续调整。

考虑闭回路：x11-x12-x22-x25-x45-x44-x34-x31-x11，调整量△＝20，调整后的方案如下（见表7、表8）：

表6 空格检验数2.2

表7 调运方案1.3

表8 空格检验数2.3

此时，所有空格的检验数均大于0，从而当前方案为最优运输方案。

情况Ⅱ：x22＝0

类似上述方法，可得到与表7一致的最优运输方案。

2 关于此类问题的求解

本题中“0”可以添在A1行或B2列空格的任一位置，但本文仅讨论了两种不同的初始方案，看似“不太全面”。事实上，其余的添加方案都会最终归结为这两种情况。对于A1行其他位置的空格，不妨设x13＝0，这时考虑闭回路：x11-x13-x23-x25-x35-x31-x11这时调整运量△＝0，表面上看数值无变化，但是x11由空格变成了数字格0，而x13由数字格0变成了空格，也就是说，基变量发生了变化，完成了一次换基迭代。这时正好就变成了情况Ⅰ。不难验证，A1行空格处添加“0”后都可转化为情况Ⅰ，B2列空格处添加“0”后都可转化为情况Ⅱ。而这个结论具有一般性，下面给出证明。

命题2［3］运输问题列向量线性无关向量对应格集中不含闭回路

引理在退化型运输问题（仅一个退化解）的初始调运方案表中，同一行（列）上不与其他数字格构成闭回路的任意两个空格之间一定存在闭回路。

证明设xik和xij是第i行上不与其他数字格构成闭回路的任意两个空格。令xik＝0，此时xik从空格变成了数字格，从而变成了基变量，此时基变量数与运输问题约束矩阵的秩相同（等于m＋n-1）。xij作为非基变量，其对应列向量可由基向量组线性表示，又空格xij不与其他数字格构成闭回路，由命题2易推出，xij与xik之间一定存在闭回路。对于同一列的情况类似可证。

定理对于仅一个退化解的退化型运输问题，在利用添加0运量的方法保证基变量数时，在同一行（列）可添加0运量的任一空格处添加0运量的方案彼此等价。

证明设xik和xij是第i行可添加0运量的任意两个空格，选择在xik处添加0称为方案Ⅰ，选择在xij处添加0称为方案Ⅱ，下面证明这两个方案等价。

对于方案Ⅰ，因为xik和xij是可添加0运量的空格，根据命题1，xik和xij不与其他数字格构成闭回路。从而由引理可知，必存在通过xik和xij的一条闭回路，且xik与xij是相邻的两个节点。此时作运量调整△＝0，则xij从空格变成了0数字格，而相邻节点xik从0数字格变成了空格，其余数字格的数值不变，这时候即为方案Ⅱ。同理，方案Ⅱ也可以转化为方案Ⅰ，从而这两种方案是等价的。同一列的情况类似可证。

3 结束语

在利用表上作业法求解运输问题时，一定要始终考察其数字格是否为m＋n-1个。当出现退化解时，可利用本文提出的添加“0”的办法来解决。特别地，对于仅有一个退化解的运输问题，所有可行的添加0运量方案都是等价的，因此我们只需任意选择其中一种方案。

［1］《运筹学》教材编写组.运筹学［M］.3版.北京：清华大学出版社，2005.

［2］唐文广.运输问题的退化解及表解中0元的添加［J］.数学的实践与认识，2009，39（1）：160-166.

［3］高旅端.线性规划［M］.北京：北京工业大学出版社，1989.