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

admin2018-10-14 47

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

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

选项 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元素)的最大个数。
数学定理总是很难令人理解，但匈牙利算法的具体步骤还是比较简单的。
第一步：找出效率矩阵每行的最小元素，并分别从每行中减去该行的最小元素，这称之为行变换，如下图所示。

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

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

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

独立的0对应着最优分配：甲完成任务Ⅳ、乙完成任务Ⅱ、丙完成任务Ⅰ、丁完成任务Ⅲ，花费的总时间=4+4+9+11=28天。

转载请注明原文地址:https://kaotiyun.com/show/vcFZ777K

本试题收录于：信息系统项目管理师上午综合知识考试题库软考高级分类

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

软考高级

相关试题推荐

随机试题

最新回复(0)

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

软考高级

(45)不属于关系数据库管理系统。

设计模式(Design　pattern)是一套被反复使用、多数人知晓的、经过分类编目的、代码设计经验的总结。下面关于设计模式所倡导的基本原则的描述，错误的是(32)。

缺陷排除效率(DRE)是对软件质量保证及控制活动过滤能力的一个测量。假设某个软件在交付给最终用户之前发生的错误数量为45，软件交付之后发现的缺陷数为15，那么对应的DRE值为(20)。

面向对象分析的任务不包含(5)。

下述任务中，不属于软件工程需求分析阶段的是______。

下列关于建设项目环境风险评价工作等级划分的说法，正确的有(　　　)。

某公司拟购置一套设备，付款条件是：从第7年开始，每年年初支付10万元，连续支付10次，共100万元，假设该公司的资本成本率为10%，则相当于该公司现在一次付款的金额为()万元。

明代施耐庵的《水浒传》是我国第一部以城镇为题材的长篇小说。()

被称为“无产阶级革命音乐的开路先锋”的作曲家是()。

如果主送机关名称过多导致公文首页不能显示正文时，应当将主送机关名称移至()。

糖对于()相当于汞对于()

下面模型中为概念模型的是

AccordingtoSharon,whoisthemostlylikelytofallvictimtohemochromatosis?

Rumorshaveswirledforyearsaboutthemysticalphone,whichFacebookintroducedatitsheadquarterstoday.Forthefinancials

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

软考高级

(45)不属于关系数据库管理系统。

设计模式(Design pattern)是一套被反复使用、多数人知晓的、经过分类编目的、代码设计经验的总结。下面关于设计模式所倡导的基本原则的描述，错误的是(32)。

缺陷排除效率(DRE)是对软件质量保证及控制活动过滤能力的一个测量。假设某个软件在交付给最终用户之前发生的错误数量为45，软件交付之后发现的缺陷数为15，那么对应的DRE值为(20)。

面向对象分析的任务不包含(5)。

下述任务中，不属于软件工程需求分析阶段的是______。

下列关于建设项目环境风险评价工作等级划分的说法，正确的有( )。

某公司拟购置一套设备，付款条件是：从第7年开始，每年年初支付10万元，连续支付10次，共100万元，假设该公司的资本成本率为10%，则相当于该公司现在一次付款的金额为()万元。

明代施耐庵的《水浒传》是我国第一部以城镇为题材的长篇小说。()

被称为“无产阶级革命音乐的开路先锋”的作曲家是()。

如果主送机关名称过多导致公文首页不能显示正文时，应当将主送机关名称移至()。

糖对于()相当于汞对于()

下面模型中为概念模型的是

AccordingtoSharon,whoisthemostlylikelytofallvictimtohemochromatosis?

Rumorshaveswirledforyearsaboutthemysticalphone,whichFacebookintroducedatitsheadquarterstoday.Forthefinancials

设计模式(Design　pattern)是一套被反复使用、多数人知晓的、经过分类编目的、代码设计经验的总结。下面关于设计模式所倡导的基本原则的描述，错误的是(32)。

下列关于建设项目环境风险评价工作等级划分的说法，正确的有(　　　)。