第5章 整数线性规划-习题附1

北京林业大学运筹学课件

1 篮球队需要选择5名队员组成出场阵容参加比赛.参 赛的8名队员的身高及擅长位置见下表:队员 身高 擅长 位置 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号和4号均上场, 则6号不上场; 4) 2号和8号至少有一个不出场. 问:应当选择哪5名队员上场,才能使出场队员平均身高最高? 试建立数学模型.

北京林业大学运筹学课件

1 max Z = (1.92x1 +1.90x2 +1.88x3 +1.86x4 +1.85x5 +1.83x6 +1.80x7 +1.78x8) m z in 5 x1 +x2 +x3 +x4 +x5 +x6 +x7 +x8 =5 x1 +x2 =1 st.x6 +x7 +x8 ≥1 x +x +x ≤2 1 4 6 x2 +x8 ≤1 xi = 0或1 (i = 1, 2...,8)

北京林业大学运筹学课件

2 解下列系数矩阵的最小化指派问题10 11 4 2 8 7 11 10 14 12 5 6 9 12 14 13 15 11 10 7

(1)

北京林业大学运筹学课件

人少事多,添加虚拟的"人",对应系数矩阵为:10 11 4 2 8 7 11 10 14 12 5 6 9 12 14 13 15 11 10 7

10 11 4 2 8 7 11 10 14 12 5 6 9 12 14 13 15 11 10 7 0 0 0 0 0

下面按照标准形式,使用匈牙利法解之:

北京林业大学运筹学课件

第一步:分别从每行中减去最小元素,有10 11 4 2 8 2 7 11 10 14 12 7 5 6 9 12 14 5 13 15 11 10 7 7 0 0 0 0 0 0 8 0 0 6 0 9 4 1 8 0 2 3 4 4 0 0 7 7 3 0 6 5 9 0 0

第二步:再分别从每列中减去最小元素,有 8 9 2 0 6 8 9 2 0 4 3 7 5 0 4 3 0 1 4 7 9 0 1 4 6 8 4 3 0 6 8 4 0 0 0 0 0 0 0 0

0 7 7 3 0

0 0 0 0 0

6 5 9 0 0

北京林业大学运筹学课件

第三步:用最少的直线覆盖所有"0",得8 0 0 6 0 9 4 1 8 0 2 3 4 4 0 0 7 7 3 0 6 5 9 0 0

覆盖所有零最少需要4条直线,表明矩阵中最多存在 4个不同行不同列的零元素. 需要作变换

北京林业大学运筹学课件

第四步:变换系数矩阵8 0 0 6 0 9 4 1 8 0 2 3 4 4 0 0 7 7 3 0 6 5 9 0 0

-1 -1

+1

9 0 0 7 1

9 3 0 8 0

2 2 3 4 0

0 6 6 3 0

6 4 8 0 0

北京林业大学运筹学课件

第五步:用最少直线覆盖 9 9 2 0 0 3 2 6 0 0 3 6 7 8 4 3 1 0 0 0 9 0 0 7 1

6 4 8 0 0 6 4 8 0 0

即存在5个不同行不同列的独立零元素.圈09 3 0 8 0 2 2 3 4 0 0 6 6 3 0

北京林业大学运筹学课件

(2)

3 7 3 6 5 5

6 1 8 4 2 7

2 4 5 3 4 6

6 4 8 7 3 2

人多事少,添加虚拟的"事",对应系数矩阵为: 3 7 3 6 5 5 6 1 8 4 2 7 2 4 5 3 4 6 6 4 8 7 3 2 0 0 0 0 0 0 0 0 0 0 0 0

北京林业大学运筹学课件

第一步:分别从每行中减去最小元素,有3 7 3 6 5 5 3 7 3 6 5 5 6 1 8 4 2 7 6 1 8 4 2 7 2 4 5 3 4 6 2 4 5 3 4 6 6 4 8 7 3 2 6 4 8 7 3 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

北京林业大学运筹学课件

第二步:再分别从每列中减去最小元素,有3 7 3 6 5 5 6 1 8 4 2 7 2 4 5 3 4 6 6 4 8 7 3 2 0 0 0 0 0 0 0 0 0 0 0 0

3 1 2 2 0 0

0 4 0 3 2 2

5 0 7 3 1 6

0 2 3 1 2 4

4 2 6 5 1 0

0 0 0 0 0 0

0 0 0 0 0 0

北京林业大学运筹学课件

第三步:用最少的直线覆盖所有"0",得0 4 0 3 2 2 5 0 7 3 1 6 0 2 3 1 2 4 4 2 6 5 1 0 0 0 0 0 0 0 0 0 0 0 0 0

覆盖所有零最少需要6条直线,表明矩阵中存在6个 不同行不同列的零元素.容易看出这6个"0"的

位置.

北京林业大学运筹学课件

0 4 0 3 2 2 0 0 1 X * = 0 0 0

5 0 7 3 1 6 0 1 0 0 0 0

0 2 3 1 2 4 1 0 0 0 0 0

4 2 6 5 1 0 0 0 0 0 0 1

0 0 0 0 0 0 0 0 0 0 1 0

0 0 0 0 0 0 0 0 1 0

0

0

北京林业大学运筹学课件

3 需要分配 5 人去做5项工作,每人做各项工作的能 力评分见下表.应如何分派,才能使总的得分最大.业务 人员

B11.3 0 1.0 0 1.0

B20.8 1.2 0 1.05 0.9

B30 1.3 0 0 0.6

B40 1.3 1.2 0.2 0

B51.0 0 0 1.4 1.1

A1A2 A3 A4 A5

北京林业大学运筹学课件

最大化指派问题,应先转化为标准形式1.3 0 1.0 0 1.0 0.8 1.2 0 1.05 0.9 0 1.3 0 0 0.6 0 1.0 1.3 0 1.2 0 0.2 1.4 0 1.1

其中,最大元素m = 1.4, 令矩阵 B为:

B = (bij ) n×n = (m cij ) n×n

北京林业大学运筹学课件

0.1 0.6 1.4 0.2 B = 0.4 1.4 1.4 0.35 0.4 0.5

1.4 0.1 1.4 1.4 0.8

1.4 0.1 0.2 1.2 1.4

0.4 1.4 1.4 0 0.3

下面按照标准形式,使用匈牙利法解之:

北京林业大学运筹学课件

第一步:分别从每行中减去最小元素,有0.1 1.4 0.4 1.4 0.4 0.6 1.4 1.4 0.4 0.1 0.2 0.1 0.1 1.4 0.1 1.4 1.4 0.2 1.4 0.2 0.35 1.4 1.2 0 0 0.5 0.8 1.4 0.3 0.3 1.3 1.3 0.3 0 0 1.3 1.2 0 1.2 1.4 1.2 0 0.5 1.1 0

0 0.5 1.3 0.1 0.2 1.2 1.4 0.35 0.1 0.2

北京林业大学运筹学课件

第二步:再分别从每列中减去最小元素,有0 1.3 0.2 1.4 0.1 1.3 1.3 0.3 0 0 1.3 1.2 0 1.2 1.4 1.2 0 0.5 1.1 0 0 0.1 0 0 0 0.5 0.1 1.2 0.35 0.2 0 1.3 0.2 1.4 0.1 0.4 0 1.1 0.25 0.1 1.3 1.3 0.3 0 0 1.3 1.2 0 1.2 1.4 1.2 0 0.5 1.1 0

北京林业大学运筹学课件

第三步:用最少的直线覆盖所有"0",得0 1.3 0.2 1.4 0.1 0.4 0 1.1 0.25 0.1 1.3 1.3 0.3 0 0 1.3 1.2 0 1.2 1.4 1.2 0 0.5 1.1 0

这里直线数等于4(等于5时停止运算),要进行下 一轮计算.