问题 单项选择题

某国内知名系统集成公司准备于今年下半年(7~12月)安排8个系统集成项目(命名为A,B,…,H)的施工,共有16个项目团队(编号为1,2,…,16)参与这些项目,各团队对应参加的项目如下表所示(“√”表示相应的团队将参加相应的系统集成项目)。

某公司各项目团队参与项目的基本情况
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
A
B
C
D
E
F
G
H
公司领导层希望妥善安排这8个项目的施工顺序的方案,使每个项目团队不会连续参加两个系统集成项目。针对表中的情况,这样的方案______。

A.只有1个
B.共有两个
C.共有3个
D.多于3个

答案

参考答案:D

解析: 本题考查考生在运筹学应用方面的能力。利用图的方法解决此类问题比较直观。可在平面上将每个项目用一个节点表示,在两个项目之间,只要有同一团队都参加,则在相应点之间用虚直线连接。若某个团队参加多个项目,则在相应点之间都用虚直线连接(已有连线时不用重复画)。换言之,每两个项目,若有项目团队都参加,则在相应两点之间画连线(如图1所示),表示这两个项目不能接续安排。为清晰起见,可以根据图1再画一张连线状态相反的图(如图2所示)。同样使用8个节点表示8个项目,但图1中凡是两点之间有连线的地方,图2中就没有连线;图1中凡是两点之间无连线的地方,图2中就有连线。因此,图2中的每条连线表示相应的两端项目是可以接续安排的。这样,只要在图2中找到一条连线通路,正好将这8个点依次不重复地全都连接起来,就形成了一种可行的安排方案。


图1 不能接续安排的项目

多项选择题
单项选择题