The corner-point method

The fundamental theorem of linear programming states: if a linear function attains its maximum (or minimum) on a bounded convex polygon, the optimum occurs at a corner point (or possibly along an entire edge, if the objective is parallel to it). This reduces the search for an optimum from an infinite region to a finite set of vertices.

The corner-point theorem (intuition)

A linear function $Z = ax + by$ has level lines (curves of constant $Z$ ) that are straight lines parallel to $ax + by = 0$ . As $Z$ varies, the level lines sweep across the plane. On a polygon, the level line eventually leaves through a vertex , the optimum sits at that vertex.

If the level line happens to be parallel to an edge of the polygon, the entire edge gives the same value of $Z$ . Then there are infinitely many optima (all on that edge), and the two endpoints (corners) are among them.

The algorithm

Identify and list all corner points of the feasible region.
Compute $Z = ax + by$ at each corner.
Choose the largest (for maximisation) or smallest (for minimisation) value of $Z$ .
The corresponding corner is the optimal $(x, y)$ .

If the feasible region is unbounded and the objective is to maximise (or minimise), check whether the maximum (or minimum) actually exists by examining the objective at infinity:

For maximisation: if the feasible region extends in a direction where $Z$ grows without bound, no maximum exists.
For minimisation: similar check on the other end.

A useful rule of thumb: for an unbounded feasible region defined by $\ge$ constraints, the minimum (typically the smallest value of $Z$ ) is finite and attained at a corner; the maximum is usually infinite. The opposite for $\le$ constraints.

Worked examples

Example 1. Maximise $Z = 5x + 4y$ subject to $x + y \le 4$ , $2x + y \le 6$ , $x, y \ge 0$ .

Corners (from earlier analysis): $(0, 0), (3, 0), (2, 2), (0, 4)$ .

Values:

$(0, 0)$ : $Z = 0$ .
$(3, 0)$ : $Z = 15$ .
$(2, 2)$ : $Z = 10 + 8 = 18$ .
$(0, 4)$ : $Z = 16$ .

Maximum: $Z = 18$ at $(2, 2)$ .

Example 2. Minimise $Z = 3x + 5y$ subject to $x + 3y \ge 3$ , $x + y \ge 2$ , $x, y \ge 0$ .

Lines: $x + 3y = 3$ at $(3, 0), (0, 1)$ ; $x + y = 2$ at $(2, 0), (0, 2)$ .

Region is above both lines. Corners:

$(3, 0)$ (on first line; check second: $3 + 0 \ge 2$ , yes).
$(0, 2)$ (on second line; check first: $0 + 6 \ge 3$ , yes).
Intersection of two lines: $x + 3y = 3, x + y = 2 \Rightarrow 2y = 1, y = 1/2, x = 3/2$ .

Values: $(3, 0)$ : $9$ . $(0, 2)$ : $10$ . $(3/2, 1/2)$ : $9/2 + 5/2 = 7$ .

Region is unbounded toward upper-right. Minimum is $Z = 7$ at $(3/2, 1/2)$ . (Max doesn't exist , $Z$ grows without bound.)

Example 3. Maximise $Z = 3x + 2y$ subject to $x + 2y \le 10$ , $3x + y \le 15$ , $x, y \ge 0$ .

Corners: $(0, 0), (5, 0), (0, 5)$ , and intersection of $x + 2y = 10, 3x + y = 15$ : solve $3x + y = 15, x + 2y = 10$ . From first: $y = 15 - 3x$ . Substitute: $x + 30 - 6x = 10$ , so $5x = 20, x = 4, y = 3$ .

Values: $(0,0): 0$ ; $(5, 0): 15$ ; $(4, 3): 18$ ; $(0, 5): 10$ .

Maximum $Z = 18$ at $(4, 3)$ .

Example 4. Minimise $Z = 3x + 5y$ subject to $-2x + y \le 4$ , $x + y \ge 3$ , $x - 2y \le 2$ , $x, y \ge 0$ .

The constraint $-2x + y \le 4$ is $y \le 2x + 4$ , region below this line. The constraint $x + y \ge 3$ , region above this line. The constraint $x - 2y \le 2$ , region above the line $y = (x - 2)/2$ , which crosses $x$ -axis at $(2, 0)$ , $y$ -axis at $(0, -1)$ (outside first quadrant).

Sketch: in first quadrant, constraints intersect. Corners are at intersections:

$x + y = 3, x = 0$ : $(0, 3)$ . Check others: $-0 + 3 = 3 \le 4$ ✓; $0 - 6 = -6 \le 2$ ✓.
$x + y = 3, y = 0$ : $(3, 0)$ . $-6 + 0 \le 4$ ✓; $3 - 0 = 3 > 2$ ✗. Excluded.
$x - 2y = 2, y = 0$ : $(2, 0)$ . $-4 + 0 \le 4$ ✓; $2 + 0 = 2$ not $\ge 3$ ✗. Excluded.
$x + y = 3, x - 2y = 2$ : solve: from first $x = 3 - y$ , sub: $3 - y - 2y = 2$ , $y = 1/3$ , $x = 8/3$ . Check: $-16/3 + 1/3 = -5 \le 4$ ✓.
$-2x + y = 4, x = 0$ : $(0, 4)$ . Check: $0 + 4 = 4 \ge 3$ ✓; $0 - 8 = -8 \le 2$ ✓.

(More corners on unbounded boundaries... but for minimisation typically the relevant corners are toward the lower-left.)

At $(0, 3)$ : $Z = 15$ . At $(8/3, 1/3)$ : $Z = 8 + 5/3 \approx 9.67$ . At $(0, 4)$ : $Z = 20$ .

Minimum at $(8/3, 1/3)$ : $Z = 29/3$ .

Example 5. Maximise $Z = x + y$ subject to $2x + 3y \le 6$ , $x + 4y \le 4$ , $x, y \ge 0$ .

Lines: $2x + 3y = 6$ at $(3, 0), (0, 2)$ . $x + 4y = 4$ at $(4, 0), (0, 1)$ . Region is bounded.

Corners:

$(0, 0)$ : $Z = 0$ .
$(3, 0)$ , but check $3 \le 4$ , yes (from $x + 4y \le 4$ , with $y = 0$ gives $x \le 4$ ). Valid. $Z = 3$ .
$(0, 1)$ , on $x + 4y = 4$ , $y = 1$ . Check $2(0) + 3(1) \le 6$ , yes. Valid. $Z = 1$ .
Intersection of $2x + 3y = 6$ and $x + 4y = 4$ : from second $x = 4 - 4y$ , sub: $8 - 8y + 3y = 6$ , so $-5y = -2$ , $y = 2/5$ , $x = 4 - 8/5 = 12/5$ . Valid. $Z = 12/5 + 2/5 = 14/5$ .

Best of $\{0, 3, 1, 14/5\}$ is $3$ at $(3, 0)$ .

Example 6. A diet problem. Minimise $Z = 4x + 3y$ subject to $2x + y \ge 8$ , $x + 2y \ge 10$ , $x, y \ge 0$ .

Lines $2x + y = 8$ at $(4, 0), (0, 8)$ ; $x + 2y = 10$ at $(10, 0), (0, 5)$ . Region is above both, unbounded.

Corners: $(0, 8)$ on first axis ( $x = 0$ ), check $0 + 16 \ge 10$ ✓; $(10, 0)$ , check $20 + 0 \ge 8$ ✓; intersection of $2x + y = 8$ and $x + 2y = 10$ : solve: multiply first by 2: $4x + 2y = 16$ , subtract second: $3x = 6$ , $x = 2$ , $y = 4$ .

Values: $(0, 8)$ : $24$ ; $(10, 0)$ : $40$ ; $(2, 4)$ : $8 + 12 = 20$ . Minimum is $20$ at $(2, 4)$ .

Try it yourself

Maximise $Z = 4x + 3y$ subject to $3x + 4y \le 24$ , $8x + 6y \le 48$ , $x \le 5$ , $y \le 6$ , $x, y \ge 0$ .
Minimise $Z = 4x + 5y$ subject to $x + 2y \ge 8$ , $2x + y \ge 10$ , $x, y \ge 0$ .
Maximise $Z = 5x + 8y$ subject to $3x + 2y \le 60$ , $x + y \le 25$ , $x, y \ge 0$ .
Minimise $Z = 6x + 3y$ subject to $4x + y \ge 80$ , $x + 5y \ge 115$ , $3x + 2y \le 150$ , $x, y \ge 0$ .
Maximise $Z = 2x + 3y$ subject to $x + 2y \le 8$ , $4x + 3y \le 12$ , $x, y \ge 0$ .
Minimise $Z = 3x + 4y$ subject to $x + y \ge 5$ , $x + 2y \ge 6$ , $x, y \ge 0$ .
Maximise $Z = 7x + 8y$ subject to $x + 2y \le 16$ , $3x + y \le 24$ , $x, y \ge 0$ .
Minimise $Z = 2x + y$ subject to $4x + y \ge 4$ , $2x + 3y \ge 6$ , $x + y \ge 2$ , $x, y \ge 0$ .
Maximise $Z = 9x + 12y$ subject to $x + y \le 50$ , $2x + y \le 80$ , $x, y \ge 0$ .
Minimise $Z = 50x + 70y$ subject to $2x + y \ge 8$ , $x + 2y \ge 10$ , $x, y \ge 0$ .
Maximise $Z = x + y$ subject to the constraints in Try-it-yourself #8 above.
Minimise $Z = 3x + 9y$ subject to $x + 3y \le 60$ , $x + y \ge 10$ , $x \le y$ , $x, y \ge 0$ .
Maximise $Z = 60x + 40y$ subject to $5x + 6y \le 45$ , $3x + 2y \le 18$ , $x, y \ge 0$ .
A unique-edge case: $Z = x + 2y$ subject to $x + 2y \le 10$ , $x, y \ge 0$ . (Predict the answer.)

Pitfalls and tricks

Compute $Z$ carefully at each corner , arithmetic mistakes cost marks.
Check feasibility of each candidate corner. Not every intersection of two constraint lines lies in the feasible region.
For unbounded regions, check whether the optimum exists. Plot the gradient of $Z$ (the direction of fastest increase) and see if the feasible region extends in that direction.
Equal $Z$ at two adjacent corners means infinitely many optima along the edge connecting them. Mention this in your answer.
Round only at the end , keep exact fractions throughout to avoid drift.