安徽大学：《运筹学》课程习题详解（PPT讲稿）第五章 整数规划

运筹学教程 第五章习题解答 5.1某地准备投资D元建民用住宅。可以建住宅 的地点有n处：A1,A2, A。在A处每幢住宅的 造价为d；，最多可造a,幢。问应当在哪几处建住宅， 分别建几幢，才能使建造的住宅总数最多，试建立问 题的数学模型。 解：设x,表示在A处所建住宅的数量，i=1,2,.,n。 maxZ=∑x i=1 2dx≤D,xsai=l2,n x,是整数 page 2 23 April 2025 School of Management

运筹学教程 School of Management page 2 23 April 2025 第五章习题解答 5.1 某地准备投资D元建民用住宅。可以建住宅 的地点有n处：A1，A2，.，An。在Ai处每幢住宅的 造价为dj；，最多可造aj幢。问应当在哪几处建住宅， 分别建几幢，才能使建造的住宅总数最多，试建立问 题的数学模型。        = = =   = = 是整数 解：设 表示在 处所建住宅的数量 。 i n i i i i i n i i i i x d x D x a i n Z x x A i n , 1,2, , max , 1,2, , 1 1  

运筹学教程 第五章习题解答 5.2要在长度为的一根圆钢上截取不同长度的零 件毛坯，毛坯长度有n种，分别为a,(j=1,2,n)。 问每种毛坯应当各截取多少根，才能使圆钢残料最少， 试建立本问题的数学模型 解：设x,表示各种毛坯的数量，i=1,2,.,n。 maxZ=∑a,x 会 ,x,≤1 x,是整数 page 3 23 April 2025 School of Management

运筹学教程 School of Management page 3 23 April 2025 5.2 要在长度为l的一根圆钢上截取不同长度的零 件毛坯，毛坯长度有n种，分别为aj，(j=1，2，.,n)。 问每种毛坯应当各截取多少根，才能使圆钢残料最少， 试建立本问题的数学模型。 第五章习题解答       = =   = = 是整数 解：设 表示各种毛坯的数量 。 i n i i i n i i i i x a x l Z a x x i n 1 1 max , 1,2,

运筹学教程 第五章习题解答 5.3有一批每根长度为的圆钢，需要截取n种不 同长度的零件毛坯。长度为a,的毛坯必须有m段=1， 2,)。为了方便，每根圆钢只截取一种长度的 毛坯。应当怎样截取，才能使动用的圆钢数目最少， 要求建立数学模型。 解：设x,表示各种毛坯使用圆钢的数量，i=1,2,.,n。 y,表示各种毛坯在一根圆钢上可得到的数量。 mmZ=∑x i=l ay,≤1，i=1,2,.,n y,x,≥m,i=1,2,.,n x,y,≥0，且都是整数，i=1,2,.,n page 4 23 April 2025 School of Management

运筹学教程 School of Management page 4 23 April 2025 第五章习题解答 5.3 有一批每根长度为l的圆钢，需要截取n种不 同长度的零件毛坯。长度为aj的毛坯必须有mj段(j＝1， 2，.，n)。为了方便，每根圆钢只截取一种长度的 毛坯。应当怎样截取，才能使动用的圆钢数目最少， 要求建立数学模型。       =  =  = = = = x y i n y x m i n a y l i n Z x y x i n i i i i i i i n i i i i , 0, 1,2, , , 1,2, , , 1,2, , min , 1,2, , 1     且都是整数， 表示各种毛坯在一根圆钢上可得到的数量。 解：设 表示各种毛坯使用圆钢的数量

运筹学教程 第五章习题解答 5.4篮球队需要选择5名队员组成出场阵容参加 比赛。8名队员的身高及擅长位置见表5-10。 表5-10 队员 1 2 5 6 7 8 身高(m 1.92 1.90 1.88 1.86 1.85 1.83 1.80 1.78 擅长位置 中锋 中锋 前锋 前锋 前锋 后卫 后卫 后卫 出场阵容应满足以下条件： (1)只能有一名中锋上场： (2)至少有一名后卫； (3)如1号和4号均一上场，则6号不出场； page 5 23 April 2025 School of Management

运筹学教程 School of Management page 5 23 April 2025 5.4 篮球队需要选择5名队员组成出场阵容参加 比赛。8名队员的身高及擅长位置见表5-10。 第五章习题解答 表5-10 队员 1 2 3 4 5 6 7 8 身高(m) 1.92 1.90 1.88 1.86 1.85 1.83 1.80 1.78 擅长位置 中锋 中锋 前锋 前锋 前锋 后卫 后卫 后卫 出场阵容应满足以下条件： (1) 只能有一名中锋上场； (2) 至少有—名后卫； (3) 如1号和4号均—上场，则6号不出场；

运筹学教程 第五章习题解答 (4)2号和8号至少有一个不出场。 问应当选择哪5名队员上场，才能使出场队员 平均身高最高，试建立数学模型。 解：设x=1表示第i个队员出场，i=1,2,.,n。 max 2- 8 x=5 i=1 x1+x2≤1x6+x7+xg≥1 x2+xg≤1X1+x4+x6≤2 x,是0-1变量 page 6 23 April 2025 School of Management

运筹学教程 School of Management page 6 23 April 2025 (4) 2号和8号至少有一个不出场。 问应当选择哪5名队员上场，才能使出场队员 平均身高最高，试建立数学模型。 第五章习题解答          − +  + +  +  + +  = = = =   = = 是 变量 解：设 表示第 个队员出场， 。 0 1 1 2 1 1 5 5 1 max 1 1,2, , 2 8 1 4 6 1 2 6 7 8 8 1 8 1 i i i i i i x x x x x x x x x x x x Z x x i i  n

运筹学教程 第五章习题解答 5.5 一个旅行者要在其背包里装一些最有用的旅 行物品。背包容积为a,携带物品总重量最多为b。现 有物品m件，第i件物品体积为a,重量为b(i=1, 2,.,m)。为了比较物品的有用程度，假设第j件物 品的价值为ci=1,2,m)。若每件物品只能整件 携带，每件物品都能放人背包中，并且不考虑物品放 人背包后相互的间隙。问旅行者应当携带哪几件物品 才能使携带物品的总价值最大，要求建立本问题的数 学模型。 page 7 23 April 2025 School of Management

运筹学教程 School of Management page 7 23 April 2025 5.5 一个旅行者要在其背包里装一些最有用的旅 行物品。背包容积为a，携带物品总重量最多为b。现 有物品m件，第i件物品体积为ai，重量为bi (i＝1， 2，.，m)。为了比较物品的有用程度，假设第j件物 品的价值为ci (i＝1，2，.，m)。若每件物品只能整件 携带，每件物品都能放人背包中，并且不考虑物品放 人背包后相互的间隙。问旅行者应当携带哪几件物品， 才能使携带物品的总价值最大，要求建立本问题的数 学模型。 第五章习题解答

运筹学教程 第五章习题解答 解：设x,=1表示携带第i件物品，i=1,2,.,m。 maxZ=∑c,x i- 2 ,x,≤a i= b,x,≤b i=1 x,是0-1变量 i=1,2,.m page 8 23 April 2025 School of Management

运筹学教程 School of Management page 8 23 April 2025 第五章习题解答          = −   = = =    = = = i m x b x b a x a Z c x x i i m i m i i i m i i i m i i i i   1,2, 0 1 max 1 1,2, , 1 1 1 是 变量 解：设 表示携带第 件物品，

运筹学教程 第五章习题解答 5.6用割平面法解下列整数规划： min Z=5x+x2 max Z=x+x2 3x1+x2≥9 2x1+x2≤6 st. 4x1+5x2≤20 (2) x1+x2≥5 st x,x2≥0，且为整数 x1+8x2≥8 x1,x2≥0，且为整数 解：x1=1,x2=3,Z=4 解：x1=4,x2=1,Z=5 page 9 23 April 2025 School of Management

运筹学教程 School of Management page 9 23 April 2025 5.6 用割平面法解下列整数规划： 第五章习题解答 1, 3, 4 , 0, 4 5 20 2 6 . max (1) 1 2 1 2 1 2 1 2 1 2 = = =       +  +  = + x x Z x x x x x x st Z x x 解： 且为整数 4, 1, 5 . , 0, 8 8 5 3 9 min 5 (2) 1 2 1 2 1 2 1 2 1 2 1 2 = = =         +  +  +  = + x x Z x x x x x x x x st Z x x 解： 且为整数

运筹学教程 第五章习题解答 5.7用分支定界法解下列整数规划： max Z=2x+2 min Z=5x-x2+2x3 x1+x2≤5 3x,+10x2≤50 (1) -x1+x2≤0 (2) 7x1-2x2≤28 st st 6x1+2x2≤21 1,x2≥0 x1,x2≥0，且为整数 x2为整数 解：x1=3,x2=1,Z=7 解：x1=0,x2=5,x3=0,Z=-5 page 10 23 April 2025 School of Management

运筹学教程 School of Management page 10 23 April 2025 5.7 用分支定界法解下列整数规划： 第五章习题解答 3, 1, 7 . , 0, 6 2 21 0 5 max 2 (1) 1 2 1 2 1 2 1 2 1 2 1 2 = = =         +  − +  +  = + x x Z x x x x x x x x st Z x x 解： 且为整数 0, 5, 0, 5 . , 0 7 2 28 3 10 50 min 5 2 (2) 1 2 3 2 1 2 1 2 1 2 1 2 3 = = = = −         −  +  = − + x x x Z x x x x x x x st Z x x x 解： 为整数

运筹学教程 第五章习题解答 5.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变量。 page 11 23 April 2025 School of Management

运筹学教程 School of Management page 11 23 April 2025 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变量。） 第五章习题解答