寻找费用下降最大的闭合回路的算法

Algorithm of finding the closed circuit on the largest down cost

针对求解运输问题的经典算法,即闭合回路法和位势法,在寻找费用下降最大的闭合回路时,检验数求解计算量庞大的缺点,通过引入运输问题的检测矩阵及检测量,给出了一种求解运输问题的新算法。该算法对检测矩阵使用匈牙利法及元素求和得到最优解,从而得出最优运输方案。与经典的闭合回路法和位势法相比,在大规模的运输问题上,或基可行解出现退化的运输问题上,新算法更适合求解运输问题。

Point to old algorithms for finding transportion problem which is closed circuit method and potential method, a new algorithm for finding transportion problem is given by introducing test matrix and test quantity. The algorithm is efficient and reliable compared with classical closed circuit method and potential method on large scale and degenerate transportation problem, so the new algorithm is suitable for finding thansportion problem.