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`