Linear Programming
Linear Programming tests formulation of a linear objective under linear constraints, graphical solution in two variables, identification of the feasible region and optimisation by the corner-point method. The mathematics is simple; most marks are lost in translation and shading.
Core rules
- Define decision variables x and y, write the objective Z=ax+by, and list every constraint with the correct inequality and non-negativity x≥0, y≥0.
- Plot each constraint as a line; use a test point to decide which half-plane satisfies the inequality.
- The feasible region is the intersection of all half-planes. It may be bounded, unbounded, empty or a single point.
- Corner-point theorem: if the feasible region is bounded, the optimal value of a linear objective occurs at a vertex.
- Evaluate Z at every vertex and compare; do not stop after finding one value.
- If the region is unbounded, the maximum may not exist; check with an objective line or an arbitrary feasible point.
Worked example
Maximise Z=3x+2y subject to x+y≤4, x≤2, x≥0, y≥0. The vertices are (0,0), (2,0), (2,2) and (0,4). Values: Z(0,0)=0, Z(2,0)=6, Z(2,2)=10, Z(0,4)=8. The maximum is 10 at (2,2).
Mark-losing traps
- Reversing an inequality when reading a word problem such as at most or at least.
- Shading the wrong side of a constraint line.
- Missing a vertex formed by the intersection of two boundary lines.
- Assuming an unbounded region always has a maximum.
- Giving only the maximum value without the coordinates that produce it.