运筹学讲义 又J0-∑/,≤J60<1,…∴f-∑≤0,故满足割平面■ 注:将割平面作为约束条件添加到(P)后,原(P)的可行解仍在新(P)的可行域中 增添割平面后的新单纯形表 对松弛线性规划问题 (LP): s.t. Ax= b x≥0 增添割平面f0-∑/x,50分f0-∑x1+xm=0分-∑/x+xm=-后, 得新的线性规划 max 2=c x s.t. Ax=b x1≥0,j=1,2,…,n,n+1 取基B:=/B0 071/其中0=(00,…0)y∈R", 则新单纯形表为 x201…02+1b xbb:b 1 b x00…0-+1一天测 z|00 o r he (新(LP)的单纯形表仅是在原(LP)的单纯形表中增加松弛变量xn的行、列而已!)运 筹 学 讲 义 4 又 ˆ 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 ，故 x ˆ 满足割平面.▌ 注：将割平面作为约束条件添加到 (IP) 后，原 (IP) 的可行解仍在新 (IP) 的可行域中. 增添割平面后的新单纯形表： 对松弛线性规划问题       = = 0 . . max ( ) : x st Ax b z c x LP T ， 增添割平面 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 + = + + = + = +    后， 得新的线性规划         = + − + = − = = + = +  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 1 0 : T B B ，其中 T m 0 = (0,0,, 0)  R ， 则新单纯形表为 （新 (LP) 的单纯形表仅是在原 (LP) 的单纯形表中增加松弛变量 n+1 x 的行、列而已！）