Is it correct to state that if a linear objective function is not in parallel with any of the constraints, than there is a single optimal solution at some vertex of the polytope?

  • $\begingroup$ there can be more than one optimal solution, neednt be single $\endgroup$ – Bhargav Sep 27 '11 at 9:06
  • $\begingroup$ Even if the objective function is not in parallel with any of constraints? Can you construct such example with 2 variables? $\endgroup$ – Michael Sep 27 '11 at 9:17

This is incorrect. To construct a class of simple counterexamples in three dimensions, consider problems of the form $Ax \le b, \, x \ge 0$ where $A$ is any positive $2 \times 3$ matrix of rank 2 and $b$ is a positive 2-vector. This defines a non-empty bounded feasible set in the first octant. Now consider objective functions of the form $x \mapsto cx$ where $c$ is a convex combination of the two rows of $A$. The solution set of the maximization problem is the line segment where $x \ge 0$ and $Ax = b$, but the objective function is not parallel to any of the constraints.

You may get multiple solutions in any situation where $c$ is in the space spanned by the rows of $A$.

  • $\begingroup$ You are right. Thank you very much for the answer. But is there a way I can use LP to find some vertex of a given polytope? $\endgroup$ – Michael Sep 27 '11 at 13:57
  • $\begingroup$ ask a new question, asking questions in comments is not advisable on the site $\endgroup$ – Bhargav Sep 29 '11 at 1:03

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.