Assignment Problem匈牙利法研讨  

Assignment Problem Hungarian Law Deliberation

作　　者：宋占奎[1] 

机构地区：[1]湖北十堰职业技术学院,湖北十堰442000

出　　处：《陕西教育学院学报》2009年第2期93-96,共4页Journal of Shaanxi Institute of Education

摘　　要：目的Assignment Problem求最优解.方法应用匈牙利法,变换效益矩阵到缩减矩阵,再得最优解矩阵.结果由最优解矩阵得最优Assignment Problem,最终求得了最优解.结论对任务和人数相等、某任务不能由某人去做以及对任务和人数不等的Assignment Problem,都可用匈牙利法求得最优解。匈牙利法的基本原理是:如果在一个费用矩阵里,变换效益矩阵C,确保每行、每列有且仅有一个0打上"*",由此找到n个独立0的位置,从而得到另一个矩阵,并对这个矩阵进行分派所得出的费用为最小,求出最优Assignment Problem,则这样的分派对原费用矩阵也会得最小费用.Aim： The Assignment Problem asks the optimal solution;Methods：Applied Hungary law, Transformation benefit matrix to deflation matrix, again optimal solution matrix;Results：By optimal solution matrix most superior assignment problem has obtained the optimal solution;Conclusions： To the duty and the population equal, some duty cannot do by somebody as well as to the duty and the population different assignment problem, all the available Hungarian law obtains the optimal solution. Hungary＇ s method basic principle is： If in an expense matrix, transformation benefit matrix C, guarantees each line, includes also only has one every time 0 to get ＂ ＊ ＂, from this found the independence 0 positions, thus obtains another matrix, and carries on the expense to this matrix which the distribution obtains for slightly, extracts the most superior assignment problem. Then such distribution also can result in the minimum-cut to the original expense matrix.

关 键 词：效益矩阵 匈牙利法 增零变换 缩减矩阵 最优解 

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