Linear programming: the corner point method

Linear programming finds the best value (largest profit, smallest cost) when resources are limited. A factory has only so many machine hours; a diet must contain at least so much protein.

The parts of a problem:

• Decision variables x, y: what you choose (how many chairs, how many tables). They cannot be negative: x ≥ 0, y ≥ 0.
• Objective function Z = ax + by: what you want to maximise or minimise.
• Constraints: linear inequalities that describe the limits, such as x + y ≤ 6.

The feasible region is the area on the graph where all the constraints hold at once. Any point in it is a feasible solution; the best one is the optimal solution.

Corner point method (when the region is bounded, i.e. closed in on all sides):

• Draw each constraint as a line, and shade the side that satisfies it (test with (0, 0) if the line does not pass through it).
• Find the corner points of the common region, solving pairs of line equations where needed.
• Work out Z at every corner.
• The largest value is the maximum; the smallest is the minimum.

Why corners? Z = ax + by changes steadily as you move in a straight line, so the extreme values sit at the edges, and the most extreme at the corners.

Example: maximise Z = 2x + 3y subject to x + y ≤ 6, x ≤ 4, x, y ≥ 0.

So the maximum is 18 at (0, 6).

If two corners tie for the best value, every point on the edge between them is optimal too: there are infinitely many optimal solutions.

For word problems, a small table (items in the rows, resources in the columns) makes writing the constraints much easier.