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

割平面法求解整数规划问题：MaxZ=3x +2x122x +3x ?141 24x +2x ?181 2x ,x ?0,且为整数1 2解：首先，将原问题的数学模型标准化，这里标准化 有两层含义：（1）将不等式转化为等式约束，（2）将 整数规划中所有非整数系数全部转化为整数，以便于 构造切割平面。从而有：MaxZ=3x +2x1 22x +3x +x =141232x +x +x =9124x ,x ?0，且为整数1 2利用单纯形法求解，得到最优单纯形表，见表1：表1TBB3200X1X2X3X4A/ 2X25/2011/2-1/23X113/410-1/4A/3/4?j59/4001/45/4最优解为：x =13/4,x =5/2,Z=59/412根据上表，写出非整数规划的约束方程，如：x +1/2x -1/2x =5/2(1)234 将该方程中所有变量的系数及右端常数项均改写成 “整数与非负真分数之和”的形式，即：(1+0)x +(0+1/2)x +(-1+1/2)x =2+1/22 34把整数及带有整数系数的变量移到方程左边，分数及 带有分数系数的变量称到方程右边，得：x -x -2=1/2-(1/2x +1/2x )(2)2 434由于原数学模型已经“标准化”，因此，在整数最优解 中，x和x也必须取整数值，所以(2)式左端必为整数2 4或零，因而其右端也必须是整数。又因为x,x?O,所3 4以必有：1/2-(1/2x +1/2x)13 4由于(2)式右端必为整数，于是有：1/2-(1/2x +1/2x)?0(3)3 4或x+x ?134这就是考虑整数约束的一个割平面约束方程，它是用 非基变量表示的，如果用基变量来表示割平面约束方 程，则有：2x +2x ?11(5)12从图1 中可以看出， (5)式所表示的割平面约束仅割去线性规划可行域中不包含整数可行解的部分区域，使 点E(3.5, 2)成为可行域的一个极点。图1在(3)式中加入松弛变量 x ，得：-1/2x -1/2x +x =-1/2 (6)3455将(6)式增添到问题的约束条件中，得到新的整数规划 问题：MaxZ=3x +2x1 22x +3x +x =141232x +x +x =9124-1/2x -1/2x +x =-1/2345x ?0,且为整数，i=1,2, ,5i该问题的求解可以在表1中加入式,然后运用对偶单纯形法求出最优解。具体计算过程见表2：表2BB200X1X2X3=a/ n.X4AX52X25/2011/2-1/203X113/41000X5-1/200-1/2-1/21?j59/4001/4022010-113717/2T00T1/203T00T/ ?j “一一58/400011/2田此得最优解为：x =7/2,x =2，z=58/412该最优解仍不满足整数约束条件，因而需进行第二次 切割。为此，从表2中抄下非整数解x.的约束方程为:x +x -1/2x =7/2145按整数、分数归并原则写成：x +x -x -3=1/2-1/2x ?01455这就是一个新的割平面方程，(7)用基变量来表示，得：x +x ?51 2在(7)中加入松弛变量x，得：6-1/2x +x =-1/2(9)56将(9)式增添到前一个问题的约束条件中去，得到又一 个新的整数规划问题，对它求解可以在表2中加入 式，然后运用对偶单纯形法求出最优解。具体计算过 程见表3：表3X3-2-000uBB厂厂XrX123456X9200一Tu32X17T2-00-1/r0从图1中可以看出，由式表示的割平面约束，不仅割去线性规划可行域中剩下的不含整数解域，而且使最优整数解x =4,x =1 （即图2中的G点），成为新的线性规划可行域的一个极点。1 2