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 )
Linear programmimg
-
0in 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
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
-
0just great !!! loads of thanks :) a crystal clear explanation.. a proof rather, awesome... – 2011-11-27