I have a LP with constricting constraints, i.e. there is no feasible region. How would I use the simplex method to show this?
After one iteration of the simplex method I have found no negative values in the row corresponding to the objective function, which causes the algorithm to terminate...but so what..?
Any input/ideas?
If the original program was $\min \{ c^T x | A x \leq b, \ \ x \geq 0 \}$, where the constraints are infeasible, instead solve the following program over $(\alpha, x) \in \mathbb{R}^{n+1}$: $\min \{ \alpha | A x \leq b+\alpha (1,...,1)^T, \ \ x \geq 0, \ \ \alpha \geq 0 \}$. The original constraints are infeasible iff the minimum value is strictly positive.
The extended program can be expressed as a standard LP.