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?

$\endgroup$
  • 1
    $\begingroup$ Use the LP method to determine the minimum constraint violation. $\endgroup$ – copper.hat Sep 30 '12 at 15:26
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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