许多管理部门可能经常面临这样的问题：有若干件事情需要人去完成，又有若干人员能够完成各项事情。由于每人员的特点与能力不同，完成各项事情的效益也不相同。 又因事情的性质和管理上的需要等，每项事情只能由一个人完成，则应如何分配人员去完成所有事情，能使完成各项事情总效益最佳？这类问题就称之为指派模型分配模型。

先分析事情数与人员数相等时的指派模型。更具体点，设有五项工程A，B，C，D，E，需分配①、②、③、④、⑤五个公司去完成。每个公司只能完成一件工作，每项工程只能由一个公司去完成。五个公司分别完成各项工程的报价如表9.1所示。问如何分配工程才能使总费用最省？

表9.1五个公司对各项工程的报价表（单位：万元）

为叙述方便，将上述报价表写成矩阵形式（称为效益矩阵）。注意到矩阵内的元素都是正数，即 。

指定每个公司完成一项工程，就是在矩阵的每一行取一个数而只取一个数；指定每项工程由一个公司完成就是在矩阵的每一列取一个数而只取一个数。一种指派方案就是在矩阵中取不同行、不同列的五个数。所取五个数之和就是这种方案的总费用。于是问题变成：

在效益矩阵中取不同行、不同列的五个数，使这五个数之和最小。

思考 所有可取的方案总共有几个？

1、先施行如下的变换：矩阵每一行中的各数减去该行的最小数，每列中的各数减去该列的最小数。由分析可以知道，对变换后的矩阵求得的最优方案，就是原效益矩阵的最优方案。这个过程表示如下：矩阵外右边的数表示对应的行中的最小数，作变换时该行的每个数减去该数；得到第二个矩阵；第二个矩阵外下边的数表示同一列中的最小数，作变换时该列的每个数减去该数。这样，变换后得到的矩阵每个数非负，且在每一行中至少有一个零，每列中也至少有一个零。

2、对于这样的矩阵，如果在不同行、不同列有五个零，则按零所在位置指派工作，必然是最优方案。

对于一个5阶矩阵，是否有不同行、不同列的五个零，可以用下面的方法检验： 寻找覆盖所有零元素的最少直线（只考虑水平直线和垂直直线）。如果可以用少于5（不能等于5）条直线覆盖所有零元素，则还没有找到最佳方案。例如上述矩阵可用四条直线覆盖矩阵中所有的零元素：

3、调整，使之增加一些零元素。为此，在没有被直线覆盖的元素（没有零元素）中找出的最小元素，这里。然后将矩阵按如下的法则变换成：

• 所有没有被覆盖的元素减去；
• 所有在直线交叉点上的元素加上；
• 其余（被覆盖但不在交叉点上的元素）保持不变。

对这个矩阵再用直线覆盖的方法检验是否得到了最优方案。对上述矩阵确实找到了最佳方案：在上述矩阵中可以挑出不在同一行、同一列的五个零，用标出：

这时的指派方案为：①完成B、②完成A、③完成E、④完成D、⑤完成C。总费用为 （万元）。

这个问题有多个最优解，例如

也是最优解：①完成D、②完成A、③完成E、④完成B、⑤完成C，总费用也是15万元。

思考

上例还有一个最优解，你能找出来吗？

思考

1. 如果人员数与任务数不等时这个方法应如何改进？

2. 如果最佳方案是要求最大值而不是求最小值，这个方法应如何改进？

1. 人员数与任务数不等

如果上例中只有A，B，C，D四项工程要完成，却有①、②、③、④、⑤五个公司报价，应该如何指派哪四个公司来完成这四项工程？这时人员数与任务数不相等的情况。

表9.2五个公司对各项工程的报价表（单位：万元）

有一种办法就是虚加一个工程E，每个公司的报价都是0，即把上表转为

表9.3五个公司对各项工程（包含虚工程）的报价表（单位：万元）

然后按任务数与人员数相等时的情况求最佳方案，其中指派到完成E的公司事实上在竞争中出局。

此时也得到多种最佳方案，例如其中一种：①出局、②完成A、③完成C、④完成D、⑤完成B。

2 最佳方案要求最大值

某公司要招聘翻译、文书、项目经理、广告策划各一名，进行了外语、计算机、管理学和传媒学的考试。现录取了四个应聘者，他们各门课程的考试成绩如下表。问如何分配他们的岗位？

表9.4 四个应聘者的考试成绩一览表

假设各门课程的考试成绩真实地反映了这些应聘者的能力，这就是说，A做翻译的能力为84分，做文书的能力为81分，做项目经理的能力为77分，做广告策划的能力为83分等等。分配一个应聘者到一个岗位上表明发挥了他相应的的能力：例如分配A任广告策划，其实是发挥了他85分的能力。分配四个人担任各个岗位的最佳方案，就变成在上述表格中取不同行、不同列的四个数，使其和达到最大。

怎样把这个问题化为上述求最小值的问题从而可以用匈牙利算法求解？一种办法就是将各人的实际得分换算成各门课程考试成绩被扣去了几分。将上表改写成下表：

表9.5 换算后四个应聘者的考试成绩一览表

分配四个人担任各个岗位的最佳方案，就变成在上述表格中取不同行、不同列的四个数，使其和达到最小。