第章整数规划割平面法.docx

第章整数规划割平面法
第章整数规划割平面法
第章整数规划割平面法
割平面法
求解整数规划问题：
Max Z=3x1+2x2
2x1+3x2 14
4x1+2x2 18
x1,x 2第章整数规划割平面法
第章整数规划割平面法
第章整数规划割平面法
割平面法
求解整数规划问题：
Max Z=3x1+2x2
2x1+3x2 14
4x1+2x2 18
x1,x 2 0，且为整数
解：第一，将原问题的数学模型标准化，这里标准化有两层含义：（1）将不等式转变为等式拘束，
2）将整数规划中所有非整数系数所有转变为整数，以便于结构切割平面。进而有：
Max Z=3x1+2x2
2x1+3x2+x3=14
2x1+x2+x4=9
x1,x 2 0，且为整数
利用纯真形法求解， 获得最优纯真形表， 见表 1：
表 1
CB
XB
b
3
2
0
0
X1
X2
X3
X4
2
X2
5/2
0
1
1/2
-1/2
3
X1
13/4
1
0
-1/4
3/4
j
59/4
0
0
1/4
5/4
最优解为： x1=13/4, x 2=5/2, Z=59/4
依据上表，写出非整数规划的拘束方程，如：
x2+1/2x 3-1/2x 4=5/2 (1)
将该方程中所有变量的系数及右端常数项均改写成“整数与非负真分数之和”的形式，即：
(1+0)x 2+(0+1/2)x 3+(-1+1/2)x 4=2+1/2
把整数及带有整数系数的变量移到方程左侧， 分数及带有分数系数的变量称到方程右侧，得：
x2 - x 4-2 =1/2-(1/2x
3+1/2x 4)
(2)
因为原数学模型已经“标准化” ，所以，在整数最优解中， x2 和 x4 也一定取整数值，所以 (2) 式
左端必为整数或零，因此其右端也一定是整数。
又因为 x3,x 4 0，所以必有：
1/2-(1/2x
3+1/2x
4)<1
因为 (2)
式右端必为整数，于是有：
1/2-(1/2x
3+1/2x
4) 0
(3)
或
x3+x4
1
(4)
这就是考虑整数拘束的一个割平面拘束方程， 它是用非基变量表示的， 假如用基变量来表示割平面拘束方程，则有：
2x1+2x2 11 (5)
第章整数规划割平面法
第章整数规划割平面法
第章整数规划割平面法
从 1 中能够看出， (5) 式所表示的割平面 束 割去 性 划可行域中不包括整数可行解的
部分地区，使点 E( ，2) 成 可行域的一个极点。
1
在 (3) 式中加入废弛 量 x5，得：
-1/2x 3-1/2x 4+x5=-1/2
(6)
将 (6) 式增加到 的 束条件中，获得新的整数 划 ：
Max Z=3x1+2x2
2x1+3x2+x3=