某项目有Ⅰ、Ⅱ、Ⅲ、Ⅳ四项不同任务，恰有甲、乙、丙、丁四个人去完成各项不同的任务。由于任务性质及每人的技术水平不同，他们完成各项任务所需时间也不同，具体如下表所示。项目要求每个人只能完成一项任务，为了使项目花费的总时间最短，应该指派丁完成(

admin2018-10-14 77

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

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

选项 A、Ⅰ
B、Ⅱ
C、Ⅲ
D、Ⅳ

答案C

解析这是一道非常复杂的分配问题(Assignment Problem)。
“项目要求每个人只能完成一项任务”，适用于匈牙利算法。
匈牙利数学家克尼格(Konig)证明了下面两个基本定理，为计算分配问题奠定了基础。因此，基于这两个定理基础上建立起来的解分配问题的计算方法被称为匈牙利算法。
假设问题求最小值，m个人恰好做m项工作，第i个人做第j项工作的效率为c_ij，效率矩阵为[c_ij]。
[定理1]如果从分配问题效率矩阵[c_ij]的每一行元素中分别减去(或加上)一个常数u_i(被称为该行的位势)，从每一列分别减去(或加上)一个常数v_j(称为该列的位势)，得到一个新的效率矩阵[b_ij]，若其中b_ij=c_ij一u_i一v_j，则[b_ij]的最优解等价于[c_ij]的最优解。这里c_ij、b_ij均非负。
[定理2]若矩阵A的元素可分成“0”与非“0”两部分，则覆盖“0”元素的最少直线数等于位于不同行不同列的“0”元素(称为独立0元素)的最大个数。
数学定理总是很难令人理解，但匈牙利算法的具体步骤还是比较简单的。
第一步：找出效率矩阵每行的最小元素，并分别从每行中减去该行的最小元素，这称之为行变换，如下图所示。