Business Mathematics and Statistics · Ch 10 — Operations Research (Linear Programming Problem, Network Analysis)
Solving an LPP by the Graphical (Corner-Point) Method
Solving an LPP by the Graphical (Corner-Point) Method
Once the feasible region is graphed, the graphical (corner-point) method finds the optimal value of the objective function using one remarkable fact, stated here without proof, since this syllabus's own scope calls for applying the graphical method, not deriving why it works:
The Corner-Point Theorem
If the feasible region of an LPP is bounded, the objective function attains both its maximum and its minimum on the feasible region, and each occurs at one of the region's corner points.
This is exactly why the method never tests every one of the infinitely many points inside the feasible region — only the handful of corner points, found by ordinary algebra.
The Procedure
- Graph every constraint and shade to find the feasible region.
- List every corner point — solving pairs of boundary equations simultaneously, plus checking where a boundary meets an axis — discarding any intersection that violates some other constraint.
- Evaluate at every corner point.
- The largest value is the maximum of ; the smallest is the minimum — read off whichever the problem asks for.
A caution for an unbounded feasible region. When a constraint is an at least () requirement, the feasible region can extend outward without limit. The Corner-Point Theorem still places any optimum at a corner point, but for a minimum on an unbounded region, its existence must additionally be confirmed: draw the line (the smallest corner value found) and check that no feasible point lies in the open half-plane where would be smaller still. …
On a bounded feasible region, an LPP's objective function attains both its maximum and minimum at one of the region's corner points, so evaluating at every corner poin …
A bounded region does not extend infinitely in any direction, so the Corner-Point Theorem guarantees both a maximum and minimum exist; an unbounded region (typical with at-least constraints) may or may not have an optimum, and a minimum found at a corner point …