福01100bCBXBX5X1X2X3X400113/4-1/41/4X110103/41/4714X2[-3 ]00-1-301X5000-1/2-1/2Z=5/2a由于X1、X2的值已都是整数，角解题已完成
C B X B b 1 1 0 0 0 x 1 x 2 x 3 x 4 x 5 1 x 1 3/4 1 0 -1/4 1/4 0 1 x 2 7/4 0 1 3/4 1/4 0 0 x 5 - 3 0 0 - 3 - 1 1 Z=5/2 σ 0 0 -1/2 -1/2 0 1 x 1 1 1 0 0 1/3 1/12 1 x 2 1 0 1 0 0 1/4 0 x 3 1 0 0 1 1/3 -1/3 Z=2 σ 0 0 0 -1/3 -1/3 由于 x 1 、 x2的值已都是整数，解题已完成
注：新约束-3x3-×4≤-3的几何意义。上述约束中以x1，x2表示x3，x4，得FX2≤1，其图形见下图。-X,+X2=13X,+X2=4X2≤1
注：新约束-3x3-x4 -3的几何意义。 上述约束中以x1，x2 表示x3，x4 ，得 x2 1， 其图形见下图。 3x1+x2=4 -x1+x2=1 x2 1
【练习】已知整数规划max z = 3x; + 2x2[2x+3x2≤142x+x2≤9X,≥0且为整数【解】不考虑整数约束，松弛问题的最优表如下2030CjbCBXBX4X1X2X32015/21/21/2X23011/43/413/4X100^j 1/4-5/4
【练习】已知整数规划 + + = + , 0且为整数 2 9 2 3 14 max 3 2 1 2 1 2 1 2 1 2 x x x x x x z x x 【解】不考虑整数约束，松弛问题的最优表如下 cj 3 2 0 0 b CB XB x1 x2 x3 x4 2 x2 0 1 1/2 －1/2 5/2 3 x1 1 0 －1/4 3/4 13/4 λj 0 0 －1/4 －5/4
3200::Cjb:8XBCBX1X2X3X40215/21/2-1/2X2310—1/43/413/4X100入j1/4-5/4最优解X=（一1/2，3/4，0，0）T，X1、×2不满足整数要求，选择x2行进行分割：X+-x=X,+X -X +x=2+11X2 -X4 -2=-1x,-1x42XsX4 =得到Gomory约束添加到最优表中，得
cj 3 2 0 0 b CB XB x1 x2 x3 x4 2 x2 0 1 1/2 －1/2 5/2 3 x1 1 0 －1/4 3/4 13/4 λj 0 0 －1/4 －5/4 最优解X=(－1/2，3/4，0，0)T ， x1 、x2不满足整数要求， 选择x2行进行分割： 2 5 2 4 1 2 3 1 x2 + x − x = 2 1 2 4 1 2 3 4 1 x2 + x − x + x = 2+ 2 1 2 4 1 2 3 1 得到Gomory约束 x5 − x − x = − 添加到最优表中，得 2 4 1 2 3 1 2 4 2 1 x − x − 2 = − x − x
32000Cj：b.CBXBX1X2X4X3X502101/25/2 X21/231001/43/413/4X10001-1/2-1/2-1/2X5000Λj1/45/402101/22-1X2310011/27/2X1000111-2X3000Λj-1- 1/2Xi+x-1xs=2xi行:X +x4-Xs-3=-xs+X=将约束添加到最优表中，得
2 7 2 5 1 x1 + x4 − x = cj 3 2 0 0 0 C b B XB x1 x2 x3 x4 x5 2 x2 0 1 1/2 －1/2 0 5/2 3 x1 1 0 －1/4 3/4 0 13/4 0 x5 0 0 －1/2 －1/2 1 －1/2 λj 0 0 －1/4 －5/4 0 2 x2 0 1 0 －1 ½ 2 3 x1 1 0 0 1 －1/2 7/2 0 x3 0 0 1 1 －2 1 λj 0 0 0 －1 －1/2 x1行： 将约束 2 1 2 5 1 x6 − x = − 添加到最优表中，得 2 1 2 5 1 x1 + x4 − x5 −3 = − x +