运筹学习题答案(第五章)

运筹学教程（第二版）习题解答电话：5108157(H)，5107443(O)E-mail:[e-mail]安徽大学管理学院洪文运筹学教程SchoolofManagementpage225February2020第五章习题解答5.1某地准备投资D元建民用住宅。可以建住宅的地点有n处：A1，A2，…，An。在Ai处每幢住宅的造价为dj；，最多可造aj幢。问应当在哪几处建住宅，分别建几幢，才能使建造的住宅总数最多，试建立问题的数学模型。是整数。处所建住宅的数量表示在解：设iniiiiiniiiixniaxDxdxZniAx,,2,1,max,,2,1,11运筹学教程SchoolofManagementpage325February20205.2要在长度为l的一根圆钢上截取不同长度的零件毛坯，毛坯长度有n种，分别为aj，(j=1，2，…,n)。问每种毛坯应当各截取多少根，才能使圆钢残料最少，试建立本问题的数学模型。第五章习题解答是整数。表示各种毛坯的数量解：设iniiiniiiixlxaxaZnix11max,,2,1,运筹学教程SchoolofManagementpage425February2020第五章习题解答5.3有一批每根长度为l的圆钢，需要截取n种不同长度的零件毛坯。长度为aj的毛坯必须有mj段(j＝1，2，…，n)。为了方便，每根圆钢只截取一种长度的毛坯。应当怎样截取，才能使动用的圆钢数目最少，要求建立数学模型。niyxnimxynilyaxZynixiiiiiiiniiii,,2,1,0,,,2,1,,,2,1,min,,2,1,1且都是整数，钢上可得到的数量。表示各种毛坯在一根圆。的数量表示各种毛坯使用圆钢解：设运筹学教程SchoolofManagementpage525February20205.4篮球队需要选择5名队员组成出场阵容参加比赛。8名队员的身高及擅长位置见表5-10。第五章习题解答表5-10队员12345678身高(m)1.921.901.881.861.851.831.801.78擅长位置中锋中锋前锋前锋前锋后卫后卫后卫出场阵容应满足以下条件：(1)只能有一名中锋上场；(2)至少有—名后卫；(3)如1号和4号均—上场，则6号不出场；运筹学教程SchoolofManagementpage625February2020(4)2号和8号至少有一个不出场。问应当选择哪5名队员上场，才能使出场队员平均身高最高，试建立数学模型。第五章习题解答变量是。个队员出场，表示第解：设102111551max,,2,1164182876218181iiiiiixxxxxxxxxxxxxZniix运筹学教程SchoolofManagementpage725February20205.5一个旅行者要在其背包里装一些最有用的旅行物品。背包容积为a，携带物品总重量最多为b。现有物品m件，第i件物品体积为ai，重量为bi(i＝1，2，…，m)。为了比较物品的有用程度，假设第j件物品的价值为ci(i＝1，2，…，m)。若每件物品只能整件携带，每件物品都能放人背包中，并且不考虑物品放人背包后相互的间隙。问旅行者应当携带哪几件物品，才能使携带物品的总价值最大，要求建立本问题的数学模型。第五章习题解答运筹学教程SchoolofManagementpage825February2020第五章习题解答mixbxbaxaxcZmiiximiiimiiimiiii,2,110max,,2,11111变量是。件物品，表示携带第解：设运筹学教程SchoolofManagementpage925February20205.6用割平面法解下列整数规划：第五章习题解答4,3,1,0,205462.max)1(2121212121ZxxxxxxxxstxxZ解：且为整数5,1,4.,0,885935min)2(212121212121ZxxxxxxxxxxstxxZ解：且为整数运筹学教程SchoolofManagementpage1025February20205.7用分支定界法解下列整数规划：第五章习题解答7,1,3.,0,2126052max)1(212121212121ZxxxxxxxxxxstxxZ解：且为整数5,0,5,0.0,28275010325min)2(3212212121321ZxxxxxxxxxxstxxxZ解：为整数运筹学教程SchoolofManagementpage1125February20205.8某公司生产A，B和C3种产品，售价分别为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变量。）第五章习题解答运筹学教程SchoolofManagementpage1225February2020第五章习题解答表5-11-12-13产品A产量（件）成本（元/件）产品B产量（件）成本（元/件）产品C产量（件）成本（元/件）0~40100~5060~100541~100951~1004100以上4101~1508100以上3150以上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变量；运筹学教程SchoolofManagementpage1325February2020第五章习题解答.10100101100501015115010040151101411,400231,70054101,1002)45()346()78910(6712max323133223222122322141312111141312323132123222132114131211321332312232221114131211321是任意大的数变量，是是整数变量，是：总利润最大的数学模型MyxMyyxyMyyyxyyMyyyyxyyyyyxxxyyyxxxyyyyxxxxyyxyyyxyyyyxxxZiji运筹学教程SchoolofManagementpage1425February20205.9解下列0-1型整数规划：第五章习题解答解：此题无解。或.10,,,,122022362245331075min)1(543215432543215432154321xxxxxxxxxxxxxxxxxxxstxxxxxZ2,0,110,,44225423.2max)2(432132132132132321321ZxxxxxxxxxxxxxxxxxxstxxxZ解：或运筹学教程SchoolofManagementpage1525February20205.10有五项设计任务可供选择。各项设计任务的预期完成时间分别为3，8，5，4，10(周)，设计报酬分别为7，17，11，9，21(万元)。设计任务只能一项一项地进行，总的期限是20周。选择任务时必须满足下面要求：1．至少完成3项设计任务；2．若选择任务1，必须同时选择任务2；3．任务3和任务4不能同时选择。应当选择哪些设计任务，才能使总的设计报酬最大?第五章习题解答运筹学教程SchoolofManagementpage1625February2020第五章习题解答5,4,3,2,1,1-0132010458321911177max5,,2,114321543215432154321ixxxxxxxxxxxxxxxxxxxxZiixii变量是。项任务被选中，表示第解：设运筹学教程SchoolofManagementpage1725February20205.11某城市可划分为11个防火区，已设有4个消防站，见下图所示。第五章习题解答运筹学教程SchoolofManagementpage1825February2020上图中，虚线表示该消防站可以在消防允许时间内到达该地区进行有效的消防灭火。问能否关闭若干消防站，但仍不影响任何一个防火区的消防救灾工作。(提示：对每—个消防站建立一个表示是否将关闭的0-1变量。)第五章习题解答号消防站。显然，可以关闭变量是。，个消防站保留，表示第解：设24,3,2,1,1-011111111max43,2,114424214133211214321ixxxxxxxxxxxxxxxxxxxxZiixii运筹学教程SchoolofManagementpage1925February20205.12现有P个约束条件第五章习题解答pibxanjiijij,,2,11需要从中选择q个约束条件，试借助0-1变量列出表达式。piinjiijijiiqypibxaypiy11,,2,10)(,,2,1,10变量是解：设运筹学教程SchoolofManagementpage2025February20205.13解下列系数矩阵的最小化问题：第五章习题解答71011151314129651214101178241110)1(22,01000000100000110000Z解：267534257346858344176263)2(8,100000000000000100100100Z解：运筹学教程SchoolofManagementpage2125February20205.14需要分派5人去做5项工作，每人做各项工作的能力评分见表5-14。应如何分派，才能使总的得分最大?第五章习题解答表5-14业务人员B1B2B3B4B5A11.30.8001.0A201.21.31.30A31.0001.20A401.0500.21.4A51.00.90.601.1运筹学教程SchoolofManagementpage2225February2020第五章习题解答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.4Z最优解是：，得到矩阵：，用它减去所有元素，解：最大元素是运筹学教程SchoolofManagementpage2325February20205.15考虑下列问题：式中)y≥0，且x的值只能等于0、1、4和6。(1)请用一个等价的整数规划模型来表达这个问题。第五章习题解答62252.73maxyxyxstyxZ