运筹学讲义 §6.3.1割平面法(1) 给定整数规划 max (IP): s.L. Ax=b x20整数,j=12…n 对应的松弛线性规划问题为 max 2=c (LP): s.L. Ax=b 0 割平面法的基本思想 利用单纯形法求解(LP),设得其最优解为x’.若x 是整数解,则由§6.2Thl推论知,x即为(P)的最优 解;否则,设法给(LP)增加一个约束条件(割平面),将 K 含x在内的(LP)的一部分可行解“割”去,但不割去(lP 的任一可行解.然后,利用对偶单纯形法求解增加了割平 A 面后的新的(LP),设得其最优解为x”.对x”重复以上 步骤,直到求得(P)的最优解或判明(P)无最优解为止 割平面的选取 W.L.O.G.设利用单纯形法求解(LP)最终得最优基B=(F,P2…P),(LP)关于基B的典式 为 x+∑bx1=b1=12…,mx1=b-∑x,1=12 S 相应的单纯形表为运 筹 学 讲 义 1 §6.3.1 割平面法（1） 给定整数规划       = = = 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 . 割平面法的基本思想： 利用单纯形法求解 (LP) ，设得其最优解为  x .若  x 是整数解，则由§6.2 Th1 推论知，  x 即为 (IP) 的最优 解；否则，设法给 (LP) 增加一个约束条件（割平面），将 含  x 在内的 (LP) 的一部分可行解“割”去，但不割去 (IP) 的任一可行解.然后，利用对偶单纯形法求解增加了割平 面后的新的 (LP) ，设得其最优解为  x .对  x 重复以上 步骤，直到求得 (IP) 的最优解或判明 (IP) 无最优解为止. 割平面的选取： W.L.O.G.设利用单纯形法求解 (LP) 最终得最优基 ( , , , ) B = P1 P2  Pm ，(LP) 关于基 B 的典式 为        + = + = =   = + = + 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 ij j         = − = − =    = + = + n j m j j n j m i i ij j z z r x x b b x i m 1 0 1 0 , 1,2,, ， 相应的单纯形表为