《运筹学基础及应用》习题六 6.1、6.2、6.3题 解题参考
6.1有八种化学药品A 、B 、C 、D 、P 、R 、S 、T 要放进储藏室保管。出于安全原因，下列各组药品不能储藏在同一室内：A-R,A-C,A-T,R-P,P-S,S-T,T-B,B-D,D-C,R-S,R-B,P-D,S-C,S-D，问储存这八种药品至少需要多少间储藏室。 解：将八种药品用8个点表示，不能放在一室的药品用连接两点的边表示。绘出下图：
分析：互不相邻的点有：APB PCT ABS DRT BCP 。取PCT,ABS,DR 需要3个储藏室；取DRT,BCP,AS 需要3个储藏室，可见，至少需要3个储藏室。 6.2已知有十六个城市及它们之间的道路联系（见图6-28）。某旅行者从城市A 出发，沿途经J 、N 、H 、K 、G 、B 、M 、I 、E 、P 、F 、C 、L 、D 、O 、C 、G 、N 、H 、K 、O 、D 、L 、P 、E 、I 、F 、B 、J 、A ，最后到达城市M 。由于疏忽，该旅行者忘了在图上标明各城市的位置。请用图的基本概念及理论，在图6-28中标明各城市A~P 的位置。 图6-28
解：分析：A 点与J 、M 相连次数为2。所以A 点必须是角上的点，且J 、M 的次数3。到J 和M 的共同连接点B 。与B 连接的点还有G 、F 。可见B 是一个4次的点，依次类推，可以标出各城市的位置如上图。
表6-4给出了每个研究生参加考试的课程（打△号的）。规定考试应在三天内结束，每天上 D C I
下午各安排一门。研究生提出希望每人每天最多考一门，又课程A 必须安排在第一天上午考，课程F 必须安排在最后一门，课程B 只能安排在下午考。试列出一张满足各方面要求的考试日程表。
解：六门考试用六个点A 、B 、C 、D 、E 、F 表示。将每个研究生考试的点用边连接起来如下图。按
要求将A 和F 课程先添入下表中。即第一天上午A ，第三天下午F 。在图中到与A 不相邻的点E ，添到第一天下午。由于B 只能在下午考，所以B 添入第二天下午，将与B 不相邻的点C 添入第二天上午。最后将D 添入第三天上午，就完成了考试日程表。
第一天
第二天
上午 A
C D 下午 E B F
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议