Properties of Linear Programming Problems

1. We can assume without loss of generality that $A\in {\mathbb{R}}^{m\times n},m<n$.
   • If $m\ge n$, the problem is either
     • Infeasible ($Ax=b$ has no solution)
     • Trivial ($Ax=b$ has one solution, for instance $x=A^{-1}b$)
     • Can be transformed to an equivalent problem with $m<n$
2. They don’t always have a solution
   • This can be either due to
     • Infeasibility, $Ax=b$ has no solutions (the feasible set $\Omega$ is empty)
     • Unboundedness (There exists a sequence $x^k\in \Omega \text{ such that }{c}^T{x}^k\to -\infty$).