cj
3
2
1
0
0
0
0
CB
XB
b
x1
x2
x3
x4
x5
x6
x7
2
1
3
0
x2
x3
x1
x7
11/3
4/3
5
3
0
0
1
0
1
0
0
1
0
1
0
0
1/3
-1/12
1/2
0
1/3
1/6
0
0
1/3
5/12
1/2
0
0
0
0
1
cj-zj
0
0
0
-25/12
-5/6
-31/12
0
2
1
3
0
x2
x3
x1
x7
11/3
4/3
5
-2/3
0
0
1
0
1
例1用分枝定界法求解下面的整数规划：
已知其放松的线性规划的最优单纯形表：
cj
3
2
1
0
0
0
CB
XB
b
x1
x2
x3
x4
x5
x6
2
1
3
x2
x3
x1
11/3
4/3
5
0
0
1
1
0
0
0
1
0
1/3
-1/12
1/2
1/3
1/6
0
1/3
5/12
1/2
cj-zj
0
0
0
-25/12
-5/6
-31/12
解：由线性规划的最优单纯形表知其最优解为x1=5，x2=11/3，x3=4/3非整数解，最优值z0=71/3, x1=0，x2=0，x3=0为一整数可行解，目标函数值为z=0,定界 。分枝 ，相应的问题设为 ，解 如下表：
0
0
0
0
1
0
0
1/3
-1/12
1/2
-1/3
1/3
1/6
0
-1/3
1/3
5/12
1/2
-1/3
0
0
0Байду номын сангаас
1
cj-zj
0
0
0
-25/12
-5/6
-31/12
0
2
1
3
0
x2
x3
x1
x5
3
1
5
2
0
0
1
0
1
0
0
0
0
1
0
0
0
-1/4
1/2
1
0
0
0
1
0
1/4
1/2
1
1
1/2
0
-3
cj-zj
0
0
0
-5/4
0
-7/4
-5/2
得到一个整数最优解x1=5，x2=3，x3=1，最优值为22，因该最优解是满足整数条件，所以该整数规划的下界z=22。
同理求解另一个线性规划问题(要写出求解的单纯形表) ，因无可行解，因此该整数规划的上界也为22，所以整数规划的最优值为22，上面的这个解即为最优解。