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

1、第五章习题解答第五章习题解答 5.1 某地准备投资某地准备投资D元建民用住宅。可以建住宅的元建民用住宅。可以建住宅的地点有地点有n处：处：A1，A2，An。在。在Ai处每幢住宅的造价处每幢住宅的造价为为dj；，最多可造；，最多可造aj幢。问应当在哪几处建住宅，分别幢。问应当在哪几处建住宅，分别建几幢，才能使建造的住宅总数最多，试建立问题的建几幢，才能使建造的住宅总数最多，试建立问题的数学模型。数学模型。 是整数。处所建住宅的数量表示在解：设iniiiiiniiiixniaxDxdxZniAx, 2 , 1,max, 2 , 1,11第五章习题解答第五章习题解答 5.2 要在长度为要在长度为l的

2、一根圆钢上截取不同长度的零的一根圆钢上截取不同长度的零件毛坯，毛坯长度有件毛坯，毛坯长度有n种，分别为种，分别为aj，(j=1，2，,n)。问每种毛坯应当各截取多少根，才能使圆钢残料最少，问每种毛坯应当各截取多少根，才能使圆钢残料最少，试建立本问题的数学模型。试建立本问题的数学模型。 是整数。表示各种毛坯的数量解：设iniiiniiiixlxaxaZnix11max, 2 , 1,第五章习题解答第五章习题解答 5.3 有一批每根长度为有一批每根长度为l的圆钢，需要截取的圆钢，需要截取n种不种不同长度的零件毛坯。长度为同长度的零件毛坯。长度为aj的毛坯必须有的毛坯必须有mj段段(j1，2，n)。

3、为了方便，每根圆钢只截取一种长度的毛。为了方便，每根圆钢只截取一种长度的毛坯。应当怎样截取，才能使动用的圆钢数目最少，要坯。应当怎样截取，才能使动用的圆钢数目最少，要求建立数学模型。求建立数学模型。 niyxnimxynilyaxZynixiiiiiiiniiii, 2 , 1, 0, 2 , 1, 2 , 1,min, 2 , 1,1且都是整数，钢上可得到的数量。表示各种毛坯在一根圆。的数量表示各种毛坯使用圆钢解：设第五章习题解答第五章习题解答 5.4 篮球队需要选择篮球队需要选择5名队员组成出场阵容参加比名队员组成出场阵容参加比赛。赛。8名队员的身高及擅长位置见表名队员的身高及擅长位置见表

4、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、，试建立数学模型。平均身高最高，试建立数学模型。 变量是。个队员出场，表示第解：设102111551max, 2 , 1164182876218181iiiiiixxxxxxxxxxxxxZniix第五章习题解答第五章习题解答 5.5 一个旅行者要在其背包里装一些最有用的旅行一个旅行者要在其背包里装一些最有用的旅行物品。背包容积为物品。背包容积为a，携带物品总重量最多为，携带物品总重量最多为b。现有。现有物品物品m件，第件，第i件物品体积为件物品体积为ai，重量为，重量为bi(i1，2，m)。为了比较物品的有用程度，假设第。为了比较物品的有用程度，假设第j件物品的价值件物品的价值为为ci(i1

6、，2，m)。若每件物品只能整件携带，每。若每件物品只能整件携带，每件物品都能放人背包中，并且不考虑物品放人背包后件物品都能放人背包中，并且不考虑物品放人背包后相互的间隙。问旅行者应当携带哪几件物品，才能使相互的间隙。问旅行者应当携带哪几件物品，才能使携带物品的总价值最大，要求建立本问题的数学模型。携带物品的总价值最大，要求建立本问题的数学模型。 第五章习题解答第五章习题解答mixbxbaxaxcZmiiximiiimiiimiiii, 2 , 110max, 2 , 11111变量是。件物品，表示携带第解：设第五章习题解答第五章习题解答 5.6 用割平面法解下列整数规划：用割平面法解下列整数规

7、划： 4, 3, 1, 0,205462.max) 1 (2121212121ZxxxxxxxxstxxZ解：且为整数5, 1, 4., 0,885935min)2(212121212121ZxxxxxxxxxxstxxZ解：且为整数第五章习题解答第五章习题解答 5.7 用分支定界法解下列整数规划：用分支定界法解下列整数规划： 7, 1, 3., 0,2126052max) 1 (212121212121ZxxxxxxxxxxstxxZ解：且为整数5, 0, 5, 0.0,28275010325min)2(3212212121321ZxxxxxxxxxxstxxxZ解：为整数第五章习题解答第五

8、章习题解答 5.8 某公司生产某公司生产A，B和和C 3种产品，售价分别为种产品，售价分别为12元、元、7元和元和6元。生产每件元。生产每件A产品需要产品需要1h技术服务、技术服务、10h直接劳动、直接劳动、3kg材料；生产每件材料；生产每件B产品需要产品需要2h技术服务、技术服务、4h直接劳动、直接劳动、2kg材料；生产每件材料；生产每件C产品需要产品需要1h技术服技术服务、务、5h直接劳动、直接劳动、1k8材料。现在最多能提供材料。现在最多能提供100h技术技术服务、服务、700h直接劳动、直接劳动、400kg材料。生产成本是生产量材料。生产成本是生产量的非线性函数，如表的非线性函数，如表

9、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变量；变量；

10、表表5-11-12-135-11-12-13产品产品A A产量（件）产量（件）成本成本（元（元/ /件）件）产品产品B B产量（件）产量（件）成本成本（元（元/ /件）件）产品产品C C产量（件）产量（件）成本成本（元（元/ /件）件）0 0404010100 050506 60 01001005 541411001009 951511001004 4100100以上以上4 41011011501508 8100100以上以上3 3150150以上以上7 7第五章习题解答第五章习题解答.10100101100501015115010040151101411,400231,70054101,10

11、02)45()346()78910(6712max323133223222122322141312111141312323132123222132114131211321332312232221114131211321是任意大的数变量，是是整数变量，是：总利润最大的数学模型MyxMyyxyMyyyxyyMyyyyxyyyyyxxxyyyxxxyyyyxxxxyyxyyyxyyyyxxxZiji第五章习题解答第五章习题解答 5.9 解下列解下列0-1型整数规划：型整数规划： 解：此题无解。或.10,122022362245331075min) 1 (54321543254321543215432

12、1xxxxxxxxxxxxxxxxxxxstxxxxxZ2, 0, 110,44225423.2max)2(432132132132132321321ZxxxxxxxxxxxxxxxxxxstxxxZ解：或第五章习题解答第五章习题解答 5.10 有五项设计任务可供选择。各项设计任务的有五项设计任务可供选择。各项设计任务的预期完成时间分别为预期完成时间分别为3，8，5，4，10(周周)，设计报酬分，设计报酬分别为别为7，17，11，9，21(万元万元)。设计任务只能一项一项。设计任务只能一项一项地进行，总的期限是地进行，总的期限是20周。选择任务时必须满足下面要周。选择任务时必须满足下面要求：求

13、： 1至少完成至少完成3项设计任务；项设计任务； 2若选择任务若选择任务1，必须同时选择任务，必须同时选择任务2； 3任务任务3和任务和任务4不能同时选择。不能同时选择。 应当选择哪些设计任务，才能使总的设计报酬最大应当选择哪些设计任务，才能使总的设计报酬最大?第五章习题解答第五章习题解答5 , 4 , 3 , 2 , 1,1-0132010458321911177max5 , 2 , 114321543215432154321ixxxxxxxxxxxxxxxxxxxxZiixii变量是。项任务被选中，表示第解：设第五章习题解答第五章习题解答 5.11 某城市可划分为某城市可划分为11个防火区

14、，已设有个防火区，已设有4个消防个消防站，见下图所示。站，见下图所示。第五章习题解答第五章习题解答 上图中，虚线表示该消防站可以在消防允许时间上图中，虚线表示该消防站可以在消防允许时间内到达该地区进行有效的消防灭火。问能否关闭若干内到达该地区进行有效的消防灭火。问能否关闭若干消防站，但仍不影响任何一个防火区的消防救灾工作。消防站，但仍不影响任何一个防火区的消防救灾工作。(提示：对每提示：对每个消防站建立一个表示是否将关闭的个消防站建立一个表示是否将关闭的0-1变量。变量。) 号消防站。显然，可以关闭变量是。，个消防站保留，表示第解：设24,3 ,2, 1,1-011111111max43 ,2

15、, 114424214133211214321ixxxxxxxxxxxxxxxxxxxxZiixii第五章习题解答第五章习题解答 5.12 现有现有P个约束条件个约束条件 pibxanjiijij, 2 , 11 需要从中选择需要从中选择q q个约束条件，试借助个约束条件，试借助0-10-1变量列变量列出表达式。出表达式。piinjiijijiiqypibxaypiy11, 2 , 10)(, 2 , 1,10变量是解：设第五章习题解答第五章习题解答 5.13 解下列系数矩阵的最小化问题：解下列系数矩阵的最小化问题： 71011151314129651214101178241110) 1 (2

16、2,01000000100000110000Z解：267534257346858344176263)2(8,100000000000000100100100Z解：第五章习题解答第五章习题解答 5.14 5.14 需要分派需要分派5 5人去做人去做5 5项工作，每人做各项工项工作，每人做各项工作的能力评分见表作的能力评分见表5-145-14。应如何分派，才能使总的得。应如何分派，才能使总的得分最大分最大? ?表表5-14业务业务人员人员 B1B2B3B4B5A11.30.8001.0A201.21.31.30A31.0001.20A401.0500.21.4A51.00.90.601.1第五章习

17、题解答第五章习题解答1 . 6,00010100000100000100000013 . 04 . 18 . 05 . 04 . 002 . 14 . 135. 04 . 14 . 12 . 04 . 14 . 14 . 04 . 11 . 01 . 02 . 04 . 14 . 04 . 14 . 16 . 01 . 01.4Z最优解是：，得到矩阵：，用它减去所有元素，解：最大元素是第五章习题解答第五章习题解答 5.15 5.15 考虑下列问题：考虑下列问题： 式中式中)y0)y0，且，且x x的值只能等于的值只能等于0 0、1 1、4 4和和6 6。 (1)(1)请用一个等价的整数规划模型

18、来表达这个请用一个等价的整数规划模型来表达这个问题。问题。 62252.73maxyxyxstyxZ变量是解：10, 016264252.7333max321321321321xxxyxxxyxxxxxyxstyxxxZ第五章习题解答第五章习题解答 (2)(2)如果在目标函数中，用如果在目标函数中，用3x3x2 2来代替来代替3x3x，请相应地，请相应地修改修改(1)(1)的答案。的答案。第五章习题解答第五章习题解答 5.16 5.16 卡车送货问题卡车送货问题( (覆盖问题覆盖问题) )。龙运公司目。龙运公司目前必须向五家用户送货，在用户前必须向五家用户送货，在用户A A处卸下处卸下1 1单

19、位重量的单位重量的货物，在用户货物，在用户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。假定一辆卡车不能同时给用户

20、。假定一辆卡车不能同时给用户A A和和C C二者送货；同样，也不能同时给用户二者送货；同样，也不能同时给用户B B和和D D二者送货。二者送货。 (1)(1)请列出一个整数规划模型表达式，以确定装请列出一个整数规划模型表达式，以确定装运全部货物应如何配置卡车，使其运费为最小。运全部货物应如何配置卡车，使其运费为最小。 第五章习题解答第五章习题解答4 , 3 , 2 , 1; 5 , 4 , 3 , 2 , 1, 00)(11, 8, 6, 28, 4, 3, 2, 1min4142315145135125114154141441324114151jixxxxxxxxxxxxxxxcZjixij

21、jjjjjiiiiiiiijjjjjjjjjjjiijjij。辆卡车得到的实际运量个用户从第表示第解：设第五章习题解答第五章习题解答 (2) (2)如果卡车如果卡车j j给用户给用户i i运货时须收附加费运货时须收附加费c cijij，试，试叙述应如何修改这一表达式。叙述应如何修改这一表达式。 答：在目标函数中增加答：在目标函数中增加c cijijx xijij。 (3)(3)如果每辆卡车在一天内的送货次数不能超过如果每辆卡车在一天内的送货次数不能超过两次，试说明应如何修改表达式。两次，试说明应如何修改表达式。 答：将每辆卡车的运量增加一倍。答：将每辆卡车的运量增加一倍。 (4)(4)请说明如

22、果在卡车的运货路线上增加一些约请说明如果在卡车的运货路线上增加一些约束条件时，对模型的表达式有何影响。束条件时，对模型的表达式有何影响。 答：如果某辆车不能到达某用户，可以通过将附答：如果某辆车不能到达某用户，可以通过将附加费加费c cijij设为无穷大来实现。设为无穷大来实现。 第五章习题解答第五章习题解答 5.17 5.17 东方公司必须为其五台主要设备拟订预东方公司必须为其五台主要设备拟订预防性维修计划，这个计划将持续八周。假定每台设备防性维修计划，这个计划将持续八周。假定每台设备的编号为的编号为1 1、2 2、3 3、4 4、5 5。维修设备。维修设备1 1时，在第一周内时，在第一周内

23、需要需要4 4单位的劳动量单位的劳动量( (比如说为人比如说为人- -周周) )，在第二周内需，在第二周内需要要6 6单位，在第三周内需要单位，在第三周内需要3 3单位。维修工作最早可以单位。维修工作最早可以在第一周开始，最晚在第四周开始。其余各台设备的在第一周开始，最晚在第四周开始。其余各台设备的数据列在表数据列在表5-155-15中。中。 请对下列各小题列出最优化模型表达式。请对下列各小题列出最优化模型表达式。 (1)(1)假定在第假定在第i i周内可供使用的最大劳动量为周内可供使用的最大劳动量为L Li i单单位。请列出一个可行的速度计划位。请列出一个可行的速度计划( (即确定每台设备从

24、即确定每台设备从哪一周开始维修哪一周开始维修) )。第五章习题解答第五章习题解答表表5-155-15设备编号设备编号第一周第一周第二周第二周第三周第三周最早开工周最早开工周最迟开工周最迟开工周1 14 46 63 31 14 42 23 32 25 51 13 33 37 71 11 12 25 54 41 13 36 62 26 65 58 89 92 23 35 5第五章习题解答第五章习题解答8 , 2 , 1; 5, 2 , 11-08 , 2 , 1,5 , 4 , 3 , 2 , 1, 1, 1, 11, 1, 13 , 2 , 1; 5, 2 , 18 , 2 , 1; 5, 2

25、, 1151,6351517281851, 5351516271751,4351515261651, 3351514251551,2351513241451, 13515122315151312215121118155545346454443423534333223222114131211jipLjLwptptptwptptptwptptptwptptptwptptptwptptptwptptwptwippppppppppppppppppppkikitjijipijjjjiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii

26、ijijikij变量，为为周最大劳动量。周的人数，台设备维修第表示第周开始维修，台设备第表示第解：设第五章习题解答第五章习题解答 (2) (2)假定该公司要求每周使用的劳动量波动幅度之假定该公司要求每周使用的劳动量波动幅度之和为最小。和为最小。 例如，若每台设备都尽可能的早开始维修，例如，若每台设备都尽可能的早开始维修，则每周所需的劳动量为则每周所需的劳动量为7 7、1616、2020、1616、2 2、0 0、0 0、0 0，结果，周与周之间的波动幅度之和为结果，周与周之间的波动幅度之和为(16-7)+(20-(16-7)+(20-16)+(20-16)+(16-2)+(2-0)+(0-0)+(0-0)16)+(20-16)+(16-2)+(2-0)+(0-0)+(0-0)3333。 解：增加目标函数解：增加目标函数 min Z = min Z = |w|wi+1i+1- w- wi i| |第五章习题解答第五章习题解答 (3) (3)假设