Purchase Solution

Branch and Bound

Not what you're looking for?

Ask Custom Question

Solve the following problem using Branch and Bound.Show the B&B tree.If node is fathomed,indicate why it is fathomed.Provide the sequence of problems solved,. eg. P1-P3-P4, etc.Clearly indicate what the optimal solution is.Note: x4 does not have to be integer.After solving the root node, branch on x1 first.

Max Z=4x1-2x2+7x3-x4
x1+5x3<=10
x1+x2-x3<=1
6x1-5x2<=0
-x1+2x3-2X4<=3

x1,x2,x3,x4>=0, x1,x2, x3 integer

Thanks

Purchase this Solution

Solution Summary

The solution examines branch and bound for tree integers with details are provided.

Solution Preview

Max Z=4x1-2x2+7x3-x4
x1+5x3<=10
x1+x2-x3<=1
6x1-5x2<=0
-x1+2x3-2X4<=3

x1,x2,x3,x4>=0, x1,x2, x3 integer Branch on x1 first
P1: x1=1
P2:x1=0

At root node, the LP relaxation is
Max Z=4x1-2x2+7x3-x4
x1+5x3<=10
x1+x2-x3<=1
6x1-5x2<=0
-x1+2x3-2X4<=3
x1,x2,x3,x4>=0
The optimal solution is
(x1,x2,x3,x4)=(1.25, 1.5, 1.75, 0), with objective value=14.25.
Then the current upper bound of the original problem is 14.25. Any other sub-problem with objective value>=14.25 will be fathomed.

We first branch on x1, by
X1<=1, ...

Purchase this Solution


Free BrainMass Quizzes
Geometry - Real Life Application Problems

Understanding of how geometry applies to in real-world contexts

Graphs and Functions

This quiz helps you easily identify a function and test your understanding of ranges, domains , function inverses and transformations.

Know Your Linear Equations

Each question is a choice-summary multiple choice question that will present you with a linear equation and then make 4 statements about that equation. You must determine which of the 4 statements are true (if any) in regards to the equation.

Multiplying Complex Numbers

This is a short quiz to check your understanding of multiplication of complex numbers in rectangular form.

Probability Quiz

Some questions on probability