2. Capital Budgeting Problem  1
1. Find solution using 01 Integer programming problem method MAX Z = 300x1 + 90x2 + 400x3 + 150x4 subject to 35000x1 + 10000x2 + 25000x3 + 90000x4 <= 120000 4x1 + 2x2 + 7x3 + 3x4 <= 12 x1 + x2 <= 1 and x1,x2,x3,x4 >= 0
Solution: To apply branch and bound method, the following 4 constraints have to be added to the LP model. `x_1<=1`
`x_2<=1`
`x_3<=1`
`x_4<=1`
Solution stpes by BigM method
Max `Z`  `=`  ``  `300`  `x_1`  ` + `  `90`  `x_2`  ` + `  `400`  `x_3`  ` + `  `150`  `x_4` 
 subject to  ``  `35000`  `x_1`  ` + `  `10000`  `x_2`  ` + `  `25000`  `x_3`  ` + `  `90000`  `x_4`  ≤  `120000`  ``  `4`  `x_1`  ` + `  `2`  `x_2`  ` + `  `7`  `x_3`  ` + `  `3`  `x_4`  ≤  `12`  ``  ``  `x_1`  ` + `  ``  `x_2`        ≤  `1`  ``  ``  `x_1`           ≤  `1`     ``  ``  `x_2`        ≤  `1`        ``  ``  `x_3`     ≤  `1`           ``  ``  `x_4`  ≤  `1` 
 and `x_1,x_2,x_3,x_4 >= 0; ` 
Solution is Max `Z_(A)=750` `(x_1=1,x_2=0,x_3=1,x_4=0.3333)`
and `Z_L=700` `(x_1=1,x_2=0,x_3=1,x_4=0)` obtainted by the rounded off solution values.
The branch and bound diagram
A `x_1=1,x_2=0,x_3=1,x_4=0.3333` `Z_A=750` `Z_L=700` Solution stpes by BigM method 
In Subproblem A, `x_4(=0.3333)` must be an integer value, so two new constraints are created, `x_4=0` and `x_4=1`
Subproblem B : Solution is found by adding `x_4=0`. Solution stpes by BigM method
Max `Z`  `=`  ``  `300`  `x_1`  ` + `  `90`  `x_2`  ` + `  `400`  `x_3`  ` + `  `150`  `x_4` 
 subject to  ``  `35000`  `x_1`  ` + `  `10000`  `x_2`  ` + `  `25000`  `x_3`  ` + `  `90000`  `x_4`  ≤  `120000`  ``  `4`  `x_1`  ` + `  `2`  `x_2`  ` + `  `7`  `x_3`  ` + `  `3`  `x_4`  ≤  `12`  ``  ``  `x_1`  ` + `  ``  `x_2`        ≤  `1`  ``  ``  `x_1`           ≤  `1`     ``  ``  `x_2`        ≤  `1`        ``  ``  `x_3`     ≤  `1`           ``  ``  `x_4`  ≤  `1`           ``  ``  `x_4`  =  `0` 
 and `x_1,x_2,x_3,x_4 >= 0; ` 
Solution is Max `Z_(B)=700` `(x_1=1,x_2=0,x_3=1,x_4=0)` and `Z_L=700` `(x_1=1,x_2=0,x_3=1,x_4=0)` 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_4=1`. Solution stpes by BigM method
Max `Z`  `=`  ``  `300`  `x_1`  ` + `  `90`  `x_2`  ` + `  `400`  `x_3`  ` + `  `150`  `x_4` 
 subject to  ``  `35000`  `x_1`  ` + `  `10000`  `x_2`  ` + `  `25000`  `x_3`  ` + `  `90000`  `x_4`  ≤  `120000`  ``  `4`  `x_1`  ` + `  `2`  `x_2`  ` + `  `7`  `x_3`  ` + `  `3`  `x_4`  ≤  `12`  ``  ``  `x_1`  ` + `  ``  `x_2`        ≤  `1`  ``  ``  `x_1`           ≤  `1`     ``  ``  `x_2`        ≤  `1`        ``  ``  `x_3`     ≤  `1`           ``  ``  `x_4`  ≤  `1`           ``  ``  `x_4`  =  `1` 
 and `x_1,x_2,x_3,x_4 >= 0; ` 
Solution is Max `Z_(C)=595` `(x_1=0,x_2=0.5,x_3=1,x_4=1)` and `Z_L=550` `(x_1=0,x_2=0,x_3=1,x_4=1)` obtainted by the rounded off solution values. `Z_(C)=595 < Z_(B)=700`, so no further branching is required.

The branch and bound diagram
A `x_1=1,x_2=0,x_3=1,x_4=0.3333` `Z_A=750` `Z_L=700` Solution stpes by BigM method  `x_4=0`   `x_4=1`  B `x_1=1,x_2=0,x_3=1,x_4=0` `Z_B=700` `Z_L=700` Solution stpes by BigM method   C `x_1=0,x_2=0.5,x_3=1,x_4=1` `Z_C=595` `Z_L=550` Solution stpes by BigM method 
The 01 Integer programming problem algorithm thus terminated and the optimal integer solution is : `Z_(B)=700` and `x_1=1,x_2=0,x_3=1,x_4=0`
This material is intended as a summary. Use your textbook for detail explanation. Any bug, improvement, feedback then
