Skip to content

Business Mathematics and Basic Statistics · Ch 17 — Linear Inequalities and Linear Programming

Solving an LPP by the Graphical (Corner-Point) Method

4

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:

Note

The Corner-Point Theorem

If the feasible region of an LPP is bounded, the objective function ZZ 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:

  1. Graph every constraint's boundary line and shade to find the feasible region (as in the previous two sections).
  2. 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 x=0x=0 or y=0y=0 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.
  3. Evaluate ZZ at every corner point found in step 2.
  4. The largest of these values is the maximum of ZZ on the feasible region, and the smallest is the minimum — read off whichever the problem actually asks for. …
Definition 14Corner-Point Theorem

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 ZZ at every corner poin …

Definition 15Optimal solution

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 …

Definition 16Bounded feasible region

A feasible region that does not extend infinitely in any direction; here the Corner-Point Theorem guarantees BOTH a maximum and a minimum exis …

Definition 17Unbounded feasible region

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 …