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