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 )
Tell me more
×
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.
|
|
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 |
||||
|
