第五章 整数规划练习题答案
一. 判断下列说法是否正确
1. 用分枝定界法求解一个极大化的整数规划问题时，任何一个可行整数解的目标函数值是
该问题目标函数值的下界。

()
2. 用割平面法求解整数规划时，构造的割平面有可能切去一些不属于最优解的整数解。

()
3. 用割平面法求解纯整数规划时，要求包括松弛变量在内的全部变量必须取整数值。

()
4. 指派问题数学模型的形式与运输问题十分相似，故也可以用表上作业法求解。

() 二. 设有五项工作要分派给五个工人，每人的作业产值如下表所示，为了使总产值最大，问
应如何分配这五项工作，并求得最大产值。

工作 工人
A &
B
C D E 甲 9 4 6 8 5 \ 乙
8 5 9 10 6 丙 9 7 3 ' 5 8 丁 4 8 6 9 5 戊
10
； 5
3
6
3
答案：
设原矩阵为A ，因求极大问题，令B=[M-a ij ]，其中M=Max {a ij }=10，则：
16425105
3140
42
13251042510424003B 1
3752102
64
10
154062415151
3045
020305
7470574704646111-⎛⎫⎛⎫⎛⎫
⎪
⎪ ⎪
⎪ ⎪ ⎪ ⎪ ⎪ ⎪
=→→- ⎪
⎪ ⎪- ⎪ ⎪ ⎪ ⎪ ⎪ ⎪⎝⎭⎝⎭⎝⎭
---
m 4n 5l m 4
4
21342132432431541545235234
6
4
64
6
4
6=<===⎛
⎫⎛⎫ ⎪ ⎪∅∅ ⎪ ⎪ ⎪ ⎪→→−−−−→∅∅ ⎪ ⎪∅∅ ⎪ ⎪ ⎪ ⎪∅∅⎝
⎭
⎝
⎭
031023
4003115406020303535⎛⎫ ⎪
⎪ ⎪
⎪
⎪ ⎪⎝
⎭
31234311546233
5
3
5∅
⎛⎫ ⎪∅ ⎪ ⎪→ ⎪∅ ⎪ ⎪⎝
⎭ m=5=n ，得最优解。

解矩阵*0001000100X 0000101
00010000⎛⎫
⎪
⎪ ⎪= ⎪
⎪ ⎪⎝⎭。

即，甲D ，乙C ，丙E ，丁B ，戊A ，最大产值=10+8+9+8+8=43。

三. — 四. 对整数规划
12
121212
MaxZ 8x 5x 2x 3x 12
x x 6x ,x 0,=++≤⎧⎪
-≤⎨⎪≥⎩整数 解得其松弛问题最优表如下：
c j 8 5 0 0 θ C B 、 X B b x 1 x 2 x 3
x 4
5 x 2 3/2 ? 0 1 1/4 -1/4 8
x 1
15/4 1 0 :
1/8 3/8 σj
75/2
-9/4 -7/4
|
要求：用割平面法完成求解过程。

答案：
(1) 产生高莫雷约束：
根据Max {f i }，应选取x 1所在行为源行：134133x x x 3884+
+=，即，134133x 0x 0x 3884⎛⎫⎛⎫
++++=+ ⎪ ⎪⎝⎭⎝⎭
产生高莫雷约束为：34313
x x 0488
--≤。

(2) 将高莫雷约束加入松弛变量x 5，写入原表最后一行形成下表并用对偶单纯形法求解：
c j 8 5 0 $
0 θ C B X B b x 1 x 2 x 3 x 4 *
x 5
5 x 2 3/2 0 1 1/4 -1/4 0 ;
8 x 1 15/4 1 0 1/8 3/8 0 ；
x 5 -3/4 0 0 -1/8 -3/8 1 → σj `
75/2
0 0 -9/4 -7/4↑ 0
c j 8 —
5
0 0 0 θ C B X B b x 1 x 2 `
x 3
x 4 x 5 5 x 2 2 0 1 1/3 \
-2/3 8 x 1 3 1 0 0 0 —
1 0 x 4
2 0 0 1/
3 1 -8/3
σj
34 0 0 -5/3 0 -14/3
b列均为整数，所有σj均非负，已得最优整数解：X*=(3, 2)T，Z*=34。