Enquiry to Linear Programming.

Question

I came across this Theorem on Optimum solution to a Linear programming problem:

" If $S$ is the feasible region of some linear program with objective function $ z=c^{T}\textbf{x}$ then 1) $z$ attains its optimal value at some vertex of $S$, 2) the linear program is infeasible, or 3) the linear program is unbounded. "

But, if we consider $\text{max}_{\textbf{x}\in \mathbb{R}^2}$ $x_1+x_2$ s.t. $x_1+x_2=1$ and $\textbf{x} \geq \textbf{0},$ then it is clear that $(0.5,0.5)$ is an optimal solution but it does not lie on vertex of the feasible region (which is a polyhedra).

Hence, I think (1) means that if $X$ is an extreme point of $S,$ then $X$ corresponds to an optimal solution(but converse is not necessarily true) ?

Could anyone advise please? Thank you.

Answer 1

The theorem says that the optimum is achieved at some vertex. It doesn't say that every optimal solution is a vertex. It may happen that the set of optima coincides with some face of the polyhedron representing the feasible region. In that case, interior points of the face are optimal, but they are not vertices. As in your example. But the optimal set does contain vertices, which is what the theorem tells us.

To be more explicit ...

Let $S$ be the set of feasible points (which is a polyhedron), let $E$ be the set of extreme points of $S$ (i.e. vertices), let $B$ (B for "best") be the set of optimal points. Statement (1) does not say that $E \subset B$ or $B \subset E$. It says that $B \cap E \ne \emptyset$.

Answer 2

Take another example: $\max \{ x_1 | 0 \le x_1 \le 1, 0 \le x_2 \le 1 \}$.

The solution is clearly $1$ and the feasible set is $S = \operatorname{co} E$, where $E=\{ (0,0), (0,1), (1,0), (1,1) \}$ is the set of extreme points.

The set of optimizers is $M=\operatorname{co}\{(1,0), (1,1) \}$.

There are extreme points which are not solutions and solutions which are not extreme points.

The point of the theorem is that $M$ contains an extreme point of $S$.