2
$\begingroup$

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 )

  • 0
    in simple words, I wan$t$ 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...2011-11-27

1 Answers 1

3

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

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},

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

  • 0
    just great !!! loads of thanks :) a crystal clear explanation.. a proof rather, awesome...2011-11-27