运筹学chap5整数规划.pptVIP

* * 第二节 分支定界法 分支定界的实质是在保留原问题全部整数可行解前提下，将原问题分解为若干子问题，即分支，并利用子问题的目标值来判定分支的界限。 整数线性规划的分支原则是利用整数规划的相邻整数点之间无可行域这一特点，因而可以按相邻整数为边缘来分支。 整数规划的最优解不会更优于相应的线性规划的最优解。即对于最大化问题，与整数规划相应的线性规划的目标函数值，是该整数规划目标函数值的上界；对于最小化问题，其目标函数值是相应的下界。 例1： * 分支定界法求解过程（1） 求解相应的线性规划 最优解:(5/3,8/3) * 分支定界法求解过程（2） 第一次对x1分支:分成 和 最优解:(1,16/5) 目标函数最优值：68/5 （整数解的上界） 最优解:(2,2) 目标函数最优值：14 B1 B2 因, 68/5 ＜14 14,整数解 不再分支 * 分支定界法求解过程（3）(不必进行) B1的最优解中含有非整数，再对x2分支： 和 最优解:(1,3) 目标函数最优值：13 B11 最优解:(0,4) 目标函数最优值：12 整数解 不再分支 B12 所有分支都检查完毕，得到最优解(2, 2)。 整数解 不再分支 * 例2：求解整数规划 maxZ=3X1+2X2, S.t. 2X1+3X2≤14 4X1+2X2≤18 X1,X2≥0,而且X1,X2取整数 * 求解过程可用下列树状结构表示 * 分支定界法求解步骤 1.设原整数规划问题为问题A，相应的线性规划为问题B，解问题B。 2.如问题B没有可行解，即停止。这时问题A也没有解。 3.如求得问题B的最优解，检查它是否满足整数条件，如果满足整数条件，它就是问题A的最优解；如果不满足整数条件，即转如下一步。 4.在问题B的解中，任选一个符合整数条件的变量xi,，如xi的值是bi，作两个后继问题，它们是对问题B分别增加一个约束条件： （1） （2） 其中，为数值不大于的最大整数。不考虑整数条件，解这两个后继问题。 5.在现有的，且还没有分解出后继问题的各可行问题中，选目标函数值为最大的问题。重新称这个问题为问题B，回到步骤3，重复进行。 * 分支定界法对纯整数规划和混合整数规划问题均适用。 优点：以非整数规划最优解为树根，最优目标值为上界，按决策变量整数值分支，求到目标函数值最优的整数解为止，比枚举法有效。 缺点：当分支越多，要求的子问题越多，且子问题的约束条件也增多，计算量加大，对于多变量整数规划问题，求解过程非常繁琐和费时。 分支定界法的适用与优缺点 * 第四节 割平面法 基本思想：当得到的解不满足取整约束时，就设法在问题上增加一个约束条件，把包含这个非整数解的一部分可行域从原来的可行域中割除，但不割掉任何一个整数可行解。这个新增加的约束条件就称为割平面。 割平面法步骤： （1）解除整数约束，用单纯形法求解。如所得到的解为整数解，停止计算；否则转步骤（2）。 （2）寻求附加约束（割平面方程）； （3）将割平面方程标准规范化后加到约束方程组中求解，如所得到的解仍为非整数，则转步骤（2），直到找到最优整数解。 难点及重点：如何找到割平面方程，并使包含割平面约束在内的新的规划问题的一个极点解成为最优整数解。 * 例：Max z = x1 + x2 - x1 + x2 ? 1 3x1 + x2 ? 4 x1，x2 ? 0且取整 解：1.求解相应的线性规划L0 Max z = x1 + x2 - x1 + x2 ? 1 3x1 + x2 ? 4 x1，x2 ? 0 * 非整数解，为建立割平面，首先考虑非整数解中余数最大的基变量，此例中x1、 x2的余数均为3/4，不妨选取x2 ： x2 +3/4 x3 +1/4 x4 =7/4 * x2 +3/4 x3 +1/4 x4 =7/4 现将各系数分成整数和非负真分数两部分，从而可得： (1+0)x2+(0+3/4) x3+(0+1/4) x4 =(1+3/4) 将整数部分的变量移至等式右端有： 3/4 x3 +1/4 x4 =3/4+（1- x2 ） 非负整数解?(1- x2)为整数，左端非负故有： 3/4 x3 +1/4 x4 =3/4+非负整数 从而： 3/4 x3 +1/4 x4 ?3/4 或 x2 ? 1 以x2 ? 1为割平面可使可