指派问题：匈牙利算法

匈牙利法的基本思路：对费用矩阵C的行和列减去某个常数，将C化为有n个位于不同行不同列的零元素，令这些零元素对应的变量取1，其余变量取0，即得到指派问题的最优解。

匈牙利法是基于指派问题的标准型的，标准型需满足以下3个条件：

（1）目标函数求min；

（2）效率矩阵为n阶方阵；

（3）效率矩阵中所有元素Cij≥0，且为常数。

匈牙利法的计算步骤：

（1）变换效率矩阵C，使每行每列至少有一个0，变换后的矩阵记为B

• 行变换：找出每行min值，该行各元素减去它；
• 列变换：找出每列min值，该列各元素减去它；
• 若某行/列已有0元素，则不用减。

（2）

（3）如果○的个数少于n，则进行这一步。

1. 对没有圈○的行打“√”；
2. 在已打“√”的行中，对×所在列打“√”；
3. 在已打“√”的列中，对圈○的行打“√”；
4. 重复2和3步骤，直到再也找不到可以打“√”的行/列为止；
5. 对没有打“√”的行画横线表示去掉这一行，对打“√”的列画横线表示去掉这一列，这样就得到能覆盖所有0的最小横线。

（4）变换矩阵B以增加0。

1. 在未被直线覆盖的所有元素中找到min；
2. 然后在打“√”的所有行中减去这个min；
3. 而在打“√”的所有列中加上这个min，以保持原来0不变(为了消除负元素)；
4. 得到新的系数矩阵C。

（5）返回步骤（2），直到得到n个0元素，即得到最优解。

指派问题的其他衍生问题：

（1）求maxZ的指派问题

找出系数矩阵中的max，然后令系数矩阵变为max-系数矩阵各元素值，得到新系数矩阵，按照正常匈牙利法即可求到。

（2）人数与工作数不等的指派问题

工作＜人数，增加虚拟工作；人数＜工作，增加虚拟工人。

（3）一个人可做几件事的指派问题

例如：一个人可以做t件事。把这个人复制成有t个人，可以做t件事，每个人做事费用都一样。

（4）某人一定不能做某事的指派问题

求minZ，Cij取正无穷M；求maxZ，Cij取0。

例题：

版权声明：本文为博主原创文章，未经博主允许不得转载。