Linear Programming
Linear Programming tests formulation of an objective and constraints, graphical solution of two-variable problems, feasible regions and the corner point theorem.
Core rules
- Write the objective as maximise or minimise Z=ax+by, with constraints as linear inequalities and non-negativity restrictions.
- Graph each inequality; the feasible region is the common shaded side, including boundary lines when the inequality is ≤ or ≥.
- The corner point theorem says a linear objective on a bounded feasible region attains its optimum at a vertex. Evaluate Z at every vertex and compare.
- For unbounded regions, check whether the objective can improve without limit before accepting a vertex value.
Worked example
Maximise Z=3x+2y subject to x+y≤4, x≥0, y≥0. The vertices are (0,0), (4,0) and (0,4). Values: Z=0, 12 and 8. The maximum is 12 at (4,0). The constraint line x+y=4 is a boundary, and the origin test confirms the feasible side.
Traps
- Reversing an inequality when multiplying or dividing by a negative changes the feasible region.
- Do not test only the origin; vertices come from intersections of boundary lines.
- A feasible region can be unbounded, so a largest vertex value may not be the true maximum.
- Include non-negativity constraints; omitting them can add invalid vertices.
- In word problems, translate phrases such as at least and at most into the correct inequality direction.