2
$\begingroup$

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?

  • 1
    Use the LP method to determine the minimum constraint violation.2012-09-30

1 Answers 1

1

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.