第5章-整数规划(割平面法)

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

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

3、2)式右端必为整数，于是有：1/2-(1/2X3+1/2X4) 0(3)或X3+X4 1(4)这就是考虑整数约束的一个割平面约束方程，它是用非基变量表示的，如果用基变量来表示割平面约束方程，则有：2X1+2X2 11(5)从图1中可以看出，(5)式所表示的割平面约 束仅割去线性规划可行域中不包含整数可行解的部分区域，使点E, 2)成为可行域的一个极点。图1在式中加入松弛变量X5 ,得：-1/2x3-1/2x4+X5=-1/2(6)将(6)式增添到问题的约束条件中，得到新的整数规划问题：Max Z=3xi+2x22xi+3x2+X3=142xi+x2+x4=9-1/2x3-1/2x4+x5=-1

4、/2xi 0,且为整数，i=1,2,5该问题的求解可以在表 1中加入（6）式，然后 运用对偶单纯形法求出最优解。具体计算过 程见表2:表2CbXbb32000X1X2X3X4X52X2卬2011/2-1/203X113410-1/43400X5-1/200-1/2-1/21j59/4001/45402X22010-113X17/21001-1/20X310011-2j58/400011/2由此得最优解为：Xi=72, X2=2, z=58/4该最优解仍不满足整数约束条件，因而需进行第二次切割。为此，从表 2中抄下非整数 解Xi的约束方程为：X1+X4-1/2X5 = 72按整数、分数归并原则写

5、成:xi+X4-X5-3 = 1/2-1/2X5 0这就是一个新的割平面方程，用基变量来表示，得：xi+X2 5(8)在(7)中加入松弛变量X6,得：-1/2x5+X6=-1/2(9)将(9)式增添到前一个问题的约束条件中去， 得到又一个新的整数规划问题，对它求解可 以在表2中加入(7)式，然后运用对偶单纯形法求出最优解。具体计算过程见表3:表3CbXbb320000XiX2X3X4X5X62X22010-1103Xi7/21001-1/200X510011-200X6-1/20000-11j58400011/202X21010-1023Xi410010-10X3300110-40X5100001-2j14000101由此得最优解为：Xi=4, X2=1,z=14。该最优解 符合整数条件，因此也是原整数规划问题的 最优解。从图1中可以看出，由(8)式表示的割平面 约束，不仅割去线性规划可行域中剩下的不 含整数解域，而且使最优整数解Xi=4, X2=1(即