0

Given the following set:

$$ -x_1 + x_2 = 4$$

$$ x_1 - 2x_2 + x_3 <= 6 $$ $$ x_3 >= 1 $$ $$ x_1,x_2,x_3 >= 0 $$

Without drawing the feasible region can I know if it is bounded or unbounded?

moli
  • 69

1 Answers1

2

A polyhedron is unbounded if there exists a point $x$ and a direction $d$ such that $x + \alpha d$ is in the polyhedron for all $\alpha \geq 0$. Denote the polyhedron as $Ax \leq b$, then $x$ and $d$ need to satisfy $A(x+\alpha d) \leq b$ for all $\alpha \geq 0$. That is equivalent to finding $x$ and $d$ such that $Ax \leq b$ and $Ad \leq 0$.

LinAlg
  • 19,822
  • Are you saying if Ad<= has a solution then we have an unbounded problem? – moli Nov 25 '20 at 19:43
  • 1
    If the polyhedron is not empty, yes. – LinAlg Nov 25 '20 at 19:45
  • One last question,although could be a silly one, how do we know if it is empty? – moli Nov 25 '20 at 19:52
  • 1
    to find a point $x$ that satisfies $Ax \leq b$ or a point $d$ that satisfies $Ad \leq 0$ you can use the simplex method – LinAlg Nov 25 '20 at 19:54
  • @LinAlg Can we say that if any simplex table contains a variable with non positive column then we are sure that the problem will be unbounded in that direction certainly. Next thatdirection can inturn point to unboundedness in some other direction. – Upstart Feb 20 '23 at 16:47