3.3割平面法 基本思想
3.3 割平面法 一、基本思想
求P: 松弛问题Lo 1o+(x1≤3)得L1 max z=8x, +5x 2x1+3x,≤12 maxz=8x1+5x2 max z=8x,+5x2 2x1+3x,≤12 2x1-x2≤6 2x1+3x2≤12 s t st2x 2x x1≥0,x2≥0 S Z 2 x1≥02x,≥0 3 x1,x2为整数 L0的最优解: ≥6,x2≥0 3.75,x2=1.5 ∈割平面 P的可行解斗L的整数解 2x1+3x,=12 P的可行解←L的整数解 L的最优解:x1=3,x2=2 >得P的最优解:x1=3,x2=2 思想:在L上增加一个约束 该约束去掉了L的最优解 保留了L的所有整数解 即保留了P的所有整数解 二=8x1+5x2
− + = + 为整数 求 ： 1 2 1 2 1 2 1 2 1 2 , 0, 0 2 6 2 3 12 . max 8 5 x x x x x x x x st z x x IP − + = + 0, 0 2 6 2 3 12 . max 8 5 1 2 1 2 1 2 1 2 0 x x x x x x st z x x 松弛问题L ： IP的可行解 L0 的整数解 2 3 12 x1 + x2 = 2 6 1 2 x − x = · · · · · · · · · · · · · · 1 2 z = 8x + 5x · · − + = + 0, 0 3 2 6 2 3 12 . max 8 5 1 2 1 1 2 1 2 1 2 x x x x x x x st z x x L0 + (x1 3)得L1 ： IP的可行解 L1 的整数解3.75, 1.5 1 2 0 x = x = L 的最优解： 思想：在L0 上增加一个约束， 保留了L0 的所有整数解 L1 的最优解：x1 = 3, x2 = 2 3, 2 得IP的最优解：x1 = x2 = 该约束去掉了L0 的最优解， 即保留了IP的所有整数解 割平面
割平面法的基本思想: 若整数规划P的松弛规划L0的最优解不是整数解, 对L增加一个约束条件,得线性规划L,此过程缩 小了松弛规划的可行解域,在切去松弛规划的最优 解的同时,保留松弛规划的任一整数解,因此整数 规划P的解均在L1中,若L1的最优解为整数解,则 得P的最优解。若L的最优解不是整数解,重复以 上步骤,由于可行解域在不断缩小,且保留IP所有 的整数解,总可以在有限次后得到I的最优解
割平面法的基本思想： 若整数规划IP的松弛规划L0的最优解不是整数解， 对L0增加一个约束条件，得线性规划L1，此过程缩 小了松弛规划的可行解域，在切去松弛规划的最优 解的同时，保留松弛规划的任一整数解，因此整数 规划IP的解均在L1中，若L1的最优解为整数解，则 得IP的最优解。若L1的最优解不是整数解，重复以 上步骤，由于可行解域在不断缩小，且保留IP所有 的整数解，总可以在有限次后得到IP的最优解
问题:如何寻找割平面? 增加的约束方程须满足什么条件才能使 割掉松弛规划的最优解 2、保留所有的整数解
问题：如何寻找割平面？ 增加的约束方程须满足什么条件才能使： 1、割掉松弛规划的最优解 2、保留所有的整数解
割平面法 对整数规划问题 TP: max z= CX 其松弛问题Lo max z= CX AX= b sX≥0 AX=b s. x,为整数 lX≥0 设L的最优解X不是整数解 不妨设 105…b bn0…0)其中b0是分数 即x1…x2…x是基变量, m+1 ,x是非基变量
= = 为整数 ： 对整数规划问题 j x X AX b st IP z CX . 0 max = = 0 . max 0 X AX b st z CX 其松弛问题L 二、割平面法 设L0 的最优解X0 不是整数解 ( ) X0 = b1 0 ,bi0 ,bm0 ,0,0 不妨设 即x1 , xi , xm 是基变量，xm+1 , , xn 是非基变量 其中bi0 是分数