信息系统项目管理师计算题考点：指派问题(匈牙利算法)

指派问题——所谓指派问题是指这样一类问题：有n项任务，恰好有n个人可以分别去完成其中任何一项，由于任务的性质和每个人的技术专长各不相同，因此，各人去完成不同任务的效率也不一样。于是提出如下问题：应当指派哪个人去完成哪项任务，才能使总的效率最高?类似的指派问题还有：n台机床加工n项任务;n条航线安排n艘船或n架客机去航行等。

指派问题一般用匈牙利算法进行求解：

算法本质：变换系数矩阵，找到n个不同行不同列的0元素，以求解指派问题最有解

【例题详解】

某项目有Ⅰ、Ⅱ、Ⅲ、Ⅳ四项不同任务，恰有甲、乙、丙、丁四个人去完成各项不同的任务.由于任务性质及每人的技术水平不同，他们完成各项任务所需时间也不同，具体如下表所示

项目要求每个人只能完成一项任务，为了使项目花费的总时间最短，应该指派丁完成()任务。

A.Ⅰ

B.Ⅱ

C.Ⅲ

D.Ⅳ

【答案】C

步骤一：系数矩阵初等行列变换，使各行各列都出现0元素

1、每行减去该行最小元素，使得每行都出现0元素

2、每列减去该行最小元素，使得每列都出现0元素

注意：有0元素的就不需要减了

 注意：必须先变行 , 然后再变列 , 行列不能同时进行改变 ; 否则矩阵中会出现负数 , 该矩阵中不能出现负数 ;

步骤二：试指派，寻找最优解

题目的约束条件为每个人只能完成一项任务，那么简单来说就是每行每列只能有1个0元素。

1、找只有一个0元素的行，给这个0元素标记下，同时划去该列其它0元素，这表示这列的任务已经派完了

2、找只有一个0元素的列，给这个0元素标记下，同时划去该行其它0元素。重复1、2两步，直到所有0元素有标记或被划去。最终我们可以得到下表，每行每列均标记了1个0元素。

3、上表中刚好每行每列都仅有1个0元素，符合题目要求，所以到此就指派完成了，也就是找到最优解了：甲去完成任务IV；乙去完成任务Ⅱ；丙去完成任务I；丙去完成任务Ⅲ所以该题答案选择C。

温馨提示：上题中是比较理想的情况，有时候还会出现特殊情况（注：本文就不做详细的图文描述了，大家可以网上搜索相关信息看下，最好看看视频讲解）。

特殊情况：

1、出现零元素的闭合回路

在确定0元素时如仍然有没有标记的零元素，且同行(列)的0元素至少有两个(表示对这个可以从两项任务中指派其一)。这时可用不同的方案去试探。从剩有零元素最少的行开始，比较这行各0元素所在列中0元素的数目，选择0元素少的那列的这个0元素标记（因为一列中零元素多，说明可派的人选择较多，我们应派可选择较少的任务)，然后去掉同行同列的其他0元素。可反复进行，直到所有的0元素都已经圈出和去掉为止。这种情况一般会出现多个解！

2、标记的0元素个数小于n

遇到这种情况我们可以进行“画盖0线”，即以最少的直线覆盖所有0元素，确定当前系数矩阵中能找到的最多的0元素。按以下步骤进行:

步骤一：

(1）对没有标记的行打√ ;

(2）对已经打√行中所有含有划掉0元素的列打上√ ;

(3）再对打有√的列中含有标记元素的行打√ ;

(4)重复第2,3步，直到无法继续打√为止;

(5)对没有打√的行划线，对打√的列划线。这就得到了覆盖所有0元素的最少直线数。若直线数l<n，说明需增加0元素，转下一步：

步骤二：增加0元素：

对第一步中没有被直线覆盖的部分中找出最小元素，然后在打√行各元素中都减去这个最小元素，打√列的各元素多加上这个最小元素，以保证原来的0元素不变。这样得到的新矩阵（和原来同解)，若得到n个独立的0元素，则已经得到最优解，否则需回到上—步重复进行。