Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
1  
Use the LP method to determine the minimum constraint violation. –  copper.hat Sep 30 '12 at 15:26

1 Answer 1

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|improve this answer

Your Answer

 
discard

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.