Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

My question is about having an LP in the standard form $Ax \leq b$ and the set of basic feasible solutions. For each basic feasible solution (bfs) does there exist an appropriate objective function $cx,$ such that this bfs is the optimal solution for this particular objective function?

My answer is yes, because the objective function is just a vector; therefore, for each bfs we can adjust the vector appropriately.

What's your opinion?

share|cite|improve this question
I believe it is "yes" for the same reason as you. – marvinthemartian Feb 21 '12 at 20:19
up vote 3 down vote accepted

Yes. The feasible set is a (possibly unbounded) convex polytope, and the basic feasible solutions are its extreme points. A basic theorem of convex geometry is that for any extreme point $v$ of a convex set $S$ in ${\mathbb R}^n$ there is a supporting hyperplane, i.e. a nonzero vector $w$ such that $w \cdot v \ge w \cdot x$ for all $x \in S$.

share|cite|improve this answer
+1. For a discussion of how to determine an optimal objective function given a basic feasible solution, see "Inferring an LP cost vector from its solution." – Mike Spivey Feb 21 '12 at 21:10

Your Answer


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.