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

第八章习题解答 第八章习题解答 第八章习题解答 8.13 某设备今后五年的价格预测分别是(5，5，6，7，8)，若该设备连续使用，其第j年的维修费分别为(1，2，3，5，6)，某单位今年购进一台，问如何确定更新方案可使5年里总支出最小(不管设备使用了多少年，其残值为0)。 解：最优解为：先使用两年，更新后再使用三年。或先使用三年，更新后再使用两年。最小总支出20。 第八章习题解答 8.14 求图8-58中网络最大流，边上数为(cij，fij)。 解：最大流量为14。 第八章习题解答 第八章习题解答 8.15 如图8-59，发点S1，S2分别可供应10和15个单位，收点t1，t2可以接收10和25个单位，求最大流，边上数为cij。 第八章习题解答 解：最大流量为21。 第八章习题解答 8.16 如图8-60，从v0派车到v8，中间可经过v1，…，v7各站，若各站间道路旁的数字表示单位时间内此路上所能通过的最多车辆数，问应如何派车才能使单位时间到达v8的车辆最多? 第八章习题解答 解：最大流量为40辆。 第八章习题解答 8.17 某单位招收懂俄、英、日、德、法文翻译各1人，有5人应聘。已知：乙懂俄文，甲、乙、丙懂英文，甲、丙、丁懂日文，乙、戊懂德文，戊懂法文，问这5个人是否都能得到聘书?最多几人能得到招聘，各从事哪一方面的翻译任务? 解：某人懂某种语言作一条连线，权数为1。 甲英语 乙俄语 丁日语 戊法语 最多招聘4个人。 第八章习题解答 8.18 甲、乙、丙、丁、戊、己6人组成一个小组，检查5个单位的工作，若一单位和乙、丙、丁三人有工作联系，则用{乙，丙，丁}表示，其余四个单位分别为{甲，戊，己}，{甲，乙，戊，己}，{甲，乙，丁，己}，{甲，乙，丙}。若到一个单位去检查工作的人必须是和该单位没有联系的人，问应如何安排? 解：此题应该假设1人只能去1个单位检查工作。但是一个单位可以有多人去检查。具体安排如下： 甲和己→单位1、乙→单位2 、丙→单位3 、丁→单位5 、戊→单位4 。 第八章习题解答 8.19 图8-61所示网络中，有向边旁数字为(cij，dij)，cij表示容量，dij表示单位流量费用，试求从vs到vt流值为6的最小费用流。 解： 最小费用为35。流量分布见下一个图形。 第八章习题解答 第八章习题解答 8.20 某种货物由2个仓库A1，A2运送到3个配货中心B1，B2，B3。A1，A2的库存量分别为每天13t，9t；B1，B2，B3每天需求分别为9t，5t，6t。各仓库到配货中心的运输能力、单位运费如表8—4，求运费最省的运输方案。 表8-4 运程 运量限制(t／d) 运费(百元/t) Al—B1 8 3 Al—B2 7 1l Al—B3 5 10 A2—B1 6 S A2—B2 3 7 A2—B3 5 4 第八章习题解答 解：最小费用流为105。流量分布如下： 第八章习题解答 8.21 有5批货物，要用船只从x1,x2地分别运往y1,y2,y3地。规定每批货物出发日期如表8-5所示，又知船只航行所需时间(d)如表8-6所示。每批货物只需一条船装运，在空载和重载时航行时间相同，要求制定计划，以最少的船只完成这5项运输任务。 表8-5 地点 y1 y2 y3 x1 5 10 / x2 / 12 1,8 表8-5 地点 y1 y2 y3 x1 2 3 2 x2 1 1 2 (提示：用Ti表示运输任务(i=1，2，3，4，5)。作二部图，凡完成Ti项任务后可继续完成Tj项任务的在Ti,Tj间连线，再求二部图的最大匹配。) 第八章习题解答 解：两条船就够了。 一条船完成：T4→T5→T3； 另一条船完成：T1→T2 。 运筹学教程 School of Management page * * 第八章习题解答 8.1 证明在9座工厂之间，不可能每座工厂只与其他3座工厂有业务联系，也不可能只有4座工厂与偶数个工厂有业务联系。 解：将有联系的工厂做一条连线。 如果仅有9座工厂只与其他3座工厂有业务联系，说明顶点次数之和为27，矛盾。 如果只有4座工厂与偶数个工厂有业务联系，其他5个工厂一定与奇数个工厂有业务联系，说明顶点次数之和还是奇数，矛盾。 第八章习题解答 8.2 有八种化学药品A、B、C、D、E、F