Optimal Feasible Solutions and the Corner Point Method

The Corner Point Theorem. The central theoretical fact underlying the whole graphical method is this: if a linear programming problem has an optimal solution over its feasible region, that optimal value is always attained at one of the corner points (vertices) of the feasible region. Equivalently: to find the maximum or minimum of a linear objective function $Z=ax+by$ over a feasible region, it is never necessary to check any point in the interior of the region or along the interior of an edge -- only the (typically very few) corner points need to be checked. This is a consequence of $Z$ being LINEAR: along any straight edge of the feasible region, $Z$ changes at a constant rate as one moves from one end to the other, so its largest and smallest values on that edge occur only at the edge's two endpoints (its corners), never strictly in between -- and the same reasoning, applied to every edge of the polygon in turn, shows the overall maximum and minimum over the whole region must occur at one of the corners.

Multiple optimal solutions. If two adjacent corner points give exactly the same (optimal) value of $Z$, this happens precisely when the objective line $ax+by=k$ is parallel to the edge joining those two corners -- and in that case, EVERY point on that entire edge, not just its two endpoints, gives the same optimal value of $Z$. This produces infinitely many optimal solutions all sharing the one optimal value (Example 3 and Miscellaneous Question 1 both work through this case in full).

The Corner Point Method -- complete algorithm. (1) Formulate the LPP and graph the feasible region as in Section 3. (2) Find every corner point: solve each relevant pair of boundary equations simultaneously, keeping an intersection only if it also satisfies every OTHER constraint of the problem (Section 3, Step 4). (3) Evaluate $Z=ax+by$ at every corner point found. (4a) If the feasible region is bounded (Section 4), the largest of these values is the maximum of $Z$ and the smallest is the minimum -- both are guaranteed to exist and to be attained at one of the corners. (4b) If the feasible region is unbounded, identify the largest (for a maximum) or smallest (for a minimum) value among the corners as a candidate, then apply the half-plane test of Section 4: if the corresponding open half-plane shares no point with the feasible region, the candidate is confirmed as the genuine optimal value; otherwise, no optimal value of that kind (maximum or minimum) exists at all. …