匈牙利法：优化指派问题求解

指派问题是0-1 规划的特例，也是运输问题的特例，当然可用整数规划、0-1 规划或运输问题的解法去求解，但是，这就如同用单纯形法求解运输问题不合算一样。利用指派问题的特点会有更简便的解法，这就是匈牙利法，即系数矩阵中独立0 元素的最多个数能覆盖所有0 元素的最少直线数。

第一步：变换指派问题的系数矩阵（cij）为（bij），使在（bij）的各行各列中都出现0 元素，即：

（1）从（cij）的每行元素都减去该行的最小元素。

（2）再从所得新系数矩阵的每列元素中减去该列的最小元素。

第二步：进行试指派，以寻求最优解。

在（bij）中找尽可能多的独立0 元素，若能找出n 个独立0 元素，就以这n 个独立0 元素对应解矩阵（xij）中的元素为1，其余为0，这就得到最优解。找独立0 元素，常用的步骤为：

（1）从只有一个0 元素的行（列）开始，给这个0 元素加圈，记作◎。然后划去◎所在列（行）的其他0 元素，记作∅；这表示这列所代表的任务已指派完，不必再考虑别人了。

（2）给只有一个0 元素的列（行）中的0 元素加圈，记作◎；然后划去◎所在行（列）的0 元素，记作∅。

（3）反复进行（1）、（2）两步，直到尽可能多的0 元素都被圈出和划掉为止。

（4）若仍有没有加圈的0 元素，且同行（列）的0 元素个数至少有两个，则从剩余0 元素最少的行（列）开始，比较此行中各0 元素所在的列中0 元素的数目，选择0 元素少的那列的这个0 元素加圈（表示选择性多的要“礼让”选择性少的）。然后划掉同行同列的其他0元素。可反复进行，直到所有0 元素都已圈出和划掉为止。

（5）若◎元素的数目m 等于矩阵的阶数n，那么此指派问题的最优解已得到。若m ＜ n，则转入第三步。

第三步：作最少的直线覆盖所有0 元素。

（1）对没有◎的行打√号。

（2）对已打√号的行中所有含∅元素的列打√号。

（3）再对打有√号的列中含◎元素的行打√号。

（4）重复（2），（3）直到得不出新的打√号的行、列为止。

（5）对没有打√号的行画横线，对打了√号的列画纵线，这就得到覆盖所有0 元素的最少直线数l。l 应等于m，若不相等，说明试指派过程有误，回到第二步的（4），另行试指派；若l=m ＜ n，须再变换当前的系数矩阵，以找到n 个独立的0 元素，为此转到第四步。

第四步：变换矩阵（bij）以增加0 元素。(www.xing528.com)

在没有被直线覆盖的所有元素中找出最小元素，然后打√号，各行都减去这个最小元素，同时，各列都加上这个最小元素以保证系数矩阵中不出现负元素。新系数矩阵的最优解和原问题仍相同，转回第二步。

例4-7　有一份中文说明书，需译成英、日、德、俄四种文字，分别记作A，B，C，D。现有甲、乙、丙、丁四人，他们将中文说明书译成不同语种的说明书所需时间如表4-9 所示，问如何分派任务可使总时间最少？

表4-9　翻译说明书所需时间

第一步：变换系数矩阵：

第二步：试指派：

找到3 个独立0 元素，但m=3＜ n=4。

第三步：作最少的直线覆盖所有0 元素，即

独立0 元素的个数m 等于最少直线数，即l=m=3＜ n=4。

第四步：变换矩阵（bij）以增加0 元素：没有被直线覆盖的所有元素中的最小元素为1，然后打√号，各行都减去1，同时，各列都加上1，得到如下矩阵，并转到第二步进行试指派。

得到4 个独立0 元素，所有最优解矩阵为

即最优的分配方案为甲将说明书翻译成俄文，乙将说明书翻译成英文，丙将说明书翻译成日文，丁将说明书翻译成德文。