0

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'?).
callculus42
  • 30,550
Julius Baer
  • 17
  • 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

1 Answers1

1

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\ $.
  2. Since the feasible region is bounded, there is no linear function which could be unbounded on it.
  3. I don't see how to make any sense of the third question. The feasible region doesn't depend in any way on the choice of objective, and since this particular feasible region is non-empty, no choice of objective is going to give a linear program that has no feasible solutions.

feasible region

lonza leggiera
  • 28,646
  • 2
  • 12
  • 33