Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
Use the LP method to determine the minimum constraint violation. – copper.hat Sep 30 '12 at 15:26
up vote 1 down vote accepted

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.