首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
某项目有Ⅰ、Ⅱ、Ⅲ、Ⅳ四项不同任务,恰有甲、乙、丙、丁四个人去完成各项不同的任务。由于任务性质及每人的技术水平不同,他们完成各项任务所需时间也不同,具体如下表所示。 项目要求每个人只能完成一项任务,为了使项目花费的总时间最短,应该指派丁完成(
某项目有Ⅰ、Ⅱ、Ⅲ、Ⅳ四项不同任务,恰有甲、乙、丙、丁四个人去完成各项不同的任务。由于任务性质及每人的技术水平不同,他们完成各项任务所需时间也不同,具体如下表所示。 项目要求每个人只能完成一项任务,为了使项目花费的总时间最短,应该指派丁完成(
admin
2018-10-14
73
问题
某项目有Ⅰ、Ⅱ、Ⅲ、Ⅳ四项不同任务,恰有甲、乙、丙、丁四个人去完成各项不同的任务。由于任务性质及每人的技术水平不同,他们完成各项任务所需时间也不同,具体如下表所示。
项目要求每个人只能完成一项任务,为了使项目花费的总时间最短,应该指派丁完成( )任务。
选项
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
信息系统项目管理师上午综合知识考试
软考高级
相关试题推荐
某公司的部门(部门号,部门名,负责人,电话)、商品(商品号,商品名称,单价,库存量)和职工(职工号,姓名,住址)三个实体之间的关系如表1、表2和表3所示。假设每个部门有一位负责人和一部电话,但有若干名员工;每种商品只能由一个部门负责销售。部门关系不
某公司的部门(部门号,部门名,负责人,电话)、商品(商品号,商品名称,单价,库存量)和职工(职工号,姓名,住址)三个实体之间的关系如表1、表2和表3所示。假设每个部门有一位负责人和一部电话,但有若干名员工;每种商品只能由一个部门负责销售。部门关系不
面向对象系统由对象及其相互间的通信构成。一般来说,面向对象软件的测试可以分为4个层次进行。其中,(3)测试,测试类中定义的每个方法,基本上相当于传统软件测试中的(4);(5)测试,测试一组协同工作的类之间的相互作用。
某文件管理系统在磁盘上建立了位示图(bitmap),记录磁盘的使用情况。若磁盘上的物理块依次编号为0、1、2、…,系统中字长为32位,每一位对应文件存储器上的一个物理块,取值0和1分别表示空闲和占用,如下图所示。假设将4195号物理块分配给某文件,那么
某文件管理系统在磁盘上建立了位示图(bitmap),记录磁盘的使用情况。若磁盘上的物理块依次编号为0、1、2、…,系统中字长为32位,每一位对应文件存储器上的一个物理块,取值0和1分别表示空闲和占用,如下图所示。假设将4195号物理块分配给某文件,那么
下图中左边的UML类图描绘的是设计模式中的(1)模式。右边的UML类图描述了该模式的一种应用,其中与左图中的Abstraction对应的类是(2)。
静态图像的相邻像素之间具有较大的相关性,这是(61)。JPEG压缩编码利用变换编码与量化来消除这种冗余。
某磁盘盘组共有10个盘面,每个盘面上有100个磁道,每个磁道有32个扇区,假定物理块的大小为2个扇区,分配以物理块为单位。若使用位图(bitmap)管理磁盘空间,则位图需要占用(49)字节空间。若采用空白文件管理磁盘空间,且空白文件目录的每个表项占用5个字
在进行项目计划前,应该首先建立______的目的和范围,考虑可选的解决方案、标识技术和管理的约束。没有这些信息,就不可能进行合理的成本估算、有效的风险评估、适当的项目任务划分或是可管理的项目进度安排。
随机试题
血病之阴虚火旺者治疗宜选用血病之寒凝经脉证治疗宜选用
患儿,男,4岁。以病毒性脑膜炎入院,经积极治疗,除右侧肢体仍活动不利,其他临床症状明显好转,家长要求回家休养。护士为其进行出院指导,不妥的是
在综合布线工程测试中,()近端串音衰减值/衰减值,表示串音衰减比。
当某工程网络计划的计算工期等于计划工期时,该网络计划中的关键工作是指( )的工作。
财务会计报告由()组成。
下列各项中,()是支付结算的法律依据。
2019年5月,陈某从某汽车销售公司(增值税一般纳税人)购买轿车一辆供自己使用,支付含增值税价款230000元,另支付购置工具件和零配件含税价款1300元,车辆装饰费6000元,支付的所有款项均由销售公司开具统一发票。则陈某应纳车辆购置税()元。
上市商业银行信息披露应与银行的经营特点相适应,其原则不包括()。
小强2岁时由于父母忙于工作被送到乡下外婆家抚养,外公外婆对其十分疼爱,百般呵护。6岁时,小强回到父母身边并进入小学。这时他性格十分内向,爱哭,害怕与陌生人交往。按照埃里克森的理论,小强心理问题形成的原因是没有完成()的矛盾冲突。
以下程序用来统计文件中字符的个数(函数feof用以检查文件是否结束,结束时返回非零)#include<stdio.h>main(){FILE*fp;longnum=0;fp=fopen("fname.dat","r");while(__
最新回复
(
0
)