D1 5.3 - The Simplex algorithm | Edexcel A-Level Further Mathematics

Simplex improves a feasible linear programming solution through exact tableau row operations. You will choose pivots, solve maximisation and minimisation problems with upper-bound constraints, reconstruct models from tableaux, and check optimality and exceptional outcomes (D1 5.3).

Read a tableau as a system of equations

If product $x$ earns $3$ pounds and product $y$ earns $2$ pounds, should you fill the capacity with $x$ and stop? Under $x+y\le4$ , $2x+y\le6$ , the feasible plan $(3,0)$ earns $9$ , but $(2,2)$ earns $10$ . Producing less of the better-paid product can earn more overall.

Simplex makes that improvement systematically. It solves a continuous linear program; integer requirements need a separate integer-solution check.

You already know

Formulation turns $\le$ constraints into equations with non-negative slack variables. Artificial variables are temporary and must vanish at an original solution. Keep the objective direction, variable meanings and all original constraints visible.

For the opening model, maximise $P=3x+2y$ . The equations are

x+y+s_1=4,\qquad2x+y+s_2=6,\qquad P-3x-2y=0

Pearson's tableau puts constraint rows first, the objective or profit row last, and the right-hand side in Value:

b.v.	$x$	$y$	$s_1$	$s_2$	Value
$s_1$	$1$	$1$	$1$	$0$	$4$
$s_2$	$2$	$1$	$0$	$1$	$6$
$P$	$-3$	$-2$	$0$	$0$	$0$

The coefficient of $P$ in its equation is implicitly $1$ ; there is no separate $P$ column.

Basic feasible solution

Basic-variable columns have one $1$ and zeros elsewhere in the constraint rows, with zero coefficients in the objective row. Set the non-basic variables to zero; each basic variable is then its row's Value. The solution is feasible when these basic values are non-negative and the original constraints are satisfied.

Here $s_1,s_2$ are basic, while $x=y=0$ , giving $s_1=4,s_2=6,P=0$ . Ordinary slack-start Simplex requires non-negative right-hand sides and an available initial feasible basis. Lower-bound or equality rows may need the methods developed in the next lesson.

Different variable bounds may first need a substitution. For example, $z\le-3$ can be written $z=-3-Z$ , $Z\ge0$ . Then $2x-z\le8$ becomes $2x+Z\le5$ , and an objective $C=x+2z$ becomes $C=x-2Z-6$ . Substitute into the objective and every constraint, then translate the final answer back.

Key idea

A tableau row is an equation, not a list of variable values. Basic values come from Value after non-basic variables are set to zero; objective-row coefficients are not solution coordinates.

Read the displayed initial tableau using its basis.

Choose a feasible improving pivot and update every row

Choose an improving non-basic column, then use the ratio test to keep basic values non-negative.

With this maximisation convention, a negative profit-row coefficient represents a variable whose increase can improve the objective, provided a positive feasible move is possible. Use the most negative coefficient when instructed.

One Simplex iteration

For a feasible maximisation tableau:

Choose the most negative profit-row coefficient, excluding Value, as the entering column. If none is negative, the tableau is optimal.
For constraint rows with a strictly positive entry in that column, calculate Value divided by that entry. Choose the least non-negative ratio; that basic variable leaves.
Divide the entire pivot row by the pivot entry. Change its basic-variable label to the entering variable.
Use the new pivot row to make every other entry in the entering column zero, including the profit row. Update every column, including Value.
Repeat, checking feasibility and the basis.

The algorithm and tableau conventions are not supplied.

Not in the formula booklet: learn it.

Ignore zero or negative pivot-column entries when forming ratios. A zero Value divided by a positive entry is a valid ratio zero: do not ignore it. For tied eligible ratios or tied most-negative coefficients, choose one consistently and show the choice. A zero-ratio pivot may change the basis without immediately improving the objective.

Worked example 1: an improvement that reduces an earlier decision

Question. Use Simplex to maximise $P=3x+2y$ , subject to $x+y\le4$ , $2x+y\le6$ , $x,y\ge0$ . State row operations.

Plan. Start from the displayed slack basis, pivot on the most negative profit coefficient and continue until no improving coefficient remains.

Enter $x$ . Ratios are $4/1=4$ , $6/2=3$ , so $s_2$ leaves. Write $R_P$ for the profit row. Use

R_2\leftarrow\frac12R_2,\qquad R_1\leftarrow R_1-R_2,\qquad R_P\leftarrow R_P+3R_2

The latter two operations use the new pivot row.

b.v.	$x$	$y$	$s_1$	$s_2$	Value
$s_1$	$0$	$1/2$	$1$	$-1/2$	$1$
$x$	$1$	$1/2$	$0$	$1/2$	$3$
$P$	$0$	$-1/2$	$0$	$3/2$	$9$

This means $P=9+y/2-3s_2/2$ . A feasible increase in $y$ can improve profit, so this point is not optimal.

Now enter $y$ . Ratios are $1/(1/2)=2$ , $3/(1/2)=6$ , so $s_1$ leaves. Use

R_1\leftarrow2R_1,\qquad R_2\leftarrow R_2-\frac12R_1,\qquad R_P\leftarrow R_P+\frac12R_1

b.v.	$x$	$y$	$s_1$	$s_2$	Value
$y$	$0$	$1$	$2$	$-1$	$2$
$x$	$1$	$0$	$-1$	$1$	$2$
$P$	$0$	$0$	$1$	$1$	$10$

Why this step? The least ratio stops a basic variable becoming negative. Whole-tableau operations preserve the equations and make the new basis readable.

Answer. Set $s_1=s_2=0$ : $x=y=2$ , maximum $P=10$ .

Check. Both capacities hold with equality. The final equation $P=10-s_1-s_2$ proves $P\le10$ . Moving from $(3,0)$ to $(2,2)$ raises profit from $9$ to $10$ .

Worked example 2 changes only the objective's $y$ coefficient, from $2$ to $4$ . The entering column and route through feasible solutions change.

Worked example 2: a different first pivot

Question. For the same constraints, maximise $P=3x+4y$ using Simplex.

Plan. Retain the constraint rows and start with profit row $(-3,-4,0,0\mid0)$ .

Enter $y$ . Ratios $4/1=4$ , $6/1=6$ select $R_1$ , replacing $s_1$ by $y$ . The pivot is already $1$ . Use

R_2\leftarrow R_2-R_1,\qquad R_P\leftarrow R_P+4R_1

b.v.	$x$	$y$	$s_1$	$s_2$	Value
$y$	$1$	$1$	$1$	$0$	$4$
$s_2$	$1$	$0$	$-1$	$1$	$2$
$P$	$1$	$0$	$4$	$0$	$16$

Why this step? The changed reward selects $y$ , but the unchanged constraints still determine its limiting feasible ratio.

Answer. All profit coefficients are non-negative. With $x=s_1=0$ , $y=4,s_2=2$ , maximum $P=16$ .

Check. $P=16-x-4s_1\le16$ . Original profit is $3(0)+4(4)=16$ , and the second resource has two units unused.

With three or four decision variables, the same operations include every decision, slack and Value entry. Retain exact fractions.

Exam tip

State row operations as assignments and identify an updated pivot row. Update basic-variable labels and the profit row. Explain from the profit equation which feasible increase improves the objective, rather than merely mentioning a negative entry.

Change only the objective's $y$ coefficient again.

Watch out

Wrong: divide the pivot row, then eliminate other rows using its old entries. All eliminations must use the same new normalised pivot row, including the profit row and Value column. Otherwise the new tableau no longer represents equivalent equations, even if the pivot column appears correct.

State the row assignments before interpreting the resulting optimum.

Minimise by maximising a transformed objective

To minimise $C$ , maximise $P=-C$ ; retain the constraints and restore the original objective and variables at the end.

A negative transformed objective value can be correct. Its sign does not decide optimality: use the profit coefficients and feasible basis. A constant objective term belongs in Value, not a decision-variable column.

Minimisation and translated variables

\min C\quad\Longleftrightarrow\quad\max(-C)

For a lower bound $x\ge b$ , substitute $x=X+b$ , $X\ge0$ . For an upper bound $x\le b$ , substitute $x=b-X$ , $X\ge0$ , when using that one-sided bound as the variable's domain. Substitute into every constraint and the objective.

These reformulate the same optimisation question.

Not in the formula booklet: learn it.

The following problems show why an objective offset must be retained even though it does not change which feasible plan is best.

Worked example 3: a lower bound and a cost objective

Question. Minimise $C=20-3x-2y$ , subject to $x+y\le5$ , $2x+y\le8$ , $x\ge1,y\ge0$ , using Simplex after substitution.

Plan. Set $x=X+1$ , $y=Y$ , maximise $P=-C$ , then translate back.

\begin{aligned} X+Y&\le4,\qquad2X+Y\le6,\qquad X,Y\ge0 &&\text{translate both capacities}\\ P&=-17+3X+2Y &&\text{transform the entire objective} \end{aligned}

The initial tableau is

b.v.	$X$	$Y$	$s_1$	$s_2$	Value
$s_1$	$1$	$1$	$1$	$0$	$4$
$s_2$	$2$	$1$	$0$	$1$	$6$
$P$	$-3$	$-2$	$0$	$0$	$-17$

Enter $X$ , using ratios $4,3$ . Apply $R_2\leftarrow R_2/2$ , then $R_1\leftarrow R_1-R_2$ , $R_P\leftarrow R_P+3R_2$ :

b.v.	$X$	$Y$	$s_1$	$s_2$	Value
$s_1$	$0$	$1/2$	$1$	$-1/2$	$1$
$X$	$1$	$1/2$	$0$	$1/2$	$3$
$P$	$0$	$-1/2$	$0$	$3/2$	$-8$

Enter $Y$ , with ratios $2,6$ . Use $R_1\leftarrow2R_1$ , then $R_2\leftarrow R_2-R_1/2$ , $R_P\leftarrow R_P+R_1/2$ :

b.v.	$X$	$Y$	$s_1$	$s_2$	Value
$Y$	$0$	$1$	$2$	$-1$	$2$
$X$	$1$	$0$	$-1$	$1$	$2$
$P$	$0$	$0$	$1$	$1$	$-7$

Why this step? The tableau gives transformed variables and $P=-C$ . Reporting $X=2$ as the original $x$ , or reporting $P=-7$ as the cost, would answer a different question.

Answer. $X=Y=2$ , hence $x=3,y=2$ , minimum $C=7$ .

Check. Both original capacities hold with equality, $x\ge1$ , and $20-3(3)-2(2)=7$ . The final equation gives $P=-7-s_1-s_2\le-7$ .

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 Mathematics

Further Pure Mathematics 1

Further Pure Mathematics 2

Further Statistics 1

Further Statistics 2

Further Mechanics 1

Further Mechanics 2

Decision Mathematics 1

Decision Mathematics 2

D1 5.3 - The Simplex algorithm

Read a tableau as a system of equations

Choose a feasible improving pivot and update every row

Minimise by maximising a transformed objective

Continue this lesson.

Learn faster with Nova