Home > Operation Research calculators > Simplex method example


7. Branch and Bound method example
( Enter your problem )

2. Example1
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
In Subproblem A, `x_2(=2.25)` must be an integer value, so two new constraints are created, `x_2<=2` and `x_2>=3`
Subproblem 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.
 Subproblem 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
In Subproblem C, `x_1(=6.5)` must be an integer value, so two new constraints are created, `x_1<=6` and `x_1>=7`
Subproblem 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.
 Subproblem 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
In Subproblem D, `x_2(=3.25)` must be an integer value, so two new constraints are created, `x_2<=3` and `x_2>=4`
Subproblem 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.
 Subproblem 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
A `x_1=8,x_2=2.25` `Z_A=35.25` `Z_L=34` Solution stpes by BigM method, Graphical method  `x_2≤2`   `x_2≥3`  B `x_1=8,x_2=2` `Z_B=34` `Z_L=34` Solution stpes by BigM method, Graphical method   C `x_1=6.5,x_2=3` `Z_C=34.5` `Z_L=33` Solution stpes by BigM method, Graphical method    `x_1≤6`   `x_1≥7`    D `x_1=6,x_2=3.25` `Z_D=34.25` `Z_L=33` Solution stpes by BigM method, Graphical method   E
Infeasible Solution
Solution stpes by BigM method, Graphical method    `x_2≤3`   `x_2≥4`    F `x_1=6,x_2=3` `Z_F=33` `Z_L=33` Solution stpes by BigM method, Graphical method   G `x_1=4.5,x_2=4` `Z_G=33.5` `Z_L=32` Solution 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



Share with your friends, if solutions are helpful to you.


