首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
某项目有Ⅰ、Ⅱ、Ⅲ、Ⅳ四项不同任务,恰有甲、乙、丙、丁四个人去完成各项不同的任务。由于任务性质及每人的技术水平不同,他们完成各项任务所需时间也不同,具体如下表所示。 项目要求每个人只能完成一项任务,为了使项目花费的总时间最短,应该指派丁完成(
某项目有Ⅰ、Ⅱ、Ⅲ、Ⅳ四项不同任务,恰有甲、乙、丙、丁四个人去完成各项不同的任务。由于任务性质及每人的技术水平不同,他们完成各项任务所需时间也不同,具体如下表所示。 项目要求每个人只能完成一项任务,为了使项目花费的总时间最短,应该指派丁完成(
admin
2018-10-14
97
问题
某项目有Ⅰ、Ⅱ、Ⅲ、Ⅳ四项不同任务,恰有甲、乙、丙、丁四个人去完成各项不同的任务。由于任务性质及每人的技术水平不同,他们完成各项任务所需时间也不同,具体如下表所示。
项目要求每个人只能完成一项任务,为了使项目花费的总时间最短,应该指派丁完成( )任务。
选项
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
信息系统项目管理师上午综合知识考试
软考高级
相关试题推荐
面向对象系统由对象及其相互间的通信构成。一般来说,面向对象软件的测试可以分为4个层次进行。其中,(3)测试,测试类中定义的每个方法,基本上相当于传统软件测试中的(4);(5)测试,测试一组协同工作的类之间的相互作用。
假设磁盘上每个磁道划分成9个物理块,每块存放1个逻辑记录。逻辑记录R0, R1,…,R8存放在同一个磁道上,记录的安排顺序如下表所示。假定磁盘旋转一圈的时间为27ms,磁头当前处在R0的开始处。若系统顺序处理这些记录,使用单缓冲区,每个记录处理时间为3
某文件管理系统在磁盘上建立了位示图(bitmap),记录磁盘的使用情况。若磁盘上的物理块依次编号为0、1、2、…,系统中字长为32位,每一位对应文件存储器上的一个物理块,取值0和1分别表示空闲和占用,如下图所示。假设将4195号物理块分配给某文件,那么
缺陷排除效率(DRE)是对软件质量保证及控制活动过滤能力的一个测量。假设某个软件在交付给最终用户之前发生的错误数量为45,软件交付之后发现的缺陷数为15,那么对应的DRE值为(20)。
采用软件冗余的方法提高系统的可靠性,需要设计N个相同功能的程序模块,这些模块必须(18)。
某公司网上销售管理系统的数据库部分关系模式如下所示。其中,客户号唯一标识一位客户,产品号唯一标识一件产品,订单号唯一标识一份订单。一份订单必须且仅对应一位客户,一份订单可由一到多条订单明细组成,一位客户可以有多份订单。客户(客户号,姓名,性别,地址
现实世界中随机性多于确定性。在计算机上模拟随机的实际问题,并进行统计计算,这是非常有用的方法。为此,各种程序设计语言都有产生(伪)随机数的函数。这种函数,每调用一次,就可以获得一个位于区间(0,1)内的数。在程序运行时,多次产生的这些数会均匀地分布在0,1
某磁盘盘组共有10个盘面,每个盘面上有100个磁道,每个磁道有32个扇区,假定物理块的大小为2个扇区,分配以物理块为单位。若使用位图(bitmap)管理磁盘空间,则位图需要占用(49)字节空间。若采用空白文件管理磁盘空间,且空白文件目录的每个表项占用5个字
面向对象分析的任务不包含(5)。
软件设计的主要任务是设计软件的结构、过程和模块,其中软件结构设计的主要任务是要确定______。
随机试题
背景某写字楼,剪力墙结构。因工程需要在其剪力墙的外侧安装点式玻璃幕墙。土建工程已经完毕,施工时没有预埋件,而且抹灰工序已经完成。现需要在该处安装后埋件,安装完毕后土建要对其进行抹灰和涂料处理;抹灰后埋件不得外露。监理工程师要求上报安装后埋件前对剪力墙部位
男,30岁,今晨出现肠鸣腹痛,排便次数增多,泄泻十余次,清稀如水样,伴恶寒头痛,舌淡红苔白腻,脉濡。若病情迁延不愈,大便时干时溏,食后脘闷不舒,面色萎黄,舌苔淡白,脉细。治宜选用()。
某护士从该院近3年的护理记录中随机抽取100份。分析护理记录中存在的缺陷,此种科研设计的类型为
肾腺瘤分型中,最多见的是
A.生津养血B.开胃摄唾C.固精止带D.养血安神E.清热燥湿大枣除补中益气外,还可()。
曹某不慎把孙某的岳母刘某的轿车撞坏,与刘某发生争吵。之后,孙某闯入曹某家中,要求赔偿。不料发生了打斗,致使曹某左面部软组织挫伤。曹:襞向法院提起诉讼,请求法院判决孙某赔偿医药费40000元、误工损失费8000元。诉讼中,孙某对曹某提起诉讼,请求法院判决曹某
为个体计划膳食经常借助RNI、EAR和以食物为基础的膳食指南来完成。()
下列各句中,没有语病的一句是()。
2,3,6,15,()。
A、 B、 C、 D、 C
最新回复
(
0
)