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

运筹学教程
第五章习题解答
5.1 某地准备投资 元建民用住宅。可以建住宅 某地准备投资D元建民用住宅 元建民用住宅。 的地点有n处：A1，A2，…，An。在Ai处每幢住宅的 的地点有 处 ， 造价为d ；，最多可造 最多可造a 问应当在哪几处建住宅， 造价为 j；，最多可造 j幢。问应当在哪几处建住宅， 分别建几幢，才能使建造的住宅总数最多， 分别建几幢，才能使建造的住宅总数最多，试建立问 题的数学模型。 题的数学模型。
(1)
解： x1 = 1, x 2 = 3, Z = 4
min Z = 5 x1 + x 2 3 x1 + x 2 ≥ 9 x + x ≥ 5 ( 2) 2 . st 1 x1 + 8 x 2 ≥ 8 x1 , x 2 ≥ 0, 且为整数 解： x1 = 4, x 2 = 1, Z = 5
page 6 23 April 2012
School of Management
运筹学教程
第五章习题解答
(4) 2号和 号至少有一个不出场。 号和8号至少有一个不出场 号和 号至少有一个不出场。 问应当选择哪5名队员上场 名队员上场， 问应当选择哪 名队员上场 ， 才能使出场队员 平均身高最高，试建立数学模型。 平均身高最高，试建立数学模型。
运筹学教程
同样适合第三版黄皮版
page 1 23 April 2012
School of Management
运筹学教程（第二版） 运筹学教程（第二版） 习题解答
安徽大学管理学院
洪 文
电话： 电话：5108157(H)，5107443(O) ， E-mail: Hongwen9509_cn@sina.com
page 10 23 April 2012
School of Management
运筹学教程
第五章习题解答
5.7 用分支定界法解下列整数规划： 用分支定界法解下列整数规划：
max Z = 2 x1 + x 2 x1 + x 2 ≤ 5 − x + x ≤ 0 (1) 2 . st 1 6 x1 + 2 x 2 ≤ 21 x1 , x 2 ≥ 0, 且为整数 解： x1 = 3, x 2 = 1, Z = 7 min Z = 5 x1 − x 2 + 2 x3 3 x1 + 10 x 2 ≤ 50 7 x − 2 x ≤ 28 ( 2) 2 . st 1 x1 , x 2 ≥ 0 x 2为整数 解： x1 = 0, x 2 = 5, x3 = 0, Z = − 5
page 9 23 April 2012
School of Management
运筹学教程
第五章习题解答
5.6 用割平面法解下列整数规划： 用割平面法解下列整数规划：
max Z = x1 + x 2 2 x1 + x 2 ≤ 6 st . 4 x1 + 5 x 2 ≤ 20 x , x ≥ 0, 且为整数 1 2
解：设 xi 表示各种毛坯使用圆钢 的数量 , i = 1, 2, L , n 。 y i 表示各种毛坯在一根圆 钢上可得到的数量。 min Z = ∑ xi
i =1 n
a i y i ≤ l , i = 1, 2, L , n y i xi ≥ m i , i = 1, 2, L , n x , y ≥ 0, 且都是整数， i = 1, 2, L , n i i
page 7 23 April 2012
School of Management
运筹学教程
第五章习题解答
5.5 一个旅行者要在其背包里装一些最有用的旅 行物品。背包容积为a，携带物品总重量最多为b。现 行物品。 背包容积为 ， 携带物品总重量最多为 。 有物品m 物品体积为 积为a 量为b 有物品 件 ， 第 i 件 物品体 积为 i ， 重 量为 i(i ＝ 1， ， 2，…，m)。为了比较物品的有用程度，假设第j件物 ， ， 。 为了比较物品的有用程度， 假设第 件物 品的价值为c ＝ ， ， ， 。 品的价值为 i(i＝1，2，…，m)。若每件物品只能整件 携带，每件物品都能放人背包中， 携带 ， 每件物品都能放人背包中 ， 并且不考虑物品放 人背包后相互的间隙。问旅行者应当携带哪几件物品， 人背包后相互的间隙 。 问旅行者应当携带哪几件物品， 才能使携带物品的总价值最大， 才能使携带物品的总价值最大 ， 要求建立本问题的数 学模型。 学模型。
表5-10 队员 身高(m) 身高 擅长位置 1 1.92 2 1.90 3 1.88 4 1.86 5 1.85 6 1.83 7 1.80 8 1.78
中锋 中锋 前锋 源自文库锋 前锋 后卫 后卫 后卫
出场阵容应满足以下条件： 出场阵容应满足以下条件： (1) 只能有一名中锋上场； 只能有一名中锋上场； (2) 至少有—名后卫； 至少有—名后卫； (3) 如1号和 号均—上场，则6号不出场； 号和4号均 号不出场； 号和 号均—上场， 号不出场
解：设 xi = 1表示第 i个队员出场， i = 1, 2, L , n 。 1 8 max Z = ∑ xi 5 i =1 8 ∑ xi = 5 i =1 x + x ≤ 1 x + x + x ≥ 1 1 2 6 7 8 x + x ≤ 1 x + x + x ≤ 2 8 1 4 6 2 xi 是 0 − 1变量
page 13 23 April 2012
School of Management
运筹学教程
第五章习题解答
总利润最大的数学模型 是： max Z = 12 x1 + 7 x 2 + 6 x3 − (10 y11 + 9 y12 + 8 y13 + 7 y14 ) x1 − ( 6 y 21 + 4 y 22 + 3 y 23 ) x 2 − (5 y 31 + 4 y 32 ) x3 x1 + 2 x 2 + x3 ≤ 100 , y11 + y12 + y13 + y14 = 1 y 21 + y 22 + y 23 = 1 10 x1 + 4 x 2 + 5 x3 ≤ 700 , 3 x + 2 x + x ≤ 400 , y 31 + y 32 = 1 2 3 1 41 y12 + 101 y13 + 151 y14 ≤ x1 ≤ 40 y11 + 100 y12 + 150 y13 + My 14 51 y + 101 y ≤ x ≤ 50 y + 100 y + My 22 23 2 21 22 23 101 y 32 ≤ x3 ≤ 100 y 31 + My 32 xi 是整数变量， y ij 是 0 − 1变量， M 是任意大的数 .
page 5 23 April 2012
School of Management
运筹学教程
第五章习题解答
5.4 篮球队需要选择 名队员组成出场阵容参加 篮球队需要选择5名队员组成出场阵容参加 比赛。 名队员的身高及擅长位置见表 名队员的身高及擅长位置见表5-10。 比赛。8名队员的身高及擅长位置见表 。
page 12 23 April 2012
School of Management
运筹学教程
第五章习题解答
表5-11-12-13 11-12产品A 产品B 产品C 产品A 成本 产品B 成本 产品C 成本 产量（ 产量（ 产量（ 产量（件）（元/件） 产量（件） （元/件） 产量（件） （元/件） 0~100 100 0~40 40 0~50 50 10 6 5 41~100 41 100 101~150 101 150 150以上 150以上 9 8 7 51~100 51 100 100以上 100以上 4 3 100以上 100以上 4
解：设 xi 表示在 Ai 处所建住宅的数量 , i = 1, 2, L , n 。 max Z = ∑ xi
i =1 n
n ∑ d i xi ≤ D , i =1 x 是整数 i
page 3 23 April 2012
xi ≤ a i
i = 1, 2, L , n
School of Management
解：设 xi 表示各种毛坯的数量 , i = 1, 2, L , n 。 max Z = ∑ a i xi
i =1 n
n ∑ ai xi ≤ l i =1 x 是整数 i
page 4 23 April 2012
School of Management
运筹学教程
第五章习题解答
5.3 有一批每根长度为 的圆钢，需要截取 种不 有一批每根长度为l的圆钢 需要截取n种不 的圆钢， 同长度的零件毛坯。长度为a 的毛坯必须有m 同长度的零件毛坯。长度为 j的毛坯必须有 j段(j＝1， ＝ ， 2，…，n)。为了方便，每根圆钢只截取一种长度的 ， ， 。为了方便， 毛坯。应当怎样截取，才能使动用的圆钢数目最少， 毛坯。应当怎样截取，才能使动用的圆钢数目最少， 要求建立数学模型。 要求建立数学模型。
运筹学教程
第五章习题解答
5.2 要在长度为 的一根圆钢上截取不同长度的零 要在长度为l的一根圆钢上截取不同长度的零 件毛坯，毛坯长度有n种 分别为a 件毛坯，毛坯长度有 种，分别为 j，(j=1，2，…,n)。 ， ， 。 问每种毛坯应当各截取多少根，才能使圆钢残料最少， 问每种毛坯应当各截取多少根，才能使圆钢残料最少， 试建立本问题的数学模型。 试建立本问题的数学模型。
分别表示三个产品的产量。 解：设x1,x2,x3分别表示三个产品的产量。 Y11,y12,y13,y14对应产品A的4个成本的 变量； 对应产品 的 个成本的0-1变量； 个成本的 变量 Y21,y22,y23对应产品 的3个成本的 变量； 对应产品B的 个成本的 变量； 个成本的0-1变量 Y31,y32对应产品 的3个成本的 变量； 对应产品B的 个成本的 变量； 个成本的0-1变量
page 8 23 April 2012
School of Management
运筹学教程
第五章习题解答
解：设 xi = 1表示携带第 i件物品， i = 1, 2, L , m 。 max Z = ∑ ci xi
i =1 m
m ∑ a i xi ≤ a i =1 m ∑ bi xi ≤ b i =1 xi 是 0 − 1变量 i = 1, 2, L m
page 11 23 April 2012
School of Management
运筹学教程
第五章习题解答
5.8 某公司生产 ，B和C 3种产品，售价分别为 某公司生产A， 和 种产品 售价分别为12 种产品， 元和6元 生产每件A产品需要 技术服务、 产品需要1h技术服务 元、7元和 元。生产每件 产品需要 技术服务、10h 元和 直接劳动、 材料； 产品需要2h技术服务 直接劳动、3kg材料；生产每件 产品需要 技术服务、 材料 生产每件B产品需要 技术服务、 4h直接劳动、2kg材料；生产每件 产品需要 技术服 直接劳动、 材料； 产品需要1h技术服 直接劳动 材料 生产每件C产品需要 务、5h直接劳动、1k8材料。现在最多能提供100h技术 直接劳动、 材料。现在最多能提供 技术 直接劳动 材料 服务、 直接劳动、 材料。 服务、700h直接劳动、400kg材料。生产成本是生产量 直接劳动 材料 的非线性函数，如表5-11、表5-12、表5-13所示。要求 所示。 的非线性函数，如表 、 、 所示 建立一个总利润最大的生产计划的数学模型。提示： 建立一个总利润最大的生产计划的数学模型。提示： 对每种产品不同成本的产量范围各设一个0-1变量 变量。） 对每种产品不同成本的产量范围各设一个 变量。）
page 14 23 April 2012
School of Management
运筹学教程
第五章习题解答
5.9 解下列 型整数规划： 解下列0-1型整数规划： 型整数规划
max Z = 2 x1 + x 2 − x3 min Z = 5 x1 + 7 x 2 + 10 x3 + 3 x 4 + x5 x1 + 3 x 2 + x3 ≤ 2 x1 − 3 x 2 + 5 x3 + x 4 − 4 x5 ≥ 2 4x + x ≤ 5 2 3 − 2 x + 6 x − 3 x − 2 x + 2 x ≥ 0 ( 2) (1) 1 2 3 4 5 st . x1 + 2 x 2 − x3 ≤ 2 st . x + 4x − x ≤ 4 − 2 x 2 + 2 x 3 − x 4 − x5 ≥ 1 2 3 1 x1 , x 2 , x3 , x 4 , x5 = 0或1 x1 , x 2 , x3 = 0或1 解：此题无解。 解： x1 = 1, x 2 = x3 = x 4 = 0, Z = 2