6.3割平面法【荐】.pptVIP

6.3 割平面法 一、基本思想 第三步： 作业： * · · · · · · · · · · · · · · · · 割平面 割平面法的基本思想： 若整数规划IP的松弛规划L0的最优解不是整数解，对L0增加一个约束条件，得线性规划L1，此过程缩小了松弛规划的可行解域，在切去松弛规划的最优解的同时，保留松弛规划的任一整数解，因此整数规划IP的解均在L1中，若L1的最优解为整数解，则得IP的最优解。若L1的最优解不是整数解，重复以上步骤，由于可行解域在不断缩小，且保留IP所有的整数解，总可以在有限次后得到IP的最优解. 问题：如何寻找割平面？ 增加的约束方程须满足什么条件才能使： 1、割掉松弛规划的最优解 2、保留所有的整数解 二、割平面计算步骤： 第一步： 用单纯形法解整数问题IP的松弛问题L0 若L0没有最优解，则IP没有最优解。停止 若L0有最优解X0: (1)X0是整数解， 则X0也是IP的最优解，停止 (2)X0不是整数解， 转第二步 第二步： 求割平面方程 将割平面加到L0得L1 第四步： 解L1 在L0的最优单纯型表中增加一行一列， 得L1的单纯型表， 用对偶单纯刑法求解， 若其解是整数解，则该解也是原整数规 划的最优解 否则将该解记为X0，返回第二步 例 用割平面法求解IP 解：IP问题的松弛规划的 标准型： 3.75 1 0 0.125 0.375 X1 1.5 0 1 0.25 -0.25 X2 Z-37.5 0 0 -2.25 -1.75 X1 X2 X3 X4 X5 0 0 0 X5 0 0 -0.125 -0.375 1 -0.75 2 0 0 0.333 1 -2.667 X4 X1 X2 Z X1 X2 X3 X4 X5 1 0 0 0 1 3 0 1 0.333 0 -0.667 2 0 0 -1.667 0 -4.667 z-34 整数 最优值： Z=34 例： 用割平面法求解 解：IP的松弛规划的标准型 9/2 1 0 -1/22 3/22 X1 7/2 0 1 7/22 1/22 X2 Z-63 0 0 -28/11 -15/11 X1 X2 X3 X4 X5 0 0 -7/22 -1/22 1 -1/2 X5 0 0 0 11/7 0 0 1 1/7 -22/7 X3 X1 X2 X1 X2 X3 X4 X5 1 0 0 1/7 -1/7 32/7 0 1 0 0 1 3 0 0 0 -1 -8 Z-59 非整数 11/7 0 0 1 1/7 -22/7 X3 X1 X2 X1 X2 X3 X4 X5 1 0 0 1/7 -1/7 32/7 0 1 0 0 1 3 0 0 0 -1 -8 Z-59 X6 0 0 0 -1/7 -6/7 1 -4/7 X6 0 0 0 0 1 0 0 1 0 -4 1 X3 4 0 0 0 1 6 -7 X4 4 1 0 0