Home > Operation Research calculators > Simplex method example


7. Branch and Bound method example ( Enter your problem )
  1. Algorithm
  2. Example-1
  3. Example-2
Other related methods
  1. Simplex (BigM) method
  2. Two-Phase method
  3. Graphical method
  4. Primal to dual conversion
  5. Dual simplex method
  6. Integer simplex method
  7. Branch and Bound method
  8. 0-1 Integer programming problem

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
A
`x_1=8,x_2=2.25`
`Z_A=35.25`
`Z_L=34`
Solution 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
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




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
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




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
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 Submit Here


Share with your friends
 
Copyright © 2018. All rights reserved. Terms, Privacy