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

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

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

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

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

答案：
设原矩阵为A ，因求极大问题，令B=[M-a ij ]，其中M=Max {a ij }=10，则：
16425105
3140
42
13251042510424003B 1
3752102
6410
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,=++≤⎧⎪
-≤⎨⎪≥⎩整数 解得其松弛问题最优表如下：
答案：
(1) 产生高莫雷约束：
根据Max {f i }，应选取x 1所在行为源行：134133
x x x 3884
+
+=，即，134133x 0x 0x 3884⎛⎫⎛⎫
++++=+ ⎪ ⎪⎝⎭⎝⎭
产生高莫雷约束为：34313
x x 0488
--≤。

(2) 将高莫雷约束加入松弛变量x 5，写入原表最后一行形成下表并用对偶单纯形法求解：
b j。