表4-6 6 0 0 C X X1 x1 0 3 0 23521 (22) 0 检验数均为负,基变量均为正整数,所得为最优解,即为最优解, maxZ=22,X=(3,1,3,0,2 为了便于学习,把割平面法步骤小结于下 1.把整数规划约束不等式的变量系数a和常量b全部整数化,然后加入松弛变量, 且暂不考虑整数约束条件,用单纯形法解相应线性规划得到最优解 2.求割平面 2.1设x为相应线性规划最优解中有分数值的一个变量,并且真分数部分是最大 的,以非基变量表示为 x=b+∑bx 其中:∈B(B是基变量下标集合) k∈K(K是非基变量下标集合) 22将b和b都分解成整数部分N和非整数部分f之和,(N不大于的b最大整 数) b=N+f这里0<f<1 bn=Nk+f这里0<f<1 例如 b=2,则N=2,∫ 则N=-1,f 于是x表示为: x=N+∑N4x+f+∑瓜x表 4-6 Cj 6 4 0 0 0 0 CB XB b 1 x 2 x 3 x 4 x 5 x 6 x 4 2 x 1 0 1 0 −1 0 1 6 1 x 3 1 0 0 1 0 1 2 − 0 3 x 3 0 0 1 2 0 −3 0 5 x 2 0 0 0 1 1 5 2 − C Z j j − （22） 0 0 0 −2 0 −1 检验数均为负，基变量均为正整数，所得为最优解，即为 IP 最优解， ( ) * max Z X = = 22, 3,1,3,0,2,0 为了便于学习，把割平面法步骤小结于下： 1.把整数规划约束不等式的变量系数 和常量 全部整数化，然后加入松弛变量， 且暂不考虑整数约束条件，用单纯形法解相应线性规划得到最优解； ij a i b 2.求割平面： 2.1 设 i x 为相应线性规划最优解中有分数值的一个变量，并且真分数部分是最大 的，以非基变量表示为： i i ik k x = + b ∑b xk （1） 其中： ( ) ( ) i B B k K K ∈ ∈ 是基变量下标集合 是非基变量下标集合 2.2 将bi 和bik 都分解成整数部分 N 和非整数部分 f 之和，（ 不大于的 最大整 数）： N b 0 1 0 1 i i i i ik ik ik ik b N f f b N f f = + < < = + < < 这里 这里 例如： 1 1 2 , 2, 2 2 b N = 则 = f = 1 5 , 1, 6 6 b N = − 则 = − f = 于是 i x 表示为： i ik k i k k ik k x = + N N ∑ x + f +∑ f x （2）