DD3, DD4 - The simplex algorithm | AQA A-Level Further Mathematics

Graphical optimisation becomes awkward when there are more than two decision variables. DD3 introduces the simplex algorithm, which improves a feasible solution using row operations; DD4 explains what its tableaux mean. You will build a tableau, choose safe pivots and read the resulting optimum in the original variables.

Slack variables and the initial tableau

How can we maximise $3x+2y$ under $x+y\leq4$ , $2x+y\leq6$ and $x,y\geq0$ without drawing the region? If a workshop has 4 hours available and uses only 3, the unused hour is a number too. Recording unused capacity turns inequalities into equations that row operations can handle.

Slack variable

For a constraint $ax+by\leq c$ , introduce a nonnegative slack variable $r$ and write $ax+by+r=c$ . Thus $r=c-ax-by$ measures unused capacity. Each inequality needs its own slack variable, with the same units as that constraint.

A tableau stores the coefficients of these equations and their right-hand values. We put the objective row first, with coefficient $+1$ for $P$ , and move all variable terms to its left. Thus maximising $P=3x+2y$ starts with $P-3x-2y=0$ . Some resources use the opposite sign convention; follow the equation rather than mixing their stopping rule with this one.

Tableau convention

Write constraints as equations with nonnegative variables. Write the objective with coefficient $+1$ , for example $P-3x-2y=0$ . These rules and the simplex algorithm are not supplied in the AQA formula booklet.

For constraints of the form $A\mathbf x\leq\mathbf b$ with $\mathbf b\geq\mathbf0$ , adding slacks gives an immediate feasible start: set decision variables to zero and slacks equal to the right-hand values. Coefficients of the decision variables may be negative. What matters for this start is that the resulting slacks are nonnegative.

Worked example 1: storing equations

Question. Form the initial tableau for maximising $P=3x+2y$ , subject to $x+y\leq4$ , $2x+y\leq6$ , $x,y\geq0$ .

Plan. Add one slack per constraint, then enter every coefficient, including zeros.

The equations are $P-3x-2y=0$ , $x+y+r=4$ , $2x+y+s=6$ , where $r,s\geq0$ . Therefore

\begin{array}{c|rrrrr|r} &P&x&y&r&s&\text{value}\\\hline R_0&1&-3&-2&0&0&0\\ R_1&0&1&1&1&0&4\\ R_2&0&2&1&0&1&6 \end{array}

Answer. This is a feasible initial tableau, representing $x=y=0$ , $r=4$ , $s=6$ , $P=0$ .

Check. Reading its last two rows back gives exactly the two slack equations. Setting $x=y=0$ also satisfies both original inequalities, so the stored starting solution is feasible.

Change only the sign of $y$ in the second constraint. This does not change the rule for adding a slack.

Worked example 2: a negative coefficient is allowed

Question. Form the initial tableau for the same objective and first constraint, but replace the second constraint by $2x-y\leq6$ .

Plan. Keep each equation's signs when recording its coefficients.

\begin{array}{c|rrrrr|r} &P&x&y&r&s&\text{value}\\\hline R_0&1&-3&-2&0&0&0\\ R_1&0&1&1&1&0&4\\ R_2&0&2&-1&0&1&6 \end{array}

Answer. Only the second constraint's $y$ -entry changes. The starting solution is still $x=y=0$ , $r=4$ , $s=6$ .

Check. At $(1,2)$ , direct substitution gives slack $s=6-(2-2)=6$ . The tableau row gives $2(1)-2+s=6$ , also yielding $s=6$ . Changing the slack sign instead would describe the wrong inequality.

A lower-bound constraint requires care. For $x+y\geq3$ , the equation is $x+y-r=3$ with $r\geq0$ , or $-x-y+r=-3$ . The all-zero decision point would give $r=-3$ and is infeasible. Do not launch the ordinary feasible-start algorithm from it; a valid transformation or another supplied feasible basis is needed.

Watch out

Slack for $\leq$ is added: $ax+by+r=c$ . A negative right-hand value can destroy the all-slack feasible start. A negative decision-variable coefficient alone does not.

Build a new tableau from its equations.

Choosing a pivot and preserving feasibility

A pivot replaces one variable held at zero by a variable allowed to increase. The replacement must preserve nonnegative values of every constraint variable.

At a basic solution, choose a set of basic variables whose constraint columns form unit columns, and set the remaining nonbasic variables to zero. A unit column has one 1 and otherwise zeros. In a canonical tableau the basic variables also have zero coefficients in the objective row. Their values can then be read from the right-hand column. Initially the slacks are basic and the decision variables are nonbasic.

With our objective convention, a negative nonbasic coefficient in the objective row indicates potential improvement. For example, $P-3x-2y=0$ means $P=3x+2y$ . A usual choice is the most negative coefficient, breaking ties consistently. The pivot column belongs to that entering variable; the objective row itself is never a candidate pivot row.

For a constraint row $z+a x= b$ , increasing entering $x$ while the other nonbasic variables stay zero gives $z=b-ax$ . If $a>0$ , nonnegativity requires $x\leq b/a$ . If $a=0$ , that row imposes no limit. If $a<0$ , its basic variable increases, so it also imposes no upper limit on this move.

Ratio test and pivot

For a feasible canonical tableau, calculate $b/a$ only for strictly positive constraint entries $a$ in the entering column. Choose the smallest nonnegative ratio, including zero. Divide the pivot row by its pivot entry, then eliminate the entering column from every other row, including the objective row. These steps are not supplied in the formula booklet.

A zero ratio gives a degenerate pivot: the basis changes but the entering value and objective may initially stay unchanged. If ratios tie, either tied row preserves feasibility; state your choice. A consistent tie rule is helpful, although advanced anti-cycling rules are not needed here.

Worked example 3: a positive ratio limits the move

Question. Perform one iteration on the initial tableau in Worked example 1.

Plan. Enter $x$ , use the ratio test, then make its column a unit column.

The objective's most negative entry is $-3$ . The ratios are $4/1=4$ and $6/2=3$ ; choose $R_2$ , with pivot 2. First use $R_2'=R_2/2$ . Then use $R_1'=R_1-R_2'$ , $R_0'=R_0+3R_2'$ :

\begin{array}{c|rrrrr|r} &P&x&y&r&s&\text{value}\\\hline R_0'&1&0&-1/2&0&3/2&9\\ R_1'&0&0&1/2&1&-1/2&1\\ R_2'&0&1&1/2&0&1/2&3 \end{array}

Answer. $x$ enters and $s$ leaves. The new basic solution is $x=3$ , $r=1$ , $y=s=0$ , $P=9$ .

Check. The original constraints give $3+0\leq4$ , $6+0\leq6$ , with slacks $1,0$ . The original objective gives $3(3)+2(0)=9$ , agreeing independently with the new row.

Change only the second right-hand value from 6 to zero. Now the ratio test must allow a zero result.

Worked example 4: a zero ratio must not be discarded

Question. Perform one iteration for maximising $P=3x+2y$ , with $x+y+r=4$ , $2x+y+s=0$ , all variables nonnegative.

Plan. Choose the same entering column but include the zero ratio.

The ratios in column $x$ are $4/1=4$ and $0/2=0$ . Choose the second row. Apply the same row operations as in Worked example 3:

\begin{array}{c|rrrrr|r} &P&x&y&r&s&\text{value}\\\hline R_0'&1&0&-1/2&0&3/2&0\\ R_1'&0&0&1/2&1&-1/2&4\\ R_2'&0&1&1/2&0&1/2&0 \end{array}

Answer. The pivot is valid, but the basic solution is still $x=y=s=0$ , $r=4$ , $P=0$ . The new basic variable $x$ has value zero.

Check. The original equation $2x+y+s=0$ forces all three nonnegative terms to be zero. The calculated solution has exactly this property. Choosing the ratio 4 instead would make $s$ negative and lose feasibility.

Always compute new rows using the normalised pivot row. Record the operations so a single arithmetic slip can be located without guessing.

Watch out

Exclude zero or negative pivot-column entries, not zero ratios. A positive entry with a zero right-hand value is eligible and can be the required pivot. Apply elimination to the objective row too.

Practise choosing among positive, negative and zero entries.

Continue this lesson.

You’re previewing NovaLearn without an account. Create a free account to read the rest.

Create free account

Last Accessed

Core Pure

Mechanics

Statistics

Discrete Mathematics

DD3, DD4 - The simplex algorithm

Slack variables and the initial tableau

Choosing a pivot and preserving feasibility

Continue this lesson.

Learn faster with Nova