Consider the following IP: Maximize: 14x_1 + 18x_2 Subject to: - x_1 + 3x_2 less

Question

Consider the following IP: Maximize: 14x_1 + 18x_2 Subject to: - x_1 + 3x_2 lessthanorequalto 6 7x_1 + x_2 lessthanorequalto 35 With: x_1, x_2 Greaterthanorequalto 0 and integral The optimal canonical form for the IP's LP relaxation is given below. Maximize z Subject to z + (56/11)S_1 +(30/11)s_2 =126 x_2 + (7/22)s_1+ (1/22)s_2 = 7/2 x_1 - (1/22) s_1 + (3/22)s_2 = 9/2 With all variables (except possibly z) Greaterthanorequalto 0 and integral Use the Gomory fractional cutting plane algorithm to solve this IP by hand. For each iteration, state your LP optimal solution and the new cutting plane that you generated. What is the optimal solution to the original IP at the top? What is the optimal objective value?

Explanation / Answer

The optimal table for the LP relaxation is :

Now consider the heuristic criterian min { (7/2-1/2), (9/2-1/2)} = min {3,4} = 3

Hence we use x2-row as source row and so we get :

After a dual simplex iteration , we find the following :

Which however is still fractional. So we obtain a new cut using x1 as source row:

And so we get On right hand side :

3

4

1

4

114

Hence the solution is integer solution and the optimal value is 114

s1 s2 x2 7/22 1/22 7/2 x1 -1/22 3/22 9/2 56/11 30/11 126

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.