Linear Programming

Key idea

Optimise a linear objective over a feasible polygon; maxima occur at vertices.

In depth

Linear programming finds the best value of a linear objective under linear constraints. The feasible region is a polygon, and the maximum or minimum always occurs at a corner point.

Worked example

Maximise 3x + 2y with x + y ≤ 4, x ≥ 0, y ≥ 0: corners (0,0), (4,0), (0,4), values 0, 12, 8. Best is 12 at (4, 0).

Real-world uses

• Maximising profit from two products under labour limits
• Delivery routing and resource planning

Common mistake

Testing a non-corner point or missing a corner of the region.

How to learn this

1. Read the key idea and say it in your own words.
2. Work through the worked example, then try a similar problem.
3. Use the interactive lesson’s visual and mini-quiz to check the pattern.

Frequently asked questions

Expand all Collapse all

Related expert topics in Algebra

• Rational Root Theorem – Possible rational roots are ± factors of constant over factors of leading coefficient.
• Fundamental Theorem of Algebra – Every degree-n polynomial has exactly n complex roots counted with multiplicity.
• Binomial Theorem – Expand (a+b)ⁿ with binomial coefficients.
• Partial Fractions – Decompose a rational function into simpler fractions.
• Mathematical Induction – Prove statements for all n by base case and inductive step.
• Cramer’s Rule – Solve linear systems using determinants.