整数规划(割平面法)

1、割平面法求解整数规划问题：Max Z=3xi+2x22xi+3x2 144xi+2x2 18X1,X2 0，且为整数解：首先，将原问题的数学模型标准化，这里标 准化有两层含义：（1）将不等式转化为等式约 束，（2）将整数规划中所有非整数系数全部转 化为整数，以便于构造切割平面。从而有：Max Z=3xi+2x22xi+3x2+X3=142xi+x2+X4=9X1,X2 0，且为整数利用单纯形法求解，得到最优单纯形表，见表1 : 表1CbXb3200XX2X%2X25/2011/2-1/23X13/410-1/43/4j59/4001/45/4最优解为： x1=13/4, x 2=5/2, Z=

2、59/4 根据上表，写出非整数规划的约束方程，如：x2+1/2x 3-1/2x 4=5/2(1)将该方程中所有变量的系数及右端常数项均改 写成“整数与非负真分数之和”的形式，即： (1+0)x2+(0+1/2)x 3+(-1+1/2)x 4=2+1/2 把整数及带有整数系数的变量移到方程左边， 分 数及带有分数系数的变量称到方程右边，得：x2 - x4-2 =1/2-(1/2x 3+1/2x 4)(2)由于原数学模型已经“标准化”，因此，在整数 最优解中， x2 和 x4 也必须取整数值， 所以 (2)式左 端必为整数或零，因而其右端也必须是整数。又 因为 x3,x4 0，所以必有：1/2-(

3、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/2x3-1/2x4+X5=-1/2(6)将(6)式增添到问题的约束条件中，得到新的整数规划问题：Max Z=3xi+2x22xi+3x2+X

4、3=142X1+X2+X4=9-1/2x 3-1/2x4+X5=-1/2Xi 0,且为整数，i=1,2,5该问题的求解可以在表 1中加入(6)式，然后运用 对偶单纯形法求出最优解。具体计算过程见表2:表2CbXbb32000Xi茨%X4x2X25/2011/2-1/2 C13Xi13/410-1/43/400x-1/200-1/2 -12 1j59/4001/45/402X22010-113X17/21001-1/20X10011-2j58/400011/2由此得最优解为：Xi=7/2, X2=2, z=58/4该最优解仍不满足整数约束条件，因而需进行第二次切割。为此，从表2中抄下非整数解Xi

5、的约 束方程为：xi+ X4-1/2X5 = 7/2按整数、分数归并原则写成：x什X4-X5-3 = 1/2-1/2x 5 0(7)这就是一个新的割平面方程，用基变量来表示，得：x什X2 5(8)在(7)中加入松弛变量X6,得：-1/2x 5+X6=-1/2(9)将(9)式增添到前一个问题的约束条件中去， 得到 又一个新的整数规划问题，对它求解可以在表 2 中加入(7)式，然后运用对偶单纯形法求出最优解。具体计算过程见表3：表3Cb Ixb lb 2 To fo TooXXX3X4X5X2X22010-1103Xi7/21001-1/200X510011-200X6-1/20000-1/2 1j58/400011/202X21010-1023Xi410010-10X3300110-40X5100001-2j14000101由此得最优解为：xi=4, X2=1,z=14。该最优解符合 整数条件，因此也是原整数规划问题的最优解。从图1中可以看出，由（8