Linear Programming
Linear programming questions ask you to formulate an objective and constraints from a word problem, then solve graphically in two variables using the corner point theorem.
Formulation steps
- Name the decision variables x and y and their units.
- Write the objective Z = ax + by, stating maximise or minimise.
- Translate each resource limit into a linear inequality.
- Add the non-negativity constraints x ≥ 0, y ≥ 0.
Graphical solution
Draw each constraint as a line, shade the feasible region (the side satisfying the inequality, checked with a test point such as the origin). Find the corner points by solving pairs of boundary lines. The corner point theorem says the optimum of a linear objective on a bounded feasible region occurs at a corner; evaluate Z at every corner and pick the largest (maximisation) or smallest (minimisation) value.
Worked example
Maximise Z = 3x + 2y subject to x + y ≤ 4, x ≤ 2, x ≥ 0, y ≥ 0. Corners: (0,0), (2,0), (2,2) from x = 2 with x + y = 4, and (0,4). Values: Z = 0, 6, 10, 8 respectively. Maximum Z = 10 at (2, 2).
Traps that cost marks
- Omitting non-negativity, which lets the region run into negative x or y.
- Evaluating Z at an intersection of two lines that lies outside the feasible region.
- Shading the wrong side of a constraint and then reading off wrong corners.
- Writing a "≥" constraint where the wording means "at most".
- For an unbounded feasible region, checking only corners without confirming the minimum actually exists.