AL12, AL13 - The simplex method | OCR A-Level Further Mathematics B (MEI)

Build, pivot and interpret simplex tableaux for a maximisation problem in augmented form. Connect the algebra to movement between feasible vertices, and distinguish optimality, degeneracy and other possible outcomes.

Setting up an initial tableau

How does a table of coefficients know which corner of a feasible region to try next?

Its equations describe one basic feasible solution, and its objective row shows which changes may improve the objective. A pivot changes the description to a neighbouring feasible corner.

You already know

Convert upper-bound inequalities into equalities using non-negative slack variables. A bounded LP has an optimal vertex. Integer restrictions are a separate issue; ordinary simplex solves the continuous LP.

Use the objective equation $P-c_1x-c_2y=0$ , so an initial maximisation row contains the negative profit coefficients. Columns record variables and the right-hand side, labelled RHS.

Basic and non-basic variables

In a canonical tableau, the basic-variable columns form unit columns in the constraint rows, and their objective-row entries are zero. Set the non-basic variables to zero to read the current basic solution from RHS. It is feasible when every variable value is non-negative.

For the usual initial slack basis, the decision variables are zero and each slack equals its constraint's RHS. These RHS values must be non-negative for that starting solution to be feasible.

Worked example 1: a ready-to-start slack basis

Question. Set up the initial tableau for

\text{Maximise }P=3x+2y,\quad 2x+y\le8,\quad x+2y\le8,\quad x,y\ge0

Plan. Add slacks, move the objective terms to the left and copy coefficients into columns.

\begin{aligned} P-3x-2y&=0&&\text{objective equation}\\ 2x+y+s_1&=8&&\text{first resource}\\ x+2y+s_2&=8&&\text{second resource} \end{aligned}

$P$	$x$	$y$	$s_1$	$s_2$	RHS
$1$	$-3$	$-2$	$0$	$0$	$0$
$0$	$2$	$1$	$1$	$0$	$8$
$0$	$1$	$2$	$0$	$1$	$8$

Why this step? The slack unit columns supply a basic solution without solving simultaneous equations.

Answer. The displayed tableau has basic variables $s_1,s_2$ , non-basic variables $x,y$ , and $P=0$ .

Check. At $x=y=0$ , both slacks are $8$ , so the starting vertex is the feasible origin.

Change only the profit coefficients.

Worked example 2: the objective row changes

Question. Use the same constraints but maximise $P=2x+3y$ . Set up the initial tableau.

Plan. Retain the resource rows and replace the objective equation.

P-2x-3y=0

$P$	$x$	$y$	$s_1$	$s_2$	RHS
$1$	$-2$	$-3$	$0$	$0$	$0$
$0$	$2$	$1$	$1$	$0$	$8$
$0$	$1$	$2$	$0$	$1$	$8$

Why this step? The feasible region stays the same; only the incentive for leaving the origin changes.

Answer. The displayed initial tableau again represents $x=y=0$ , $s_1=s_2=8$ , $P=0$ .

Check. The basic unit columns and all constraint RHS values are unchanged.

The tableau is a compact system of equations, not a new set of approximate measurements. Keep fractions exact during pivots.

Watch out

Wrong: put $+3,+2$ in the first objective row for the convention used here. Right: write the equation $P-3x-2y=0$ before copying coefficients.

Use a new objective with the same resources.

Choosing an entering variable and pivot

With this maximisation convention, a negative objective-row coefficient identifies a possible entering variable. Unless directed otherwise, choosing the most negative one is a usual rule.

The leaving variable is limited by feasibility. In the entering column, use only positive constraint entries and calculate RHS divided by that entry. Choose the smallest non-negative ratio, including zero if it occurs. Ignore zero and negative column entries.

The ratio test

For entering variable $v$ , a row with positive coefficient $a_i$ gives the bound

v\le\frac{b_i}{a_i}

when the other non-basic variables stay zero. The tightest such bound identifies a pivot row; the pivot is its entering-column entry.

Not in the formula booklet: learn it.

A tie permits more than one limiting row; it can produce a degenerate solution. If a question prescribes the entering column, follow it rather than applying a different preference.

Worked example 3: x enters

Question. Choose a pivot for the initial tableau of Example 1.

Plan. Select the most negative objective entry, then compare the positive-column ratios.

\begin{aligned} -3&<-2&&\text{choose the }x\text{ column}\\ \frac82&=4&&\text{first constraint ratio}\\ \frac81&=8&&\text{second constraint ratio} \end{aligned}

Why this step? Increasing $x$ with $y=0$ reaches $2x+y=8$ first, so that resource must leave the slack basis first.

Answer. Pivot on the entry $2$ in the first constraint row and $x$ column; $x$ enters and $s_1$ leaves.

Check. The proposed new point is $(4,0)$ , with $s_2=4\ge0$ .

Change only the objective to Example 2's coefficients.

Worked example 4: y enters instead

Question. Choose a pivot for Example 2's initial tableau.

Plan. Choose the most negative entry in the new objective row and compare its column ratios.

\begin{aligned} -3&<-2&&\text{now choose the }y\text{ column}\\ \frac81&=8&&\text{first constraint ratio}\\ \frac82&=4&&\text{second constraint ratio} \end{aligned}

Why this step? The changed objective favours increasing $y$ , and the second resource limits that movement.

Answer. Pivot on $2$ in the second constraint row and $y$ column; $y$ enters and $s_2$ leaves.

Check. The resulting vertex will be $(0,4)$ , with first slack $4$ .

The ratio test is not a comparison of the RHS values alone: the entering-column coefficients determine the rate at which each slack is consumed.

Watch out

Wrong: include a negative or zero column entry in the ratio comparison, or choose the largest ratio. Right: positive entries give upper bounds; use the smallest permitted ratio.

Choose the first pivot for a fresh objective.

Transforming the tableau

Divide the pivot row by the pivot to make its entry $1$ . Then use that new row to make every other entry in its column zero, including the objective row.

These are row operations on equations, so they preserve the underlying LP while changing its basic-variable description.

Worked example 5: the first iteration

Question. For Example 1, pivot on $2$ in the first constraint row and $x$ column.

Plan. Normalise the first constraint row, then remove $x$ from the objective and second constraint.

With $R_0$ the objective and $R_1,R_2$ the constraint rows:

\begin{aligned} R_1&\leftarrow\tfrac12R_1&&\text{normalise the pivot}\\ R_0&\leftarrow R_0+3R_1&&\text{remove }-3x\\ R_2&\leftarrow R_2-R_1&&\text{remove }x \end{aligned}

$P$	$x$	$y$	$s_1$	$s_2$	RHS
$1$	$0$	$-1/2$	$3/2$	$0$	$12$
$0$	$1$	$1/2$	$1/2$	$0$	$4$
$0$	$0$	$3/2$	$-1/2$	$1$	$4$

Why this step? Every elimination uses the normalised row, not the old pivot row.

Answer. The new basic solution is $x=4,s_2=4$ , with $y=s_1=0$ and $P=12$ .

Check. The $x$ column is a unit column; substituting $(4,0)$ in $3x+2y$ gives $12$ .

Now change the entering variable at the next vertex: the remaining negative objective entry is in the $y$ column.

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 (Major and Minor)

Statistics (Major and Minor)

Modelling with Algorithms

Numerical Methods

Extra Pure

Further Pure with Technology

AL12, AL13 - The simplex method

Setting up an initial tableau

Choosing an entering variable and pivot

Transforming the tableau

Continue this lesson.

Learn faster with Nova