问题 单项选择题

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

公司领导层希望妥善安排这8个项目的施工顺序的方案,使每个项目团队不会连续参加两个系统集成项目。针对表中的情况,这样的方案()。

A.只有1个

B.共有两个

C.共有3个

D.多于3个

答案

参考答案:D

解析:

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

图1 不能接续安排的项目

图2 可以接续安排的项目

从图2可以看出,依次连接这8个项目的通路可以有多条,例如:①HAGBFCDE;②HAGBEDCF;③HBGAFCDE;④HBGAEDCF;⑤HCDEAGBF;⑥HCDEBGAF;⑦GAHBFCDE;⑧GAHBEDCF;⑨……

上述每一条通路都表示一种安排方案。按照其中任一方案,各项目团队都不会连续参加两个系统集成项目。

单项选择题
填空题