Home > Operation Research calculators > Simplex method example

7. Branch and Bound method example ( Enter your problem )
 AlgorithmExample-1Example-2 Other related methods

2. Example-1

1. Find solution using Branch and Bound method
MAX Z = 3x1 + 5x2
subject to
2x1 + 4x2 <= 25
x1 <= 8
2x2 <= 10
and x1,x2 >= 0

Solution:
Solution stpes by BigM method, Graphical method

 Max Z =  3 x_1  +  5 x_2
subject to
  2 x_1  +  4 x_2 ≤ 25   x_1 ≤ 8  2 x_2 ≤ 10
and x_1,x_2 >= 0;

Solution is
Max Z_(A)=35.25 (x_1=8,x_2=2.25)

and Z_L=34 (x_1=8,x_2=2) obtainted by the rounded off solution values.

The branch and bound diagram
 Ax_1=8,x_2=2.25Z_A=35.25Z_L=34Solution stpes by BigM method, Graphical method

In Sub-problem A, x_2(=2.25) must be an integer value, so two new constraints are created, x_2<=2 and x_2>=3

Sub-problem B : Solution is found by adding x_2<=2.
Solution stpes by BigM method, Graphical method
 Max Z =  3 x_1  +  5 x_2
subject to
  2 x_1  +  4 x_2 ≤ 25   x_1 ≤ 8  2 x_2 ≤ 10   x_2 ≤ 2
and x_1,x_2 >= 0;

Solution is
Max Z_(B)=34 (x_1=8,x_2=2)
and Z_L=34 (x_1=8,x_2=2) obtainted by the rounded off solution values.
This Problem has integer solution, so no further branching is required.
Sub-problem C : Solution is found by adding x_2>=3.
Solution stpes by BigM method, Graphical method
 Max Z =  3 x_1  +  5 x_2
subject to
  2 x_1  +  4 x_2 ≤ 25   x_1 ≤ 8  2 x_2 ≤ 10   x_2 ≥ 3
and x_1,x_2 >= 0;

Solution is
Max Z_(C)=34.5 (x_1=6.5,x_2=3)
and Z_L=33 (x_1=6,x_2=3) obtainted by the rounded off solution values.

The branch and bound diagram
 Ax_1=8,x_2=2.25Z_A=35.25Z_L=34Solution stpes by BigM method, Graphical method x_2≤2 x_2≥3 Bx_1=8,x_2=2Z_B=34Z_L=34Solution stpes by BigM method, Graphical method Cx_1=6.5,x_2=3Z_C=34.5Z_L=33Solution stpes by BigM method, Graphical method

In Sub-problem C, x_1(=6.5) must be an integer value, so two new constraints are created, x_1<=6 and x_1>=7

Sub-problem D : Solution is found by adding x_1<=6.
Solution stpes by BigM method, Graphical method
 Max Z =  3 x_1  +  5 x_2
subject to
  2 x_1  +  4 x_2 ≤ 25   x_1 ≤ 8  2 x_2 ≤ 10   x_2 ≥ 3   x_1 ≤ 6
and x_1,x_2 >= 0;

Solution is
Max Z_(D)=34.25 (x_1=6,x_2=3.25)
and Z_L=33 (x_1=6,x_2=3) obtainted by the rounded off solution values.
Sub-problem E : Solution is found by adding x_1>=7.
Solution stpes by BigM method, Graphical method
 Max Z =  3 x_1  +  5 x_2
subject to
  2 x_1  +  4 x_2 ≤ 25   x_1 ≤ 8  2 x_2 ≤ 10   x_2 ≥ 3   x_1 ≥ 7
and x_1,x_2 >= 0;

Solution is
This Problem has an infeasible solution, so this branch is terminated.

The branch and bound diagram
 Ax_1=8,x_2=2.25Z_A=35.25Z_L=34Solution stpes by BigM method, Graphical method x_2≤2 x_2≥3 Bx_1=8,x_2=2Z_B=34Z_L=34Solution stpes by BigM method, Graphical method Cx_1=6.5,x_2=3Z_C=34.5Z_L=33Solution stpes by BigM method, Graphical method x_1≤6 x_1≥7 Dx_1=6,x_2=3.25Z_D=34.25Z_L=33Solution stpes by BigM method, Graphical method EInfeasible SolutionSolution stpes by BigM method, Graphical method

In Sub-problem D, x_2(=3.25) must be an integer value, so two new constraints are created, x_2<=3 and x_2>=4

Sub-problem F : Solution is found by adding x_2<=3.
Solution stpes by BigM method, Graphical method
 Max Z =  3 x_1  +  5 x_2
subject to
  2 x_1  +  4 x_2 ≤ 25   x_1 ≤ 8  2 x_2 ≤ 10   x_2 ≥ 3   x_1 ≤ 6   x_2 ≤ 3
and x_1,x_2 >= 0;

Solution is
Max Z_(F)=33 (x_1=6,x_2=3)
and Z_L=33 (x_1=6,x_2=3) obtainted by the rounded off solution values.
This Problem has integer solution, so no further branching is required.
Sub-problem G : Solution is found by adding x_2>=4.
Solution stpes by BigM method, Graphical method
 Max Z =  3 x_1  +  5 x_2
subject to
  2 x_1  +  4 x_2 ≤ 25   x_1 ≤ 8  2 x_2 ≤ 10   x_2 ≥ 3   x_1 ≤ 6   x_2 ≥ 4
and x_1,x_2 >= 0;

Solution is
Max Z_(G)=33.5 (x_1=4.5,x_2=4)
and Z_L=32 (x_1=4,x_2=4) obtainted by the rounded off solution values.
Z_(G)=33.5 < Z_(B)=34, so no further branching is required.

The branch and bound diagram
 Ax_1=8,x_2=2.25Z_A=35.25Z_L=34Solution stpes by BigM method, Graphical method x_2≤2 x_2≥3 Bx_1=8,x_2=2Z_B=34Z_L=34Solution stpes by BigM method, Graphical method Cx_1=6.5,x_2=3Z_C=34.5Z_L=33Solution stpes by BigM method, Graphical method x_1≤6 x_1≥7 Dx_1=6,x_2=3.25Z_D=34.25Z_L=33Solution stpes by BigM method, Graphical method EInfeasible SolutionSolution stpes by BigM method, Graphical method x_2≤3 x_2≥4 Fx_1=6,x_2=3Z_F=33Z_L=33Solution stpes by BigM method, Graphical method Gx_1=4.5,x_2=4Z_G=33.5Z_L=32Solution stpes by BigM method, Graphical method

The branch and bound algorithm thus terminated and the optimal integer solution is :
Z_(B)=34 and x_1=8,x_2=2

This material is intended as a summary. Use your textbook for detail explanation.
Any bug, improvement, feedback then Submit Here