Linear Programming
Linear programming (LP) is the exam's core optimisation topic: you turn a word problem into an objective function and a set of linear constraints, then solve and interpret. STPM 950 tests formulation, graphical solutions for two variables, and the logic of the simplex method and shadow prices.
Formulation rules
- Define decision variables with units (e.g. x = chairs per day).
- Write the objective as maximise or minimise a linear expression.
- Convert every limit into an inequality; use ≥ for minimum requirements and ≤ for resource limits.
- Add non-negativity, x ≥ 0, y ≥ 0.
Graphical method
Plot each constraint as a line, shade the feasible side, identify the feasible region, and evaluate the objective at every corner point. The optimum occurs at a corner (or along an edge if the objective is parallel to a constraint).
Worked example: A workshop makes x chairs and y tables. Profit is 30x + 50y. Labour: 2x + 3y ≤ 120; wood: x + y ≤ 50. Corners: (0,0)=0; (50,0)=1500; (0,40)=2000; intersection of 2x+3y=120 and x+y=50 gives x=30, y=20, profit 1900. Maximum profit is 2000 at (0,40).
Traps: reversing an inequality when a problem says 'at least'; forgetting non-negativity; testing only intersection points; and treating a fractional solution as valid when the variables must be integers.
Simplex awareness
For more than two variables, the simplex method moves between basic feasible solutions; the final tableau's shadow prices show the marginal value of relaxing a constraint.