1
$\begingroup$

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?

  • 0
    I believe it is "yes" for the same reason as you.2012-02-21

1 Answers 1

3

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

  • 0
    +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](http://cstheory.stackexchange.com/q/8036/6543)."2012-02-21