An LP is either infeasible, has an optimal solution, or is unbounded

Given an LP in the form $\max\left\{c^Tx:Ax=b,x≥0\right\}$

Infeasibility

• No solutions which satisfy all constraints
• Farkas’ Lemma: One of the following must be true:
  • The LP is feasible; there exists an $x$ where $Ax=b$, then
  • There exists $y$ where $y^TA≥\mathbb{0}$ and $y^Tb<0$

Optimality

• For some solution $\overline{x}$, prove that it is feasible and an upper (max) or lower (min) bound

Unboundedness

• $\max\left\{c^Tx:Ax=b,x≥0\right\}$
• Unbounded if there exists $\overline{x}, r$ such that
  • $\overline{x}≥0,r≥0, A\overline{x}=b,Ar=0, c^Tr>0$