运筹学讲义 x110 0 bn 1 b bnb 由单纯形表知,(LP)的最优解为x=(b0。b20…,bn00…0),最优值为z0 若bo为整数,i=12…m,则(lP)的最优解为x=(b,b20,…,bm0,0.0,…0) 否则,不妨设bo(1≤k≤m)不是整数,则单纯形表的第k行对应的方程为 x+∑b2x=b0→xk=bo-∑b 令b=[b]+/,j= 1…,n,其中[b]为b的整数部分(不超过b的最大整 数),J为b的分数(小数)部分,J60>0,J∈[D,1,j=m+1,m+2,…,n,则上述方程即为 ∑bx=([bol+fo) ([b]+/)x ∑bJx1+f0-∑f 令A0-∑x≤0,称之为以第k行为源行( source row)的柯莫利割平面( Gomory cutting plane),简称为割平面 引入松弛变量xn1≥0,则割平面即为 f0-∑/x≤0分f-∑ 04-∑ 在算法的设计上,为尽可能快地“割去”(LP)的非整数解,常令f0=max{f0>0},再以第k运 筹 学 讲 义 2 由单纯形表知， (LP) 的最优解为 T b b bm x ( , , , ,0,0, ,0) = 10 20  0  ，最优值为 0 z . 若 i0 b 为整数, i = 1,2,  ,m，则 (IP) 的最优解为 T b b bm x ( , , , ,0,0, ,0) = 10 20  0  ； 否则，不妨设 (1 ) bk 0  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 . 令 bkj = [bkj ] + f kj , j = 0,m +1,m +1,  ,n ，其中 [ ] bkj 为 kj b 的整数部分（不超过 kj b 的最大整 数）， kj f 为 kj b 的分数（小数）部分， f k 0  0; f kj [0,1), j = m +1,m + 2,  ,n ，则上述方程即为 [ ] [ ] . ([ ] ) ([ ] ) 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 令 0 1 0 −   = + n j m k kj j f f x ，称之为以第 k 行为源行（source row）的柯莫利割平面（Gomory cutting plane），简称为割平面. 引入松弛变量 xn+1  0 ，则割平面即为 1 0 1 1 1 0 1 0 0 0 n k n j m n kj j n j m k kj j n j m k kj j f − f x   f − f x + x =  − f x + x = − f + = + + = + = +    . 在算法的设计上，为尽可能快地“割去”(LP) 的非整数解，常令 max{ 0} 0 1 0 =    i i m k f f ，再以第 k