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

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

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

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

4、2x4+x5=-1/2Xi-0,且为整数，i=1,2,5该问题的求解可以在表 1中加入式,然后 运用对偶单纯形法求出最优解。具体计算过 程见表2：表2CbXbb32000X1X2X3X4X52X2/2011/21/203Xi13/4101/4$400X51/2001/21/21j59/4001/4S402X22010113Xi7/210011/20X3100112J58/400011/2由此得最优解为：x1=72, X2=2, z=584该最优解仍不满足整数约束条件，因而需进 行第二次切割。为此，从表 2中抄下非整数 解xi的约束方程为：xi+X4-1/2x5 = 72按整数、分数归并原则写成

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