How to find out whether linear programming problem is infeasible using simplex algorithm So in http://econweb.ucsd.edu/~jsobel/172aw02/notes3.pdf, there is a mention about finding out whether linear programming (LP) problem is infeasible by simplex algorithm, but it does not actually go over it. How does one find whether LP is infeasible using simplex algorithm?
 A: 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.
A: 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$)
A: In the final simplex table ,Zj-cj >= 0 than then it is called feasible solution, if zj-cj <0 in the last table value is negative then it is called infeasible solution.If all min(xb/xi) is negative then the problem is considered as infeasible
