How is the pivot column chosen?

The most negative entry in the objective row.

How is the pivot row chosen?

Divide each right-hand side by the positive pivot-column entry in its row and take the smallest ratio.

What do you do with the pivot row?

Divide it by the pivot entry, then use it to make every other entry in the pivot column zero.

When is a simplex solution optimal?

When there are no negative coefficients in the objective row.

What are basic variables?

Variables that can be non-zero; they appear in one row with coefficient 1.

What does a slack of zero mean?

The constraint is binding: that resource is fully used.

What does a positive slack mean?

That amount of the resource is unused.

How do you minimise Q using the simplex algorithm?

Maximise P=-Q, then the minimum value of Q is -P.

What do you do after each iteration?

Check the objective row for negative entries; if any remain, do another iteration.

The simplex algorithmAQA A-Level Further Maths: Flashcards

Card 1 of 130 of 13 known

Question

What does a slack variable represent?

Tap or press Space to reveal

Tap card or press Space to flip

See all 13 cards

What does a slack variable represent?: The unused amount of a resource in a $\leq$ constraint.
How is $2x+y\leq10$ written with a slack variable?: $2x+y+r=10$ with $r\geq0$ .
How is the objective $P=4x+3y$ written in the tableau?: $P-4x-3y=0$ .
How is the pivot column chosen?: The most negative entry in the objective row.
How is the pivot row chosen?: Divide each right-hand side by the positive pivot-column entry in its row and take the smallest ratio.
What do you do with the pivot row?: Divide it by the pivot entry, then use it to make every other entry in the pivot column zero.
When is a simplex solution optimal?: When there are no negative coefficients in the objective row.
What are basic variables?: Variables that can be non-zero; they appear in one row with coefficient 1.
What is the value of a non-basic variable?: Zero.
What does a slack of zero mean?: The constraint is binding: that resource is fully used.
What does a positive slack mean?: That amount of the resource is unused.
How do you minimise $Q$ using the simplex algorithm?: Maximise $P=-Q$ , then the minimum value of $Q$ is $-P$ .
What do you do after each iteration?: Check the objective row for negative entries; if any remain, do another iteration.

Exam questions on The simplex algorithm

Maximise $P=2x+y$ subject to $x+y\leq8$ , $3x+y\leq18$ , $x\geq0$ and $y\geq0$ . The simplex algorithm is to be used, with slack variables $r$ and $s$ added to the first and second constraints.
Carry out the first iteration. State the values of $x$ , $y$ and $P$ after it.2 marks
The simplex algorithm is used to maximise $P=2x+3y$ subject to $x+2y\leq14$ and $3x+y\leq18$ , with slack variables $r$ and $s$ . After the first iteration the equations are $\frac12x+y+\frac12r=7$ , $\frac52x-\frac12r+s=11$ and $P-\frac12x+\frac32r=21$ .
Find the pivot row for the next iteration, giving a reason.2 marks
Maximise $P=4x+3y$ subject to $2x+y\leq10$ , $x+y\leq8$ , $x\geq0$ and $y\geq0$ . The simplex algorithm is to be used with slack variables $r$ and $s$ added to the first and second constraints.
Write down the initial simplex tableau as equations, and state which entry is the pivot in the first iteration, with a reason.3 marks

See the full worksheet

Written by the Exaim team, led by Shaun Daswani (Head of Upper Secondary, Improve ME Institute; MSc Financial Mathematics, Imperial College London; BSc, UCL) and Jason Daswani (operational lead, Improve ME Institute; LSE).