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
    What do you mean make clear? Illustrate?2011-11-27
  • 0
    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...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