我的离开也是爱歌词-数控专业

割平面法

求解整数规划问题：
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

2 X
2
52 0 1 12
3 X
1
134 1 0 -14
594 0 0 14

j

最优解为：x
1
=134, x
2
=52, Z=594
10
9
8
7
6
5
4
3
2
1
0
01234
2x1+3x2=14
2x1+x2=9
X
4

-12
34
54
A
B
C
56789

根据上表，写出非整数规划的约束方程，如：
x
2
+12x
3
-12x
4
=52 (1)
将该方程中所有变量的系数及右端常数项
均改写成“整数与非负真分数之和”的形式，
即：
(1+0)x
2
+(0+12)x
3
+(-1+12)x4
=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)
从图1中 可以看出，(5)式所表示的割平面约
束仅割去线性规划可行域中不包含整数可
行解的部分区域 ，使点E(3.5，2)成为可行域
的一个极点。

10
9
8
7
6
5
4
3
2
1
0
01232x1+3x2=14
2x1+x2=9
2x1+2x2=11
A
DE
B
C
456789

图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
594 0 0 14 54 0

j

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
584 0 0 0 1 12

j


由此得最优解为：x
1
=72, x
2
=2, z=584
该最优解仍不满足整数约束条件，因而需进
行第二次切割。为此，从表2中抄下非整数
解x< br>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
584 0 0 0 1 12 0

j

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
14 0 0 0 1 0 1

j

由此得最优解为：x
1
=4, x< br>2
=1,z=14。该最优解
符合整数条件，因此也是原整数规划问题的
最优解 。
从图1中可以看出，由(8)式表示的割平面
约束，不仅割去线性规划可行域中剩下的不< br>含整数解域，而且使最优整数解x
1
=4, x
2
=1
（即图2中的G点），成为新的线性规划可
行域的一个极点。 10
9
8
7
6
5
4
3
2
1< br>0

2x1+3x2=14
2x1+x2=9
2x1+2x2=11x1+x2=5
F
G

图2