割平面法.ppt

运 筹 学第四章 整数规划1.3 割平面法 割平面法是1958年美国学者R.E.Gomory提出的求解纯整数规划的一种比较简便的方法，其基本思想是：先不考虑变量的整数限制求解线性规划，如果得到的解不是整数解，则不断增加适当的约束，割掉原可行域不含整数解的一部分，最终得到一个具有若干整数顶点的可行域，而这些顶点中恰有一个顶点是原问题的整数解。割平面法的基本步骤：步骤1 不考虑变量的整数限制，求解相应的线性规划问题，如果该问题无解，或最优解已是整数解，则停止计算，否则转下一步。步骤2 对上述线性规划的可行域进行“切割”，去掉不含整数解的一部分可行域，即增加适当的线性约束，然后转步骤1。2.割平面法的关键在于如何确定切割方程，使之能对可行域进行真正的切割，而且切去部分不含有整数解点。下面讨论切割方程的求法。设与整数规划相对应的线性规划最优解中基变量XBi=（B-1b)i不是整数，将最优单纯形表中该基变量对应的行还原成约束方程，即 XBi+aijXj=（B-1b)i 将（B-1b)i，aij都分解成整数与非负真分数之和的形式，即 （B-1b)i=Ni+fi 其中0 fi 1 aij=Nij+fij 其中0 fij 1 这里Ni、Nij是整数，将、代入，得 XBi+（Nij+fij）Xj=Ni+fi 即 XBi+NijXj-Ni=fi-fijXj 当诸Xi都是整数时，式左端是整数，所以右端亦应是整数，但右端是两个正数之差，且0 fi 1，fi-fijXj是小于1的整数，从3.从而 fi-fijXj0 取式作为切割方程。因为任何整数可行解都满足这个方程，所以把它加到原问题的约束中，它能够对原可行域进行切割，而不会切割掉整数解。例3 用割平面法求解 maxZ=x1+x2 -x1+x21 3x1+x24 x1,x20，整数 解：将问题标准化得 maxZ=x1+x2 -x1+x2+x3=1 3x1+x2+x4=4 x1,x20 x1,x2 整数 不考虑条件，求解相应线性规划，结果见下表：4.C 1 1 0 0CBXBB-1b X1 X2 X3 X400 X3 X414 -1 1 1 0 3 1 0 10 1 1 0 0 11X1X23/47/4 1 0 -1/4 1/4 0 1 3/4 1/4 0 0 -1/2 -1/2表中x1=3/4，不是整数，将表中第一行还原成方程，即 x1-1/4x3+1/4x4=3/4因为3/4=0+3/4，-1/4=-1+3/4，1/4=0+1/4所以有 x1-x3=3/4-3/4x3-1/4x4因而有切割方程：3/4x3+1/4x4 3/4 即 3x3+x4 3引入松弛变量x5，得方程 -3x3-x4+x5=-3将新约束方程加到原最优表下面（切割），求得新的最优解如下：5.C 1 1 0 0 0CBXBB-1b X1 X2 X3 X4 X5110X1X2X53/47/4-3 1 0 -1/4 1/4 0 0 1 3/4 1/4 0 0 0 -3 -1 1 0 0 -1/2 -1/2 0110X1X2X3111 1 0 0 1/3 -1/12 0 1 0 0 1/4 0 0 1 1/3 -1/3 0 0 0 -1/3 -1/6 由于x1，x2的值已是整数，所以该题经一次切割已得最优解：x1=1，x2=1，最优值：Z=2 6.现在我们来看看切割方程 3x3+x4 3 的几何意义。例3对应的线性规划为 maxZ=x1+x2 -x1+x21 3x1+x24 x1,x20用图解法求得可行域D及最优解点A，见下图：x2x111-10-x1+x2=13x1+x2=4A（3/4，7/4）由标准化的约束方程组可得 x3=1+x1-x2 x4=4-3x1-x2代入切割方程 得 3（1+x1-x2）+（4-3x1-x2）3即 x21，将此切割方程 加入原约束中，就等于切掉原可行域得A1B部分，如图。B（1，1）D显然在A1B区域不含整数解点，对原可行域切割的结果是产生了一个新顶点B，用图解法在新的可行域（黄色）中可求得整数最优解恰是B（1，1）。7.在求解实际问题中，割平面法经常会遇到收敛很慢的情况，但若和其它方法，如分枝定界法，联合使用，一般能收到比较好的效果。8.