How to find out whether a linear program is infeasible using the simplex algorithm?

Question

In these notes, finding out whether a linear program (LP) is infeasible via the simplex algorithm is mentioned, but it does not actually go over it. How does one find whether an LP is infeasible using the simplex algorithm?

Answer 1

There is a relationship between a linear program and its "dual" formulation:

If the dual LP is unbounded, then the primal LP is infeasible

Therefore, you can formulate the dual and when you run the simplex method on it, you will be told the problem is unbounded (i.e., one or more variables can be pivoted to $\infty$)

Answer 2

One approach is to solve a so-called phase I problem. For instance, suppose your problem is this: \begin{array}{ll} \text{minimize} & c^T x \\ \text{subject to} & A x = b\\ & x \geq 0 \end{array} Without loss of generality we may assume that $b \geq 0$ (if it is not the case, just negate the corresponding rows of $A$ and $b$). Now consider the problem \begin{array}{ll} \text{minimize} & \vec{1}^T s \\ \text{subject to} & A x + s = b\\ & x, s \geq 0 \end{array} The point $(x,s)=(0,b)$ is feasible for this modified problem, so you can apply a standard simplex algorithm to this problem, and iterate to convergence.

Clearly, the optimal value of this problem must either be zero or positive; furthermore, it is zero only if $s^*=0$ at the solution. In the zero case, the corresponding value of $x^*$ at the solution satisfies $Ax^*=b$, $x^*\geq 0$; in other words, it is a proof of feasibility of the original problem! On the other hand, if $\vec{1}^T s^*>0$, then the original problem is infeasible.