Explore BrainMass

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

    © BrainMass Inc. brainmass.com December 24, 2021, 8:44 pm ad1c9bdddf
    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

    ADVERTISEMENT