整数规划割平面法
太阳花图片-人与狗
割平面法
求解整数规划问题：
Max
Z=3x
1
+2x
2
2x
1
+3x
2
14
4x
1
+2x
2
18
x
1
,x
2
0，且为整数
解：首先，将原问题的数学模
型标准化，这里标
准化有两层含义：（1）将不等式转化为等式约
束，（2）将整数规划中所有
非整数系数全部转
化为整数，以便于构造切割平面。从而有：
Max
Z=3x
1
+2x
2
2x
1
+3x
2
+x
3
=14
2x
1
+x
2
+x
4
=9
x
1
,x
2
0，且为整数
利用单纯形法求解，得到最优单纯形表，见表1：
表1
C
B
X
B
b 3 2 0 0
X
1
X
2
X
3
X
4
2 X
2
52 0 1 12
-12
3 X
1
134 1 0 -14 34
j
594 0 0 14 54
最优解为：x
1
=134,
x
2
=52, Z=594
根据上表，写出非整数规划的约束方程，如：
x
2
+12x
3
-12x
4
=52 (1)
将该方程中所有变量的系数及右端常数项均改
写成“整数与非负真分数之和”的形式，即： <
br>(1+0)x
2
+(0+12)x
3
+(-1+12)x
4<
br>=2+12
把整数及带有整数系数的变量移到方程左边，分
数及带有分数系数的变量称到方程右边，得：
x
2
- x
4
-2
=12-(12x
3
+12x
4
) (2)
由于原数学模型已
经“标准化”，因此，在整数
最优解中，x
2
和x
4
也必须取整数值
，所以(2)式左
端必为整数或零，因而其右端也必须是整数。又
因为x
3
,
x
4
0，所以必有：
12-(12x
3
+12x
4
)<1
由于(2)式右端必为整数，于是有：
12-(12x
3
+12x
4
)0 (3)
或
x
3
+x
4
1 (4)
这就是考虑整数约
束的一个割平面约束方程，它
是用非基变量表示的，如果用基变量来表示割平
面约束方程，则有
：
2x
1
+2x
2
11 (5)
<
br>从图1中可以看出，(5)式所表示的割平面约束仅
割去线性规划可行域中不包含整数可行解的部
分区域，使点E(3.5，2)成为可行域的一个极点。
图1
在(3)式中加入松弛变量x
5
，得：
-12x
3
-12x
4
+x
5
=-12
(6)
将(6)式增添到问题的约束条件中，得到新的整数
规划问题：
Max
Z=3x
1
+2x
2
2x
1
+3x
2
+x
3
=14
2x
1
+x
2
+x
4
=9
-12x
3
-12x
4
+x
5
=-12
x
i
0，且为整数，i=1,2,…,5
该问题的求解可以在表1中加
入(6)式，然后运用
对偶单纯形法求出最优解。具体计算过程见表2：
表2
C
B
X
B
b 3 2 0 0 0
X
1
X
2
X
3
X
4
X
5
2 X
2
52 0 1 12 -12 0
3
X
1
134 1 0 -14 34 0
0 X
5
-12 0
0 [-12] -12 1
j
594 0 0 14 54 0
2 X
2
2 0 1 0 -1 1
3
X
1
72 1 0 0 1 -12
0 X
3
1 0 0 1
1 -2
j
584 0 0 0 1 12
由此得最优解为：x
1
=72, x
2
=2, z=584
该最优解仍不满足整数约束条件，因而需进行第
二次切割。为此，从表2中抄下非整数解x
1
的约
束方程为：
x
1
+x
4
-12x
5
= 72
按整数、分数归并原则写成：
x
1
+x
4
-x
5
-3 =
12-12x
5
0 (7)
这就是一个新的割平面方程，用基变量来表示，
得：
x
1
+x
2
5 (8)
在(7)中加入松弛变量x
6
，得：
-12x
5
+x
6
=-12 (9)
将(9
)式增添到前一个问题的约束条件中去，得到
又一个新的整数规划问题，对它求解可以在表2
中
加入(7)式，然后运用对偶单纯形法求出最优
解。具体计算过程见表3：
表3
C
B
X
B
b 3 2 0 0 0 0
X
1
X
2
X
3
X
4
X
5
X
6
2 X
2
2 0 1 0 -1 1 0
3 X
1
72 1 0 0 1 -12 0
0 X
5
1 0 0 1 1 -2 0
0 X
6
-12 0 0 0 0 [-12] 1
j
584 0 0 0 1 12
0
2 X
2
1 0 1 0 -1 0 2
3 X
1
4 1 0 0 1 0 -1
0 X
3
3 0 0 1 1 0 -4
0 X
5
1 0 0 0 0 1 -2
j
14
0 0 0 1 0 1
由此得最优解为：x
1
=4,
x
2
=1,z=14。该最优解符合
整数条件，因此也是原整数规划问题的最优解。
从图1中可以看出，由(8)式表示的割平面约
束，不仅割去线性规划可行域中剩下的不含整数
解域，而且使最优整数解x
1
=4,
x
2
=1（即图2中
的G点），成为新的线性规划可行域的一个极点。
图2