Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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 )

share|improve this question
    
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

1 Answer 1

up vote 3 down vote accepted

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

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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.