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.

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?

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

1 Answer 1

up vote 4 down vote accepted

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$.

share|improve this answer
    
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? –  Michael Sep 27 '11 at 13:57
    
ask a new question, asking questions in comments is not advisable on the site –  Bhargav Sep 29 '11 at 1:03

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.