Linear programmimg

If we are solving a linear programming question using graphical method, it is said that the optimum point will be one of the extreme points. I want to make clear how this happens always (assume that we have an unique solution available )

-
What do you mean make clear? Illustrate? – user12205 Nov 27 '11 at 9:10
in simple words, I want to know how the extreme points are considered to be the only points within the feasible region that gives the optimum value. I hope I made myself clear... – Tharindu Rusira Nov 27 '11 at 15:08

The proof is based on the definition of the convex combination. Assume that $x$ is the only optimal solution with $Z$ objective value and not a vertex of the convex, therefore it can be expressed as convex combination of two other basic feasible solution, which is convex's vertices $x'$ and $x''$ and let $Z_{1}$ and $Z_{2}$ denote their respective objective function values.

$x=ax'' +(1-a)x'$, for some value $0<a<1$

Thus,

$Z=aZ_{2}+(1-a)Z_{1}$

Since the weights $a$ and $1-a$ add to 1, the only possibilities for how $Z,Z_{1},Z_{2}$ compare are

case 1: $Z=Z_{1}=Z_{2}$,

case 2: $Z_{1}<Z<Z_{2}$,

case 3: $Z_{1}>Z>Z_{2}$.

The first case implies that $x'$ and $x''$ are also optimal, which is contradiction to the assumption that there is exactly one solution. Both the latter cases contradict the assumptions that $x$ is optimal. The conclusion is there is impossible to have a optimal solution that is not vertex of the convex.

The proof was taken from the great book Introduction To Operations Research

-
just great !!! loads of thanks :) a crystal clear explanation.. a proof rather, awesome... – Tharindu Rusira Nov 27 '11 at 15:11