问题 单项选择题

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

表8-4 某公司各项目团队参与项目的基本情况
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个项目的施工顺序的方案,使每个项目团队不会连续参加两个系统集成项目。针对表8-4的情况,这样的方案______。

A.只有1个

B.共有两个

C.共有3个

D.多于3个

答案

参考答案:D

解析:[要点解析] 本题考查考生在运筹学应用方面的能力。用图的方法解决此类问题比较直观。可在平面上将每个项目用一个节点表示,在两个项目之间,只要有同一团队都参加,则在相应点之间用虚直线连接。若某个团队参加的多个项目,则在相应点之间都用虚直线连接(已有连线时不用重复画)。换言之,每两个项目,若有项目团队都参加,则在相应两点之间画连线(如图8-9所示),表示这两个项目不能接续安排。为清晰起见,可以根据图8-9再画一张连线状态相反的图(如图8-10所示)。同样使用8个节点表示8个项目,但图8-9中凡是两点之间有连线的地方,图8-10中就没有连线;图8-9中凡是两点之间无连线的地方,图8-10中就有连线。因此,图8-10中的每条连线表示相应的两端项目是可以接续安排的。这样,只要在图8-10中找到一条连线通路,正好将这8个点依次不重复地全都连接起来,就形成一种可行的安排方案。
[*]
从图8-10可以看出,依次连接这8个项目的通路可以有多条,例如:①HAGBFCDE;②HAGBEDCF;③HBGAFCDE;④HBGAEDCF;⑤HCDEAGBF;⑥HCDEBGAF;⑦GAHBFCDE;⑧GAHBEDCF;⑨……
上述每一条通路表示一种安排方案。按照其中任一方案,各项目团队都不会连续参加两个系统集成项目。

填空题
名词解释