Linear programming on a feasible region

Translate each resource constraint into an inequality and include conditions such as x ≥ 0 and y ≥ 0. Draw its boundary line, then test a point to choose the correct side. The intersection of all permitted half-planes is the feasible region. Boundaries are included for non-strict inequalities.

For a linear objective on a nonempty bounded polygon, a maximum and minimum occur at vertices, although a whole edge can share an optimum. Find intersections algebraically before comparing values. If the variables represent whole items, a fractional optimum may not be permitted; check feasible integer points. An unbounded feasible region requires checking whether the particular objective has a finite optimum.

Worked example

Maximise P = 3x + 2y subject to x ≥ 0, y ≥ 0, x + y ≤ 8 and 2x + y ≤ 12.

1. The vertices are (0,0), (6,0), (4,4) and (0,8).
2. Evaluate P at them: 0, 18, 20 and 16.
3. The largest value is attained at (4,4).

Answer: Maximum P = 20 at x = 4, y = 4

Revise first: Simultaneous linear and quadratic equations, Quadratic inequalities.