现实生活中存在各种性质的指派问题（Assignment Problem），例如，若干项工作需要分配给若干个人员（或部门）来完成、若干项工程需要选择若干个建筑公司来承包、若干门课程分配给若干个教师来教授等。这类问题可以表述为：给定一系列需要完成的任务（Tasks）及一系列完成任务的被指派者（Assignees），每个被指派者完成每项任务的时间（或成本、效率）不同，需要解决的问题：确定哪个被指派者去完成哪项任务，以保证总体的效果最好。这类问题被称为指派问题或分配问题。标准指派问题的数学模型为
标准的指派问题是一类特殊的整数规划问题，又是特殊的0-1规划问题和特殊的运输问题。虽然可以采用分支定界法、割平面法、隐枚举法、表上作业法等，但最有效和最常用的是匈牙利算法。1955年美国数学家库恩（W.W.Kuhn）利用匈牙利数学家康尼格（D.Konig）证明的两个定理，提出了求解指派问题的一种算法，称为匈牙利算法[274]。
定理2.1 若从指派问题的系数矩阵C=（cij）n×n的某行（或某列）各元素分别减去一个常数k，得到一个新的矩阵C′=（c′ij）n×n，则以C和C′为系数矩阵的两个指派问题具有相同的最优解。
推论2.1 若将指派问题的效率矩阵每一行及每一列分别减去各行及各列的最小元素，则得到的新指派问题与原指派问题有相同的最优解。
定理2.2 系数矩阵C中独立零元素的最多个数等于能覆盖所有零元素的最少直线数。
求解指派问题的匈牙利算法如下：
Step1：变换效率矩阵
令效率矩阵的各行各列都减去当前各行、各列中的最小元素，得到的新效率矩阵各行各列必然出现零元素。
Step2：试指派。若有n个加圈的独立零元素，则得到最优解，算法停止；否则，转到Step3。
Step3：做最少的直线覆盖当前所有零元素。(www.xing528.com)
（1）若某行没有划圈的零元素，则打“√”；
（2）在打“√”的行中，对划圈零元素所在列打“√”；
（3）在打“√”的列中，对划圈零元素所在行打“√”；
（4）重复（2）和（3），直到再也找不到打“√”的行或列为止。
（5）在没有打“√”的行画一横线，在打“√”的列画一竖线，这样就得到了覆盖所有零元素的最少直线数。
Step4：进行矩阵变换增加零元素，然后转到Step2。
（1）从没有被直线覆盖的所有元素中，找到最小元素；
（2）所有未被直线覆盖的元素减去最小元素，横线和竖线交叉点处的元素加上最小元素，其他元素不变。
免责声明：以上内容源自网络，版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。
