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 是分数
设L的最优解X=(b0…bo;…bm0.…0),b是分数 L的最优单纯形表: 解 检|0 1 0 Im+l in a In 0 amm+1 mm+ n mO b0所在行的方程为 ● 源方程 +a im+14m+1 十∴+a.x ∷+a.x Im+) m+J In n 0
L0的最优单纯形表： x1 … xi … xm xm+1 … xm+j … xn 解 检 0 … 0 … 0 λ1 … λm+j … λn z-z0 x1 1 … 0 … 0 a1m+1 … a1m+j … a1n b10 ︰ ︰ ︰ ︰ ︰ ︰ ︰ ︰ xi 0 … 1 … 0 aim+1 … aim+j … ain bi0 ︰ ︰ ︰ ︰ ︰ ︰ ︰ ︰ xm 0 … 0 … 1 amm+1 … amm+j … amn bm0 bi0 所在行的方程为： i i m 1 m 1 i m j m j i n n i0 x + a x + + a x + + a x = b + + + + 源方程 ( ) 设L0 的最优解X0 = b10 ,bi0 ,bm0 ,0,0 ,bi0 是分数
对源方程:x+am1xm+…+amxm+…+anxn=bo 1n+ Im+ )a2 bro]+ fro 0≤f 1+ < 0<f0<1 ∑(am Im+//m+J bol+fr +∑[m,卜m+∑ m+J 0 +J0 pn+2m]m=-2 令0-∑/mxm≤0--对应于生成行的割平面
i i m 1 m 1 i m j m j i n n i0 x + a x + + a x + + a x = b 对源方程： + + + + i0 i0 b + f 0 f i0 1 im j im j a f + + + [ ] 0 f im+ j 1 0 1 m j i n m j i im j x + a x = b + − = + 0 0 1 ( ) i m j i m j m j i i n m j i x + a + f x = b + f + + + − = 0 0 1 1 m j i i n m j m j i m j n m j i i m j x + a x + f x = b + f + − = + + − = + m j n m j m j i i m n m j i i i m j x b a x f f x + − = + + − = − + + = − 1 0 1 1 0 0 1 0 − + − = + m j n m j i i m j 令f f x ------对应于生成行i的割平面
对整数规划问题其松弛问题L 线性规划L1:maxz=CX IP: max z= CX max z= CX AX=6 AX= 6 sX≥0 aX=6 s.t. Im-t/m+/ ≥f s.t. x;为整数 X≥0 X≥0 0的最优解X=(b0…bo,…bm0…0)其中b是分数 0的最优单纯形表: 解 生成行 Im+J 0≤f <1 Im+J Im+1 1-n n 0<f0<1 a 0 0 非基 mm+1 变量 对应于生成行的割平面f∑/mxm,0,即∑f Im+) m+J
== 为整数 ： 对整数规划问题 j x X AX b s t IP z CX . 0 max == 0 . max 0 X AX b s t z CX 其松弛问题 L ( ) L0 的最优解X0 = b10 , bi0 , b m 0 ,0, 0 其中bi0 是分数 L0的最优单纯形表： x1 … xi … xm xm+1 … xm+j … xn 解 检 0 … 0 … 0 λ 1 … λm+j … λn z - z 0 x 1 1 … 0 … 0 a1m+1 … a1m+j … a1n b10 ︰ ︰ ︰ ︰ ︰ ︰ ︰ ︰ x i 0 … 1 … 0 aim+1 … aim+j … ain bi0 ︰ ︰ ︰ ︰ ︰ ︰ ︰ ︰ xm 0 … 0 … 1 amm+1 … amm+j … amn bm0 生成行 : 0 1 0 − + −= + m j n mj i im j 对应于生成行 i的割平面 f f x i 0 i 0 b + f 0 fi 0 1 im j im j a f + + + [ ] 0 f im + j 1 j = 1 , 2 , n − m = = 0 . 1 : max X AX b s t 线性规划 L z CX 0 1 m j i n m j im j f x f + −= + 0 1 , m j i n m j im j f x f + −= 即 + 非基 变量
对P:maxz=4x1+3sm St2x1+3x2+x3= 其松弛问题L0:maxz=4x1+3x2 3x1+2 St2x1+3x2+x3=6 4 0x1+2x,+x5=5 3x1+2x2+xA=3 2x,+x+x=4 0x1+2x2+x5=5 X1.X.X X.x.x 2x1+x,+ 6 4 x12x2x3,x4,x5,x为整数 1>422 x2,X1,X,x≥0 的最优单纯形表 最优解x。=[m/+Jm0) 0 ⅨXXXX,Xb_日 Im-+ ·n-m 00-0.500-1.59 x2010.500-0.51 ∑ Im+/m+ i0 00-175103.255.5 x00-10 0 0-0.25000751.5 0<f0<1 对应第2行的割平面:025x3+025x6205 对应第4行的割平面:075x3+023x205
X1 X2 X3 X4 X5 X6 b 1 5 4 2 x x x x 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 , , , , , 0 2 4 0 2 5 3 2 3 . 2 3 6 max 4 3 1 2 3 4 5 6 1 2 6 1 2 5 1 2 4 1 2 3 0 1 2 + + = + + = − + + = + + = = + x x x x x x x x x x x x x x x st x x x 其松弛问题L ： z x x 为整数 对 1 2 3 4 5 6 1 2 3 4 5 6 1 2 6 1 2 5 1 2 4 1 2 3 1 2 , , , , , , , , , , 0 2 4 0 2 5 3 2 3 . 2 3 6 : max 4 3 x x x x x x x x x x x x x x x x x x x x x st x x x IP z x x + + = + + = − + + = + + = = + L0的最优单纯形表： (1.5 1 0 5.5 3 0) 最优解X0 = 对应第2行的割平面： 0 1 m j i n m j im j f x f + − = + i0 i0 b + f 0 f i0 1 im j im j a f + + + [ ] 0 f im+ j 1 j = 1,2, n − m 0.25 0.25 0.5 x3 + x6 对应第4行的割平面： 0.75 0.25 0.5 x3 + x6
对整数规划问题其松弛问题L。线性规划L1:maxz=CX IP: max z=CX maxz=CX aX=6 AX= 6 AX=b sX≥0 s t X≥0 Im-+m-t/ x为整数 非 最优解X不是整数基 X≥0 定理:L割去了L的最优解并保留量的所有整数解 证:把L的最优解X代入∑fm,xm≥0 得0≥0,10<f0<1矛盾 整数 所以L0的最优解不是L的可行解 设X*=(*…b*…b,+)是L的任一整数解 n-n 只需证∑fmbm*≥,即f0-∑ fimt+, bn*≤0 因为0<1,1m20.bm*≥0,所以0=∑/m im+/m+/< 所以0-∑fm+bm+*≤0,即X*是L的可行解
== 为整数 ： 对整数规划问题 j x X AX b s t IP z CX . 0 max == 0 . max 0 X AX b s t z CX 其松弛问题 L = = 0 . 1 : max X AX b s t 线性规划 L z CX 0 1 m j i n m j im j f x f + −= + 最优解X 0不是整数 定理：L1 割去了 L 0 的最优解并保留了 L 0 的所有整数解 证：把L0 的最优解X 0 代入 0 1 m j i n m j im j f x f + −= + 0 i 0 得 f , 与0 fi 0 1矛盾 所以L0 的最优解不是 L 1 的可行解 设X * = (b1 *, bi *, b n *)是L 0 的任一整数解 只需证 * , 0 1 m j i n m j im j f b f + −= + , 0 * 0 f im + 1 ， b m + j * 0 1 0 − + −= + m j n m j 即fi f i m j b 整数 因为fi0 1 , * 1 1 0 − + −= + m j n mj i i m j 所以f f b * 0 1 0 − + −= + m j n m j 所以fi f i m j b ，即X *是L1 的可行解 非基变量