运筹学 Operations Research §4.3割平面法 给定整数规划 maX Z=C x (IP): s.t. Ax=b x,≥0,整数,j=1,2,…,n 对应的松弛线性规划问题为 max 2=C x (LP): s.t. Ax=b x≥0 2021/2/20
2021/2/20 1 运 筹 学 Operations Research §4.3 割平面法 = = = x j n st Ax b z c x IP j T 0, , 1,2, , . . max ( ) : 整数 给定整数规划 对应的松弛线性规划问题为 = = 0 . . max ( ) : x st Ax b z c x LP T
运筹学 Operations Research 割平面法的基本思想: 利用单纯形法求解(LP),设得最优解x 若x*为整数解,则x即为P)的最优解; 否则,给(LP)增加一个约束条件--割 X K 平面,割去含x在内的(LP一部分 可行解,而不割去(P)的任一可行解 x1继续求解新的(LP,设得最优解为x", 继续上述步骤,直到得到(P)的最优 解为止 2021/2/20 2
2021/2/20 2 运 筹 学 Operations Research 割平面法的基本思想： . ( ) ( ) ( ) . ( ) ( ) ( ) ( ) . 解为止 继续上述步骤，直到得到 的最优 继续求解新的 ，设得最优解为 ， 可行解，而不割去 的任一可行解 平面，割去含 在内的 的一部分 否则，给 增加一个约束条件 割 若 为整数解，则 即为 的最优解； 利用单纯形法求解 ，设得最优解 IP LP x IP x LP LP x x IP LP x − −
运筹学 Operations Research 割平面的选取: WLOG设利用单纯形法求解(LP)最终得最优基B=(P,P2,…P 相应的单纯形表为 +∑ iO l +∑rx j=m+1 J 0 J=m+ 2021/2/20 3
2021/2/20 3 运 筹 学 Operations Research 割平面的选取： 相应的单纯形表为 W.L.O.G.设利用单纯形法求解(LP)最终得最优基B = (P1 ,P2 ,,Pm )， + = + = = = + = + 0 1 0 1 , 1,2, , z r x z x b x b i m n j m j j i n j m i i j j = − = − = = + = + n j m j j n j m i i i j j z z r x x b b x i m 1 0 1 0 , 1,2,
运筹学 Operations Research 单纯形表为 x m2+1 2 xn b 110 0 +2 l x201…0b2x+1b2+2…b27 x,0 0 M+1 M+2 bb N?2 w 0 z00 0 2 LP)的最优解为x=(bo,b2o,…bn,0,0,…0),最优值为-0 2021/2/20 4
2021/2/20 4 运 筹 学 Operations Research 单纯形表为 ( ) ( , , , ,0,0, ,0) . 1 0 2 0 0 0 LP x b b b z T 的最优解为 = m ，最优值为
运筹学 Operations Research 若b∈Z,则IP)的最优解为x=(b0,b ,m0 否则,不妨设b0丝Z(1≤k≤m),则单纯形表的第行对应 的方程为 ,+ k ∑bx=b0→xk=b∑ i=m+1 j=m+1 令b=[b]+f,其中b为b的整数部分,f为b的小数部分, fA0>0,/6∈[0,1,则 xk=b0-∑bx=([bo1+/)-∑(b]+/) J=m+1 ∑bJx1+∫6-∑ j=m+1 2021/2/20
2021/2/20 5 运 筹 学 Operations Research ( ) ( , , , ,0,0, ,0) . 0 1 0 2 0 0 T i b b bm 若b Z，则 IP 的最优解为x = 的方程为 否则，不妨设bk 0 Z(1 k m)，则单纯形表的第k行对应 = + = + + = = − n j m k k k kj j n j m k kj j x b x b x b b x 1 0 0 1 0 [ ] [ ] 0, [0,1), kj kj kj kj kj kj kj k kj b b f b b f b f f = + 令 ，其中 为 的整数部分， 为 的小数部分， 则 [ ] [ ] . ([ ] ) ([ ] ) 1 0 1 0 1 0 0 1 0 = + = + = + = + = − + − = − = + − + n j m k kj j n j m k kj j n j m k k kj kj j n j m k k kj j b b x f f x x b b x b f b f x