首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
某项目有Ⅰ、Ⅱ、Ⅲ、Ⅳ四项不同任务,恰有甲、乙、丙、丁四个人去完成各项不同的任务。由于任务性质及每人的技术水平不同,他们完成各项任务所需时间也不同,具体如下表所示。 项目要求每个人只能完成一项任务,为了使项目花费的总时间最短,应该指派丁完成(
某项目有Ⅰ、Ⅱ、Ⅲ、Ⅳ四项不同任务,恰有甲、乙、丙、丁四个人去完成各项不同的任务。由于任务性质及每人的技术水平不同,他们完成各项任务所需时间也不同,具体如下表所示。 项目要求每个人只能完成一项任务,为了使项目花费的总时间最短,应该指派丁完成(
admin
2018-10-14
91
问题
某项目有Ⅰ、Ⅱ、Ⅲ、Ⅳ四项不同任务,恰有甲、乙、丙、丁四个人去完成各项不同的任务。由于任务性质及每人的技术水平不同,他们完成各项任务所需时间也不同,具体如下表所示。
项目要求每个人只能完成一项任务,为了使项目花费的总时间最短,应该指派丁完成( )任务。
选项
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%、30%、 30%,各车间的次品率分别为3%、4%、5%(正品率分别为97%、96%、95%)。以上叙述如下图所示。在图中,从“厂”结点出发选择三个车间产品的概率分别为0.4、0.3、
某文件管理系统在磁盘上建立了位示图(bitmap),记录磁盘的使用情况。若磁盘上的物理块依次编号为0、1、2、…,系统中字长为32位,每一位对应文件存储器上的一个物理块,取值0和1分别表示空闲和占用,如下图所示。假设将4195号物理块分配给某文件,那么
事务处理系统运行时,系统的吞吐率指标(每秒处理的事务数)会随系统负荷(系统中待处理的事务数量)大小而变化。当系统的负荷从0开始逐步增大时,系统吞吐率的变化一般将先后经历如下三个阶段:(62)。
静态图像的相邻像素之间具有较大的相关性,这是(61)。JPEG压缩编码利用变换编码与量化来消除这种冗余。
(60)是适合作为多媒体创作工具的软件。
关于网络工程需求分析的论述,正确的是(8)。
微内核的操作系统(OS)结构如下图所示,图中①和②分别工作在(51)方式下,与传统的OS结构模式相比,采用微内核的OS结构模式的优点是提高了系统的灵活性、可扩充性,(52)。
Windows NT或Windows 2000是当前流行的一类操作系统,(6)是 Windows NT真正的中心,它提供了一组操作系统原语和机制。Windows NT采用线程机制来提高系统的(7)。NT采用基于(8)的方案选定线程执行的次序。
假设甲、乙二人合作开发了某应用软件,甲为主要开发者。该应用软件所得收益合理分配后,甲自行将该软件作为自己独立完成的软件作品发表,甲的行为(29)。
线性规划问题就是求出一组变量,在一组线性约束条件下,使某个线性目标函数达到极大(小)值。满足线性约束条件的变量区域称为可行解区。由于可行解区的边界均是线性的(平直的),属于单纯形,所以线性目标函数的极值只要存在,就一定会在可行解区边界的某个顶点达到。因此,
随机试题
患者,男,70岁。因听力逐渐减退一年多,来院就诊。经过医生检查发现其骨传导功能正常,空气传导功能障碍。空气传导过程中,错误的说法是
预防性树脂充填操作不包括
下列哪项症状不符合脑疝前驱的表现:
在会计核算过程中,其主要的工作程序师填制和审核凭证、登记账簿和编制会计报表()
下列哪项情形发生时,股票上市首日实行价格涨(跌)幅限制?( )
根据个人所得税法律制度的规定,下列各项中,纳税义务人应当自行申报缴纳个人所得税的有()。
19世纪擅长表现农民题材和关怀农民生活的画家是()。
霍桑实验
婚姻关系成立的法定标志是()
The______emphasisonexaminationsisbyfartheworstformofcompetitioninschools.
最新回复
(
0
)