割平面法

第二节解纯整数规划的割平面法一、割平面方法的基本思想和步骤二、构造割平面约束的方法三、示例一、割平面方法的基本思想和步骤•基本思想：在IP问题的松弛问题中依次引进线性约束（称Gomory约束或割平面），使问题的可行域逐步缩小，所割去的区域仅包含问题的部分非整数解；当规划问题的最优解恰好位于缩小的可行域的一个顶点时，算法结束。•求解步骤１、求出松弛问题的最优解，若全部变量为整数解，停止计算；否则转２。２、构造割平面方程•构造方法割平面约束具备两个性质：⑴已获得的非整数最优解不满足该线性约束，从而保证在以后的解中不可能再出现。⑵所有的整数解皆满足该线性约束，从而保证整数规划问题的最优解始终都保留在每次所形成的、新的线性规划问题的可行域中。我们通过下面的例子来说明构造这种线性约束的思路。解松弛问题的最优表如下：7314x不是整数，该行对应的方程是：731722)73(534xxx-3/70-5/7002/73/722/70011/7-2/7-3/701010013/79/731/7x1x2x43-10000-13jcjjzcbCBXBx1x2x3x4x573717453xx或者，X4-3/7x3+22/7x5=31/7⑴由于基变量、非基变量均要求取整数值，所以，在上述式子中，我们将变量系数与常数项皆化为两部分：不超过该数的最大整数与非负分数，即-3/7=-1+4/722/7=3+1/731/7=4+3/7于是，（1）式变为734)713()741(534xxx⑵将所有整数项放在等式的左边，非整数值项放在右边，得5353471747343xxxxx⑶⑶式左边是一个整数值，右边是一个小于１的数。由于是等式，所以，右边应该是一个小于或等于０的整数值，即071747353xx⑷亦即73717453xx⑸通过分析可以得出⑸式具有如下两个性质：①松弛问题的非整数最优解不满足该式。（因为x3与x5都是非基变量，将松弛问题的非整数最优解代入该式得到“－３／７≥０”，矛盾）。②IP的所有整数可行解都满足此式。（因所有整数可行解都满足⑴式，从而满足⑵、⑶、⑷式。kobb的分量;,为非负真分数的最大整数，为不超过其中kokokokokokofbNfNbkobjkojkojkofNa,,,kokofxfjj,二、构造割平面约束的方法在松弛问题的最优表中，设不是整数，将其分成整数与非负分数之和，即所在行中的每一个非基变量xj的系数分成整数与非负分数两部分：则割平面方程为：例如：下表是整数规划松弛问题的最优单纯表。-3/70-5/7002/73/722/70011/7-2/7-3/701010013/79/731/73-10000-13jcbBCBX1x2x3x4x5x1x2x4xjjzcb列中X4=9/7是非整数，将其分成两部分，即该行中非基变量x3与x5的系数也分成两部分，即：9/7=1+2/7-2/7=-1+5/73/7=0+3/7则割平面方程为72737553xx注：⑴从最优单纯形表中选择具有最大非负分数部分的非整分量所在的行构造割平面约束，可以提高切割效果，减少切割次数。⑵可以证明：①任意整数可行解都满足此切割方程。②松弛问题的非整数最优解不满足此方程。例２用割平面法求解纯整数规划为整数2,121212121210,5210453233maxxxxxxxxxxxxxZ解用单纯形法求得松弛问题的最优表如下：三、示例松弛问题的最优解为非整数,而在13/7=1+6/79/7=1+2/731/7=4+3/7的非负分数中,6/7最大,所以将13/7所在的行中非基变量所对应的系数进行分解:1/7=0+1/72/7=0+2/7则割平面方程为：76727153xx⑴-3/70-5/7002/73/722/70011/7-2/7-3/701010013/79/731/73-10000-13jcBCBX1x2x3x4x5xbjjzc421xxx将割平面约束⑴并入松弛问题的最优表中，然后利用对偶单纯法求出其最优解，见下表。76727153xx-6/700-1/70-2/70100006x-3/70-5/7002/73/722/70011/7-2/7-3/701010013/79/731/73-100000-13…………jc1x2x3x4x5xjjzc6421xxxxbXCBB-17/41-5/4-11/2-3/400-1/400000010-1/4-1/21/400100100100015/45/27/43-100000-13jc1x2x3x4x5x6xjjzcbXCBB6321xxxx由上表的第四行产生的割平面约束为⑵将⑵并入上表中（略），求出该问题的最优解为1max,2,121zxx43414164xx1767271153xxx34341412164xxxx152342x1231x返回)2,1()45,1()79,713(321xxmax