第三节-割平面法

割平面法的基本思想是：首先不考虑整数条件，增加另外的约束条件，把原来的可行域切掉一部分，被切掉的部分不包含任何整数可行解.经过有限次的切割，最终得到某个顶点的坐标恰好是整数，并且是问题的最优解.3.3割平面法例如求解整数规划问题1212121212max134,0,Zxxxxxxxxxx为整数1237,=4410max4xxZ111x2x(34,74)A(11,)C例如求解整数规划问题1212121212max134,0,Zxxxxxxxxxx为整数1237,=4410max4xxZ111x2x(34,74)A(11,)C例如求解整数规划问题1212121212max134,0,Zxxxxxxxxxx为整数1237,=4410max4xxZ111x2x(11,)C割平面整数规划（A）松弛问题（B）1maxnjjjScx1(1,,)nijjijaxbim0jx且为整数1maxnjjjScx1(1,,)nijjijaxbim0jx回到一般问题上：设松弛问题（B）的最优单纯形表为：11immnxxxxx00010000mnSbbb1101111mnxbbb011iiiminxbbb011mmmmmnxbbb0ib设不是整数，01niijjijmxbxb再设000[],[],ijijijiiibbfbbf0011[][]nniijjijjiijmjmxbxfxbf表3-1即0011[][]nniijjijjiijmjmxbxfxbf0011[][]nniijjiiijjjmjmxbxbffx0(0,1)iijff整数010niijjjmffx若要决策变量都取整数，则10nijjjmfx01if011niijjjmffx即0011[][]nniijjijjiijmjmxbxfxbf0011[][]nniijjiiijjjmjmxbxbffx0(0,1)iijff整数010niijjjmffx若要决策变量都取整数，则对上式引入松弛变量iy010niijjijmffxy割平面不等式01nijjiijmfxyf割平面方程例1用割平面法求解整数规划问题12max79Sxx且为整数(I)(II)解（1）把约束条件中的系数化为整数，加上松弛变量，去掉整数约束，得到相应的松弛问题12123xx12157xx12,0xx12max79Sxx23136xxx124735xxx14,,0xx(II).用单纯形法求解问题，得最优单纯形表(II)S2x9210-12232272017221221x-6300-2811-1511最优解为，不是整数1292,72xx（2）引进以所在行为来源行的割平面：2x3412722122xx表3-2010niijjjmffx20233244()0ffxfxS2x9210-12232272017221221x-6300-2811-1511选择割平面的经验规则：①选择的值大的；②若相等，则选择小的．01niijjmff0if表3-2102012ff13142122322=2422ff2324722122=822ff√S2x9210-12232272017221221x-6300-2811-1511最优解为，不是整数1292,72xx（2）引进以所在行为来源行的割平面：2x3412722122xx表3-2010niijjjmffx20233244()0ffxfx割平面不等式3412722122xx加入松弛变量，得割平面方程1y34172212212xxy将割平面方程表达的约束条件加到单纯形表的最后一行，并把松弛变量补到最后一列S2x9210-1223220720172212201x-6300-2811-151101y1200-722-1221表3-33472212212xxS2x9210-1223220720172212201x-6300-2811-151101y1200-722-1221表3-3用对偶单纯形法求解，得最终单纯形表S2x32710017-173010011x-59000-1-83x11700117-227表3-4S2x32710017-173010011x-59000-1-83x11700117-227以为来源行得割平面不等式：1x414717670xy引进松弛变量，得割平面方程2y412176747xyy如前所述，修改单纯形表表3-4010niijjjmffx10133144()0ffxfxS2x32710017-17030100101x-59000-1-803x11700117-22702y47000-17-671S2x1x550000273x4x4100011301001010010414000167换基迭代，得124,3,55xxS表3-5表3-6请练习：100页习题三第3题（用割平面法求解）答案：122,14xxZ作业：用割平面法求解整数规划问题12121212max7936735,0Zxxxxxxxx且为整数答案：124,3,55xxZ胡运权习题集5.8(a)