二三版兼用《运筹学教程》胡运权主编课后习题答案(第八章)ppt课件

1、第八章练习题的答案，8.1证明了9个工厂之间，各工厂并不与其他3个工厂有业务关系，并不是只有4个工厂与偶数工厂有业务关系。 解：连接有联系的工厂。 只有9个工厂和其他3个工厂有业务关系时，顶点次数之和为27，是矛盾的。 只要4家工厂和偶数工厂有业务关系，其他5家工厂一定和奇数工厂有业务关系，顶点次数之和说明奇数、矛盾。 在第8章的练习题中，8.2中将8种化学药品a、b、c、d、e、f、g、h放入储藏室。 从安全的观点来看，不能将a-c、a-f、a-h、b-d、b-f、b-h、c-d、c-g、d-e、d-g、e-g、e-f、f-g、g-h各组的药品储存在同一室内。 至少有必要在几个储藏室储藏这些

2、药品。 解：把可以储藏在同一室内的两种药品之间连接起来。 同一室内储藏的药品必须构成完整的图。 ABG、CFH、DE构成了完整的图。 因此，保管这些药品至少需要三个储藏室。 第八章练习题的答案，8.3 6人围着圆坐着，谁都不认识，新坐下，谁能认识邻居吗？ 解：两个人知道一个联系。 第8章练习题解答，8.4判定图8-50这两个图是否出现了一个画面，如果可能的话，用图表表示其画法。 解： (a )图均为偶数点，可一画出。 (b )图中只有两个奇点，一个奇点是起点，另一个奇点是终点。 第八章练习题解答，解决如8.5图8-51所示的中国邮件问题，a点是邮局。 第8章练习题解答，第8章练习题解答，8.6

3、分别用深搜索法、广搜索法、破圈法找到图8-52所示图中的一个生成树。 设计第八章练习题解答、第八章练习题解答、第八章练习题解答、第八章练习题解答、第八章练习题解答、8.7图5-53所示的从锅炉房到各楼层铺设供暖管道的路径，使管道总长最长(单位： m )。 第8章练习题解答，第8章练习题解答，第8.8分别用回避法和破圆法求出图8-54所示的各图的最小树。 第八章练习题解答，第八章练习题解答，8.9规定的权重1、4、9、16、25、36、49、64、81，结构-霍夫曼树。 第八章练习题解答，8.10图8-55，v0是仓库，v9是商店，求从v0到v9的最短。 第8章练习题解答，第8章练习题解答，求8

4、.11图8-56中从v1到各点的最短短路。 求第8章练习题解答、第8章练习题解答、8.12图8-57网络中各顶点间的最短短路。第八章练习题解答、第八章练习题解答、第八章练习题解答、8.13某设备今后5年的价格预测分别为(5，5，6，7，8 )，如果该设备连续使用，该第j年的修理费分别为(1，2，3，5，6 )，某单位今年购买更新方案，将在哪个解：最佳解首先为2年，更新后为3年。 或者先使用3年，更新后2年使用。 最小总支出20。 第8章练习题解答，用8.14图8-58求出网最大流，边上数为(cij，fij )。 解：最大流量为14。 第八章练习题解答、第八章练习题解答、8.15图8-59、起点

5、S1、S2分别能提供10和15的单位，接受点t1、t2能接收10和25的单位，能求出最大流，边的数量为cij。 第八章练习题解答，解：最大流量为21。 第八章练习题的解答，8.16图8-60，从v0到v8，中途可以通过v1、v7各站。 如果各站之间道路沿线的数字表示单位时间内能通过这条道路的最大车辆数，应该如何发送到达v8的车，第八章练习问题解答，解：最大流量为40台。 第八章练习题的解答，8.17家公司各招募了一名俄罗斯、英、日、德语、法语翻译，有5人应聘。 知道：乙知道俄语，甲、乙、丙知道英语，甲、丙、丁知道日语，乙、戊知道德语，戊知道法语，这五个人能拿到聘书吗？最多的人能拿到招聘，各有哪

6、些方面解：有人知道某种语言，建立一个联系，权重为1。甲-英语乙-俄语丁-日语戊-法语最多招聘4人。 第八章练习题的解答，8.18甲、乙、丙、丁、戊、己六人组成小组，检查五个部门的工作，一个部门与乙、丙、丁三人有工作关系的情况下，用乙、丙、丁表示，其馀四个部门分别为甲、戊、己 到某个职场检查工作的人，如果必须是与该职场没有联系的人，该怎么安排？解：该问题应该假定一个人只能在一个职场检查工作。 但是，一个职场有很多人可以去检查。 具体来说，安排为甲和己单位1、乙单位2、丙单位3、丁单位5、戈单位4。 第8章练习问题解答，8.19在图8-61所示的网络中，有向边的数字是(cij，dij )，cij表

7、示容量，dij表示单位流量费用，求出从vs到vt的流值为6的最小费用流。 解：最小费用是35。 流量分布请参照以下图表。 第八章练习题解答，第八章练习题解答，有8.20的货物从两个仓库A1、A2运送到三个配送中心B1、B2、B3。 A1、A2的库存量分别为每天13t、9t，B1、B2、B3的每天的需求分别为9t、5t、6t。 各仓库到配送中心的运输能力、单位运费如表8-4所示，要求运输费用最节约的运输方案。 第八章习题解答、解：最小费用流程为105。 流量分布如下：第八章练习题解答，8.21中有5批货物，用船从x1、x2地分别运送到y1、y2、y3地。 各货物的出发日期如表8-5所示，船航行所需的时间(d )如表8-6所示。 每批货物用一艘船发货，空载时和重载时航行时间相同，制定计划，要求用最小的船完成这五项运输任务。 提示：用Ti表示运输任务