首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
某项目有Ⅰ、Ⅱ、Ⅲ、Ⅳ四项不同任务,恰有甲、乙、丙、丁四个人去完成各项不同的任务。由于任务性质及每人的技术水平不同,他们完成各项任务所需时间也不同,具体如下表所示。 项目要求每个人只能完成一项任务,为了使项目花费的总时间最短,应该指派丁完成(
某项目有Ⅰ、Ⅱ、Ⅲ、Ⅳ四项不同任务,恰有甲、乙、丙、丁四个人去完成各项不同的任务。由于任务性质及每人的技术水平不同,他们完成各项任务所需时间也不同,具体如下表所示。 项目要求每个人只能完成一项任务,为了使项目花费的总时间最短,应该指派丁完成(
admin
2018-10-14
74
问题
某项目有Ⅰ、Ⅱ、Ⅲ、Ⅳ四项不同任务,恰有甲、乙、丙、丁四个人去完成各项不同的任务。由于任务性质及每人的技术水平不同,他们完成各项任务所需时间也不同,具体如下表所示。
项目要求每个人只能完成一项任务,为了使项目花费的总时间最短,应该指派丁完成( )任务。
选项
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
信息系统项目管理师上午综合知识考试
软考高级
相关试题推荐
(45)不属于关系数据库管理系统。
面向对象系统由对象及其相互间的通信构成。一般来说,面向对象软件的测试可以分为4个层次进行。其中,(3)测试,测试类中定义的每个方法,基本上相当于传统软件测试中的(4);(5)测试,测试一组协同工作的类之间的相互作用。
需求分析是一种软件工程活动,它在系统级软件分配和软件设计间起到桥梁的作用。需求分析使得系统工程师能够刻画出软件的(27)、指明软件和其他系统元素的接口、并建立软件必须满足的约束。需求分析是发现、求精、建模和规约的过程。包括详细地精化由系统工程师建立并在软件
某系统进程的状态包括运行状态、活跃就绪状态、静止就绪状态、活跃阻塞状态和静止阻塞状态。针对下图的进程状态模型,为了确保进程调度的正常工作,(a)、(b)和(c)的状态分别为(50)。
某公司网上销售管理系统的数据库部分关系模式如下所示。其中,客户号唯一标识一位客户,产品号唯一标识一件产品,订单号唯一标识一份订单。一份订单必须且仅对应一位客户,一份订单可由一到多条订单明细组成,一位客户可以有多份订单。客户(客户号,姓名,性别,地址
统一软件开发过程是一种基于面向对象技术的软件开发过程,其特点是“用例驱动,以架构为核心,迭代并增量”。统一软件开发过程定义了4种通用的开发阶段,它们按照过程顺序分别是:起始阶段、(20)、构建阶段和(21),其中在构建阶段主要产生的文档有(22)。
某高校管理信息系统的数据库设计过程中,(43)阶段是在需求分析的基础上,对用户信息加以分类、聚集和概括,建立信息模型,并依照选定的数据库管理系统软件,转换成为数据的(44),再依照软硬件环境,最终实现数据的合理存储。
某订单处理系统中,“创建新订单”和“更新订单”两个用例都需要检查客户的账号是否正确,为此定义一个通用的用例“核查客户账户”。用例“创建新订单”和“更新订单”与用例“核查客户账户”之间是(1)。
假设某操作系统采用非剥夺法来分配资源,且对资源的申请和释放可以在任何时候进行。当进程A请求资源得不到满足时,①若没有因等待资源而阻塞的其他进程,则进程A(24)。②若有因等待资源而阻塞的其他进程,则(25)检查所有由于等待资源而被阻塞的进程
某公司计划开发一种新产品,其开发前景有成功、较成功与失败三种可能情况。根据该公司的技术水平与市场分析,估计出现这三种情况的概率分别为40%、40%和20%。现有三种开发方案可供选择,每种方案在不同开发前景下估计获得的利润(单位:万元)如下表:为获得最大的期
随机试题
设y=f(y)是由方程.xy+lny=0确定的函数,则=().
=____________.
尿糖阳性,除糖尿病外还可能包括
A.四逆散B.逍遥散C.大柴胡汤D.葛根芩连汤E.小柴胡汤
定量分析时,对分离度的要求是在重复性试验中,对峰面积测量值的RSD的要求是
国家统一规定,养老保险的结余要预留相当于()的养老金开支,其余按规定处理。
《旅馆业治安管理办法》规定,饭店对旅客寄存的财物要建立()
简述《中华人民共和国民办教育促进法》的基本原则。
据联合国人口基金预计:如果出生率降到每位妇女平均生两个孩子,到2050年世界人口将达94亿,2200年将达110亿。联合国人口基金报告预i贝0了世界人口分布将发生变化,因为生活在发达地区人口所占的百分比将从1995年的19%降到2150年的10%。1950
[2009年10月]关于x的方程a2x2一(3a2一8a)x+2a2一13a+15=0至少有一个整数根。(1)a=3;(2)a=5。
最新回复
(
0
)