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.
WHAT YOU PROBABLY THINK
The optimal solution of a linear program is always at the vertex furthest from the origin.
Writing the problem down
Start by defining the variables in words, including their units: marks are lost for x with no explanation 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 that 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; and an artificial variable is then added to that same constraint so that a starting solution exists at all.
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): 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; the last corner it touches is the optimum. It is faster and shows at once when two corners tie, which happens when the objective is parallel to a constraint. Whichever is used, say which, and draw the line if the question asks for it.
When the variables must be whole numbers, the optimum may not be 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.
YOUR TURN
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 would not improve the answer.
THE EXAM BIT
- 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 rather than rounding.
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
5
x
+
2
y
−
s
₁
+
t
₁
=
3
0
,
w
h
e
r
e
s
₁
i
s
t
h
e
s
u
r
p
l
u
s
r
e
c
o
r
d
i
n
g
t
h
e
e
x
c
e
s
s
o
v
e
r
3
0
a
n
d
t
₁
i
s
t
h
e
a
r
t
i
f
i
c
i
a
l
v
a
r
i
a
b
l
e
t
h
a
t
p
r
o
v
i
d
e
s
a
s
t
a
r
t
i
n
g
s
o
l
u
t
i
o
n
.
The optimum of a linear program is 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.
CHECK YOUR PROGRESS
Rate how confident you feel with each objective for this lesson. Ratings are saved in this browser, on this device only.
- 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.
Open the full revision checklist to see every objective in the course in one place.
No animated video for this topic yet; these notes stand alone.