Consider a linear programming problem. Is it possible for an optimal solution to exist, but not at an extreme point? According to Bertsimas & Tsitsikalis ("Introduction to Linear Optimization", Athena Scientific, 1997), yes… and no. I'd appreciate help in reconciling the contradiction and resolving the matter.
On the one hand, on page 75, we find that
If the feasible set is unbounded, there are the following possibilities:
(i) There exists an optimal solution which is an extreme point.
(ii) There exists an optimal solution, but no optimal solution is an extreme point. (This can only happen if the feasible set has no extreme points; it never happens when the problem is in standard form.)
(iii) The optimal cost is $-\infty$.
So if the feasible set is unbounded, it is possible for a non extreme point to be an optimal solution. The answer to my question is therefore: Yes. But… this is only possible as long as the problem is not in standard form. However, on page 5 we learned that
A general linear programming problem can be transformed into an equivalent problem in standard form.
So it must be that after transforming the problem into an equivalent one in standard form, the non extreme, optimal point becomes an extreme point. But this is impossible, since, according to page 75,
An interesting aspect of the material in this chapter is the distinction between geometric (representation independent) properties of a polyhedron and those properties that depend on a particular representation. In that respect, we have established the following:
(a) Whether or not a point is an extreme point (equivalently, a vertex, or basic feasible solution) is a geometric property.
Confused? So am I!
Best Answer
What I remember is that if the objective function is parallel to any part of the boundary that contains an extreme point, then any number on that boundary is also an extreme point.
Admittedly it has been a long time since I looked a linear programming though.