Math Is Fun Forum

AlachimUI

Guest

Linear programming - please help

I present the following integer linear programming challenge:

max(x1 + x2),
4x1 + 6x2 + x3 = 17,
x1 − x2 + x4 = 2,
xi ≥ 0, x1, x2 ∈ Z.

i. Determine the solution manually for the linear programming relaxation of the given problem, beginning with B = (x3, x4) as the initial feasible solution.

ii. Identify and elucidate a Gomory cut for the optimal solution of the
previously mentioned linear programming problem.

Bob

Administrator

Registered: 2010-06-20

Posts: 10,640

Re: Linear programming - please help

hi AlachimUI

Welcome to the forum.

From the graph it looks like (2,1) and (1,2) are two solutions.

That makes x3 = 3 x4 = 1 and x3 = 1 and x4 = 3

What happens if you start with x3 and x4 taking those values?

Bob

---

Children are not defined by school ...........The Fonz
You cannot teach a man anything;  you can only help him find it within himself..........Galileo Galilei
Sometimes I deliberately make mistakes, just to test you!  …………….Bob