If we have a feasible space for a given LPP (linear programming problem), how is it that its optimum solution lies on one of the corner points of the graphical solution? (I am here concerned only with those LPP's which have a graphical solution with more than one corner/end point.)
I was asked to take this as a lemma in the class, but got curious about the proof. Any help is sincerely appreciated.
Best Answer
In two dimensional case the linear optimization (linear programming) is specified as follows: Find the values $(x, y)$ such that the goal function $$g(x, y) = a x + b y \;\;\; (Eq. 1)$$ is maximized (or minimized) subject to the linear inequalities $$a_1 x + b_1 y + c_1 \ge 0 \;\; (or \le 0) $$ $$a_2 x + b_2 y + c_2 \ge 0 \;\; (or \le 0) $$ $$ ... $$
Each of these linear inequalities defines a half plane bounded by the line obtained by replacing the inequality by equality. The solution $(x, y)$ that maximizes the goal function must lie in the intersection of all these halfplanes which is obviously a convex polygon. This polygon is called the feasible region. Let the value of the goal function at a point $(x, y)$ of the feasible region be $m$ $$g(x, y) = a x + b y = m \;\;\; (Eq. 2)$$ The value $m$ of the goal function will obviously not change when we move $(x, y$) on the line defined by (Eq. 2). But the value of $g()$ will be increased when we increase $m$. This leads to a new line which is parallel to (E.q. 2). We can do this as long as the line contains at least one point of the feasible region. We conclude that the maximum of the goal function is achieved at an extreme point of the feasible region which - for a convex polygon - is a vertex (or an edge when the goal line is parallel to the restriction line going through the extreme vertex).