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

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

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

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

第二步：找出效率矩阵每列的最小元素，并分别从每列中减去该列的最小元素，这称之为列变换，如下图所示。

第三步：用最少的直线覆盖所有的“0”。

如果所用直线数等于矩阵的维度，即至少需要4根直线才能覆盖所有的0，则说明最优分配已经产生，可以停止行变换和列变换。
第四步：寻找四个独立的0(这四个0中的任意2个都不能出现在同一行或同一列中)。

独立的0对应着最优分配：甲完成任务Ⅳ、乙完成任务Ⅱ、丙完成任务Ⅰ、丁完成任务Ⅲ，花费的总时间=4+4+9+11=28天。
转载请注明原文地址:https://kaotiyun.com/show/vcFZ777K
本试题收录于： 信息系统项目管理师上午综合知识考试题库软考高级分类
0

信息系统项目管理师上午综合知识考试

软考高级

相关试题推荐
随机试题
最新回复(0)