Linear Programming

About this unit

Linear programming is a method for making the best decision when resources are limited. A business may want to maximise profit or minimise cost while staying within limits of labour, raw material, machine time or budget. When the objective and all the limits are linear expressions, the problem is a linear programming problem (LPP). In this unit you learn the vocabulary, translate word problems into mathematical form, and solve two-variable problems by drawing the feasible region and testing its corner points.

Key ideas

• Decision variables (usually x and y) are the quantities to be chosen; they are non-negative.
• The objective function Z = ax + by is to be maximised or minimised.
• Constraints are linear inequalities expressing the limits.
• The feasible region is the set of points satisfying all constraints.
• The optimal value, if it exists, occurs at a corner point of the feasible region.
• Feasible regions can be bounded or unbounded; some problems have no feasible solution.

How to prepare

Practise turning word problems into constraints, paying close attention to "at least" (≥) and "at most" (≤). Draw graphs neatly with intercepts, find corner points by solving pairs of equations, and tabulate Z at each corner. Learn the extra check needed when the feasible region is unbounded.