运筹学 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 不满足割平面 ▌