3.3割平面法.ppt

3.3 割平面法 一、基本思想 第三步： 作业： * · · · · · · · · · · · · · · · · 割平面 割平面法的基本思想： 若整数规划IP的松弛规划L0的最优解不是整数解，对L0增加一个约束条件，得线性规划L1，此过程缩小了松弛规划的可行解域，在切去松弛规划的最优解的同时，保留松弛规划的任一整数解，因此整数规划IP的解均在L1中，若L1的最优解为整数解，则得IP的最优解。若L1的最优解不是整数解，重复以上步骤，由于可行解域在不断缩小，且保留IP所有的整数解，总可以在有限次后得到IP的最优解. 问题：如何寻找割平面？ 增加的约束方程须满足什么条件才能使： 1、割掉松弛规划的最优解 2、保留所有的整数解 二、割平面法 L0的最优单纯形表： bm0 amn … amm+j … amm+1 1 … 0 … 0 xm ︰ ︰ ︰ ︰ ︰ ︰ ︰ ︰ bi0 ain … aim+j … aim+1 0 … 1 … 0 xi ︰ ︰ ︰ ︰ ︰ ︰ ︰ ︰ b10 a1n … a1m+j … a1m+1 0 … 0 … 1 x1 z-z0 λn … λm+j … λ1 0 … 0 … 0 检 解 xn … xm+j … xm+1 xm … xi … x1 源方程 ------对应于生成行i的割平面 L0的最优单纯形表： bm0 amn … amm+j … amm+1 1 … 0 … 0 xm ︰ ︰ ︰ ︰ ︰ ︰ ︰ ︰ bi0 ain … aim+j … aim+1 0 … 1 … 0 xi ︰ ︰ ︰ ︰ ︰ ︰ ︰ ︰ b10 a1n … a1m+j … a1m+1 0 … 0 … 1 x1 z-z0 λn … λm+j … λ1 0 … 0 … 0 检 解 xn … xm+j … xm+1 xm … xi … x1 生成行 对应于生成行i的割平面 非基变量 b 0 1 0.5 0 0 -0.5 1 0 0 -1.75 1 0 3.25 5.5 0 0 -1 0 1 1 3 1 0 -0.25 0 0 0.75 1.5 0 0 -0.5 0 0 -1.5 z-9 对应第2行的割平面： 对应第4行的割平面： 非基变量 如何求解？ bm0 amn … amm+j … amm+1 1 … 0 … 0 xm ︰ ︰ ︰ ︰ ︰ ︰ ︰ ︰ bi0 ain … aim+j … aim+1 0 … 1 … 0 xi ︰ ︰ ︰ ︰ ︰ ︰ ︰ ︰ b10 a1n … a1m+j … a1m+1 0 … 0 … 1 x1 z-z0 cn … cm+j … c1 0 … 0 … 0 检 解 xn … xm+j … xm+1 xm … xi … x1 s s 0 … 0 … 0 -fim+1 … -fim+j … -fin 1 –fi0 0 0 ︰ 0 ︰ 0 对偶单纯刑法 四、割平面计算步骤： 第一步： 用单纯刑法解整数问题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