首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
某项目有Ⅰ、Ⅱ、Ⅲ、Ⅳ四项不同任务,恰有甲、乙、丙、丁四个人去完成各项不同的任务。由于任务性质及每人的技术水平不同,他们完成各项任务所需时间也不同,具体如下表所示。 项目要求每个人只能完成一项任务,为了使项目花费的总时间最短,应该指派丁完成(
某项目有Ⅰ、Ⅱ、Ⅲ、Ⅳ四项不同任务,恰有甲、乙、丙、丁四个人去完成各项不同的任务。由于任务性质及每人的技术水平不同,他们完成各项任务所需时间也不同,具体如下表所示。 项目要求每个人只能完成一项任务,为了使项目花费的总时间最短,应该指派丁完成(
admin
2018-10-14
85
问题
某项目有Ⅰ、Ⅱ、Ⅲ、Ⅳ四项不同任务,恰有甲、乙、丙、丁四个人去完成各项不同的任务。由于任务性质及每人的技术水平不同,他们完成各项任务所需时间也不同,具体如下表所示。
项目要求每个人只能完成一项任务,为了使项目花费的总时间最短,应该指派丁完成( )任务。
选项
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)。
某公司的部门(部门号,部门名,负责人,电话)、商品(商品号,商品名称,单价,库存量)和职工(职工号,姓名,住址)三个实体之间的关系如表1、表2和表3所示。假设每个部门有一位负责人和一部电话,但有若干名员工;每种商品只能由一个部门负责销售。部门关系不
面向对象系统由对象及其相互间的通信构成。一般来说,面向对象软件的测试可以分为4个层次进行。其中,(3)测试,测试类中定义的每个方法,基本上相当于传统软件测试中的(4);(5)测试,测试一组协同工作的类之间的相互作用。
需求分析是一种软件工程活动,它在系统级软件分配和软件设计间起到桥梁的作用。需求分析使得系统工程师能够刻画出软件的(27)、指明软件和其他系统元素的接口、并建立软件必须满足的约束。需求分析是发现、求精、建模和规约的过程。包括详细地精化由系统工程师建立并在软件
事务处理系统运行时,系统的吞吐率指标(每秒处理的事务数)会随系统负荷(系统中待处理的事务数量)大小而变化。当系统的负荷从0开始逐步增大时,系统吞吐率的变化一般将先后经历如下三个阶段:(62)。
设计模式(Design pattern)是一套被反复使用、多数人知晓的、经过分类编目的、代码设计经验的总结。下面关于设计模式所倡导的基本原则的描述,错误的是(32)。
某公司网上销售管理系统的数据库部分关系模式如下所示。其中,客户号唯一标识一位客户,产品号唯一标识一件产品,订单号唯一标识一份订单。一份订单必须且仅对应一位客户,一份订单可由一到多条订单明细组成,一位客户可以有多份订单。客户(客户号,姓名,性别,地址
某磁盘盘组共有10个盘面,每个盘面上有100个磁道,每个磁道有32个扇区,假定物理块的大小为2个扇区,分配以物理块为单位。若使用位图(bitmap)管理磁盘空间,则位图需要占用(49)字节空间。若采用空白文件管理磁盘空间,且空白文件目录的每个表项占用5个字
某企业拥有多个应用系统,分别采用不同的语言和平台独立构建而成,企业需要集成来自不同系统的数据,并使用可定制格式的数据频繁地、立即地、可靠地、异步地传输数据。以下集成方式,最能满足这种要求的是(32)。
某工厂仓库有一名保管员,该仓库可存放n箱零件。该工厂生产车间有m名工人,只要仓库空闲,工人将生产好的整箱零件放入仓库,并由保管员登记入库数量;该工厂销售部有k名销售员,只要仓库库存数能满足客户要求,便可提货,并由保管员登记出库数量。规定工人和销售员不能同时
随机试题
A.湿疹瘙痒B.痢疾C.目赤肿痛D.咽喉肿痛白矾、大蒜皆可用治的病证是
甲公司与乙公司签订技术转让合同,由乙公司支付使用费100万元。后甲公司转让的技术被确认为系侵犯丙公司的技术秘密而取得,为此发生纠纷。经查,乙公司对此并不知情。下列表述正确的有()。
我国随着“九五”计划的完成,社会主义市场经济体制已初步建立,具体表现在()。
施工现场临时性桥梁,宽度应不小于施工车辆最大宽度的()倍。
某普通合伙企业成立时,下列人员不能成为合伙人的有()。
《卖报歌》的曲作者是()。
掌握学习理论认为学生能力上的差异并不能决定他们能否成功掌握教学内容,而在于他们()。
Contrabandarticles
当投标人对现场勘察后向招标方提出问题质疑,而招标方书面回答的问题与招标文件中规定的不一致时,应以______为准。
WhereistheEmeraldAirlinesoffice?WhatisHelen’sdegreein?
最新回复
(
0
)