指派问题的改进算法

宋雨晴

（浙江海洋学院数理与信息学院 浙江 舟山 316000）

在生活中，我们经常遇到这样的问题，某单位需要完成n项任务，恰好有n个人可承担这些任务。又由于每个人的专长不同，各人完成任务所费的时间效率不尽相同。于是产生应指派哪个人去完成哪项任务，使完成n项任务的总效率最高，即所需的时间或所消耗的资金等最小。这类问题称为指派问题或分派问题（assignment problem）。

1 指派问题的标准形式和数学模型

例1、有一份说明书，需译成英、日、德、俄四种文字。现有甲、乙、丙、丁四个人，他们将说明书译成不同文字所需的时间如下表所示。问应指派哪个人完成哪项工作，使所需的总时间最少?

表1

有n项任务，n个完成人，第i人完成第j项任务的代价为 cij（i，j＝1，2，…，n）。 为了求得总代价最小的指派方案，引入0-1 型变量 xij，并令

可见指派问题是0-1型整数规划的特例。不难发现，指派问题也是运输问题的特例，其产地和销地数都为n，各产地的产量和各销地的销量都为1。

2 指派问题的求解方法——匈牙利算法

2.1 匈牙利算法

匈牙利算法是基于Hall定理中充分性证明的思想，它是部图匹配最常见的算法，该算法的核心就是寻找增广路径，它是一种用增广路径求二分图最大匹配的算法。其基本思想是修改矩阵的行或列，使得每一行或每一列中至少有一个为零的元素，经过修正后，直至在不同行 不同列中至少有一个零元素，从而得到与这些零元素相对应的一个完全分配方案。当它用于效益矩阵时，这个完全分配方案就是一个最优分配，它使总的效益为最小。这种方法总是在有限步内收敛于一个最优解。该方法的理论基础是：在效益矩阵的任何行或列中，加上或减去一个常数后不会改变最有分配。其求解步骤如下：

第一步，使指派问题的系数矩阵经变换，在各行各列都出现0元素。（1）从系数矩阵的每行元素减去该行的最小元素；（2）再从所得系数矩阵的每列元素中减去该列的最小元素（若某行或某列中已有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

例2、用匈牙利算法确定例1的最优分配方案。

解：这是一个人数等于任务数的情况，用匈牙利算法求解过程如图1。

图1

此时，◎元素的数目等于矩阵的阶数，那么这指派问题的最优解已经得到。

从而得到最优指派：

甲→俄

乙→日

丙→英

丁→德

2.2 匈牙利算法改进

在第二步即是指一个完全分配方案中，常规情况下得到的缩减矩阵是一个n阶方阵。但对于人数和任务数不相等时，所得到的的缩减矩阵是一个m×n阶矩阵（m，n不相等，不妨设m×n），则这个时候所分布在不同行不同列的0元素只要达到m个即可，若不够则转下一步。是的覆盖所有0元素的最少直线数达到m条即可。这既减少了计算步骤，也简化了算法。

2.2.1 人数等于或多于任务数的情况

人数等于或多于任务数时，要求每一项任务只能由一个人去完成。这是只要按照改进匈牙利算法即可找到m条直线。 如例1、例2。

2.2.2 任务数多于人数的情况

任务数多于人数时，一般要求每一项任务只能有一个人完成，但一个人可以完成多项任务。这是先按照改进匈牙利算法找到m条直线，如果最后一个效益矩阵中未被分配的任务所在列（行）不含有零元素或者未被分配的任务数多余1个，则返回到第一步，直到所有的任务都被分配为止;如果最后一个效益矩阵中未被分配的任务所在列（行）只剩下1列（行），且含有0元素，则根据未被分配的任务所在列（行）中的0元素与原效益矩阵结合，找出完成该项任务的最优解。

例3、某班级准备从5名游泳队员中选择4人组成接力队，参加学校的4×50m混合泳接力比赛。5名队员4种姿势的50m平均成绩如表2所示。问应如何从中选拔一个4×50m混合泳的接力队，使预期的比赛成绩为最好（图表 2）。

表2 5名队员4种泳姿的50m平均成绩

解法1（匈牙利算法）如图2

图2

经过以上5步得到了最优方案：赵——自由泳，钱——蝶泳，王——蛙泳，周——仰泳。这时的最好成绩为：29.2＋28.5＋34.7＋35.4＝127.8（s）。

解法2（改进后的匈牙利算法）如图3

而改进后的匈牙利算法只需2步就得到了我们想要的最优方案：赵——自由泳，钱——蝶泳，王——蛙泳，周——仰泳。 这时的最好成绩为：29.2＋28.5＋34.7＋35.4＝127.8（s）。

图3

3 削高排除法

对于最初给定的指派问题矩阵A，可将其理解为圈圆个数为0的带圈指派长阵A0。此时自然有minA0＝minA。对于这个A0：

第一步，首先，尽可能多的找出一组属于不同行不同列的k个行最小元素。将这些行最小元素分别用“ ”圈出来。

第二步，对A0尽可能多的连续实现ψ变换。ψ变换的实施，不仅有利于找到一组更多的属于不同行不同列的行最小元素，而且能使许多隐含的非指派元显露出来。

第三步，对连续实现ψ变换后的所成矩阵，运用削高排除辅助定理，判定出一组尽可能多的属于不同行不同列的行最小元素所在裂地集合D。

第四步，在这个连续实现ψ变换后的所成矩阵上，对其列坐标属于列坐标集D的格列所在元实施削高排除辅助定理，得一与A0同阶的带圈指派矩阵B0。由于这个B0满足minB0＝minB，可对这个B0按上述4个步骤继续求解，直到最后求出整个问题的解为止。这就是削高消除法的一般求解过程。

例4、求解指派矩阵A所决定的指派问题，这里

解：在A中可以标出4个属于不同行不同列的行最小元素，这种标定有很多种组合，先去下面的标定：

观察指派矩阵的行严格最小元（小于它所在行中其他各元的元），可确立简便的同解的矩阵。在这里，我们规定，用在aij顶上标出常数c的方法表示在A的第j列各元上同时加上常数 c 的所成矩阵 B。 与 A 同解的指派矩阵 B=ψ1（5，5）ψ5（3，1）（A）（取此标定，不是唯一）

此时，B中存在属于不同行不同列的5个行最小元。对B进行削高排除法，得一与B同解的带圈指派矩阵D0。

将矩阵中所在行或所在列中其他非圈元为圈元，最后得到E0与D0同解，

［1］李维铮.运筹学[M].3 版.清华大学出版社，2005，6.

［2］张新辉.任务数多于人数的指派问题[J].1997.

［3］张伯生，范君晖，田叔阁.运筹学[M].科学出版社，2008，1.

［4］廖敏.运筹学基础与应用[M].南京大学出版社，2009，6.

［5］孙麟平.运筹学[M].科学出版社，2005，7.