对最大化指派问题的匈牙利解法的一点改进

针对指派问题中最小化问题的匈牙利解法,提出一种不同于传统解法的最大化问题的求解方法.该方法不必一开始就去用新的系数矩阵代替原系数矩阵,而是可直接在原系数矩阵上进行求解,只是求解过程中的一些原则与最小化问题的求解原则有所不同.由于其解题步骤的多少与先后同最小化问题解题步骤的多少与先后是相对应的,所以可用同一段带系数的程序去解决最大化、最小化两个不同的问题.此方法简捷、直观,为计算机上解法的实现提供了方便途径.

Improvement of Hungary Solution for the Maximum Assigned Problem

Based on Hungary solution for the minximum assigned problem, this paper puts forward an solution for the maximum problem which is different from the traditional solution. This solution can solve problem by original coefficient matrix directly. Instead of replacing the original coefficient matrix with new coefficient matrix from beginning, but some principles in the course of solution are different from the minximum problem. Because the number of procedure and the order of solution are always correspomding with that of the minximum problem, we can make use of the program of the same segment with coefficient to solve the maximum and minximum problem. This solution is short-cut and audio-visual, and provides the comvenient approach for realizing the solution by computer.