运筹学 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
运筹学 Operations Research 柯莫利割平面( Gomory cutting plane): ∑fx≤ =m+1 台→f0-∑fx+xm=0 ∑f6 x+x j=m+1 为加快计算的速度,常令 ko max 1≤i<m 2021/2/20 6
2021/2/20 6 运 筹 学 Operations Research 柯莫利割平面（Gomory cutting plane）: 1 0 1 1 1 0 1 0 0 0 n k n j m kj j n n j m k kj j n j m k kj j f x x f f f x x f f x − + = − − + = − + = + + = + = + 为加快计算的速度，常令 max{ 0} 0 1 0 = i i m k f f
运筹学 Operations Research 割平面的两个性质: Thl割平面割去(LP)的非整数最优解 证:仅需证x=(bo,b2…,bn0…,0)不满足割平面即可 fA0-∑fx=f0>0 J=m+ x=(bo,b2o,…,bn00,…0)不满足割平面 2021/2/20 7
2021/2/20 7 运 筹 学 Operations Research 割平面的两个性质： Th1 割平面割去(LP)的非整数最优解. ( , , , ,0,0, ,0) . 证：仅需证x = b1 0 b2 0 bm0 T 不满足割平面即可 0 0 1 0 − = = + k n j m k kj j f f x f ( , , , ,0,0, ,0) . x = b1 0 b2 0 bm0 T 不满足割平面 ▌
运筹学 Operations Research 7h2割平面不割去(P)的任一可行解 证:仅需证(P)的任一可行解都满足割平面即口 V众=(x,x2,…,文n)∈K(P),则∈K(LP 又x满足典式 =b0-∑b=([bl+f)-∑(b]+f6) J=m+I toko ∑f J=m+1 J=m+1 k, Luko ∈ A0-∑f年∈Z j=m+1 J=n+1 2021/2/20 8
2021/2/20 8 运 筹 学 Operations Research Th2 割平面不割去(IP)的任一可行解. 证：仅需证(IP)的任一可行解都满足割平面即可. ˆ (ˆ , ˆ , , ˆ ) ( ) ˆ ( ). x x1 x2 x K IP x K LP T = n ，则 又x ˆ满足典式 [ ] [ ]ˆ ˆ . ˆ ˆ ([ ] ) ([ ] )ˆ 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 ˆ [ ] [ ]ˆ , 1 x b 0 b x Z n j m k k − kj j = + ， ˆ . 1 f 0 f x Z n j m k − kj j = +
运筹学 Operations Research 又0-∑ x:≥0 fro j=m+1 f6x1≤0 J=m+1 2021/2/20
2021/2/20 9 运 筹 学 Operations Research 又 ˆ 0 1， 0 ˆ 0 1 0 − = + k f x n j m k kj j f f x f kj j ˆ 0 1 0 − = + n j m k kj j f f x ▌
运筹学 Operations Research 增添割平面后的新单纯形表: 对松弛线性规划问题 maX Z=C x (LP): s.t. Ax=b 增添割平面后得新的线性规划 max2三Cx s.t. Ax=b ∑fx1+ m+1 x≥0,j=1,2,…,n,n+1 2021/2/20 10
2021/2/20 10 运 筹 学 Operations Research 增添割平面后得新的线性规划 = + − + = − = = + = + 0, 1,2, , , 1. . . max 1 0 1 x j n n f x x f st Ax b z c x j n k n j m kj j T 增添割平面后的新单纯形表： 对松弛线性规划问题 = = 0 . . max ( ) : x st Ax b z c x LP T