D1-5 Linear programming — 9FM0 revision notes

D1-5.1

Formulation of problems as linear programs including the meaning and use of slack, surplus and artificial variables.

Notes

Evidence from your answers: none yet

Your confidence:

A self-report of how sure you feel. It does not measure mastery. Evidence from your answers reaches secure after the latest Tier 2/3 attempt is correct, with three correct distinct drills across at least two dates and two practice sources.

Explanation

To formulate a linear program, define each decision variable precisely with its units, write the objective as a linear expression to be maximised or minimised, and write one inequality for each limited resource, together with the non-negativity conditions. To use the simplex algorithm every inequality must become an equation.
A constraint such as $3x+2y\leqslant20$ becomes $3x+2y+s_1=20$ , where the slack variable $s_1\geqslant0$ measures the unused amount of that resource.
A constraint such as $x+y\geqslant5$ becomes $x+y-s_3=5$ , where the surplus variable $s_3\geqslant0$ measures the excess over the minimum.
A surplus alone does not give a basic feasible starting point, because setting $x=y=0$ would force $s_3=-5$ , so an artificial variable is added: $x+y-s_3+t_1=5$ with $t_1\geqslant0$ .
Artificial variables have no meaning in the original problem, so the algorithm must drive every one of them to zero before the real optimisation begins.

Worked example

A factory makes $x$ tables and $y$ chairs. Wood is limited to $30$ units, with $5$ per table and $2$ per chair, and at least $4$ tables must be made. Each table yields a profit of $£40$ and each chair $£15$ . Formulate the problem and write the constraints as equations.

1.Maximise $P=40x+15y$ subject to $5x+2y\leqslant30$ and $x\geqslant4$ , with $x\geqslant0$ and $y\geqslant0$ .
2.The wood constraint becomes $5x+2y+s_1=30$ , where $s_1$ is the unused wood.
3.The table constraint becomes $x-s_2=4$ , where $s_2$ is the number of tables above the minimum.
4.Since $x=y=0$ would make $s_2=-4$ , add an artificial variable: $x-s_2+t_1=4$ .

Answer: Maximise $P=40x+15y$ subject to $5x+2y+s_1=30$ and $x-s_2+t_1=4$ , with all variables non-negative.

Common mistakes

Don't fall into the trap of adding a slack variable to a $\geqslant$ constraint instead of subtracting a surplus.
Don't fall into the trap of omitting the artificial variable, so the initial tableau is not feasible.
Don't fall into the trap of defining variables loosely, for example as "tables" rather than "the number of tables made each day".

Exam tip

Write the units into every variable definition; a formulation mark is often lost for a variable that is named but not quantified.

Tier 1 · Easy

ORIGINAL

1.

Write the constraint

4x+3y\leqslant36

as an equation using a slack variable, and state what the slack variable measures.

(2)

(Total for Question 1 is 2 marks)

Tier 2 · Standard

ORIGINAL

1.

A bakery makes

x

loaves and

y

rolls each day. A loaf uses

500

g of flour and

12

minutes of oven time; a roll uses

80

g of flour and

3

minutes. There are

60

kg of flour and

600

minutes of oven time available, and at least

40

rolls must be made. A loaf sells for

£3

and a roll for

£0.60

. Formulate the problem as a linear program.

(6)

(Total for Question 1 is 6 marks)

Tier 3 · Hard

ORIGINAL

1.

A haulier runs

x

small vans,

y

medium vans and

z

large lorries each week. Small vans carry

2

tonnes, medium

5

tonnes and large

12

tonnes, and at least

180

tonnes must be moved. Weekly costs are

£300

,

£550

and

£1100

, and the budget is

£28000

. Drivers are available for at most

40

vehicles in total, and the number of large lorries may not exceed the number of medium vans. Formulate the problem as a linear program and write every constraint as an equation.

(8)

(Total for Question 1 is 8 marks)

D1-5.2

Graphical solution of two variable problems using objective line and vertex methods including cases where integer solutions are required.

Notes

Evidence from your answers: none yet

Your confidence:

A self-report of how sure you feel. It does not measure mastery. Evidence from your answers reaches secure after the latest Tier 2/3 attempt is correct, with three correct distinct drills across at least two dates and two practice sources.

Explanation

For two variables, draw each constraint as a line and shade the region it excludes, leaving the feasible region unshaded. The optimum of a linear objective always occurs at a vertex, so the vertex method evaluates the objective at every corner of the feasible region and picks the best value.
The objective line method instead draws one line of the form $ax+by=k$ for a convenient $k$ and slides it parallel across the region;
the last vertex it touches on the way out is optimal, and this method also shows immediately when an edge is optimal, which happens when the objective line is parallel to a constraint and gives infinitely many optimal points.
When the variables must be whole numbers the optimal vertex is often not a lattice point, and it is not enough to round: test the integer points near the optimal vertex, checking each one against every constraint, and take the best feasible one.
That value is usually strictly worse than the continuous optimum.

Worked example

Maximise $P=5x+4y$ subject to $2x+3y\leqslant24$ and $3x+y\leqslant21$ , with $x$ , $y\geqslant0$ .

1.The lines meet where $2x+3y=24$ and $3x+y=21$ , giving $x=\frac{39}{7}$ and $y=\frac{30}{7}$ .
2.The other vertices are $(0,0)$ , $(7,0)$ and $(0,8)$ .
3.Evaluating $P$ gives $0$ , $35$ , $32$ and $5\left(\frac{39}{7}\right)+4\left(\frac{30}{7}\right)=\frac{315}{7}=45$ .
4.The largest value is $45$ .

Answer: The maximum is $P=45$ at $x=\frac{39}{7}$ , $y=\frac{30}{7}$ .

Common mistakes

Don't fall into the trap of shading the feasible side rather than the excluded side, so the region is unclear.
Don't fall into the trap of rounding a non-integer optimal vertex instead of testing nearby lattice points against every constraint.
Don't fall into the trap of testing only the vertices formed by the constraint lines and forgetting the axes.

Exam tip

Solve the two binding equations simultaneously rather than reading the intersection off the graph; examiners expect exact fractions, not measured values.

Tier 1 · Easy

ORIGINAL

1.

The feasible region of a linear program has vertices

(0,0)

,

(6,0)

,

(4,5)

and

(0,7)

. Use the vertex method to maximise

P=3x+2y

.

(3)

(Total for Question 1 is 3 marks)

Tier 2 · Standard

ORIGINAL

1.

Maximise

P=5x+4y

subject to

2x+3y\leqslant24

,

3x+y\leqslant21

,

x\geqslant0

and

y\geqslant0

, using the vertex method. Give your answer exactly.

(6)

(Total for Question 1 is 6 marks)

Tier 3 · Hard

ORIGINAL

1.

Maximise

P=5x+4y

subject to

2x+3y\leqslant24

and

3x+y\leqslant21

, with

x

,

y\geqslant0

, given that

x

and

y

must be whole numbers. Show that rounding the continuous optimum does not work, and find the integer optimum.

(8)

(Total for Question 1 is 8 marks)

D1-5.3

The Simplex algorithm and tableau for maximising and minimising problems with ≤ constraints.

Notes

Evidence from your answers: none yet

Your confidence:

A self-report of how sure you feel. It does not measure mastery. Evidence from your answers reaches secure after the latest Tier 2/3 attempt is correct, with three correct distinct drills across at least two dates and two practice sources.

Explanation

For a maximisation with only $\leqslant$ constraints, add a slack variable to each constraint and write one row per constraint plus an objective row in which the coefficients of the objective appear with their signs reversed. Each iteration has four steps.
Choose the pivot column as the one with the most negative entry in the objective row. Form the ratio of the value column to the pivot column entry for every row with a strictly positive entry there, and choose the pivot row with the smallest non-negative ratio.
Divide the pivot row by the pivot element so that the pivot becomes $1$ , then add or subtract multiples of the new pivot row from every other row, including the objective row, until the rest of the pivot column is zero.
The algorithm stops when the objective row has no negative entries; the value column then gives the basic variables, every non-basic variable is zero, and the bottom right entry is the optimal value.
To minimise $C$ , maximise $P=-C$ and negate the answer at the end.

Worked example

Maximise $P=5x+4y$ subject to $2x+3y\leqslant24$ and $3x+y\leqslant21$ . Carry out the first iteration.

1.The initial tableau has rows $s_1$ : $2, 3, 1, 0$ with value $24$ ; $s_2$ : $3, 1, 0, 1$ with value $21$ ; and $P$ : $-5, -4, 0, 0$ with value $0$ .
2.The most negative objective entry is $-5$ , so the pivot column is $x$ .
3.The ratios are $24\div2=12$ and $21\div3=7$ , so the pivot row is $s_2$ and the pivot element is $3$ .
4.Dividing gives the new $x$ row $1, \frac13, 0, \frac13$ with value $7$ , and eliminating leaves $s_1$ : $0, \frac73, 1, -\frac23$ with value $10$ , and $P$ : $0, -\frac73, 0, \frac53$ with value $35$ .

Answer: After one iteration $x=7$ , $y=0$ , $s_1=10$ and $P=35$ , and a further iteration is needed because $-\frac73$ is still negative.

Common mistakes

Don't fall into the trap of forming a ratio using a negative or zero entry in the pivot column.
Don't fall into the trap of forgetting to update the objective row, so the stopping test is applied to stale numbers.
Don't fall into the trap of reading the objective coefficients into the tableau without reversing their signs.

Exam tip

After each iteration state the current values of every variable and of $P$ ; those interim statements carry marks even if a later iteration goes wrong.

Tier 1 · Easy

ORIGINAL

1.

A simplex tableau has objective row entries

-6

,

-9

,

0

,

0

under the columns

x

,

y

,

s_1

,

s_2

. State the pivot column and explain your choice.

(2)

(Total for Question 1 is 2 marks)

Tier 2 · Standard

ORIGINAL

1.

Maximise

P=5x+4y

subject to

2x+3y\leqslant24

and

3x+y\leqslant21

with

x

,

y\geqslant0

, using the simplex algorithm. Give the final tableau and state the values of

x

,

y

,

s_1

,

s_2

and

P

.

(8)

(Total for Question 1 is 8 marks)

Tier 3 · Hard

ORIGINAL

1.

Maximise

P=5x+6y+4z

subject to

3x+2y+z\leqslant60

,

x+4y+2z\leqslant80

and

2x+2y+3z\leqslant70

, with

x

,

y

,

z\geqslant0

. Carry out two iterations of the simplex algorithm, stating the pivots and the tableau after each.

(9)

(Total for Question 1 is 9 marks)

D1-5.4

The two-stage Simplex and big-M methods for maximising and minimising problems which may include both ≤ and ≥ constraints.

Notes

Evidence from your answers: none yet

Your confidence:

A self-report of how sure you feel. It does not measure mastery. Evidence from your answers reaches secure after the latest Tier 2/3 attempt is correct, with three correct distinct drills across at least two dates and two practice sources.

Explanation

When a problem contains a $\geqslant$ constraint, the origin is not feasible, so the tableau needs an artificial variable and a way of removing it. The two-stage method runs the simplex twice.
Stage one minimises the sum of the artificial variables: express that sum in terms of the non-basic variables using the constraint rows, minimise it by ordinary pivoting, and stop when it reaches zero. If it cannot reach zero the original problem is infeasible.
Stage two then discards the artificial columns and the stage-one objective, and maximises the true objective from the feasible tableau that stage one produced.
The big-M method does the same work in one pass by subtracting $M$ times each artificial variable from the objective, where $M$ stands for a number larger than anything else in the problem.
Substituting the constraint rows to remove the artificial variables from the objective row gives coefficients containing $M$ , and because $M$ is huge those terms dominate the choice of pivot column, which forces the artificial variables out early.

Worked example

Maximise $P=3x+2y$ subject to $x+y\leqslant10$ and $x+2y\geqslant8$ . Set up the big-M tableau.

1.The constraints become $x+y+s_1=10$ and $x+2y-s_2+t_1=8$ .
2.The objective becomes $P=3x+2y-Mt_1$ , that is $P-3x-2y+Mt_1=0$ .
3.Substituting $t_1=8-x-2y+s_2$ removes $t_1$ from the objective row.
4.This gives $P-(3+M)x-(2+2M)y+Ms_2=-8M$ .

Answer: The initial tableau has rows $s_1$ : $1, 1, 1, 0, 0$ with value $10$ ; $t_1$ : $1, 2, 0, -1, 1$ with value $8$ ; and $P$ : $-(3+M), -(2+2M), 0, M, 0$ with value $-8M$ .

Common mistakes

Don't fall into the trap of leaving the artificial variable in the objective row instead of substituting it out, so the tableau is inconsistent.
Don't fall into the trap of treating $M$ as a small number when choosing the pivot column.
Don't fall into the trap of starting stage two without checking that every artificial variable has reached zero.

Exam tip

Write the objective row of a big-M tableau in the form $-(a+bM)$ so the comparison of columns is a comparison of the $M$ coefficients first; that is the whole point of the method.

Tier 1 · Easy

ORIGINAL

1.

State the purpose of stage one of the two-stage simplex method, and state what conclusion is drawn if stage one ends with a positive value.

(3)

(Total for Question 1 is 3 marks)

Tier 2 · Standard

ORIGINAL

1.

For the problem of maximising

P=3x+2y

subject to

x+y\leqslant10

and

x+2y\geqslant8

, with

x

,

y\geqslant0

, write down the initial big-M tableau, showing how the artificial variable is removed from the objective row.

(6)

(Total for Question 1 is 6 marks)

Tier 3 · Hard

ORIGINAL

1.

Carry out the big-M method in full for maximising

P=3x+2y

subject to

x+y\leqslant10

and

x+2y\geqslant8

, with

x

,

y\geqslant0

. State each pivot and the final solution.

(10)

(Total for Question 1 is 10 marks)

Formulation of problems as linear programs including the meaning and use of slack, surplus and artificial variables.

Tier 1 · Easy

Tier 2 · Standard

Tier 3 · Hard

Graphical solution of two variable problems using objective line and vertex methods including cases where integer solutions are required.

Tier 1 · Easy

Tier 2 · Standard

Tier 3 · Hard

The Simplex algorithm and tableau for maximising and minimising problems with ≤ constraints.

Tier 1 · Easy

Tier 2 · Standard

Tier 3 · Hard

The two-stage Simplex and big-M methods for maximising and minimising problems which may include both ≤ and ≥ constraints.

Tier 1 · Easy

Tier 2 · Standard

Tier 3 · Hard

Want help turning these notes into marks?