Business Mathematics and Basic Statistics · Ch 17 — Linear Inequalities and Linear Programming
Solving an LPP by the Graphical (Corner-Point) Method
Solving an LPP by the Graphical (Corner-Point) Method
Once an LPP has been formulated and its feasible region graphed, the graphical method (also called the corner-point method) finds the optimal value of the objective function using a single remarkable fact, stated here without proof — the syllabus's own scope calls for the graphical method only, not a proof of why it works:
The Corner-Point Theorem
If the feasible region of an LPP is bounded, the objective function attains BOTH its maximum value and its minimum value on the feasible region, and each of these optimal values occurs at one of the region's corner points. If two different corner points both give the same optimal value, then every point on the segment joining them is also optimal.
This is precisely why the method never needs to test every one of the infinitely many points inside the feasible region — only the handful of corner points, which can be found exactly by ordinary algebra.
The procedure, step by step:
- Graph every constraint's boundary line and shade to find the feasible region (as in the previous two sections).
- List every corner point of the feasible region — every point where two boundary lines meet, found by solving the corresponding pair of boundary equations simultaneously, PLUS the points where a boundary line meets an axis (found by setting or in turn). A point counts as a genuine corner of the feasible region only if it also satisfies every OTHER constraint of the problem — an intersection that violates some other constraint is not a corner point of the feasible region and must be discarded.
- Evaluate at every corner point found in step 2.
- The largest of these values is the maximum of on the feasible region, and the smallest is the minimum — read off whichever the problem actually asks for. …
On a bounded feasible region, an LPP's objective function attains both its maximum and its minimum value at one of the region's corner points, so evaluating at every corner poin …
The corner point (or points) of the feasible region at which the objective function attains the required maximum or minimum value; the corresponding value of $Z …
A feasible region that does not extend infinitely in any direction; here the Corner-Point Theorem guarantees BOTH a maximum and a minimum exis …
A feasible region that extends indefinitely in at least one direction (typical when every constraint is an at-least requirement); an optimum may or may not exist, and if a minimum is found at a corner point, it must be …