Homework Soursesolve the following problem using branch and bound Max Z 18X
solve the following problem using branch and bound
Max Z= 18X1 + 14X2 + 8X3 + 4X4
St.
15X1 + 12X2 + 7X3 + 4X4 + X5 ? 37
X1, X2, X3, X4, X5= (0,1)
Solution
Using the branch and bound approach, we can approach the answer
There will be 2^(5) combinations possible out of which some will not be suiting the constraints
(0,0,0,0,0) -> Zval = 0 , Constraint -> Satisfied
(0,0,0,0,1) -> Zval = 0 , Constraint -> Satisfied
(0,0,0,1,0) -> Zval = 4 , Constraint -> Satisfied
(0,0,0,1,1) -> Zval = 4 , Constraint -> Satisfied
(0,0,1,0,0) -> Zval = 8 , Constraint -> Satisfied
(0,0,1,0,1) -> Zval = 8 , Constraint -> Satisfied
(0,0,1,1,0) -> Zval = 12 , Constraint -> Satisfied
(0,0,1,1,1) -> Zval = 8 , Constraint -> Satisfied
(0,1,0,0,0) -> Zval = 14 , Constraint -> Satisfied
(0,1,0,0,1) -> Zval = 14 , Constraint -> Satisfied
(0,1,0,1,0) -> Zval = 18 , Constraint -> Satisfied
(0,1,0,1,1) -> Zval = 18 , Constraint -> Satisfied
(0,1,1,0,0) -> Zval = 22 , Constraint -> Satisfied
(0,1,1,0,1) -> Zval = 22 , Constraint -> Satisfied
(0,1,1,1,0) -> Zval = 26 , Constraint -> Satisfied
(0,1,1,1,1) -> Zval = 26 , Constraint -> Satisfied
(1,0,0,0,0) -> Zval = 18 , Constraint -> Satisfied
(1,0,0,0,1) -> Zval = 18 , Constraint -> Satisfied
(1,0,0,1,0) -> Zval = 22 , Constraint -> Satisfied
(1,0,0,1,1) -> Zval = 22 , Constraint -> Satisfied
(1,0,1,0,0) -> Zval = 26 , Constraint -> Satisfied
(1,0,1,0,1) -> Zval = 26 , Constraint -> Satisfied
(1,0,1,1,1) -> Zval = 30 , Constraint -> Satisfied
(1,1,0,0,0) -> Zval = 32 , Constraint -> Satisfied
(1,1,0,0,1) -> Zval = 32 , Constraint -> Satisfied
(1,1,0,1,0) -> Zval = 36 , Constraint -> Satisfied
(1,1,0,1,1) -> Zval = 36 , Constraint -> Satisfied
(1,1,1,0,0) -> Zval = 40 , Constraint -> Satisfied
(1,1,1,0,1) -> Zval = 40 , Constraint -> Satisfied
(1,1,1,1,0) -> Zval = 44 , Constraint -> Not Satisfied
(1,1,1,1,1) -> Zval = 44 , Constraint -> Not Satisfied
The maximum value occurs at two points i.e. (1,1,1,1,0) and (1,1,1,1,1) but the condition is not satisfied at this point.
Hence the point satisfying the condition and having maximum value are (1,1,1,0,0) and (1,1,1,0,1) having the value of 40
Hence the maximum value = 40 using branch and bound
