7.07a–7.07d - Using a simplex tableau | OCR A-Level Further Mathematics A

Set up a simplex tableau, choose a pivot and carry out an iteration using exact row operations. You will identify basic and non-basic variables, read the current feasible solution, recognise an optimum and investigate how a changed coefficient affects it.

Setting up the standard tableau

Can a table find the maximum of $P = 3x + 2y$ , subject to $x + y \le 8$ , $2x + y \le 10$ and $x, y \ge 0$ , without drawing the feasible region? The simplex algorithm does exactly that. Its table records equations; each iteration rewrites the same equations around a better feasible solution.

You already know

A slack variable records unused capacity: $ax + by \le c$ becomes $ax + by + s = c$ , with $s \ge 0$ . A linear objective on a non-empty bounded feasible polygon attains a maximum at a vertex.

For the opening problem, introduce $s$ and $t$ . The equations are

P - 3x - 2y = 0,\qquad x + y + s = 8,\qquad 2x + y + t = 10

with $x, y, s, t \ge 0$ . Put their coefficients into a tableau. OCR's standard layout puts the objective row first. Its columns are the objective variable, the decision variables, the slack variables and finally the right-hand side, labelled RHS.

Simplex tableau

A simplex tableau is a coefficient table for the objective equation and the constraint equations. Every row represents an equation, so a blank coefficient must be written as $0$ . For example, $P - 3x - 2y = 0$ gives the row $1, -3, -2, 0, 0, 0$ under $P, x, y, s, t,\mathrm{RHS}$ .

The sign change in the objective comes from moving its variable terms to the left; it is not a change from maximising to minimising.

Worked example 1: a standard initial tableau

Question. Set up the initial simplex tableau for maximising $P = 3x + 2y$ , subject to $x + y \le 8$ , $2x + y \le 10$ and $x, y \ge 0$ .

Plan. Introduce one non-negative slack variable per constraint, move the objective terms to the left and enter all coefficients in standard order.

\begin{aligned} P - 3x - 2y &= 0 && \text{objective first} \\ x + y + s &= 8 && \text{first slack} \\ 2x + y + t &= 10 && \text{second slack} \end{aligned}

Why this step? The slack columns form an identity pattern, giving a starting solution with the decision variables zero.

Answer.

\begin{array}{c|rrrrr|r} &P&x&y&s&t&\mathrm{RHS}\\ \hline R_0&1&-3&-2&0&0&0\\ R_1&0&1&1&1&0&8\\ R_2&0&2&1&0&1&10 \end{array}

Check. Setting $x = y = 0$ gives $P = 0$ , $s = 8$ and $t = 10$ , all satisfying the equations and non-negativity restrictions.

The second example changes only the way the second inequality is written. A negative right-hand side must be dealt with before adding its slack.

Worked example 2: an equivalent reversed inequality

Question. Set up the initial simplex tableau for maximising $P = 3x + 2y$ , subject to $x + y \le 8$ , $-2x - y \ge -10$ and $x, y \ge 0$ .

Plan. Multiply the second inequality by $-1$ , reversing its sign, then use the same slack-variable construction.

\begin{aligned} -2x - y \ge -10 &\iff 2x + y \le 10 && \text{reverse the inequality} \\ 2x + y + t &= 10 && t \ge 0 \\ P - 3x - 2y &= 0 && \text{objective equation} \end{aligned}

Why this step? Adding a positive slack to the unreversed inequality would give the wrong feasible set.

Answer.

\begin{array}{c|rrrrr|r} &P&x&y&s&t&\mathrm{RHS}\\ \hline R_0&1&-3&-2&0&0&0\\ R_1&0&1&1&1&0&8\\ R_2&0&2&1&0&1&10 \end{array}

Check. The model is identical to the first one: $t = 10 - 2x - y$ is non-negative exactly when $-2x - y \ge -10$ .

This construction starts from a feasible slack basis when the constraints have been written with non-negative right-hand sides and the starting point satisfies them. A different-looking inequality must not be forced into that form by changing its meaning.

Watch out

Wrong: $P + 3x + 2y = 0$ . Right: $P - 3x - 2y = 0$ , because the objective is $P = 3x + 2y$ . Keep the objective first and the RHS last.

The tableau layout and the most-negative-column convention must be learnt; the pivot algorithm itself is in the formula booklet.

Basic and non-basic variables

A tableau contains more variables than constraint equations; a basis specifies which variables will be solved for and which will be set to zero.

In the initial tableau, the columns for $P$ , $s$ and $t$ each contain one $1$ and otherwise zeroes. Those columns let you read the solution $P = 0$ , $s = 8$ , $t = 10$ after setting $x = y = 0$ . The objective variable $P$ is included when checking the tableau's unit columns, but it is not a production quantity.

Basic and non-basic variables

A basic variable corresponds to a chosen column consisting of zeroes and a single $1$ ; the basic columns occupy different rows. The remaining variables are non-basic and are set to zero to read the current solution. For example, the initial basis contains the slack variables $s, t$ , with $x, y$ non-basic.

After one iteration of the opening problem, the tableau will be

\begin{array}{c|rrrrr|r} &P&x&y&s&t&\mathrm{RHS}\\ \hline R_0&1&0&-\frac12&0&\frac32&15\\ R_1&0&0&\frac12&1&-\frac12&3\\ R_2&0&1&\frac12&0&\frac12&5 \end{array}

Now $x$ has replaced $t$ in the constraint basis. Set the non-basic variables $y = t = 0$ . Then $x = 5$ , $s = 3$ and $P = 15$ . Notice that $t$ is non-basic even though its constraint entries look simple: its whole column is not a unit column.

Basic feasible solution

A basic feasible solution is obtained by setting the non-basic variables to zero and solving for the basic variables, with every decision and slack variable non-negative. For example, $x = 5$ , $y = 0$ , $s = 3$ , $t = 0$ is feasible. A basic solution with a negative slack is not feasible.

A basic variable is allowed to have value zero. Such a basic feasible solution is called degenerate: “basic” describes the chosen column, not whether the current value is positive. At a degenerate vertex, more than one basis may describe the same point. These definitions are not in the formula booklet: learn them.

Key idea

Set non-basic variables to zero first, then read each basic variable from the RHS in the row containing its $1$ .

The following error comes from checking only the constraint rows and forgetting the objective row.

Choosing the pivot

Choose a direction that improves the objective, then find how far the current feasible solution can move in that direction.

In the initial objective equation $P - 3x - 2y = 0$ , increasing either $x$ or $y$ from zero increases $P$ . OCR requires the column with the most negative objective entry, unless the question specifically instructs you otherwise. Here that is the $x$ column, with entry $-3$ . This rule does not promise the largest total improvement: the constraints also limit how far you can move. For example, maximising $4x+3y$ with $4x+y\le4$ and $x,y\ge0$ chooses $x$ first, giving $P=4$ ; choosing $y$ instead would give $P=12$ in one step. Follow the specified rule even when a different first move would gain more.

The simplex ratio rule

In the selected entering column of a feasible maximisation tableau, consider only positive constraint entries $a_i$ . Choose a row minimising the non-negative ratio

\frac{b_i}{a_i}

where $b_i$ is its RHS. The selected positive entry is the pivot element. A zero ratio is allowed; a zero or negative pivot entry is not.

In the formula booklet.

The most-negative-entry requirement is not in the formula booklet: learn it. The ratio is an upper bound on the entering variable when the other non-basic variables remain zero. Take the smallest bound, so that no slack becomes negative.

Worked example 3: the first limiting constraint

Question. Choose the first pivot for the initial tableau in Worked example 1.

Plan. Choose the most negative objective entry, then calculate RHS divided by each positive entry in that column.

\begin{aligned} -3 &< -2 && \text{choose the }x\text{ column} \\ R_1:\quad \frac{8}{1} &= 8 && \text{first bound on }x \\ R_2:\quad \frac{10}{2} &= 5 && \text{second bound on }x \end{aligned}

Why this step? At $x = 5$ , the second slack first reaches zero; taking $x = 8$ would make that slack negative.

Answer. Pivot on the $2$ in row $R_2$ , column $x$ . The entering variable is $x$ ; $t$ leaves the basis.

Check. With $x = 5$ , $y = 0$ , the slacks are $s = 8 - 5 = 3$ and $t = 10 - 2(5) = 0$ .

The next example changes only the coefficient of $x$ in the objective. The feasible region is unchanged, but a different variable enters first.

Worked example 4: a changed entering column

Question. Choose the first pivot when the objective is $P = x + 2y$ , with the same constraints $x + y \le 8$ , $2x + y \le 10$ and $x, y \ge 0$ .

Plan. Compare the new objective coefficients and repeat the ratio test in the selected column.

\begin{aligned} P - x - 2y &= 0 && \text{new objective row} \\ -2 &< -1 && \text{choose the }y\text{ column} \\ R_1:\quad \frac{8}{1} &= 8,\qquad R_2:\quad\frac{10}{1}=10 && \text{positive pivot entries} \end{aligned}

Why this step? The ratio test must use the chosen column; the old $x$ -column ratios no longer answer the question.

Answer. Pivot on the $1$ in row $R_1$ , column $y$ . The variable $y$ enters and $s$ leaves.

Check. At $x = 0$ , $y = 8$ , the remaining slack is $t = 10 - 8 = 2 \ge 0$ .

A coefficient $0$ imposes no bound in that direction. A negative coefficient also gives no upper bound: increasing the entering variable increases, rather than consumes, the corresponding basic variable. Do not divide by either in the ratio test. If positive pivot entries tie for the minimum ratio, either tied row may be chosen unless instructed otherwise.

Watch out

Wrong: choose the largest ratio, or use a negative ratio because its numerical value is smallest. Right: use only positive pivot entries and choose the smallest non-negative RHS-to-entry ratio.

Show the ratios when asked to show the pivot calculations. Merely circling the correct entry omits the requested working.

Performing an iteration

A pivot replaces one basic variable with the entering variable by turning the entering column into a unit column.

First divide the entire pivot row by the pivot element. Then eliminate the other entries in that column using multiples of the new pivot row. Include the objective row and the RHS in every operation.

Pivot row operations

If $R_j$ contains pivot element $a$ , set

R_j'=\frac{1}{a}R_j,\qquad R_i'=R_i-c_iR_j'\quad(i\ne j)

where $c_i$ is the old entry in the pivot column of row $R_i$ . The pivot entry must be positive and chosen by the ratio rule.
In the formula booklet.

Continue this lesson.

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

Create free account

Last Accessed

Pure Core

Statistics

Mechanics

Discrete Mathematics

Additional Pure Mathematics

7.07a–7.07d - Using a simplex tableau

Setting up the standard tableau

Basic and non-basic variables

Choosing the pivot

Performing an iteration

Continue this lesson.

Learn faster with Nova