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

第五章习题解答 5.1 某地准备投资D元建民用住宅。可以建住宅的 地点有n处：A1，A2，An。在Ai处每幢住宅的造价 为dj；，最多可造aj幢。问应当在哪几处建住宅，分别 建几幢，才能使建造的住宅总数最多，试建立问题的 数学模型。 第五章习题解答 5.2 要在长度为l的一根圆钢上截取不同长度的零 件毛坯，毛坯长度有n种，分别为aj，(j=1，2，,n)。 问每种毛坯应当各截取多少根，才能使圆钢残料最少 ，试建立本问题的数学模型。 第五章习题解答 5.3 有一批每根长度为l的圆钢，需要截取n种不 同长度的零件毛坯。长度为aj的毛坯必须有mj段(j1 ，2，n)。为了方便，每根圆钢只截取一种长度的 毛坯。应当怎样截取，才能使动用的圆钢数目最少， 要求建立数学模型。 第五章习题解答 5.4 篮球队需要选择5名队员组成出场阵容参加比 赛。8名队员的身高及擅长位置见表5-10。 表5-10 队员12345678 身高(m)1.921.901.881.861.851.831.801.78 擅长位置中锋中锋前锋前锋前锋后卫后卫后卫 出场阵容应满足以下条件： (1) 只能有一名中锋上场； (2) 至少有名后卫； (3) 如1号和4号均上场，则6号不出场； 第五章习题解答 (4) 2号和8号至少有一个不出场。 问应当选择哪5名队员上场，才能使出场队员 平均身高最高，试建立数学模型。 第五章习题解答 5.5 一个旅行者要在其背包里装一些最有用的旅行 物品。背包容积为a，携带物品总重量最多为b。现有 物品m件，第i件物品体积为ai，重量为bi(i1，2， m)。为了比较物品的有用程度，假设第j件物品的价值 为ci(i1，2，m)。若每件物品只能整件携带，每 件物品都能放人背包中，并且不考虑物品放人背包后 相互的间隙。问旅行者应当携带哪几件物品，才能使 携带物品的总价值最大，要求建立本问题的数学模型 。 第五章习题解答 第五章习题解答 5.6 用割平面法解下列整数规划： 第五章习题解答 5.7 用分支定界法解下列整数规划： 第五章习题解答 5.8 某公司生产A，B和C 3种产品，售价分别为12 元、7元和6元。生产每件A产品需要1h技术服务、10h 直接劳动、3kg材料；生产每件B产品需要2h技术服务 、4h直接劳动、2kg材料；生产每件C产品需要1h技术 服务、5h直接劳动、1k8材料。现在最多能提供100h技 术服务、700h直接劳动、400kg材料。生产成本是生产 量的非线性函数，如表5-11、表5-12、表5-13所示。要 求建立一个总利润最大的生产计划的数学模型。提示： 对每种产品不同成本的产量范围各设一个0-1变量。） 第五章习题解答 解：设x1,x2,x3分别表示三个产品的产量。 Y11,y12,y13,y14对应产品A的4个成本的0-1变量； Y21,y22,y23对应产品B的3个成本的0-1变量； Y31,y32对应产品B的3个成本的0-1变量； 表5-11-12-13 产品A 产量（件 ） 成本 （元/件 ） 产品B 产量（件 ） 成本 （元/件 ） 产品C 产量（件 ） 成本 （元/件 ） 04010050601005 411009511004100以上4 1011508100以上3 150以上7 第五章习题解答 第五章习题解答 5.9 解下列0-1型整数规划： 第五章习题解答 5.10 有五项设计任务可供选择。各项设计任务的 预期完成时间分别为3，8，5，4，10(周)，设计报酬分 别为7，17，11，9，21(万元)。设计任务只能一项一项 地进行，总的期限是20周。选择任务时必须满足下面要 求： 1至少完成3项设计任务； 2若选择任务1，必须同时选择任务2； 3任务3和任务4不能同时选择。 应当选择哪些设计任务，才能使总的设计报酬最大? 第五章习题解答 第五章习题解答 5.11 某城市可划分为11个防火区，已设有4个消防 站，见下图所示。 第五章习题解答 上图中，虚线表示该消防站可以在消防允许时间 内到达该地区进行有效的消防灭火。问能否关闭若干 消防站，但仍不影响任何一个防火区的消防救灾工作 。(提示：对每个消防站建立一个表示是否将关闭的 0-1变量。) 第五章习题解答 5.12 现有P个约束条件 需要从中选择q个约束条件，试借助0-1变量列出表 达式。 第五章习题解答 5.13 解下列系数矩阵的最小化问题： 第五章习题解答 5.14 需要分派5人去做5项工作，每人做各项工 作的能力评分见表5-14。应如何分派，才能使总的得 分最大? 表5-14 业务 人员 B1B2B3B4B5 A11.30.8001.0 A201.21.31.30 A31.0001.20 A401.0500.21.4 A51.00.90.601.1 第五章习题解答 第五章习题解答 5.15 考虑下列问题： 式中)y0，且x的值只能等于0、1、4和6。 (1)请用一个等价的整数规划模型来表达这个问 题。 第五章习题解答 (2)如果在目标函数中，用3x2来代替3x，请相应地 修改(1)的答案。 第五章习题解答 5.16 卡车送货问题(覆盖问题)。龙运公司目 前必须向五家用户送货，在用户A处卸下1单位重量的 货物，在用户B处卸下2单位重量的货物，在用户C处卸 下3单位重量的货物，在用户D处卸下4单位重量的货物 ，在用户E处卸下8单位重量的货物。公司有各种卡车 四辆。1号车载重能力为2单位重量，2号车载重能力为 6，3号车载重能力为8，4号车载重能力为11。卡车j的 运费为cj。假定一辆卡车不能同时给用户A和C二者送 货；同样，也不能同时给用户B和D二者送货。 (1)请列出一个整数规划模型表达式，以确定装 运全部货物应如何配置卡车，使其运费为最小。 第五章习题解答 第五章习题解答 (2)如果卡车j给用户i运货时须收附加费cij，试 叙述应如何修改这一表达式。 答：在目标函数中增加cijxij。 (3)如果每辆卡车在一天内的送货次数不能超过 两次，试说明应如何修改表达式。 答：将每辆卡车的运量增加一倍。 (4)请说明如果在卡车的运货路线上增加一些约 束条件时，对模型的表达式有何影响。 答：如果某辆车不能到达某用户，可以通过将附 加费cij设为无穷大来实现。 第五章习题解答 5.17 东方公司必须为其五台主要设备拟订预 防性维修计划，这个计划将持续八周。假定每台设备 的编号为1、2、3、4、5。维修设备1时，在第一周内 需要4单位的劳动量(比如说为人-周)，在第二周内需 要6单位，在第三周内需要3单位。维修工作最早可以 在第一周开始，最晚在第四周开始。其余各台设备的 数据列在表5-15中。 请对下列各小题列出最优化模型表达式。 (1)假定在第i周内可供使用的最大劳动量为Li单 位。请列出一个可行的速度计划(即确定每台设备从哪 一周开始维修)。 第五章习题解答 表5-15 设备编号第一周第二周第三周最早开工周最迟开工周 146314 232513 371125 413626 589235 第五章习题解答 第五章习题解答 (2)假定该公司要求每周使用的劳动量波动幅度之 和为最小。例如，若每台设备都尽可能的早开始维修， 则每周所需的劳动量为7、16、20、16、2、0、0、0，结 果，周与周之间的波动幅度之和为(16-7)+(20-16)+(20- 16)+(16-2)+(2-0)+(0-0)+(0-0)33。 解：增加目标函数 min Z = |wi+1- wi| 第五章习题解答 (3)假设该公司要求在八周内的任何一周所需的最 大劳动量为最小。 解：增加 min Z = w,w wi,i=1,2,3,4,5,6,7,8 (4)假设该公司要求将最大的每周劳动量波动幅度 减至最小。(如果每台设备都尽可能早的开始维修，则 在第四周至第五周之间的最大波动幅度为16-214。) 解：增加 min Z = w,w|wi+1-wi|, i=1,2,7 (5)如果设备3不能在设备1开始维修前开工，试说 明应如何修改(1)的答案。 解：增加 p11+p12p32; p11+p12+p13p33; 第五章习题解答 如果设备4必须