Linear Programming
Linear Programming is a short, high-scoring chapter: formulate the objective and constraints from a word problem, draw the feasible region, and apply the corner point theorem. Only two-variable problems appear, so every constraint is a straight line you can graph.
Method
- Define decision variables x and y, state the objective Z = ax + by, and list constraints as linear inequalities, including x ≥ 0 and y ≥ 0.
- Graph each constraint, decide the side by testing a point (usually the origin), and shade the region satisfying all constraints at once.
- Corner point theorem: if the feasible region is bounded, the maximum and minimum of Z occur at vertices. Evaluate Z at every vertex and compare.
- If the region is unbounded, test whether the open half-plane Z > k (for a maximum) meets the feasible region; if it does not, k is the maximum.
- The region may be empty (infeasible) or a single point.
Worked example
Maximise Z = 3x + 2y subject to x + y ≤ 4, x + 3y ≤ 6, x ≥ 0, y ≥ 0. The two boundary lines meet at (3, 1). The vertices of the feasible region are (0, 0), (4, 0), (3, 1) and (0, 2), where Z equals 0, 12, 11 and 4. The maximum is Z = 12 at (4, 0).
Traps
- Omitting the non-negativity constraints, which lets the region become unbounded.
- Shading the wrong side of a constraint line.
- Testing only intersection points and ignoring the intercept vertices on the axes.
- Assuming an unbounded region has no maximum; the half-plane check decides.