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

admin2018-10-14 32

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

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

选项 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)

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

软考高级

关于数据库中关系性质的描述，错误的是(40)。

关于poka-yoke技术的叙述，错误的是(25)。

某系统进程的状态包括运行状态、活跃就绪状态、静止就绪状态、活跃阻塞状态和静止阻塞状态。针对下图的进程状态模型，为了确保进程调度的正常工作，(a)、(b)和(c)的状态分别为(50)。

某个系统在开发时，用户已经定义了软件的一组一般性目标，但不能标识出详细的输入、处理及输出需求；开发者也可能暂时不能确定算法的有效性、操作系统的适应性或人机交互的形式。在这种情况下，采用(23)开发最恰当。

“用于管理活动和工程活动的软件过程已经文档化、标准化，并与整个组织的软件过程相集成。所有项目都使用文档化的、组织认可的过程来开发和维护软件。”满足这样描述的软件开发过程符合能力成熟度模型(CMM)中的(19)级。

患儿，3个月，近2天发生腹泻，呈黄绿色稀便，内有奶瓣和泡沫，为防止患儿发生脱水应选择

下列哪种建筑物内可附金属面聚苯乙烯泡沫夹芯板(B2级)做隔断?[2014—037]

对于伪造、变造、买卖海关单证的行为，海关的处罚为：

有关我国建设工程造价的类型和编制时期的一般表述不正确的是()。

对袭击人民警察的违法犯罪分子，可以使用武器。()

走进苏州的水巷，伴着缓缓流过的水声，随小船_在高高的粉墙下。木桨一点水，飘过古老民宅的石库门，你感觉到的是恬静，是一种在心里_、深入骨髓的欣然。填入划横线部分最恰当的一项是()。

某一磁盘请求序列(磁道号)：0245713202，按照最短寻道时间优先磁盘调度算法对磁盘进行请求服务，设当前磁头在4道上，则磁臂总移动道数为______。

操作系统中的文件管理系统为用户提供的功能是()。

Readthefollowingarticleaboutresponsibilityforthenaturalenvironmentandthequestionsontheoppositepage.Foreach

Imagineananimalthatbecomesfrozenincoldweather.Then,whenitgetswarmer,theanimalsimplyunfreezesandgoesbacktoi

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

软考高级

关于数据库中关系性质的描述，错误的是(40)。

关于poka-yoke技术的叙述，错误的是(25)。

某系统进程的状态包括运行状态、活跃就绪状态、静止就绪状态、活跃阻塞状态和静止阻塞状态。针对下图的进程状态模型，为了确保进程调度的正常工作，(a)、(b)和(c)的状态分别为(50)。

某个系统在开发时，用户已经定义了软件的一组一般性目标，但不能标识出详细的输入、处理及输出需求；开发者也可能暂时不能确定算法的有效性、操作系统的适应性或人机交互的形式。在这种情况下，采用(23)开发最恰当。

患儿，3个月，近2天发生腹泻，呈黄绿色稀便，内有奶瓣和泡沫，为防止患儿发生脱水应选择

下列哪种建筑物内可附金属面聚苯乙烯泡沫夹芯板(B2级)做隔断?[2014—037]

对于伪造、变造、买卖海关单证的行为，海关的处罚为：

有关我国建设工程造价的类型和编制时期的一般表述不正确的是()。

对袭击人民警察的违法犯罪分子，可以使用武器。()

走进苏州的水巷，伴着缓缓流过的水声，随小船_______在高高的粉墙下。木桨一点水，飘过古老民宅的石库门，你感觉到的是恬静，是一种在心里_______、深入骨髓的欣然。填入划横线部分最恰当的一项是()。

某一磁盘请求序列(磁道号)：0245713202，按照最短寻道时间优先磁盘调度算法对磁盘进行请求服务，设当前磁头在4道上，则磁臂总移动道数为______。

操作系统中的文件管理系统为用户提供的功能是()。

Readthefollowingarticleaboutresponsibilityforthenaturalenvironmentandthequestionsontheoppositepage.Foreach

Imagineananimalthatbecomesfrozenincoldweather.Then,whenitgetswarmer,theanimalsimplyunfreezesandgoesbacktoi

走进苏州的水巷，伴着缓缓流过的水声，随小船_在高高的粉墙下。木桨一点水，飘过古老民宅的石库门，你感觉到的是恬静，是一种在心里_、深入骨髓的欣然。填入划横线部分最恰当的一项是()。