首先不考虑 x i ∈ Z x_i\in Z xi​∈Z的约束条件，即问题 B B B： max ⁡ z = 40 x 1 + 90 x 2 s . t . { 9 x 1 + 7 x 2 ≤ 56 7 x 1 + 20 x 2 ≤ 70 x i ≥ 0 \begin{array}{l}\max z=40x_1+90x_2 \\ s.t.\left\{\begin{array}{c} 9x_1+7x_2\le 56\\ 7x_1+20x_2\le 70\\ x_i\ge 0 \end{array}\right.\end{array} maxz=40x1​+90x2​s.t.⎩⎨⎧​9x1​+7x2​≤567x1​+20x2​≤70xi​≥0​​，求得此问题的最优解： x ∗ = ( 4.81 , 1.82 ) T ,   z ∗ = 356 x^*=(4.81,1.82)^T,~z^*=356 x∗=(4.81,1.82)T, z∗=356

基于 x 1 x_1 x1​，对原问题增加两个约束条件 x 1 ≤ 4 , x 1 ≥ 5 x_1\le 4,x_1\ge 5 x1​≤4,x1​≥5（也可以对 x 2 x_2 x2​增加约束条件），从而将原问题分解为两个子问题 B 1 B_1 B1​和 B 2 B_2 B2​，不考虑整数条件解问题 B 1 B_1 B1​和 B 2 B_2 B2​，得到各自的最优解 B 1 :   x ∗ = ( 4 , 2.1 ) T , z ∗ = 349 B_1:~x^*=(4,2.1)^T,z^*=349 B1​: x∗=(4,2.1)T,z∗=349， B 2 :   x ∗ = ( 5 , 1.57 ) T , z ∗ = 341 B_2:~x^*=(5,1.57)^T,z^*=341 B2​: x∗=(5,1.57)T,z∗=341

注：若 B B B没有可行解则直接停止；若 B B B的最优解符合整数条件，则直接得到最优解

得到 0 ≤ z ∗ ≤ 349 0\le z^*\le 349 0≤z∗≤349，继续对问题 B 1 B_1 B1​和 B 2 B_2 B2​进行分解，由于 349 > 341 349>341 349>341，因此先分解 B 1 B_1 B1​，增加两个约束条件 x 2 ≤ 2 , x 2 ≥ 3 x_2\le 2,x_2\ge 3 x2​≤2,x2​≥3，分解为两个子问题 B 3 B_3 B3​和 B 4 B_4 B4​

B 3 B_3 B3​的解都是整数，因此更新下界 340 ≤ z ∗ ≤ 341 340\le z^*\le 341 340≤z∗≤341， B 4 B_4 B4​的最优值小于下界，因此进行剪枝

注：求出一个可行解（满足整数条件）才更新下界

注：若求出的最优值小于当期下界，则进行剪枝，不再对该问题进行分支

对 B 2 B_2 B2​进行分解得到 B 5 B_5 B5​和 B 6 B_6 B6​，对于 B 5 B_5 B5​，最优值小于下界，剪枝； B 6 B_6 B6​无可行解

最终得到最优整数解为 x ∗ = ( 4 , 2 ) T , z ∗ = 340 x^*=(4,2)^T,z^*=340 x∗=(4,2)T,z∗=340