Mathematics and Statistics · Ch 14 — Linear Programming
Graphical Solution by the Corner-Point Method
Graphical Solution by the Corner-Point Method
For an LPP in two variables the feasible region is a flat region of the plane, and the optimum can be found graphically. The method rests on one key result.
The corner-point principle
Corner-Point Theorem
If an LPP has an optimal value (maximum or minimum) of its objective function , and that value exists on the feasible region, then it occurs at at least one corner point of the feasible region.
The reason is that is constant along each line (an iso-profit or iso-cost line). Sliding that line across a polygonal region, the last point of contact as increases (or decreases) is always a vertex. So we never need to test every point — only the corners.
The method, step by step
Corner-point method
- Formulate the LPP (objective , constraints, ).
- Graph every constraint and shade the feasible region (each half-plane, intersected).
- Find all corner points by solving the boundary lines in pairs.
- Evaluate at every corner point.
- Choose the optimum: the largest value is the maximum, the smallest is the minimum. State both the optimal and the corner where it occurs.
Bounded regions
On a bounded feasible region step 5 is complete as written — the largest and smallest of the corner values are genuinely the maximum and minimum.
Unbounded regions — the extra check
On an unbounded region, a corner value may not be the true optimum …
If an LPP has an optimal value on its feasible region, that value occurs at at least one corner point. Hence only the c …
A line on which the objective is constant. As changes the line slides parallel to itself; the last vertex it to …
Graph the feasible region, list its corner points, evaluate at each, and pick the largest (max) or smallest (min). On an unbounded region, confirm wit …