分配问题匈牙利解法

---

一种依据分配问题特点而建立的求解分配模型的简便算法。

此法由匈牙利数学家克尼格提出，常称“匈牙利法”。其步骤如下：

(1)对待求解问题，正确地列出效率矩阵｛C_ij｝_n×n。

(2)简化原始矩阵表，使表中每行、每列至少出现一个0元素。

方法是：将原始表格各行元素数值同时减去本行最小元素数值，或将各列元素同时减去本列最小元素。

这样组成了一新的效率矩阵表｛C′_ij｝_n×n。

(3)在新的矩阵表中，用最少的纵线条和横线条将所有的零值划去。

当所用的线条数目不少于(一般取等于)方阵的维数(n)时，即可得到最优分配方案。

进行划线盖0时，所用直线不能同一方向；将表中0全部划去的形式有多种，但只要是所用线条数目最少的，就可选取。

符合这个要求时，可用以0定方案的方法得到最优分配方案：

❶ 找出只有一个0元素的行(或列)，用圈圈起来，于是该0元素所在列(或行)上其他0元素失效，可打×记号。

❷ 再检查其它行(或列)，对只有一个0元素(打×失效的0元素不予考虑)的，也照上法圈起来，失效元素亦打×。

❸ 重复上述过程，直至打圈0元素个数为n，且分别在不同行不同列。打圈0元素所在位置变量X_ij=1，表示该元素行对应的人员应去完成该元素列对应的任务。

其余位置变量X_ij=0₀

当盖0线条最少数目不满足要求时，必须转于下一步骤。

(4)调整变换。

对矩阵表内不同元素分别进行如下变换：

❶ 矩阵表未被盖0线条划去的元素，分别减去这些元素中的最小数，得到相应的新元素。

❷ 矩阵中处于纵横盖0线交叉点的元素，加上❶ 中减去的这个最小数。

❸ 矩阵表中其他被划去的元素，按原值不予变化。

由此变换得到一个调整后的新矩阵表｛C″_1j｝_n×n，再转入第(3)步骤。

例：用匈牙利法解下表所示的分配问题。

解：上表每行分别减去该行的最小数得到：

上表中第三列每个元素减去1，得到一个每行每列都有零值的新表，并划线覆盖0元素得：

上表中最少覆盖线有三条，小于方阵阶数4，进行调整变换。

上表中未被划去的数2、5、6、1、8、5，分别减去其中最小数1；表中交叉元素2、3分别加1；其余元素不变。

这样，得到一调整后的新表，并划线覆盖0值得：

上表中最少覆盖线仍有三条，仿上面法则进行调整运算得：

上表中最少划0覆盖线有4条，问题已达到最优解，根据“按0定方案”法则进行分配，得到4个圈零数，并在不同行和不同列，仍见上表。得到的最优分配方案为：甲－C，乙－B，丙－D，丁－A。这样分配的最短时间值为：Z=5+7+11+4=27(小时)。

上述算法只适用于工作人数与任务数目相等的极小化分配问题。

对极大化分配问题，首先找到原始矩阵表中的最大元素。然后以这个最大的数作被减数，分别减去表中所有元素，得到一个“缩减矩阵”，将“缩减矩阵”按上面方法求解即可。

上面的例子如果是求极大化分配问题，首先用表中最大数15，分别减表中各元素，得到下面的“缩减矩阵”(见下表)，即化为了极小化的分配问题。

对于工作人员与任务数目不等的分配问题，只要虚拟一些工作人员(任务多于人数时)或虚拟一些任务(人员多于任务时)，虚拟行或列在矩阵中元素值取零值。这样就转变成了人员与任务数目相等的分配问题了。