Explore BrainMass

# Branch and bound solution of problem

Not what you're looking for? Search our solutions OR ask your own Custom question.

This content was COPIED from BrainMass.com - View the original, and get the already-completed solution here!

Max z= 7x1+3x2
2x1+x2<=9
3x1+2x2<=13

x1,x2>=0
x1,x2 integer

https://brainmass.com/math/integrals/branch-bound-solution-problem-308707

#### Solution Preview

Branch and bound solution of problem
Max z= 7x1+3x2
2x1+x2<=9
3x1+2x2<=13

x1,x2>=0
x1,x2 integer

First solve the LP relaxation of the problem, which is the root.
(0) Max z= 7x1+3x2
2x1+x2<=9
3x1+2x2<=13

x1,x2>=0

The optimal solution is (x1, x2)=(13/3, 0) with objective value = 91/3. So 91/3=30.333 is the upper bound of the IP solution. It is not the optimal solution to IP because x1 is fractional.
So we branch on x1 =13/3=4.333 by creating two sub-problems. Sub-problem (1) is by adding x1<=4 to the root. Sub-problem (2) is by adding x1>=5 to the root. Remember that we cannot include the LP ...

#### Solution Summary

Branch and bound solution of problem is presented.

\$2.49