Maths › Decision Mathematics 1 › Linear programming: formulation and graphical solution
Linear programming: formulation and graphical solution
Turn a description into inequalities, shade what is allowed, and the best answer will be sitting at a corner. Half the marks are for the translation and half for knowing where to look.
Builds on Simultaneous equations and inequalities and Straight lines.
IN THIS TOPIC
- Define variables and write a problem as an objective and constraints.
- Shade the feasible region and find the optimum by vertex or objective line.
- Introduce slack, surplus and artificial variables correctly.
- Deal with a problem whose variables must be whole numbers.
COMMON MISCONCEPTION
The optimal solution of a linear program is always at the vertex furthest from the origin.
Writing the problem down
Define the variables in words, including their units. Marks are lost for an unexplained x far more often than for the algebra. Then write the objective to be maximised or minimised, and each restriction as an inequality, remembering the non-negativity conditions the context implies.
Inequalities become equations by adding a variable. A slack variable is added to a ≤ constraint to take up the unused amount. A surplus variable is subtracted from a ≥ constraint to record the excess. An artificial variable is then added to that same constraint, because subtracting the surplus leaves no starting solution to work from.
WORKED EXAMPLE
Testing the corners
Maximise P = 4x + 5y subject to x + y ≤ 10, 2x + 3y ≤ 24 and x, y ≥ 0.
The vertices are (0, 0), (10, 0), (0, 8) and the intersection of the two lines.
Solving x + y = 10 with 2x + 3y = 24 gives 30 − x = 24, so x = 6 and y = 4.
P at the four corners: 0, 40, 40 and 44. The maximum is at (6, 4), which is nearer the origin than (10, 0), so distance is not what decides it.
Two ways to find the corner
The vertex method evaluates the objective at every corner and takes the best. It is reliable and needs no judgement, and with four or five corners it is quick enough.
The objective line method draws one line of constant objective value and slides it parallel across the region, with the last corner it touches being the optimum. It is faster, and it shows at once when two corners tie, which happens when the objective runs parallel to a constraint. Whichever method you use, say which, and draw the line if the question asks for it.
When the variables must be whole numbers the optimum may not sit at a corner at all. Find the corner first, then test the integer points around it that lie inside the region, and give the best of those. Rounding the corner coordinates can land you outside the region entirely.
GUIDED PRACTICE
Slack at the optimum
For the same problem, find the value of each slack variable at the optimum and say what it means.
Show the working
At (6, 4) the first constraint gives 6 + 4 + s1 = 10, so s1 = 0.
The second gives 12 + 12 + s2 = 24, so s2 = 0.
Both slacks are zero, so both constraints are binding: the optimum sits exactly where the two lines meet.
A non-zero slack would mean spare capacity in that constraint, and relaxing it further would not improve the answer.
ASSESSMENT FOCUS
- Define every variable in words with its units before writing any inequality.
- Include the non-negativity constraints. They bound the region and are worth a mark.
- Say which method you used, and for the objective line method draw the line.
- For integer problems, test the lattice points near the corner instead of rounding.
- Shade consistently and label which side of each line is allowed, or the region will be ambiguous.
CHECK YOURSELF
Write 5x + 2y ≥ 30 as an equation using a surplus and an artificial variable.
Show a hint
Subtract the surplus, then add the artificial.
Show the answer
5x + 2y − s₁ + t₁ = 30, where s₁ is the surplus recording the excess over 30 and t₁ is the artificial variable that provides a starting solution.
The optimum of a linear program sits at a vertex of the feasible region, though not necessarily the furthest one from the origin.
A ≤ constraint gains a slack variable; a ≥ constraint loses a surplus variable and gains an artificial one.
WORKBOOK
Printable practice for this topic: original exam-style questions with room to work, and a fully worked answer book. Free to use; please do not redistribute or sell.
Or read them with their worked answers on the linear programming: formulation and graphical solution questions page.
CHECK YOUR PROGRESS
Rate how confident you feel with each objective for this lesson. Ratings are saved in this browser, on this device, unless you sign in.
- Define variables and write a problem as an objective and constraints.
- Shade the feasible region and find the optimum by vertex or objective line.
- Introduce slack, surplus and artificial variables correctly.
- Deal with a problem whose variables must be whole numbers.
Open the full revision checklist to see every objective in the course in one place.