运筹学讲义 行为源行作割平面 割平面的两个性质: Th割平面Ao-∑/x,≤0割去(LP)的非整数最优解 J=m+1 证明:显然,仅需证明(LP)的最优解x=(b0,b20…,bn,00…,0)不满足割平面即可 x=0,j=m+1,“n 将x代入割平面,得f0-∑fx J6o>0,∴x不满足割平面 故将割平面添加到(LP)后,x已不再满足新(LP)的约束条件 x≥0 即割平面已将x割去 注:将割平面作为约束条件添加到(LP)后,原(LP)的最优解已不在新(LP)的可行域中 Th2割平面f-∑/x≤0不割去(P)的任一可行解 证明:显然,仅需证明(lP)的任一可行解均满足割平面即 =(x,x2,…,文n)∈K(P),则由K(P)K(LP)知,∈K(LP) 显然,x满足典式,特别地 =b0-∑b=([b61+J)-∑(b]+f) bo-∑b]+f0-∑/ 显然,,bo-∑[b均为整数,∴fA0-∑元也为整数运 筹 学 讲 义 3 行为源行作割平面. 割平面的两个性质： Th1 割平面 0 1 0 −   = + n j m k kj j f f x 割去 (LP) 的非整数最优解. 证明：显然，仅需证明 (LP) 的最优解 T b b bm x ( , , , ,0,0, ,0) = 10 20  0  不满足割平面即可. 将 x 代入割平面，得 0 0 0, 1, , 1 0 − =  = = + = +  k n x j m n j m k kj j f f x f j  ， x 不满足割平面. 故将割平面添加到 (LP) 后， x 已不再满足新 (LP) 的约束条件         −  = = + 0 0 1 0 x f f x Ax b n j m k kj j ， 即割平面已将 x 割去.▌ 注：将割平面作为约束条件添加到 (LP) 后，原 (LP) 的最优解已不在新 (LP) 的可行域中. Th2 割平面 0 1 0 −   = + n j m k kj j f f x 不割去 (IP) 的任一可行解. 证明：显然，仅需证明 (IP) 的任一可行解均满足割平面即可. ˆ (ˆ , ˆ , , ˆ ) ( ) 1 2 x x x x K IP T  =  n  ，则由 K(IP)  K(LP) 知， x ˆ  K(LP) . 显然， 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 显然， k x ˆ ， = + − n j m k kj j b b x 1 0 [ ] [ ]ˆ 均为整数， = +  − n j m k kj j f f x 1 0 ˆ 也为整数