什么是分配问题？

  分配问题也称指派问题，是一种特殊的整数规划问题，分配问题的要求一般是这样的：n个人分配n项任务，一个人只能分配一项任务，一项任务只能分配给一个人，将一项任务分配给一个人是需要支付报酬，如何分配任务，保证支付的报酬总数最小。
  简单的说：就是n*n矩阵中，选取n个元素，每行每列各有一个元素，使得和最小。

匈牙利算法

  解决分配问题的算法有多种，但是最常用的是匈牙利算法。

什么是匈牙利算法？
1）理论基础：
  若从指派问题的系数矩阵的某行（列）各元素中分别减去或者加上常数k，其最优任务分解问题不变。
2）匈牙利算法的流程图

3）.计算步骤
  下面用一个简单的例子来说明
例如：有A、B、C、D四项任务，需要分配给甲乙丙丁四个人来完成。他们完成任务所需要支付的酬劳如下表所示，问，如何分配任务，可使总费用最少？

得到的支付矩阵是：

Step 1: 行归约

找出每行的最小元素，分别从每行中减去这个最小元素；
矩阵变换如下：

Step 2 : 列归约

找出每列的最小元素，分别从每列中减去这个最小元素

经过以上两步变换，矩阵的每行每列都至少有了一个零元素。接下来就进行第三步，试着指派任务。

Step 3 : 指派任务

① 确定独立零元素。
i 从第一行(列)开始，若该行（列）中只有一个零元素，对该零元素标1，表示这个任务就指派给某人做。
每标一个1，同时将该零元素同列的其他零元素标为2，表示此任务已不能由其他人来做。（此处标1、2的操作与课本画圈、划去操作同理）

如此反复进行，直到系数矩阵中所有的零元素都已经被标为1或者2为止。
  我们得到的矩阵如下：

② 指派
我们观察到，系数矩阵中标记为1的零元素正好等于4，这表示已经确定了最优的指派方案。

此时，只需将0（1）所在位置记为1，其余位置记为0，则获得了该问题的最优解。

最优解为：

即：A任务交给丙负责，B任务交给丁负责，C任务交给甲负责，D任务交给乙负责。

此时总报酬为：1+5+2+3 = 11；