数学建模中常见的任务分配问题，有时也叫做婚配问题，这是一个整数线性规划的问题，一般使用匈牙利算法进行求解。N个人分配N项任务，一个人只能分配一项任务，一项任务只能分配给一个人，将一项任务分配给一个人是需要支付报酬，如何分配任务，保证支付的报酬总数最小。具体问题有有一些员工要完成一些任务。各个员工完成不同任务所花费的时间都不同。每个员工只分配一项任务。每项任务只被分配给一个员工。怎样分配员工与任务以使所花费的时间最少？

匈牙利算法简介

其基本的理论基础是针对cost矩阵，将cost矩阵的一行或一列数据加上或减去一个数，其最优任务分配求解问题不变。（原因是在同一行或同一列只选取一个值因此不会改变结果）

再介绍匈牙利算法之前，先介绍几个基本概念

匹配 图G的一个匹配，是由一组没有公共端点的不是圈的边构成的集合。其中有两个重点:一是匹配是变的集合，二是在该集合中任意两条边不能有共同的顶点。

二部图 给定两组定点，但是组内的任意两个顶点间没有边相连，只有两个集合之间存在边，即组1内的点可以和组2内的点相连，这样构建出来的图叫做二部图。

完美匹配 考虑部集为X={x1，x2…}和Y={y1,y2…}的二部图，一个完美匹配就是定义从X-Y的一个双射，依次为x1，x2，…，xn找到配对的顶点，最后能够得到n！个完美匹配。

最大匹配 即两个二部集中实现最多的配对。

Nature：完美匹配一定是最大匹配，最大匹配不一定是完美匹配。

交错路径：给定图G中的一个匹配M，如果一条路径的边交替出现在M中和不出现在M中，我们称之为一条M-交错路径。

M-增广路径 如果一条M-交错路径，它的两个端点都不与M中的边关联，我们称这条路径为M-增广路径。

而我们要寻找最大路径也就是在不断寻找增广路径的过程，当图中没有增广路径了，也就意味着我们找到了该图的最大匹配了。

而匈牙利算法寻找最大匹配，就是通过不断寻找原有匹配M的增广路径，因为找到一条M匹配的增广路径，就意味着一个更大的匹配M’，其恰好比M多出一条边。而对于图来说，最大匹配不是唯一的，但是最大匹配的大小是唯一的。

对于我们要解决的分配问题来说，不同的路径有着不同的的权重，从而可以求得最大匹配的不同的值，最终找到最佳的解决方案。

   匈牙利算法的实际操作

1、 每一行减去该行最小的一个数；

2、 每一列减去该列最小的一个数；

3、 必须用尽可能少的列或行标记来覆盖矩阵中的所有零；

4、 如果覆盖0的行列数量是n，则我们的步骤结束，如果小于n，则进入下一步

5、 找出没有被覆盖的最小值，则没有被覆盖的每行减去最小值，没有被覆盖的列加上最小值。

6、 跳转步骤三，直至结束。

7、 分配结果就是合适的0的位置。

通过这种方法，也就是对上边原理的利用，可以找到最大路径，且考虑了不同路径的权重。

具体实现代码参见csdn。