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

Improvement of Hungary Solution for the Maximum Assigned Problem

作　　者：杨光煜[1] 张雷顺[2] 

机构地区：[1]天津财经学院信息系,天津300040 [2]郑州工业大学水利与环境工程学院,河南郑州450002

出　　处：《郑州工业大学学报》2001年第2期57-58,64,共3页Journal of Zhengzhou University of Technology

摘　　要：针对指派问题中最小化问题的匈牙利解法 ,提出一种不同于传统解法的最大化问题的求解方法 .该方法不必一开始就去用新的系数矩阵代替原系数矩阵 ,而是可直接在原系数矩阵上进行求解 ,只是求解过程中的一些原则与最小化问题的求解原则有所不同 .由于其解题步骤的多少与先后同最小化问题解题步骤的多少与先后是相对应的 ,所以可用同一段带系数的程序去解决最大化、最小化两个不同的问题 .此方法简捷、直观 。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.

关 键 词：指派问题 匈牙利解法 最大化问题 系数矩阵 求解原则 解题步骤 

分 类 号：O224[理学—运筹学与控制论]