第五章习题解答
5.12 现有P个约束条件
a
j 1
n
ij ij
x bi
i 1,2,, p
需要从中选择q个约束条件，试借助0-1变量列出 表达式。
解：设yi是0 1变量, i 1,2, , p yi ( aij xij bi ) 0
j 1 n
i 1,2, , p
第五章习题解答
解：设xi 1表示携带第i件物品，i 1,2, , m。 max Z ci xi
i 1 m
m ai xi a i 1 m bi xi b i 1 xi是0 1变量 i 1,2, m
第五章习题解答
5.6 用割平面法解下列整数规划：
i 1 n
n d i xi D, i 1 x 是整数 i
xi ai
i 1,2, , n
第五章习题解答
5.2 要在长度为l的一根圆钢上截取不同长度的零 件毛坯，毛坯长度有n种，分别为aj，(j=1，2，…,n)。 问每种毛坯应当各截取多少根，才能使圆钢残料最少， 试建立本问题的数学模型。
第五章习题解答
5.5 一个旅行者要在其背包里装一些最有用的旅行 物品。背包容积为a，携带物品总重量最多为b。现有 物品m件，第i件物品体积为ai ，重量为bi(i＝1，2，…， m)。为了比较物品的有用程度，假设第j件物品的价值 为ci(i＝1，2，…，m)。若每件物品只能整件携带，每 件物品都能放人背包中，并且不考虑物品放人背包后 相互的间隙。问旅行者应当携带哪几件物品，才能使 携带物品的总价值最大，要求建立本问题的数学模型。
0.2
0
1.4
1.1
第五章习题解答
解：最大元素是 ，用它减去所有元素， 1.4 0.1 0.6 1.4 0.2 0 得到矩阵： .4 1.4 1.4 0.35 0.4 0.5 1 0 最优解是： 0 0 0 1 .4 1 . 4 0 .1 0 .1 1 .4 0 . 2 1 .4 1 . 2 0 .8 1 . 4 0 .4 1 .4 1.4 ， 0 0 .3
第五章习题解答
表5-11-12-13 产品A 成本 产品B 成本 产品C 成本 产量（件）（元/件） 产量（件） （元/件） 产量（件） （元/件） 0~40 41~100 10 9 0~50 51~100 6 4 0~100 100以上 5 4
101~150
150以上
8
7
100以上
3
解：设x1,x2,x3分别表示三个产品的产量。 Y11,y12,y13,y14对应产品A的4个成本的0-1变量； Y21,y22,y23对应产品B的3个成本的0-1变量； Y31,y32对应产品B的3个成本的0-1变量；
第五章习题解答
5.1 某地准备投资D元建民用住宅。可以建住宅的 地点有n处：A1，A2，…，An。在Ai处每幢住宅的造价 为dj；，最多可造aj幢。问应当在哪几处建住宅，分别 建几幢，才能使建造的住宅总数最多，试建立问题的 数学模型。
解：设xi 表示在Ai处所建住宅的数量 i 1,2, , n。 , max Z xi
第五章习题解答
5.10 有五项设计任务可供选择。各项设计任务的 预期完成时间分别为3，8，5，4，10(周)，设计报酬分 别为7，17，11，9，21(万元)。设计任务只能一项一项 地进行，总的期限是20周。选择任务时必须满足下面要 求： 1．至少完成3项设计任务； 2．若选择任务1，必须同时选择任务2； 3．任务3和任务4不能同时选择。 应当选择哪些设计任务，才能使总的设计报酬最大?
第五章习题解答
5.9 解下列0-1型整数规划：
max Z 2 x1 x2 x3 min Z 5 x1 7 x2 10x3 3x4 x5 x1 3 x2 x3 2 x1 3x2 5 x3 x4 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 x2 x3 2 st . x 4x x 4 2 x2 2 x3 x4 x5 1 2 3 1 x1 , x2 , x3 , x4 , x5 0或1 x1 , x2 , x3 0或1 解：此题无解。 解：x1 1, x2 x3 x4 0, Z 2
第五章习题解答
5.11 某城市可划分为11个防火区，已设有4个消防 站，见下图所示。
第五章习题解答
上图中，虚线表示该消防站可以在消防允许时间 内到达该地区进行有效的消防灭火。问能否关闭若干 消防站，但仍不影响任何一个防火区的消防救灾工作。 (提示：对每—个消防站建立一个表示是否将关闭的01变量。)
解：设xi 表示各种毛坯使用圆钢 的数量, i 1,2,, n。 yi 表示各种毛坯在一根圆 钢上可得到的数量。 min Z xi
i 1 n
ai yi l , i 1,2,, n yi xi mi , i 1,2,, n x , y 0, 且都是整数， 1,2,, n i i i
第五章习题解答
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变量。）
(1)
0 1 解： 0 0
1
0 0 1 0
0 0 0 0
0 0 0 1
1 0 , Z 22 0 0
( 2)
0 0 1 解： 0 0 0
0 1 0 0 0 0 0 0 0 0 0
0 0 0 ,Z 8 0 0 1
max Z x1 x2 2 x1 x2 6 st . 4 x1 5 x2 20 x , x 0, 且为整数 1 2
min Z 5 x1 x2 3 x1 x2 9 x x 5 ( 2) 2 st 1 . x1 8 x2 8 x1 , x2 0, 且为整数 解：x1 4, x2 1, Z 5
出场阵容应满足以下条件： (1) 只能有一名中锋上场； (2) 至少有—名后卫； (3) 如1号和4号均—上场，则6号不出场；
第五章习题解答
(4) 2号和8号至少有一个不出场。 问应当选择哪5名队员上场，才能使出场队员 平均身高最高，试建立数学模型。
解：设xi 1表示第i个队员出场， 1,2, , n。 i 1 8 max Z xi 5 i 1 8 xi 5 i 1 x x 1 x x x 1 2 6 7 8 1 x x 1 x x x 2 8 1 4 6 2 xi是0 1变量
第五章习题解答
5.4 篮球队需要选择5名队员组成出场阵容参加比 赛。8名队员的身高及擅长位置见表5-10。
表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)
解：x1 1, x2 3, Z 4
第五章习题解答
5.7 用分支定界法解下列整数规划：
max Z 2 x1 x2 x1 x2 5 x x 0 (1) 2 st 1 . 6 x1 2 x2 21 x1 , x2 0, 且为整数 解：x1 3, x2 1, Z 7 min Z 5 x1 x2 2 x3 3 x1 10x2 50 7 x 2 x 28 ( 2) 2 st 1 . x1 , x2 0 x2为整数 解：x1 0, x2 5, x3 0, Z 5
解：设xi 1表示第i个消防站保留， 1,2,3， i 4。 max Z x1 x2 x3 x4 x1 x2 1 x1 1 x1 x2 x3 1 x3 1 x1 x4 1 x1 x2 x4 1 x x 1 x 1 4 4 2 xi是0 - 1变量, i 1,2,3,4 显然，可以关闭 号消防站。 2
y
i 1
p
i
q
第五章习题解答
5.13 解下列系数矩阵的最小化问题：
10 11 4 2 8 7 11 10 14 12 5 6 9 12 14 13 15 11 10 7
3 7 3 6 5 5 6 1 8 4 2 7 2 4 5 3 4 6 6 4 8 7 3 2
第五章习题解答
解：设xi 1表示第i项任务被选中， 1,2,,5。 i max Z 7 x1 17x2 11x3 9 x4 21x5 3x1 8 x2 5 x3 4 x4 10x5 20 x1 x2 x3 x4 x5 3 x1 x2 x x 1 4 3 xi是0 - 1变量, i 1,2,3,4,5
第五章习题解答
5.14 需要分派5人去做5项工作，每人做各项工 作的能力评分见表5-14。应如何分派，才能使总的得 分最大?
表5-14 业务 人员 B1 B2 B3 B4 B5
A1
A2 A3
1.3
0 1.0
0.8
1.2 0
0
1.3 0
0
1.3 1.2