(精品)运筹学黄皮书第五章课件.ppt

《(精品)运筹学黄皮书第五章课件.ppt》由会员分享，可在线阅读，更多相关《(精品)运筹学黄皮书第五章课件.ppt（33页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、运筹学教程（第二版）运筹学教程（第二版）习题解答习题解答运筹学教程运筹学教程 School of ManagementSchool of Managementpage page 2 24/4/20234/4/2023第五章习题解答第五章习题解答 5.1 某地准备投资某地准备投资D元建民用住宅。可以建住宅元建民用住宅。可以建住宅的地点有的地点有n处：处：A1，A2，An。在。在Ai处每幢住宅的处每幢住宅的造价为造价为dj；，；，最多可造最多可造aj幢。问应当在哪几处建住宅，幢。问应当在哪几处建住宅，分别建几幢，才能使建造的住宅总数最多，试建立问分别建几幢，才能使建造的住宅总数最多，试建立问题的数

2、学模型。题的数学模型。运筹学教程运筹学教程 School of ManagementSchool of Managementpage page 3 34/4/20234/4/2023 5.2 要在长度为要在长度为l的一根圆钢上截取不同长度的零的一根圆钢上截取不同长度的零件毛坯，毛坯长度有件毛坯，毛坯长度有n种，分别为种，分别为aj，(j=1，2，,n)。问每种毛坯应当各截取多少根，才能使圆钢问每种毛坯应当各截取多少根，才能使圆钢残料最少，试建立本问题的数学模型。残料最少，试建立本问题的数学模型。第五章习题解答第五章习题解答运筹学教程运筹学教程 School of ManagementSchoo

3、l of Managementpage page 4 44/4/20234/4/2023第五章习题解答第五章习题解答 5.3 有一批每根长度为有一批每根长度为l的圆钢，需要截取的圆钢，需要截取n种不种不同长度的零件毛坯。长度为同长度的零件毛坯。长度为aj的毛坯必须有的毛坯必须有mj段段(j1，2，n)。为了方便，每根圆钢只截取一种长度为了方便，每根圆钢只截取一种长度的毛坯。应当怎样截取，才能使动用的圆钢数目最少，的毛坯。应当怎样截取，才能使动用的圆钢数目最少，要求建立数学模型。要求建立数学模型。运筹学教程运筹学教程 School of ManagementSchool of Managemen

4、tpage page 5 54/4/20234/4/2023 5.4 篮球队需要选择篮球队需要选择5名队员组成出场阵容参加名队员组成出场阵容参加比赛。比赛。8名队员的身高及擅长位置见表名队员的身高及擅长位置见表5-10。第五章习题解答第五章习题解答表表5-10队员队员12345678身高身高(m)1.921.901.881.861.851.831.801.78擅长位置擅长位置中锋中锋中锋中锋前锋前锋前锋前锋前锋前锋后卫后卫后卫后卫后卫后卫 出场阵容应满足以下条件：出场阵容应满足以下条件：(1)只能有一名中锋上场；只能有一名中锋上场；(2)至少有至少有名后卫；名后卫；(3)如如1号和号和4号均号

5、均上场，则上场，则6号不出场；号不出场；运筹学教程运筹学教程 School of ManagementSchool of Managementpage page 6 64/4/20234/4/2023 (4)2号和号和8号至少有一个不出场。号至少有一个不出场。问问应应当当选选择择哪哪5名名队队员员上上场场，才才能能使使出出场场队队员员平均身高最高，试建立数学模型。平均身高最高，试建立数学模型。第五章习题解答第五章习题解答运筹学教程运筹学教程 School of ManagementSchool of Managementpage page 7 74/4/20234/4/2023 5.5 一一个

6、个旅旅行行者者要要在在其其背背包包里里装装一一些些最最有有用用的的旅旅行行物物品品。背背包包容容积积为为a，携携带带物物品品总总重重量量最最多多为为b。现现有有物物品品m件件，第第i件件物物品品体体积积为为ai，重重量量为为bi(i1，2，m)。为为了了比比较较物物品品的的有有用用程程度度，假假设设第第j件件物物品品的的价价值值为为ci(i1，2，m)。若若每每件件物物品品只只能能整整件件携携带带，每每件件物物品品都都能能放放人人背背包包中中，并并且且不不考考虑虑物物品品放放人人背背包包后后相相互互的的间间隙隙。问问旅旅行行者者应应当当携携带带哪哪几几件件物物品品，才才能能使使携携带带物物品品

7、的的总总价价值值最最大大，要要求求建建立立本本问问题题的的数数学模型。学模型。第五章习题解答第五章习题解答运筹学教程运筹学教程 School of ManagementSchool of Managementpage page 8 84/4/20234/4/2023第五章习题解答第五章习题解答运筹学教程运筹学教程 School of ManagementSchool of Managementpage page 9 94/4/20234/4/2023 5.6 用割平面法解下列整数规划：用割平面法解下列整数规划：第五章习题解答第五章习题解答运筹学教程运筹学教程 School of Managem

8、entSchool of Managementpage page 10104/4/20234/4/2023 5.7 用分支定界法解下列整数规划：用分支定界法解下列整数规划：第五章习题解答第五章习题解答运筹学教程运筹学教程 School of ManagementSchool of Managementpage page 11114/4/20234/4/2023 5.8 某公司生产某公司生产A，B和和C 3种产品，售价分别为种产品，售价分别为12元、元、7元和元和6元。生产每件元。生产每件A产品需要产品需要1h技术服务、技术服务、10h直接劳动、直接劳动、3kg材料；生产每件材料；生产每件B产品

9、需要产品需要2h技术服务、技术服务、4h直接劳动、直接劳动、2kg材料；生产每件材料；生产每件C产品需要产品需要1h技术服技术服务、务、5h直接劳动、直接劳动、1k8材料。现在最多能提供材料。现在最多能提供100h技术技术服务、服务、700h直接劳动、直接劳动、400kg材料。生产成本是生产量材料。生产成本是生产量的非线性函数，如表的非线性函数，如表5-11、表、表5-12、表、表5-13所示。要求所示。要求建立一个总利润最大的生产计划的数学模型。建立一个总利润最大的生产计划的数学模型。提示：对提示：对每种产品不同成本的产量范围各设一个每种产品不同成本的产量范围各设一个0-1变量。）变量。）第

10、五章习题解答第五章习题解答运筹学教程运筹学教程 School of ManagementSchool of Managementpage page 12124/4/20234/4/2023第五章习题解答第五章习题解答表表5-11-12-135-11-12-13产品产品A A产量（件）产量（件）成本成本（元（元/件）件）产品产品B B产量（件）产量（件）成本成本（元（元/件）件）产品产品C C产量（件）产量（件）成本成本（元（元/件）件）0 0404010100 050506 60 01001005 541411001009 951511001004 4100100以上以上4 410110115

11、01508 8100100以上以上3 3150150以上以上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变量；变量；运筹学教程运筹学教程 School of ManagementSchool of Managementpage page 13134/4/20234/4/2023第五章习题解答第五章习题解答运筹学教程运筹学教程 Sc

12、hool of ManagementSchool of Managementpage page 14144/4/20234/4/2023 5.9 解下列解下列0-1型整数规划：型整数规划：第五章习题解答第五章习题解答运筹学教程运筹学教程 School of ManagementSchool of Managementpage page 15154/4/20234/4/2023 5.10 有五项设计任务可供选择。各项设计任务的预有五项设计任务可供选择。各项设计任务的预期完成时间分别为期完成时间分别为3，8，5，4，10(周周)，设计报酬分别，设计报酬分别为为7，17，11，9，21(万元万元)。

13、设计任务只能一项一项地。设计任务只能一项一项地进行，总的期限是进行，总的期限是20周。选择任务时必须满足下面要求：周。选择任务时必须满足下面要求：1至少完成至少完成3项设计任务；项设计任务；2若选择任务若选择任务1，必须同时选择任务，必须同时选择任务2；3任务任务3和任务和任务4不能同时选择。不能同时选择。应当选择哪些设计任务，才能使总的设计报酬最大应当选择哪些设计任务，才能使总的设计报酬最大?第五章习题解答第五章习题解答运筹学教程运筹学教程 School of ManagementSchool of Managementpage page 16164/4/20234/4/2023第五章习题解

14、答第五章习题解答运筹学教程运筹学教程 School of ManagementSchool of Managementpage page 17174/4/20234/4/2023 5.11 某城市可划分为某城市可划分为11个防火区，已设有个防火区，已设有4个消防个消防站，见下图所示。站，见下图所示。第五章习题解答第五章习题解答运筹学教程运筹学教程 School of ManagementSchool of Managementpage page 18184/4/20234/4/2023 上图中，虚线表示该消防站可以在消防允许时间上图中，虚线表示该消防站可以在消防允许时间内到达该地区进行有效的消

15、防灭火。问能否关闭若干内到达该地区进行有效的消防灭火。问能否关闭若干消防站，但仍不影响任何一个防火区的消防救灾工作。消防站，但仍不影响任何一个防火区的消防救灾工作。(提示：对每提示：对每个消防站建立一个表示是否将关闭的个消防站建立一个表示是否将关闭的0-1变量。变量。)第五章习题解答第五章习题解答运筹学教程运筹学教程 School of ManagementSchool of Managementpage page 19194/4/20234/4/2023 5.12 现有现有P个约束条件个约束条件 第五章习题解答第五章习题解答 需需要要从从中中选选择择q q个个约约束束条条件件，试试借借助助0

16、-10-1变变量量列列出出表表达式。达式。运筹学教程运筹学教程 School of ManagementSchool of Managementpage page 20204/4/20234/4/2023 5.13 解下列系数矩阵的最小化问题：解下列系数矩阵的最小化问题：第五章习题解答第五章习题解答运筹学教程运筹学教程 School of ManagementSchool of Managementpage page 21214/4/20234/4/2023 5.14 5.14 需要分派需要分派5 5人去做人去做5 5项工作，每人做各项工项工作，每人做各项工作的能力评分见表作的能力评分见表5-

17、145-14。应如何分派，才能使总的得。应如何分派，才能使总的得分最大分最大?第五章习题解答第五章习题解答表表5-14业务业务人员人员 B1B2B3B4B5A11.30.8001.0A201.21.31.30A31.0001.20A401.0500.21.4A51.00.90.601.1运筹学教程运筹学教程 School of ManagementSchool of Managementpage page 22224/4/20234/4/2023第五章习题解答第五章习题解答运筹学教程运筹学教程 School of ManagementSchool of Managementpage page

18、23234/4/20234/4/2023 5.15 5.15 考虑下列问题：考虑下列问题：式中式中)y0)y0，且，且x x的值只能等于的值只能等于0 0、1 1、4 4和和6 6。(1)(1)请请用用一一个个等等价价的的整整数数规规划划模模型型来来表表达达这这个个问问题。题。第五章习题解答第五章习题解答运筹学教程运筹学教程 School of ManagementSchool of Managementpage page 24244/4/20234/4/2023 (2)(2)如果在目标函数中，用如果在目标函数中，用3x3x2 2来代替来代替3x3x，请相应请相应地修改地修改(1)(1)的答案

19、。的答案。第五章习题解答第五章习题解答运筹学教程运筹学教程 School of ManagementSchool of Managementpage page 25254/4/20234/4/2023 5.16 5.16 卡卡车车送送货货问问题题(覆覆盖盖问问题题)。龙龙运运公公司司目目前前必必须须向向五五家家用用户户送送货货，在在用用户户A A处处卸卸下下1 1单单位位重重量量的的货货物物，在在用用户户B B处处卸卸下下2 2单单位位重重量量的的货货物物，在在用用户户C C处处卸卸下下3 3单单位位重重量量的的货货物物，在在用用户户D D处处卸卸下下4 4单单位位重重量量的的货货物物，在在用

20、用户户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)请请列列出出一一个个整整数数规规划划模模型型表表达达式式，以以确确定定装装运运全部货物应如何

21、配置卡车，使其运费为最小。全部货物应如何配置卡车，使其运费为最小。第五章习题解答第五章习题解答运筹学教程运筹学教程 School of ManagementSchool of Managementpage page 26264/4/20234/4/2023第五章习题解答第五章习题解答运筹学教程运筹学教程 School of ManagementSchool of Managementpage page 27274/4/20234/4/2023 (2)(2)如如果果卡卡车车j j给给用用户户i i运运货货时时须须收收附附加加费费c cijij，试试叙叙述应如何修改这一表达式。述应如何修改这一表达

22、式。答：在目标函数中增加答：在目标函数中增加c cijijx xijij。(3)(3)如如果果每每辆辆卡卡车车在在一一天天内内的的送送货货次次数数不不能能超超过过两两次，试说明应如何修改表达式。次，试说明应如何修改表达式。答：将每辆卡车的运量增加一倍。答：将每辆卡车的运量增加一倍。(4)(4)请请说说明明如如果果在在卡卡车车的的运运货货路路线线上上增增加加一一些些约约束束条件时，对模型的表达式有何影响。条件时，对模型的表达式有何影响。答答：如如果果某某辆辆车车不不能能到到达达某某用用户户，可可以以通通过过将将附附加费加费c cijij设设为无穷大来实现。为无穷大来实现。第五章习题解答第五章习题

23、解答运筹学教程运筹学教程 School of ManagementSchool of Managementpage page 28284/4/20234/4/2023 5.17 5.17 东东方方公公司司必必须须为为其其五五台台主主要要设设备备拟拟订订预预防防性性维维修修计计划划，这这个个计计划划将将持持续续八八周周。假假定定每每台台设设备备的的编编号号为为1 1、2 2、3 3、4 4、5 5。维维修修设设备备1 1时时，在在第第一一周周内内需需要要4 4单单位位的的劳劳动动量量(比比如如说说为为人人-周周)，在在第第二二周周内内需需要要6 6单单位位，在在第第三三周周内内需需要要3 3单单

24、位位。维维修修工工作作最最早早可可以以在在第第一一周周开开始始，最最晚晚在在第第四四周周开开始始。其其余余各各台台设设备备的的数数据据列在表列在表5-155-15中。中。请对下列各小题列出最优化模型表达式。请对下列各小题列出最优化模型表达式。(1)(1)假假定定在在第第i i周周内内可可供供使使用用的的最最大大劳劳动动量量为为L Li i单单位位。请请列列出出一一个个可可行行的的速速度度计计划划(即即确确定定每每台台设设备备从从哪哪一周开始维修一周开始维修)。第五章习题解答第五章习题解答运筹学教程运筹学教程 School of ManagementSchool of Managementpag

25、e page 29294/4/20234/4/2023第五章习题解答第五章习题解答表表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运筹学教程运筹学教程 School of ManagementSchool of Managementpage page 30304/4/20234/4/2023第五章习题解答第五章习题解答运筹学教程运筹学教程 School

26、of ManagementSchool of Managementpage page 31314/4/20234/4/2023第五章习题解答第五章习题解答 (2)(2)假假定定该该公公司司要要求求每每周周使使用用的的劳劳动动量量波波动动幅幅度度之之和和为为最最小小。例例如如，若若每每台台设设备备都都尽尽可可能能的的早早开开始始维维修修，则则每每周周所所需需的的劳劳动动量量为为7 7、1616、2020、1616、2 2、0 0、0 0、0 0，结结果果，周周与与周周之之间间的的波波动动幅幅度度之之和和为为(16-7)+(20-16)+(20-(16-7)+(20-16)+(20-16)+(16

27、-2)+(2-0)+(0-0)+(0-0)16)+(16-2)+(2-0)+(0-0)+(0-0)3333。解：增加目标函数解：增加目标函数 min Z=min Z=|w|wi+1i+1-w wi i|运筹学教程运筹学教程 School of ManagementSchool of Managementpage page 32324/4/20234/4/2023 (3)(3)假假设设该该公公司司要要求求在在八八周周内内的的任任何何一一周周所所需需的的最最大劳动量为最小。大劳动量为最小。解：增加解：增加 min Z=w,w min Z=w,w w wi i,i,i=1,2,3,4,5,6,7,8

28、=1,2,3,4,5,6,7,8 (4)(4)假假设设该该公公司司要要求求将将最最大大的的每每周周劳劳动动量量波波动动幅幅度度减减至至最最小小。(如如果果每每台台设设备备都都尽尽可可能能早早的的开开始始维维修修，则则在第四周至第五周之间的最大波动幅度为在第四周至第五周之间的最大波动幅度为16-216-21414。)解：增加解：增加 min Z=w,w|wmin Z=w,w|wi+1i+1-w-wi i|,i=1,2,|,i=1,2,7 7 (5)(5)如如果果设设备备3 3不不能能在在设设备备1 1开开始始维维修修前前开开工工，试试说说明应如何修改明应如何修改(1)(1)的答案。的答案。解：增

29、加解：增加 p11+p12p32;p11+p12+p13p33;第五章习题解答第五章习题解答运筹学教程运筹学教程 School of ManagementSchool of Managementpage page 33334/4/20234/4/2023如如果果设设备备4 4必必须须与与设设备备3 3同同时时开开始始维维修修(因因此此，设设备备4 4的最晚开工时间是在第五周而不是第六周的最晚开工时间是在第五周而不是第六周)。解：增加解：增加p p3i3i=p=p4i4ii=2,3,4,5i=2,3,4,5 如果设备如果设备4 4与设备与设备5 5不能在同一周内开始维修。不能在同一周内开始维修。解：增加解：增加 p p4i4i*p*p5i5i=0 i=2,3,4=0 i=2,3,4 如如果果设设备备5 5必必须须在在设设备备1 1维维修修完完工工后后才才能能开开始始维维修修(即即若若设设备备1 1在在第第一一周周开开始始维维修修，则则设设备备5 5不不得得早早于于第第四四周开始维修周开始维修)。则又应如何修改。则又应如何修改(1)(1)的答案。的答案。第五章习题解答第五章习题解答