第五章-整数规划练习题答案教程文件.doc

第五章 整数规划练习题答案

精品资料
第五章 整数规划练习题答案
一. 判断下列说法是否正确
1. 用分枝定界法求解一个极大化的整数规划问题时，任何一个可行整数解的目标函数值是该问题目标函数值的下界。(P)
2. 用割平面法求解整数规划时，构造的割平面有可能切去一些不属于最优解的整数解。(O)
3. 用割平面法求解纯整数规划时，要求包括松弛变量在内的全部变量必须取整数值。(P)
4. 指派问题数学模型的形式与运输问题十分相似，故也可以用表上作业法求解。(P)
二. 设有五项工作要分派给五个工人，每人的作业产值如下表所示，为了使总产值最大，问应如何分配这五项工作，并求得最大产值。
工作
工人
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-aij]，其中M=Max{aij}=10，则：

m=5=n，得最优解。解矩阵。
即，甲®D，乙®C，丙®E，丁®B，戊®A，最大产值=10+8+9+8+8=43。
三. 对整数规划

解得其松弛问题最优表如下：
cj
8
5
0
0
θ
CB
XB
b
x1
x2
x3
x4
5
x2
3/2
0
1
1/4
-1/4

8
x1
15/4
1
0
1/8
3/8

σj
75/2
0
0
-9/4
-7/4

要求：用割平面法完成求解过程。
答案：
(1) 产生高莫雷约束：
根据Max{fi}，应选取x1所在行为源行：，即，
产生高莫雷约束为：。
(2) 将高莫雷约束加入松弛变量x5，写入原表最后一行形成下表并用对偶单纯形法求解：
cj
8
5
0
0
0
θ
CB
XB
b
x1
x2
x3
x4
x5
5
x2
3/2
0
1
1/4
-1/4
0

8
x1
15/4
1
0
1/8
3/8
0

0
x5
-3/4
0
0
-1/8
-3/8
1
→
σj
75/2
0
0
-9/4
-7/4↑
0

cj
8
5
0
0
0
θ
CB
XB
b
x1
x2
x3
x4
x5
5
x2
2
0
1
1/3
0
-2/3

8
x1
3
1
0
0
0
1

0
x4
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。
仅供学习与交流，如有侵权请联系网站删除 谢谢3