# LP: multiple optimal solutions, unbounded, infeasible? [closed]

I'd like to ask the following question(s), to help me de-confuse things:

$$5y + x \geq 7$$
$$-3y + 4x \geq 5$$
$$4y - x \leq 15$$
$$y - 3x \geq -21$$
$$y - 4x \leq 42$$

Given these constraints,

• what could be an objective function for which the LP has multiple optimal solutions (1),
• what could be an objective function for which this LP would be unbounded (2)
• and what could be an objective function for which this LP would be infeasible (3)? (And how do I find these answers 'myself'?).
• Are you sure you want equalities ? – nicomezi Oct 11 '19 at 13:51
• There are more constraints than there are variables, so there is no feasible solution to this problem. Perhaps you meant $\leqslant$ or $\geqslant$ instead of $=$ in the constraints? – Math1000 Oct 11 '19 at 14:37
• I did mean that, sorry, the fifth constraint is redundant. – Julius Baer Oct 11 '19 at 15:15
• My idea is that Minimize z = y -3x has multiple solutions because it runs parallel to one of the constraints, but are these solutions optimal (how do I find this in general?). For (2) I read that an LP with a bounded feasible region always has a finite optimal solution, but I can't change the feasible region can I? Otherwise maximising infinity times x would be unbounded but that's probably not correct. I don't know how to find (3). – Julius Baer Oct 11 '19 at 15:18

Ignoring the redundant fifth constraint, and plotting the feasible region in the $$x$$-$$y$$ plane, shows that it's bounded by a quadrilateral whose sides are the segments of the lines $$\ -3y+4x=5\$$ between the points $$\ (2,1)\$$ and $$\ (5,5)\$$, $$\ 4y-5x=15\$$ between the points $$\ (5,5)\$$ and $$\ (9,6)\$$, $$\ y-3x=-21\$$ between the points $$\ (9,6)\$$ and $$\ (7,0)\$$, and $$\ 5y+x=7\$$ between the points $$\ (7,0)\$$ and $$\ (2,1)\$$ (see the diagram below).
1. For objectives that would have multiple extrema on this feasible set, you could take that of minimising $$\ z=y-3x\$$, as you note in a comment, minimising $$\ z=5y+x\$$, minimising $$\ z=-3y+4x\$$, or maximising $$\ z=4y-x\$$.