1 Solve the following integer programming model by using the branch and bound algorithm and LIFO...

 

Transcribed Image Text:

1 Solve the following integer programming model by using the branch and bound algorithm and LIFO approach. You have to apply the dual simplex algorithm in every iteration (graphical solutions will not be accepted). The optimum table of the LP relaxation is as given. You have to explain your work in detail. At the end, write the optimal solution explicitly. Max z=7x₁+4x₂ s.t. 2 z 1 Max z=7x₂+4x₂ s.t. 4x1+3x₂ <10 10x:+4x2 ≤ 16 X₁, X₂20, and X₁, X₂ are integer (Problem 1 integer programming model) 0 0 X1 0 0 1 X2 0 1 0 4x1+3x2 <10 10x1+4x2 ≤ 16 X₁, X₂20, and X₁, X₂ are integer Hint: In the first sub-problem, define the branches for x₂. It is sufficient to find only one optimal solution. $1 S2 rhs 6/7 5/14 100/7 5/7 -2/7 18/7 -2/7 3/14 4/7 Solve the integer programming model given in Problem 1 by using the cutting-plane algorithm. You have to apply the dual simplex algorithm in every iteration (graphical solutions will not be accepted). You have to explain your work in detail. At the end, write the optimal solution explicitly. Hint: If there are multiple candidate rows to write the new constraint, always choose the row where x₁ or x₂ is the basic variable. If the rows, where x₁ and x₂ are basic, are both candidates, choose the row where x₁ is basic. 1 Solve the following integer programming model by using the branch and bound algorithm and LIFO approach. You have to apply the dual simplex algorithm in every iteration (graphical solutions will not be accepted). The optimum table of the LP relaxation is as given. You have to explain your work in detail. At the end, write the optimal solution explicitly. Max z=7x₁+4x₂ s.t. 2 z 1 Max z=7x₂+4x₂ s.t. 4x1+3x₂ <10 10x:+4x2 ≤ 16 X₁, X₂20, and X₁, X₂ are integer (Problem 1 integer programming model) 0 0 X1 0 0 1 X2 0 1 0 4x1+3x2 <10 10x1+4x2 ≤ 16 X₁, X₂20, and X₁, X₂ are integer Hint: In the first sub-problem, define the branches for x₂. It is sufficient to find only one optimal solution. $1 S2 rhs 6/7 5/14 100/7 5/7 -2/7 18/7 -2/7 3/14 4/7 Solve the integer programming model given in Problem 1 by using the cutting-plane algorithm. You have to apply the dual simplex algorithm in every iteration (graphical solutions will not be accepted). You have to explain your work in detail. At the end, write the optimal solution explicitly. Hint: If there are multiple candidate rows to write the new constraint, always choose the row where x₁ or x₂ is the basic variable. If the rows, where x₁ and x₂ are basic, are both candidates, choose the row where x₁ is basic.

Answer rating: 100% (QA)

Solution In true or false integer linear programming pr... View the full answer