不考虑整数解约束，解松弛问题的最优单纯形表为：a?票0101bCBXBX1X2X3X40110-11X3043101X40110a......1103/4-1/41/4X11017/43/41/4X200-1/2-1/2aZ=5/2得到非整数的最优解：×,=3/4, ×2=7/4, ×3=×4=0, max z=5/2
不考虑整数解约束，解松弛问题的最优单纯形表为： CB XB b 1 1 0 0 x1 x2 x3 x4 0 x3 1 -1 1 1 0 0 x4 4 3 1 0 1 σ 1 1 0 0 . . . . . . . 1 x1 3/4 1 0 -1/4 1/4 1 x2 7/4 0 1 3/4 1/4 Z=5/2 σ 0 0 -1/2 -1/2 得到非整数的最优解： x1 =3/4，x2 =7/4，x3 =x4 =0，max z=5/2
1013/4-1/41/4X11017/43/41/4X200Z=5/2-1/2-1/2g得到非整数的最优解：X,=3/4, X2=7/4, ×3=x4=0, max z=5/2不能满足整数最优解的要求。为此考虑将带有分数的最优解的可行域中分数部分割去，再求最优解可从最终计算表中得到非整数变量对应的关系式：344731244
1 x1 3/4 1 0 -1/4 1/4 1 x2 7/4 0 1 3/4 1/4 Z=5/2 σ 0 0 -1/2 -1/2 不能满足整数最优解的要求。为此考虑将带有分 数的最优解的可行域中分数部分割去，再求最优解。 可从最终计算表中得到非整数变量对应的关系式： 4 7 4 1 4 3 4 3 4 1 4 1 2 3 4 1 3 4 + + = − + = x x x x x x 得到非整数的最优解： x1 =3/4，x2 =7/4，x3 =x4 =0，max z=5/2
347X444为了得到整数最优解。将上式变量的系数和常数项都分解成整数和非负真分数两部分之和331(1+=x +-x4x+3+44然后将整数部分与分数部分分开，移到等式左右两边得到：33X4434
4 7 4 1 4 3 4 3 4 1 4 1 2 3 4 1 3 4 + + = − + = x x x x x x 为了得到整数最优解。将上式变量的系数和常数项都分 解成整数和非负真分数两部分之和 然后将整数部分与分数部分分开，移到等式左右两边， 得到： − = − + − = − + 2 3 4 1 3 3 4 4 1 4 3 4 3 1 4 1 4 3 4 3 x x x x x x x 4 3 1 4 1 4 3 4 3 4 1 ) 4 3 ( 1 2 3 4 1 3 4 + + = + + − + + = x x x x x x
3343344现考虑整数条件要求x1、×,都是非负整数，于是由条件可知x3、×也都是非负整数，这一点对以下推导是必要的，如不都是整数，则应在引入X3、×之前乘以适当常数，使之都是整数。·在上式中（其实只都乙武即寻）从等式左边看是整数；等式右边也应是整数。在等式岩边的（·）内是正数；所以等式右边必是非正数。就是说，右边的整数值最大是零。于是整数条件可由下式所替；≤4县为整数≤0A44
现考虑整数条件 ⚫ 要求x1、x2都是非负整数，于是由条件可知x3、x4也都是非 负整数,这一点对以下推导是必要的，如不都是整数，则应 在引入x3、x4之前乘以适当常数，使之都是整数。 ⚫ 在上式中(其实只考虑一式即可)从等式左边看是整数；等式 右边也应是整数。但在等式右边的(·)内是正数；所以等式 右边必是非正数。就是说，右边的整数值最大是零。于是整 数条件可由下式所代替； ) 0 4 1 4 3 ( 4 3 − x3 + x4 − = − + − = − + 2 3 4 1 3 3 4 4 1 4 3 4 3 1 4 1 4 3 4 3 x x x x x x x Max Z=x1+x2 -x1+x2≤1 3x1+x2 ≤4 x1 , x2≥0且为整数
3_x3+=x)≤04.·即-3x3-×≤-3这就得到一个切割方程（或称为切割约束），将它作为增加约束条件，再解例3。引入松弛变量x5，得到等式-3×3-×4+×5=-3将这新的约束方程加到最终计算表11000CjCBbXBX1X2X3X4X510013/41/4-1/4X103/407/411/41X20001-3-1-3X5000-5/2-1/2-1/2Ci-Zj
⚫ 即 -3x3 -x4≤-3 这就得到一个切割方程(或称为切割约束)，将它作为 增加约束条件，再解例3。 ⚫ 引入松弛变量x5，得到等式 -3x3 -x4 +x5 =-3 ⚫ 将这新的约束方程加到最终计算表 ) 0 4 1 4 3 ( 4 3 − x3 + x4 cj 1 1 0 0 0 CB XB b x1 x2 x3 x4 x5 1 1 0 x1 x2 x5 3/4 7/4 -3 1 0 0 0 1 0 -1/4 3/4 -3 1/4 1/4 -1 0 0 1 cj-zj -5/2 0 0 -1/2 -1/2 0