第五节指派问题与匈牙利法

3.5.1标准指派问题及其数学模型

在现实生活中，经常会遇到各种性质的指派性问题，如某单位需要完成项任务，恰好有个人可承担这些任务。由于每人的专长不同，因而完成不同任务所费时间或效率也不同。于是指派哪个人去完成哪项任务，才能使完成项任务的总效率最高(或所需总时间最小)。类似的问题如项加工任务，怎样指派到台机床上分别完成；条航线，怎样指派艘船去航行；个班级，怎样指派到个教室上课等。这类问题基本要求都是在满足特定的指派要求下，使总体效果最佳。这类问题称为指派问题或分派问题(Assignment Problem，简称AP)。

对于个人做件事的指派问题，都需要有一个系数矩阵，其元素表示指派第个人去完成第项任务时的效率(或时间、成本等)。

引入0−1变量，其意义如下：

当问题要求是极小化时，一般的指派问题数学模型为：

其中第一个约束条件说明每一项任务都只能由一人去完成，第二个约束条件说明每人都只能完成一项任务。

对于指派的每一个可行解，可用下列解矩阵表示

上述矩阵中，每列元素都有且仅有一个元素为1，其它的元素都为0，表示每件事有且仅有一个人去做；每行元素也有且仅有一个元素为1，其它的元素都为0，表示每个人有且仅有一件事要做。

3.5.2标准指派问题的求解——匈牙利法

从指派问题的数学模型可以看出，它是0−1规划的特例，也是运输问题的特例，即在运输问题中，生产地的数目等于销售地的数目，每个生产地的产量和每个销售地的销量都等于1。当然可以用分枝定界法、割平面法、隐枚举法和求解运输问题的表上作业法去求解。但由于它的特殊性，可以寻求更简便的解法。

指派问题的最优解具有这样的性质，若从系数矩阵的一行(列)各元素中分别减去该行(列)的最小元素，得到新矩阵，那么以矩阵为系数矩阵求得的最优解和原系数矩阵求得的最优解相同。利用这一性质，数学家库恩(W.W.Kuhn)于1955年提出了指派问题的解法。他引用了匈牙利数学家康尼格一个关于矩阵中0元素的定理：系数矩阵中0元素最多个数等于能覆盖所有0元素的最小直线数。这种解法称为匈牙利法。

采用匈牙利法的求解步骤如下：

(1)变换系数矩阵。

先从系数矩阵的每行元素减去该行的最小元素，再从所得系数矩阵的每列元素中减去该列的最小元素。若每行(列)已有0元素，那就不必再减了。这样，系数矩阵各行各列中都出现0元素，同时又不会出现负元素。

(2)进行试指派。

经第一步变换后，系数矩阵中每行每列都已经有了0元素；但须找出个独立的0元素(即行或列中只有一个0的0元素)。若能找出，就以这些独立0元素对应的元素为1，其余为0，这就得到最优解。在较小时，可用观察法、试探法去找出个独立的0元素。若较大时，就必须按照一定的步骤去找，常用的步骤如下。

①从只有一个0元素的行(列)开始，给这个0元素作标记，如在该元素上画圈，记作◎，表示此行所代表的人只做这列的任务(或此事只由这人来做)。然后划去◎所在列(行)的其他0元素，记作φ，表示这列所代表的任务已指派完，不必再考虑别人了(或此人已被指派任务，不再做其它事)；

②再从只有一个0元素的列(行)开始，给这个0元素标记为◎，将其所在的行(列)划去的0元素划去，记作φ；

③反复进行(1)、(2)两步骤，直到所有0元素都作标记和划掉为止；

注：若同行(列)的0元素至少有两个(表示对这人可以从两项任务中指派其一)。这可用不同的方案来试探。从剩有0元素最少的行(列)开始，比较这行各0元素所在列中0元素的数目，选择0元素少的那列(行)的这个0元素作标记(表示选择性较多的要“礼让”选择性少的)，然后划掉该列(行)。可反复进行，直到所有列(行)划掉为止。

④若标记◎的元素数目等于矩阵的阶数，那么这个指派问题已得到最优解，解矩阵中，对应于系数矩阵中作标记◎的位置，该元素取1，其它元素取0，就形成了最优解。若标记◎的元素数目小于矩阵的阶数，则转入下一步。

(3)画直线

作最少的直线覆盖所有的0元素，以确定该系数矩阵能找到最多的独立元素数。具体做法如下：

①对没有◎的行打√；

②在打√的行中，对φ所在的列打√；

③在打√的列中，对◎所在的行打√；

④重复②和③，直到再也找不到可以打√的行名列为止；

⑤对没有打√的行画一横线，对打√的列画一纵线，这样就得到了能覆盖所有0元素的最少直线数。

若直线数等于系数矩阵的阶数，而已找出的独立0元素数目小于，则要回到(2)，进行再次试指派；若直线数小于系数矩阵的阶数，说明必须再变换当前的系数矩阵，才能找到个独立的0元素，转入下一步。

(4)再次变换系数矩阵。

变换的目的是增加独立的0元素，具体方法如下：

①在未被直线覆盖的元素中找出最小元素；

②对打√行各元素都减去该最小元素；

③对打√列各元素都加上该最小元素。

(5)对上一步得到的新系数矩阵再进行试指派，若标记◎的元素数目小于矩阵的阶数，再重复(3)和(4)，直到得到最优解为止。

现通过具体实例来说明匈牙利法在求解指派问题中的应用过程。

【例3.4】有四个工人，要指派他们分别完成4种工作，每人做各种工作所消耗的时间如表3-8所示，试作指派方案，使总的消耗时间最小。

表3-8

解：变换指派问题的系数矩阵，对各行减去该行的最小元素，再对每列减去该列的最小元素，使各行各列中都出现0元素，得到新的系数矩阵。

根据系数矩阵进行试指派，第一行只有一个0元素，将该元素标记为◎；第二行也只有一个0元素，将该元素标记为◎，同时将该元素所在的第四列中其它0元素记为φ；第二列只一有元素，将该元素标记为◎，同时将该元素所在的第三列中其它0元素记为Φ。得到解矩阵如下：

由于解矩阵中独立0元素的个数3小于系数矩阵的阶数4，所以需要对系数矩阵进行变换。对第四行打√，接着对第四列打√，再对第二行打√。对没有打√的第一行和第三行画一横线，对打√的第四列画一纵线，这样就得到了能覆盖所有0元素的最少直线数，结果如下：

在未被直线覆盖的元素中找出最小元素“1”，对第二行和第四行中各元素都减去1，对第四列中各元素都加上1，得到新的系数矩阵。

再根据系数矩阵进行试指派，得到解矩阵如下：

由于解矩阵中独立0元素的个数3小于系数矩阵的阶数4，所以需要再次对系数矩阵进行变换。对第四行打√，接着对第四列打√，再对第二行打√，再对第一列打√，再对第一行打√。对没有打√的第三行画一横线，对打√的第四列和第一列画纵线，这样就得到了能覆盖所有0元素的最少直线数，结果如下：

在未被直线覆盖的元素中找出最小元素“2”，对第一行、二行和第四行中各元素都减去2，对第一列和四列中各元素都加上2，得到新的系数矩阵。

再根据系数矩阵进行试指派，结果解矩阵如下：

上述解矩阵中，独立0元素的个数等于系数矩阵的阶数，即每行每列都有独立0元素，这就得到了最优解。由解矩阵得最优指派方案为：甲做工作，乙做工作，丙做工作，丁做工作，所需要总时间为70个单位。

3.5.3一般指派问题及其求解

在实际生活中，经常会碰到各种非标准形式的指派问题，处理的方法是先将其转化为标准形式，再用匈牙利法求解。

(1)最大化指派问题

若要使指派方案的目标为最大，如效率最高，效益最大等等。可按如下方法转化为最小化。

设最大化指派问题系数矩阵，其中最大元素为，用减去系数矩阵中的每一个元素，就得到新的系数矩阵，，则以为系数矩阵的最小化指派问题和以为系数矩阵的最大化指派问题有相同最优解。

(2)人数和事数不等的指派问题

处理方式和产销不平衡的运输问题一样。若人少事多，则添上一些虚拟的人，这些虚拟的人做各事的费用系数可取0，理解为这些费用实际上不会发生；若人多事少，则添上一些虚拟的事，这些虚拟的事耗费各人的费用系数为0，理解为这些费用实际上不会发生。

(3)某人可做几件事的指派问题

若某个人可做几件事，则可将此人化为几个人来接受指派，这几个人做同一件事的费用系数是一样的，这样就可以转化为一人做一件事的指派。

(4)某事一定不能由某人做的指派问题。

若某一件事不能指派给其中某一个人，则将相应的费用系数取作足够大的数M，这样在指派的时候不会将相应的系数转化为0元素，即解矩阵中相应的元素不会取1。

(5)如果事比人多一件，且存在一个人可做两件事时的指派问题。

处理方式是添加虚拟的人，费用系数为各人之最佳值。