如何避免表上作业法计算中的退化问题？

1.无穷多最优解

在本章3.1 节中提到，产销平衡的运输问题必定存在最优解，那么有唯一最优解还是有无穷多最优解？其判别依据为：当某个非基变量（空格）的检验数为0 时，该问题有无穷多最优解。表3-22 空格（1，1）的检验数是0，表明例3-1 有无穷多最优解；在表3-21中，以（1，1）为调入格，作闭回路（1，1）+-（1，4）--（2，4）+-（2，1）--（1，1）+，确定θ=min{2，3}=2，经调整后得到另一最优解，如表3-23 所示。

表3-23

2.退化

用表上作业法求解运输问题，当出现退化时，在相应的格中一定要填一个 0，表示此格为数字格。主要有以下两种情况。(www.xing528.com)

（1）当确定初始解的各供需关系时，若在（i，j）格填入某数字后，出现 Ai处的余量等于Bj处的需量，这时在产销平衡表上填一个数，而在单位运价表上相应地要划去一行和一列。为了使在产销平衡表上有（m+n-1）个数字格，这时需要添一个“0”，它的位置可在同时划去的对应的那行或那列的任一空格处，如表3-24 和表3-25 所示。因第一次划去第一列，剩下最小元素为2，其对应的销地 B2，需要量为6，而对应的产地 A3未分配量也是6，这时在产销表（3，2）交叉格中填入6，同时在单位运价表3-25中划去 B2列和 A3行。即在表3-24的空格（1，2），（2，2），（3，3），（3，4）中任选一格添加一个0。

表3-24

表3-25

（2）在用闭回路法调整时，在闭回路上出现两个或两个以上的具有（-1）标记的相等的最小值，这时只能选择其中一个作为调入格，而经调整后，得到退化解。这时另一个数字格必须填入一个0，表明它是基变量。当出现退化解后，作改进调整，此时可能在某闭回路上有标记为（-1）的取值为0的数字格，这时应取调整量θ=0。