We use cookies to improve your experience on our site and to show you relevant advertising. By browsing this website, you agree to our use of cookies. Learn more   

AtoZmath.com
Support us
(New) All problem can be solved using search box
I want to sell my website www.AtoZmath.com with complete code
Home What's new College Algebra Games Feedback About us
Algebra Matrix & Vector Numerical Methods Statistical Methods Operation Research Word Problems Calculus Geometry Pre-Algebra


Home > Operation Research calculators > Branch and Bound method example
7. Branch and Bound method example ( Enter your problem )
( Enter your problem )
  1. Algorithm
  2. Example-1
  3. Example-2
 		Other related methods
  1. Formulate linear programming model
  2. Graphical method
  3. Simplex method (BigM method)
  4. Two-Phase method
  5. Primal to dual conversion
  6. Dual simplex method
  7. Integer simplex method
  8. Branch and Bound method
  9. 0-1 Integer programming problem
  10. Revised Simplex method
1. Algorithm
(Previous example)		3. Example-2
(Next example)

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 steps 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
A
`x_1=8,x_2=2.25`
`Z_A=35.25`
`Z_L=34`
Solution steps 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 steps 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 steps 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
A
`x_1=8,x_2=2.25`
`Z_A=35.25`
`Z_L=34`
Solution steps 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 steps by
BigM method,
Graphical method		C
`x_1=6.5,x_2=3`
`Z_C=34.5`
`Z_L=33`
Solution steps 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 steps 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 steps 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
A
`x_1=8,x_2=2.25`
`Z_A=35.25`
`Z_L=34`
Solution steps 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 steps by
BigM method,
Graphical method		C
`x_1=6.5,x_2=3`
`Z_C=34.5`
`Z_L=33`
Solution steps 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 steps by
BigM method,
Graphical method		E

Infeasible Solution

Solution steps 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 steps 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 steps 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 steps 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 steps by
BigM method,
Graphical method		C
`x_1=6.5,x_2=3`
`Z_C=34.5`
`Z_L=33`
Solution steps 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 steps by
BigM method,
Graphical method		E

Infeasible Solution

Solution steps 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 steps by
BigM method,
Graphical method		G
`x_1=4.5,x_2=4`
`Z_G=33.5`
`Z_L=32`
Solution steps 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


1. Algorithm
(Previous example)		3. Example-2
(Next example)


Share this solution or page with your friends.


Home What's new College Algebra Games Feedback About us
 
Copyright © 2024. All rights reserved. Terms, Privacy
 
 

.