AL14–AL16 - Simplex for non-standard problems | OCR A-Level Further Mathematics B (MEI)

Understand why lower bounds can prevent an ordinary slack start, introduce surplus and artificial variables, and construct the initial two-stage tableau. Reformulate equalities as pairs of inequalities and recognise other cases that need an initial reformulation.

Lower bounds, surplus and artificial variables

How can simplex start at zero production when a contract already requires positive production?

It cannot treat the origin as a feasible solution of that original problem. A two-stage method first searches for a feasible starting point, using temporary artificial variables.

You already know

For an upper bound, add a non-negative slack. In the ordinary initial slack basis, decision variables are zero and slacks equal RHS, so that starting solution must be feasible.

For a lower bound, the amount above the minimum is a surplus, which is subtracted when forming an equality. This does not by itself supply a feasible slack-style basis at the origin.

Surplus and a temporary artificial variable

For $\alpha x+\beta y\ge c$ , where $c>0$ :

\alpha x+\beta y-s=c,\qquad s\ge0

Introduce a temporary artificial variable $a_1\ge0$ to obtain a starting basis:

\alpha x+\beta y-s+a_1=c

The coefficients $\alpha,\beta$ are fixed numbers; $s$ and $a_1$ are additional variables.

Not in the formula booklet: learn it.

The artificial variable temporarily permits the augmented equations to be satisfied. A solution of the original problem must ultimately have every artificial variable zero.

Worked example 1: a minimum total

Question. Prepare $x+y\ge3$ , with $x,y\ge0$ , for an initial two-stage tableau.

Plan. Subtract a non-negative surplus and add one artificial variable to provide the initial basic column.

\begin{aligned} x+y-s_1&=3&&\text{surplus above the minimum}\\ x+y-s_1+a_1&=3&&\text{temporary augmented equation}\\ x=y=s_1=0&\Longrightarrow a_1=3&&\text{initial auxiliary basis} \end{aligned}

Why this step? Without $a_1$ , setting $x=y=0$ would force $s_1=-3$ , which is forbidden.

Answer. Use $x+y-s_1+a_1=3$ , with $x,y,s_1,a_1\ge0$ . The initial basic artificial value is $3$ .

Check. The original feasible point $x=y=2$ has surplus $s_1=1$ and artificial value zero.

Change only the required minimum.

Worked example 2: a higher minimum

Question. Replace the bound by $x+y\ge5$ . Give the augmented equation and initial artificial value.

Plan. Retain the surplus and artificial signs, changing only the RHS.

\begin{aligned} x+y-s_1+a_1&=5&&\text{revised lower bound}\\ x=y=s_1=0&\Longrightarrow a_1=5&&\text{new initial basic value} \end{aligned}

Why this step? The amount of artificial feasibility needed at the zero decision point increases with the required minimum.

Answer. The equation is $x+y-s_1+a_1=5$ , and initially $a_1=5$ .

Check. At $x=2,y=4$ , the genuine surplus is $1$ , so $2+4-1+0=5$ .

Adding a positive slack instead would turn the lower bound into an upper bound and change the feasible region.

Watch out

Wrong: $x+y+s_1+a_1=5$ for a lower bound. Right: subtract the surplus and add the temporary artificial variable.

Use different coefficients and a new minimum.

Constructing the auxiliary objective row

In the convention used here, stage one minimises the sum of artificial variables. The original maximisation objective $P$ is retained for stage two.

The stage-one objective

If the artificial variables are $a_1,\ldots,a_k$ , set

\text{Minimise }Q=a_1+\cdots+a_k

Substitute their constraint equations to eliminate basic artificial variables from the $Q$ row.

If the minimum is $Q=0$ , every non-negative artificial variable is zero and the original constraints have a feasible solution. If $Q_{\min}>0$ , the original problem is infeasible.

Not in the formula booklet: learn it.

The $Q$ row has a minimisation role, unlike the retained maximisation row $P$ . Its signs follow from its equation; do not copy the ordinary $P$ -row signs by habit.

Worked example 3: one artificial variable

Question. Set up the initial two-stage tableau for

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

Plan. Augment both constraints, define $Q=a_1$ , then remove $a_1$ from the auxiliary row by substitution.

\begin{aligned} x+y-s_1+a_1&=3&&\text{lower bound}\\ x+2y+s_2&=8&&\text{upper bound}\\ Q=a_1&=3-x-y+s_1&&\text{eliminate the basic artificial}\\ Q+x+y-s_1&=3&&\text{canonical auxiliary row}\\ P-2x-y&=0&&\text{retained original objective} \end{aligned}

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

Why this step? The basic artificial column must have zero in the canonical $Q$ row, just as other basic columns do in their objective row.

Answer. The displayed tableau starts with $a_1=3,s_2=8,Q=3$ , with the other non-objective variables zero.

Check. The original point $x=3,y=0$ permits $a_1=0$ , $s_1=0$ , $s_2=5$ ; thus the auxiliary objective can reach zero.

Change only the second inequality's direction, producing a second lower bound.

Worked example 4: two artificial variables

Question. Keep $P=2x+y$ and $x+y\ge3$ , but replace the other constraint by $x+2y\ge8$ . Construct the initial two-stage tableau.

Plan. Use two surpluses and two artificial variables, then add their expressions to form $Q$ .

\begin{aligned} x+y-s_1+a_1&=3&&\text{first lower bound}\\ x+2y-s_2+a_2&=8&&\text{second lower bound}\\ Q=a_1+a_2&=11-2x-3y+s_1+s_2&&\text{sum the artificial expressions}\\ Q+2x+3y-s_1-s_2&=11&&\text{canonical auxiliary row} \end{aligned}

$Q$	$P$	$x$	$y$	$s_1$	$s_2$	$a_1$	$a_2$	RHS
$1$	$0$	$2$	$3$	$-1$	$-1$	$0$	$0$	$11$
$0$	$1$	$-2$	$-1$	$0$	$0$	$0$	$0$	$0$
$0$	$0$	$1$	$1$	$-1$	$0$	$1$	$0$	$3$
$0$	$0$	$1$	$2$	$0$	$-1$	$0$	$1$	$8$

Why this step? The auxiliary objective includes every artificial variable. Omitting one could mistake a remaining artificial violation for feasibility.

Answer. The initial basic artificial values are $3,8$ , giving $Q=11$ .

Check. At $x=0,y=4$ , take $s_1=1,s_2=0,a_1=a_2=0$ , so $Q=0$ is achievable.

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

AL14–AL16 - Simplex for non-standard problems

Lower bounds, surplus and artificial variables

Constructing the auxiliary objective row

Continue this lesson.

Learn faster with Nova