匈牙利解法

2．匈牙利解法

2.1匈牙利解法的基本步骤

从数学模型可知标准的指派问题是特殊的整数规划问题，又是特殊的0—1规划问题和特殊的运输问题，因此，它可以用各种相应的解法来求解。但是，这些解法都没有充分利用指派问题的特殊性质。目前，常用来求解指派问题的方法是匈牙利数学家克尼格的方法，习惯上称之为匈牙利解法。

匈牙利解法的依据是指派问题最优解的以下性质：设指派问题系数矩阵C=（c_ij）n×n。若将C的一行（或列）各元素分别减去一个常数k（如该行或列的最小元素），则得到一个新的矩阵C′=（c_ij′）n×n。那么，以C’为系数矩阵的指派问题和以C为系数矩阵的原指派问题有相同最优解。

这个性质容易理解，由于系数矩阵的这种变化并不影响约束方程组，只是使目标函数值减少了常数k，所以，最优解并不改变。

必须指出，虽然不必要求指派问题系数矩阵中无负元素，但在用匈牙利解法求解指派问题时，为了从已变换后的系数矩阵中判别能否得到最优指派方案，要求此时的系数矩阵中无负元素。因为只有这样，才能从总费用为零这一特征断定此时的指派方案为最优指派方案。

对于标准的指派问题，匈牙利解法的一般步骤可以表述如下：

步骤一：变换系数矩阵，使各行和各列皆出现零元素。

如各行及各列分别减去本行及本列中最小元素，这样可保证每行及每列中都有零元素，同时，也避免了出现负元素。

步骤二：做能覆盖所有零元素的最少数目的直线集合。此时，若直线数等于n，则已可得出最优解。否则，转步骤三。

对于系数矩阵非负的指派问题来说，总费用为零的指派方案一定是最优指派方案。在步骤一的基础上，若能找到n个位于不同行、不同列的零元素，则对应的指派方案总费用为零，从而是最优的。当同一行（或列）上有几个零元素时，如选择其一，则其余的零元素就不能再被选择，从而成为多余的。因此，重要的是零元素能恰当地分布在不同行和不同列上，而并不在于它们的多少。但步骤一并不能保证这一要求。若覆盖所有零元素的最少数目的直线集合中的直线数目是n，则表明能做到这一点。此时，可以从零元素最少的行或列开始圈“0”，每圈一个“0”，同时把位于同行和同列的其他零元素划去，如此逐步进行，最终如果可得n个位于不同行、不同列的零元素，它们就对应了最优解；若覆盖所有零元素的最少数目的直线集合中的元素个数少于n，则表明无法实现这一点。为此，需要对零元素的分布做适当调整，这就是步骤三。

步骤三：变换系数矩阵，使未被直线覆盖的元素中出现零元素。回到步骤二。

在未被直线覆盖的元素中总有一个最小元素。对未被直线覆盖的元素所在的行（或列）中各元素都减去这一最小元素，这样，在未被直线覆盖的元素中势必会出现零元素，但同时却又使已被直线覆盖的元素中出现负元素。为了消除负元素，只要对它们所在的列（或行）中各元素都加上这一最小元素（可以看作减去这一最小元素的相反数）即可，也可以直接在直线相交处的元素加上这一最小元素，未被直线覆盖的元素减去这一最小元素，被直线覆盖而没有相交的元素不变。

2.2匈牙利解法举例

现在，我们来解例3.24。

例3.24指派问题的系数矩阵为

（2）初始分配

从零元素最少的行或列开始圈“0”，每圈一个“0”，同时把位于同行和同列的其他零元素划去，如果该行（或列）的零元素（已经划掉的不再考虑）多于一个，则被圈的零元素所在之列（或行）应当是零元素最少的。如此反复进行，找到初始方案。

（3）利用行列标号，画直线

利用行列标号，做能覆盖所有零元素的最少数目的直线集合。1）打√

①行无（）的打√；

②打√行有／的列打√；③打√列有（）的行打√；

④反复进行，直至打不下去为止。

（4）继续缩减矩阵

在未被直线覆盖的元素中的最小元素为1，在直线相交处的元素加上这一最小元素，未被直线覆盖的元素减去这一最小元素，被直线覆盖而没有相交的元素不变。

（5）调整分配

可得5个位于不同行、不同列的零元素，它们就对应了最优解，获得最优分配。本题最优解为：

也就是说，最优指派方案为：让A₁装修B₃，A₂装修B₂，A₃装修B₁，A₄装修B₄，A₅装修B₅，这样，总的装修费用最少，为7+9+6+6+6=34万元。