Let $K= \{x: Ax\leq b, x\geq0\}, b\geq 0$. Show that if there is a nonzero solution $x\geq 0$ of $Ax\leq 0$, then $K$ is unbounded. ($A$ is $m \times n$, $x$ is $n \times 1$ matrix, $b$ is $m \times 1$ matrix)?
Asked
Active
Viewed 45 times
0
-
3Does this answer your question? Unboundedness in linear programming – tromben Dec 20 '20 at 17:39
1 Answers
2
Let $u$ be a non-zero solution to $x\geq0, Ax\leq0$. Note that $\alpha u \in K$ for any scalar $\alpha > 0$. Thus, the half-line $L = \{\alpha u | \alpha > 0\}$ is an unbounded subset of $K$. Therefore, $K$ is unbounded.
Adam Zalcman
- 3,446