Reverse Linear Programming Formulation

Question

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?

I believe it is "yes" for the same reason as you. – marvinthemartian Feb 21 '12 at 20:19 — marvinthemartian, Feb 21 '12 at 20:19

score 3 · Accepted Answer · answered Feb 21 '12 at 20:24

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

answered Feb 21 '12 at 20:24

Robert Israel

448,999

+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

Reverse Linear Programming Formulation

1 Answers1