首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
某项目有Ⅰ、Ⅱ、Ⅲ、Ⅳ四项不同任务,恰有甲、乙、丙、丁四个人去完成各项不同的任务。由于任务性质及每人的技术水平不同,他们完成各项任务所需时间也不同,具体如下表所示。 项目要求每个人只能完成一项任务,为了使项目花费的总时间最短,应该指派丁完成(
某项目有Ⅰ、Ⅱ、Ⅲ、Ⅳ四项不同任务,恰有甲、乙、丙、丁四个人去完成各项不同的任务。由于任务性质及每人的技术水平不同,他们完成各项任务所需时间也不同,具体如下表所示。 项目要求每个人只能完成一项任务,为了使项目花费的总时间最短,应该指派丁完成(
admin
2018-10-14
92
问题
某项目有Ⅰ、Ⅱ、Ⅲ、Ⅳ四项不同任务,恰有甲、乙、丙、丁四个人去完成各项不同的任务。由于任务性质及每人的技术水平不同,他们完成各项任务所需时间也不同,具体如下表所示。
项目要求每个人只能完成一项任务,为了使项目花费的总时间最短,应该指派丁完成( )任务。
选项
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
信息系统项目管理师上午综合知识考试
软考高级
相关试题推荐
用户界面设计中,设计原则不正确的是(31)。
假设磁盘上每个磁道划分成9个物理块,每块存放1个逻辑记录。逻辑记录R0, R1,…,R8存放在同一个磁道上,记录的安排顺序如下表所示。假定磁盘旋转一圈的时间为27ms,磁头当前处在R0的开始处。若系统顺序处理这些记录,使用单缓冲区,每个记录处理时间为3
(60)是适合作为多媒体创作工具的软件。
Windows NT或Windows 2000是当前流行的一类操作系统,(6)是 Windows NT真正的中心,它提供了一组操作系统原语和机制。Windows NT采用线程机制来提高系统的(7)。NT采用基于(8)的方案选定线程执行的次序。
“企业系统规划方法”和“信息工程”都推荐建立表示数据类(主题数据库)和过程之间关系的CU矩阵M。其中若第i号过程产生第k号数据类,则材Mik=C;若第j号过程使用第k号数据类,则材Mjk=U。矩阵M按照一定的规则进行调整后,可以给出划分系统的子系统方案,并
下述任务中,不属于软件工程需求分析阶段的是______。
根据詹姆斯马丁的理论,以______的规划、设计和实现为主体的企业数据环境建设,是信息工程的核心。A.应用数据库B.物理数据库C.主题数据库D.数据仓库
随机试题
下列不属于库存现金内部控制活动的是()
FrankLloydWrightprobablyisthegreatestarchitectthattheUnitedStateshaseverproduced.Hewasvery【21】andhadanatural
A.血管紧张素ⅠB.血管紧张素ⅡC.去甲肾上腺素D.醛固酮E.肾素
2007年甲公司委托乙公司加工商品一批(属于应税消费品)。有关经济业务如下:(1)1月5日,发出材料一批,计划成本为400000元,材料成本差异率为2%。(2)2月8日,支付商品加工费20000元,支付应当交纳的消费税43000元。该
()根据托运人的要求,将同一船舶的同一装货港、同一卸货港、同一收货人的两批或两批以上相同或不同的货物合并签发的一套提单。
社会总需求是指()。
下列场景最不可能发生的是()。
Amajorreasonforconflictintheanimalworldisterritory.Themaleanimal【1】anarea.Thesizeoftheareaissufficienttop
Ifyou’vegotanearforlanguages,askillofcodingorasteadyhandanddon’tfaintatthesightofbloodthenyourcareerlo
ScientistssaytherehasbeenaseveredecreaseintheamountofwaterinLakeChadinnorthernAfricainthelastthirtyyears.
最新回复
(
0
)