运筹学教程 第五章习题解答 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变量。） 第五章习题解答