第五章习题答案.pdf

第五章习题解答第五章习题解答 5.1 某地准备投资某地准备投资D元建民用住宅。可以建住宅元建民用住宅。可以建住宅 的地点有的地点有n处：处：A1，A2，An。在。在Ai处每幢住宅的处每幢住宅的 造价为造价为dj；，最多可造；，最多可造aj幢。问应当在哪几处建住宅，幢。问应当在哪几处建住宅， 分别建几幢，才能使建造的住宅总数最多，试建立问分别建几幢，才能使建造的住宅总数最多，试建立问 题的数学模型。题的数学模型。 是整数 。处所建住宅的数量表示在解：设 i n i iiii n i i ii x niaxDxd xZ niAx , 2 , 1, max , 2 , 1, 1 1 5.2 要在长度为要在长度为l的一根圆钢上截取不同长度的零的一根圆钢上截取不同长度的零 件毛坯，毛坯长度有件毛坯，毛坯长度有n种，分别为种，分别为aj，(j=1，2，,n)。 问每种毛坯应当各截取多少根，才能使圆钢残料最少，问每种毛坯应当各截取多少根，才能使圆钢残料最少， 试建立本问题的数学模型。试建立本问题的数学模型。 第五章习题解答第五章习题解答 是整数 。表示各种毛坯的数量解：设 i n i ii n i ii i x lxa xaZ nix 1 1 max , 2 , 1, 第五章习题解答第五章习题解答 5.3 有一批每根长度为有一批每根长度为l的圆钢，需要截取的圆钢，需要截取n种不种不 同长度的零件毛坯。长度为同长度的零件毛坯。长度为aj的毛坯必须有的毛坯必须有mj段段(j1， 2，n)。为了方便，每根圆钢只截取一种长度的。为了方便，每根圆钢只截取一种长度的 毛坯。应当怎样截取，才能使动用的圆钢数目最少，毛坯。应当怎样截取，才能使动用的圆钢数目最少， 要求建立数学模型。要求建立数学模型。 niyx nimxy nilya xZ y nix ii iii ii n i i i i , 2 , 1, 0, , 2 , 1, , 2 , 1, min , 2 , 1, 1 且都是整数， 钢上可得到的数量。表示各种毛坯在一根圆 。的数量表示各种毛坯使用圆钢解：设 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名队员上场名队员上场，才能使出场队员才能使出场队员 平均身高最高平均身高最高，试建立数学模型试建立数学模型。 第五章习题解答第五章习题解答 变量是 。个队员出场，表示第解：设 10 21 11 5 5 1 max , 2 , 11 64182 87621 8 1 8 1 i i i i i i x xxxxx xxxxx x xZ niix 5.5一个旅行者要在其背包里装一些最有用的旅一个旅行者要在其背包里装一些最有用的旅 行物品行物品。背包容积为背包容积为a，携带物品总重量最多为携带物品总重量最多为b。现现 有物品有物品m件件，第第i件物品体积为件物品体积为ai，重量为重量为bi(i1， 2，m)。为了比较物品的有用程度为了比较物品的有用程度，假设第假设第j件物件物 品的价值为品的价值为ci(i1，2，m)。若每件物品只能整件若每件物品只能整件 携带携带，每件物品都能放人背包中每件物品都能放人背包中，并且不考虑物品放并且不考虑物品放 人背包后相互的间隙人背包后相互的间隙。问旅行者应当携带哪几件物品问旅行者应当携带哪几件物品， 才能使携带物品的总价值最大才能使携带物品的总价值最大，要求建立本问题的数要求建立本问题的数 学模型学模型。 第五章习题解答第五章习题解答 第五章习题解答第五章习题解答 mi x bxb axa xcZ miix i m i ii m i ii m i ii i , 2 , 1 10 max , 2 , 11 1 1 1 变量是 。件物品，表示携带第解：设 5.6 用割平面法解下列整数规划：用割平面法解下列整数规划： 第五章习题解答第五章习题解答 4, 3, 1 , 0, 2054 62 . max ) 1 ( 21 21 21 21 21 Zxx xx xx xx st xxZ 解： 且为整数 5, 1, 4 . , 0, 88 5 93 5min )2( 21 21 21 21 21 21 Zxx xx xx xx xx st xxZ 解： 且为整数 5.7 用分支定界法解下列整数规划：用分支定界法解下列整数规划： 第五章习题解答第五章习题解答 7, 1, 3 . , 0, 2126 0 5 2max ) 1 ( 21 21 21 21 21 21 Zxx xx xx xx xx st xxZ 解： 且为整数 5, 0, 5, 0 . 0, 2827 50103 25min )2( 321 2 21 21 21 321 Zxxx x xx xx xx st xxxZ 解： 为整数 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变量。）变量。） 第五章习题解答第五章习题解答 第五章习题解答第五章习题解答 表表5 5- -1111- -1212- -1313 产品产品A A 产量（件）产量（件） 成本成本 （元（元/ /件）件） 产品产品B B 产量（件）产量（件） 成本成本 （元（元/ /件）件） 产品产品C C 产量（件）产量（件） 成本成本 （元（元/ /件）件） 0 0404010100 050506 60 01001005 5 41411001009 951511001004 4100100以上以上4 4 1011011501508 8100100以上以上3 3 150150以上以上7 7 解：设解：设x1,x2,x3分别表示三个产品的产量。分别表示三个产品的产量。 Y11,y12,y13,y14对应产品对应产品A的的4个成本的个成本的0-1变量；变量； Y21,y22,y23对应产品对应产品B的的3个成本的个成本的0-1变量；变量； Y31,y32对应产品对应产品B的的3个成本的个成本的0-1变量；变量； 第五章习题解答第五章习题解答 .10 100101 1005010151 1501004015110141 1,40023 1,7005410 1,1002 )45()346( )78910(6712max 3231332 23222122322 141312111141312 3231321 232221321332312232221 114131211321 是任意大的数变量，是是整数变量， 是：总利润最大的数学模型 Myx Myyxy Myyyxyy Myyyyxyyy yyxxx yyyxxx yyyyxxx xyyxyyy xyyyyxxxZ iji 5.9 解下列解下列0-1型整数规划：型整数规划： 第五章习题解答第五章习题解答 解：此题无解。 或 . 10, 122 022362 2453 31075min ) 1 ( 54321 5432 54321 54321 54321 xxxxx xxxx xxxxx xxxxx st xxxxxZ 2, 0, 1 10, 44 22 54 23 . 2max )2( 4321 321 321 321 32 321 321 Zxxxx xxx xxx xxx xx xxx st xxxZ 解： 或 5.10 有五项设计任务可供选择。各项设计任务的预有五项设计任务可供选择。各项设计任务的预 期完成时间分别为期完成时间分别为3，8，5，4，10(周周)，设计报酬分别，设计报酬分别 为为7，17，11，9，21(万元万元)。设计任务只能一项一项地。设计任务只能一项一项地 进行，总的期限是进行，总的期限是20周。选择任务时必须满足下面要求：周。选择任务时必须满足下面要求： 1至少完成至少完成3项设计任务；项设计任务； 2若选择任务若选择任务1，必须同时选择任务必须同时选择任务2； 3任务任务3和任务和任务4不能同时选择不能同时选择。 应当选择哪些设计任务应当选择哪些设计任务，才能使总的设计报酬最大才能使总的设计报酬最大? 第五章习题解答第五章习题解答 第五章习题解答第五章习题解答 5 , 4 , 3 , 2 , 1,1-0 1 3 20104583 21911177max 5 , 2 , 11 43 21 54321 54321 54321 ix xx xx xxxxx xxxxx xxxxxZ iix i i 变量是 。项任务被选中，表示第解：设 5.11 某城市可划分为某城市可划分为11个防火区，已设有个防火区，已设有4个消个消 防站，见下图所示。防站，见下图所示。 第五章习题解答第五章习题解答 上图中，虚线表示该消防站可以在消防允许时间上图中，虚线表示该消防站可以在消防允许时间 内到达该地区进行有效的消防灭火。问能否关闭若干内到达该地区进行有效的消防灭火。问能否关闭若干 消防站，但仍不影响任何一个防火区的消防救灾工作。消防站，但仍不影响任何一个防火区的消防救灾工作。 (提示：对每提示：对每个消防站建立一个表示是否将关闭的个消防站建立一个表示是否将关闭的0- 1变量。变量。) 第五章习题解答第五章习题解答 号消防站。显然，可以关闭 变量是 。，个消防站保留，表示第解：设 2 4, 3,2, 1,1-0 11 11 11 11 max 43,2, 11 442 42141 3321 121 4321 ix xxx xxxxx xxxx xxx xxxxZ iix i i 5.12 现有现有P个约束条件个约束条件 第五章习题解答第五章习题解答 pibxa n j iijij , 2 , 1 1 需要从中选择需要从中选择q q个约束条件个约束条件，试借助试借助0 0- -1 1变量列出变量列出 表达式表达式。 p i i n j iijiji i qy pibxay piy 1 1 , 2 , 10)( , 2 , 1,10 变量是解：设 5.13 解下列系数矩阵的最小化问题：解下列系数矩阵的最小化问题： 第五章习题解答第五章习题解答 710111513 1412965 121410117 8241110 ) 1 (22, 01000 00010 00001 10000 Z解： 2675 3425 7346 8583 4417 6263 )2(8, 1000 0000 0000 0001 0010 0100 Z解： 5.14 5.14 需要分派需要分派5 5人去做人去做5 5项工作，每人做各项工项工作，每人做各项工 作的能力评分见表作的能力评分见表5 5- -1414。应如何分派，才能使总的得。应如何分派，才能使总的得 分最大分最大? ? 第五章习题解答第五章习题解答 表表5-14 业务业务 人员人员 B1B2B3B4B5 A11.30.8001.0 A201.21.31.30 A31.0001.20 A401.0500.21.4 A51.00.90.601.1 第五章习题解答第五章习题解答 1 . 6, 00010 10000 01000 00100 00001 3 . 04 . 18 . 05 . 04 . 0 02 . 14 . 135. 04 . 1 4 . 12 . 04 . 14 . 14 . 0 4 . 11 . 01 . 02 . 04 . 1 4 . 04 . 14 . 16 . 01 . 0 1.4 Z最优解是： ，得到矩阵： ，用它减去所有元素，解：最大元素是 5.15 5.15 考虑下列问题：考虑下列问题： 式中式中)y)y0 0，且且x x的值只能等于的值只能等于0 0、1 1、4 4和和6 6。 ( (1 1) )请用一个等价的整数规划模型来表达这个问请用一个等价的整数规划模型来表达这个问 题题。 第五章习题解答第五章习题解答 62 252 . 73max yx yx st yxZ 变量是 解： 10, 0 162 64252 . 7333max 321 321 321 321 xxxy xxxyx xxxxyx st yxxxZ (2)(2)如果在目标函数中，用如果在目标函数中，用3x3x2 2来代替来代替3x3x，请相应，请相应 地修改地修改(1)(1)的答案。的答案。 第五章习题解答第五章习题解答 5 5. .1616卡车送货问题卡车送货问题( (覆盖问题覆盖问题) )。龙运公司目龙运公司目 前必须向五家用户送货前必须向五家用户送货，在用户在用户A A处卸下处卸下1 1单位重量的单位重量的 货物货物，在用户在用户B B处卸下处卸下2 2单位重量的货物单位重量的货物，在用户在用户C C处处 卸下卸下3 3单位重量的货物单位重量的货物，在用户在用户D D处卸下处卸下4 4单位重量的单位重量的 货物货物，在用户在用户E E处卸下处卸下8 8单位重量的货物单位重量的货物。公司有各种公司有各种 卡车四辆卡车四辆。1 1号车载重能力为号车载重能力为2 2单位重量单位重量，2 2号车载重号车载重 能力为能力为6 6，3 3号车载重能力为号车载重能力为8 8，4 4号车载重能力为号车载重能力为1111。 卡车卡车j j的运费为的运费为c cj j。假定一辆卡车不能同时给用户假定一辆卡车不能同时给用户A A和和C C 二者送货；同样二者送货；同样，也不能同时给用户也不能同时给用户B B和和D D二者送货二者送货。 ( (1 1) )请列出一个整数规划模型表达式请列出一个整数规划模型表达式，以确定装以确定装 运全部货物应如何配置卡车运全部货物应如何配置卡车，使其运费为最小使其运费为最小。 第五章习题解答第五章习题解答 第五章习题解答第五章习题解答 4 , 3 , 2 , 1; 5 , 4 , 3 , 2 , 1, 0 0)( 11, 8, 6, 2 8, 4, 3, 2, 1 min 4 1 4231 5 1 4 5 1 3 5 1 2 5 1 1 4 1 5 4 1 4 1 4 4 1 32 4 1 1 4 1 5 1 jix xxxx xxxx xxxxx xcZ jix ij j jjjj i i i i i i i i j j jj j j jj j j ji ijj ij 。辆卡车得到的实际运量个用户从第表示第解：设 ( (2 2) )如果卡车如果卡车j j给用户给用户i i运货时须收附加费运货时须收附加费c cij ij， ，试试 叙述应如何修改这一表达式叙述应如何修改这一表达式。 答：在目标函数中增加答：在目标函数中增加c cij ijx xijij。 。 ( (3 3) )如果每辆卡车在一天内的送货次数不能超过如果每辆卡车在一天内的送货次数不能超过 两次两次，试说明应如何修改表达式试说明应如何修改表达式。 答：将每辆卡车的运量增加一倍答：将每辆卡车的运量增加一倍。 ( (4 4) )请说明如果在卡车的运货路线上增加一些约请说明如果在卡车的运货路线上增加一些约 束条件时束条件时，对模型的表达式有何影响对模型的表达式有何影响。 答：如果某辆车不能到达某用户答：如果某辆车不能到达某用户，可以通过将附可以通过将附 加费加费c cij ij设为无穷大来实现 设为无穷大来实现。 第五章习题解答第五章习题解答 5 5. .1717东方公司必须为其五台主要设备拟订预东方公司必须为其五台主要设备拟订预 防性维修计划防性维修计划，这个计划将持续八周这个计划将持续八周。假定每台设备假定每台设备 的编号为的编号为1 1、2 2、3 3、4 4、5 5。维修设备维修设备1 1时时，在第一周内在第一周内 需要需要4 4单位的劳动量单位的劳动量( (比如说为人比如说为人- -周周) )，在第二周内需在第二周内需 要要6 6单位单位，在第三周内需要在第三周内需要3 3单位单位。维修工作最早可以维修工作最早可以 在第一周开始在第一周开始，最晚在第四周开始最晚在第四周开始。其余各台设备的其余各台设备的 数据列在表数据列在表5 5- -1515中中。 请对下列各小题列出最优化模型表达式请对下列各小题列出最优化模型表达式。 ( (1 1) )假定在第假定在第i i周内可供使用的最大劳动量为周内可供使用的最大劳动量为L Li i单单 位位。请列出一个可行的速度计划请列出一个可行的速度计划( (即确定每台设备从即确定每台设备从 哪一周开始维修哪一周开始维修) )。 第五章习题解答第五章习题解答 第五章习题解答第五章习题解答 表表5 5- -1515 设备编号设备编号第一周第一周第二周第二周第三周第三周最早开工周最早开工周最迟开工周最迟开工周 1 14 46 63 31 14 4 2 23 32 25 51 13 3 3 37 71 11 12 25 5 4 41 13 36 62 26 6 5 58 89 92 23 35 5 第五章习题解答第五章习题解答 8 , 2 , 1; 5, 2 , 11-0 8 , 2 , 1, , , 5 , 4 , 3 , 2 , 1, 1, 1, 1 1, 1, 1 3 , 2 , 1; 5, 2 , 1 8 , 2 , 1; 5, 2 , 11 5 1 , 63 5 1 5 1 72818 5 1 , 53 5 1 5 1 62717 5 1 , 43 5 1 5 1 52616 5 1 , 33 5 1 5 1 42515 5 1 , 23 5 1 5 1 32414 5 1 , 13 5 1 5 1 2231 5 1 5 1 31221 5 1 2111 8 1 5554534645444342 3534333223222114131211 jip LjLwptptptw ptptptwptptptw ptptptwptptptw ptptptwptptwptw ippppppppp ppppppppppp kikit jijip ij jjj i ii ii iiii i ii ii iiii i ii ii iiii i ii ii iiii i ii ii iiii i ii ii iiii ii iiii i ii j ij ik ij 变量，为 为周最大劳动量。 。周的人数，台设备维修第表示第 周开始维修，台设备第表示第解：设 第五章习题解答第五章习题解答 ( (2 2) )假定该公司要求每周使用的劳动量波动幅度之假定该公司要求每周使用的劳动量波动幅度之 和为最小和为最小。 例如例如，若每台设备都尽可能的早开始维修若每台设备都尽可能的早开始维修， 则每周所需的劳动量为则每周所需的劳动量为7 7、1616、2020、1616、2 2、0 0、0 0、0 0， 结果结果，周与周之间的波动幅度之和为周与周之间的波动幅度之和为( (1616- -7 7)+()+(2020- - 1616)+()+(2020- -1616)+()+(1616- -2 2)+()+(2 2- -0 0)+()+(0 0- -0 0)+()+(0 0- -0 0) )3333。 解：增加目标函数解：增加目标函数 minmin Z Z = = |w|wi+ i+1 1- - w wi i| | ( (