Gomory割平面法.

精品课程《运筹学》第二节Gomory割平面法§2.1Gomory割平面法的基本思想§2.2Gomory割平面法计算步骤精品课程《运筹学》§2.1Gomory割平面法的基本思想考虑纯整数线性规划问题)(P可行区域记为D(P)的松弛问题)(0P可行区域0D由有限个或可数的格点构成的集合多面凸集为整数向量xxbAxtsxcT0..min0..minxbAxtsxcT精品课程《运筹学》的关系和0DD⑴．0DD；⑵．若)(0P无可行解，则)(P无可行解；⑶．)(0P的最优值是)(P的最优值的一个下界；⑷．若)(0P的最优解0x是整数向量，则0x是)(P的最优解.精品课程《运筹学》割平面法的基本思想用单纯形法先解松弛问题)(0P，若)(0P的最优解0x是整数向量，则0x是ILP问题)(P的最优解，计算结束；费用减小方向0x精品课程《运筹学》0x若0x的分量不全是整数，则对)(0P增加一个割平面条件，将)(0P的可行区域0D割掉一块，0x恰好在被割掉的区域内，而原ILP问题的任何一个可行解（格点）都没有被割去.精品课程《运筹学》1x把增添了割平面条件的问题记为)(1P，用对偶单纯形法求解LP问题)(1P.若)(1P的最优解1x是整数向量，则1x是原ILP问题)(P的最优解，计算结束；精品课程《运筹学》否则对问题)(1P在增加一个割平面条件，形成问题)(2P，…，如此继续下去，通过求解不断改进的松弛LP问题，知道得到最优整数解为止.*x精品课程《运筹学》生成割平面条件的代数方法(Gomory)用单纯形方法解)(P的松弛问题)(0P最优基本可行解0x),,(1mBBAABmBBxx,,1基变量的下标集合为S非基变量的下标集合为S最后一张单纯形表中问题)(0P的典式为Sjjjzxz0SjijijBmibxaxr,,1,令zxB0jja000zb精品课程《运筹学》如果mibi,,1,0,，全是整数，我们已经得到了ILP问题)(P的最优解0x.否则至少有一个lb不是整数)0(ml，设lb所对应的约束方程是SjljljBbxaxllllijljljfbbSjfaa][,][Sjflj,1010lf精品课程《运筹学》SjjljSjjljxaxa][SjljljBbxaxllllijljljfbbSjfaa][,][Sjflj,1010lfSjljljBbxaxl][SjljljBbxaxl][][][])[(llSjjljljbbxaa相减精品课程《运筹学》lsjjljfxfSjjljSjjljxaxa][SjljljBbxaxl][SjljljBbxaxl][][][])[(llSjjljljbbxaa相减Gomory割平面条件lsjjljfsxf割平面精品课程《运筹学》定理3.2.1如果把割平面lsjjljfsxf加到松弛问题)(0P的最优单纯形表里，那么没有割掉原ILP的任何整数可行点，当lb不是整数时，新表里是一个原始基本不可行解和对偶可行解.精品课程《运筹学》证由于割平面lsjjljfsxf是由原ILP的整数约束推出来的，所以它不会割掉整数可行解；松弛变量s是新的基变量，并且它与原来的基变量mBBxx,,1一起构成了新松弛问题的基变量，当lb不是整数时，0lf，因此新松弛问题的基本解中有0lfs，因此它对应的是新松弛问题的原始基本不可行解.由于表中第0行（检验数行）没有改变，所以它仍保持对偶可行性.精品课程《运筹学》§2.2Gomory割平面法计算步骤第1步用单纯形法解ILP问题)(P的松弛问题)(0P.若)(0P没有最优解，则计算停止，)(P也没有最优解.若)(0P有最优解0x，假若0x是整数向量，则0x是)(P的最优解，计算停止，输出0x；否则转第2步.第2步求割平面方程lsjjljfsxf精品课程《运筹学》第3步将割平面方程lsjjljfsxf加到第1步所得最优单纯形表中，用对偶单纯形法求解这个新的松弛问题.若其最优解为整数解，则它是问题)(P的最优解，计算停止，输出这个最优解；否则将这个最优解重新记为0x，返回第2步.若对偶单纯形算法发现了对偶问题是无界的，此时原ILP问题是不可行的，计算停止.精品课程《运筹学》例3.2.1求解ILP问题maxx21x2x0123123解这个问题及其松弛LP问题的可行区域如图所示整数,0,023623..max2121212xxxxxxtsx精品课程《运筹学》增加松弛变量3x和4x，得到了松弛LP问题的第一张单纯形表000236012301010434321xxzRHSxxxx精品课程《运筹学》经过两次旋转变换得到最优单纯形表为23414110161610123414100214321xxzRHSxxxxTx23,10最优解为23z最优值为21414143xx精品课程《运筹学》000236012301010434321xxzRHSxxxx21414143xx213236xxx21423xxx12xmaxx21x2x0123123精品课程《运筹学》经过两次旋转变换得到最优单纯形表为23414110161610123414100214321xxzRHSxxxxTx)23,1(023z21414143xx21434343xx342x12x精品课程《运筹学》214141143sxx2114141002304141101061610123041410012114321sxxzRHSsxxxx精品课程《运筹学》利用对偶单纯形算法解上表中的松弛问题)(1P，得到关于问题)(1P的最优单纯形表为24110011001032323100111000032114321xxxzRHSsxxxx精品课程《运筹学》24110011001032323100111000032114321xxxzRHSsxxxxTx1,32132323214sx21xx精品课程《运筹学》Tx)1,32(132323214sx21xxmaxx21x2x0123123精品课程《运筹学》123110001235010010100101211000110100004321214321xxxxzRHSssxxxxTxILP)1,1(*问题的最优解