Optimization (D2) DPK

Easter 2005

3. THE SIMPLEX ALGORITHM

3.1 Introduction

We know that, if a linear programming problem has a finite optimal solution, it has an optimal solution at a basic feasible solution (b.f.s.). The simplex algorithm is a systematic method of searching through the basic feasible solutions in such a way that, at each iteration, it moves to a better solution in the sense of having higher value of the objective function (or ‘payoff’ as it is often called); this would be in the case of a maximization problem, we would want a lower value if we were minimizing. The better solution is an ‘adjacent’ one which is reached by moving along an edge of the feasible set. As there are only a finite number of basic feasible solutions (bounded above by \binom{n}{m}) this process will terminate in a finite number of steps. Schematically, the algorithm proceeds as follows:

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

. .

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

. .

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

. . . . . . . . . . . . . .

.

.

.

.

.

.

.

.

.

.

.

.

.

. .

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

. . . . . . . . . . . . . .

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

. . . . . . . . . . . . . .

.

.

.

.

.

.

.

.

.

.

.

.

.

.

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

.

.

.

.

.

.

.

.

.

.

.

.

.

. .

.

.

.

.

.

.

.

.

.

.

.

.

.

Take an initial b.f.s.

Test whether the current b.f.s. is optimal

Replace the b.f.s. with an adjacent

one with higher value

YES

NO

Terminate

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

We will illustrate how this goes by considering the example of the previous chapter. In this case we will take as the initial b.f.s. the point A in the diagram corresponding to the values

x_{1} = 0, x_{2} = 0, z_{1} = 4, z_{2} = 6.

In general it may not be obvious how to determine an initial b.f.s. (we will come to that question later when we introduce the two-phase algorithm) but for any example which we can write with inequality constraints Ax ⩽ b where b ⩾ 0, then when we put it in equality form Ax + z = b with slack variables z ⩾ 0 we can obtain an initial b.f.s. by setting x = 0 and z = b ⩾ 0 (as we have done here). The basic variables at A are z_{1} and z_{2} and the non-basic variables are x_{1} and x_{2}. Let us write the problem as

z_{1} = 4 − 2x_{1} − x_{2}  (1)
z_{2} = 6 − 2x_{1} − 3x_{2}  (2)
Payoff f = 3x_{1} + 2x_{2},  (3)

with the feasibility conditions x_{1} ⩾ 0, x_{2} ⩾ 0, z_{1} ⩾ 0 and z_{2} ⩾ 0. This representation of the problem expresses the basic variables z_{1}, z_{2}, and the objective function f, parametrically in terms of the non-basic variables x_{1} and x_{2}. At this b.f.s., the non-basic variables x_{1} = x_{2} = 0, and we can read off the values of the basic variables, z_{1} = 4, z_{2} = 6, and of the objective function, f = 0, at A.

It is clear that this b.f.s. is not optimal because we can increase either x_{1} or x_{2} from 0 (by a sufficiently small amount so as to keep z_{1} and z_{2} non-negative) and thus strictly increase the objective function this is because the coefficients of both x_{1} and x_{2} in the expression for the objective function are positive. The method of the simplex algorithm is to move from this b.f.s. by increasing exactly one of the non-basic variables from zero (keeping the others equal to zero) by as large an amount as possible, while retaining feasibility (that is, the current basic variables ⩾ 0). In our case, since the coefficient of x_{1} in the objective function is larger than that of x_{2} let us choose x_{1} to increase, as it will give the larger rate of increase of the payoff; this is a useful rule-of-thumb but it is not necessary to the algorithm – choosing any non-basic variable with a positive coefficient in the objective function would do.

Now as we increase x_{1} from zero, keeping x_{2} = 0, the current basic variables are z_{1} = 4 − 2x_{1}, z_{2} = 6 − 2x_{1}, and we see that we are moving along the edge AB of the feasible set; note that z_{1} becomes negative as x_{1} passes through the value 2 while z_{2} does not change sign until x_{1} = 3, so the largest value of x_{1} that we may take and remain within the feasible set is x_{1} = 2. This gives a new b.f.s. x_{1} = 2, z_{2} = 2, x_{2} = z_{1} = 0, which is the point B in the diagram. This new b.f.s. has x_{2}, z_{1} as non-basic variables and x_{1}, z_{2} basic.

We now rewrite the problem parametrically in terms of the new non-basic variables x_{2} and z_{1}. Divide (1) by 2 and rearrange to get x_{1} in (4) below, then substitute x_{1} into

24 (2) (which is the same as subtracting (1) from (2) and rearranging to get the expression for z_{2} in (5), and substitute for x_{1} in (3), which corresponds to adding \frac{3}{2} times (1) to (3) to get

x_{1} = 2 − \frac{1}{2}z_{1} − \frac{1}{2}x_{2}  (4)
z_{2} = 2 + z_{1} − 2x_{2}  (5)
Payoff f = 6 − \frac{3}{2}z_{1} + \frac{1}{2}x_{2}.  (6)

At this stage we have gone from z_{1}, z_{2} as the basic variables to x_{1} and z_{2} basic (the terminology is ‘x_{1} has entered the basis’ and ‘z_{1} has left the basis’). We are now at a better b.f.s. since the value of the objective function is now f = 6, and we start the loop again. Test for optimality: there is a coefficient of a non-basic variable, x_{2}, in the expression for the payoff (6) which is positive, so that the current b.f.s. is not optimal. We can increase x_{2} from 0 (‘x_{2} enters the basis’) to get a higher value of the objective function. Choice of variable to leave the basis: the first of the two basic variables to hit 0 as x_{2} increases (and z_{1} is kept fixed at 0) is z_{2} (when x_{2} = 1).

The new b.f.s. has x_{1}, x_{2} basic and z_{1}, z_{2} non-basic, which corresponds to the point D in the diagram. Again, we express the problem in terms of the non-basic variables. Divide (5) by 2 and rearrange to get (8). Take \frac{1}{4} × (5) from (4) (to eliminate x_{2}, or equivalently substitute for x_{2} from (8) into (4)) and rearrange to get (7); finally, add \frac{1}{4} × (5) to (6) to get (9) (again, to eliminate x_{2}), and we have the problem represented as

x_{1} = \frac{3}{2} − \frac{3}{4}z_{1} + \frac{1}{4}z_{2}  (7)
x_{2} = 1 + \frac{1}{2}z_{1} − \frac{1}{2}z_{2}  (8)
Payoff f = \frac{13}{2} − \frac{5}{4}z_{1} − \frac{1}{4}z_{2}.  (9)

We see that this b.f.s. with x_{1} = \frac{3}{2}, x_{2} = 1, z_{1} = z_{2} = 0 and the objective function f = \frac{13}{2} is optimal because in (9) the coefficients of both the non-basic variables are negative so increasing either from 0 would give a lower value of the payoff.

3.2 The simplex tableau

The discussion in the previous section contains all the essential elements of the simplex algorithm, but the somewhat adhoc transition through the steps from b.f.s. to b.f.s. that we gave needs to be systematized and formalized to cope with larger problems. The way this is done is by writing the problem in the form of the simplex tableau, which is a form of bookkeeping for the procedures we have used. We will work through the problem using the notation of the simplex tableau. Firstly the problem in equality form is:

\begin{aligned}2x_{1} + x_{2} + z_{1} & = 4 \\ 2x_{1} + 3x_{2} + z_{2} & = 6 \\ Payoff 3x_{1} + 2x_{2} & = f, \end{aligned}

with, of course, the conditions x_{1}, x_{2}, z_{1}, z_{2} ⩾ 0 always assumed. This is written in the form

* *
x_{1} x_{2} z_{1} z_{2}
z_{1}  2 1 1 0 4
z_{2}  2 3 0 1 6
Payoff 3 2 0 0 0

with the * to indicate the basic variables; the entries z_{1} and z_{2} on the left-hand side are to remind you to which basic variable each row refers, including them is a bit of overkill but a little redundancy does not hurt if it helps to make it clearer. This table is essentially equations (1)-(3). In general if the constraints are in the form Ax = b where A is an m×n matrix , x = (x_{1}, …, x_{n})^{⊤} and b = (b_{1}, …, b_{m})^{⊤}, the tableau looks like

x_{1} x_{2} ⋯ x_{n}
a_{1,1} a_{1,2} ⋯ a_{1,n} b_{1}
⋮ ⋮ ⋮ ⋮ ⋮
a_{m,1} a_{m,2} ⋯ a_{m,n} b_{m}
Payoff a_{0,1} a_{0,2} ⋯ a_{0,n} a_{0,0}

but within the box (rows 1 to m, columns 1 to n) there is the identity matrix (as there is under the basic variables in our example ). Step 1 Test for optimality. Look along the payoff row, if all the entries are ⩽ 0 (apart from the bottom right-hand entry a_{0,0} which is −f, where f is the value of the objective

26 function at the current b.f.s.), the current b.f.s. is optimal (we need all entries ⩾ 0 if the problem is a minimization). Otherwise, we proceed as follows.

Step 2 Identify the non-basic variable to enter the basis; this is called ‘choosing the pivot column’. We look along the payoff row (a_{0,1}, …, a_{0,n} ) and choose a positive element (a negative element if we are minimizing); our rule-of-thumb is to choose the largest positive element a_{0,j} indicated by ↑ below to give the steepest ascent, (but this is no guarantee that we will minimize the number of iterations of the algorithm). The choice of pivot column is to ensure that the objective function is higher (lower for minimization) at the next b.f.s..

Step 3 Choose the basic variable to leave the basis; this is called ‘choosing the pivot row’. Within the pivot column j we choose the row element a_{i,j} which minimizes the ratio b_{k}/a_{k,j} over those rows k for which a_{k,j} > 0. If all a_{k,j} ⩽ 0 for all rows k = 1, …, m then the problem is unbounded above (the maximum of the problem = ∞) because the variable x_{j} may be increased indefinitely without making any of the basic variables go negative. The element a_{i,j} chosen in this way is the pivot element and boxed in the tableau below. The variable x_{j} enters the basis and the variable that leaves the basis may be determined from the ith row label; it corresponds to the basic variable which has a 1 in the ith row in the identity matrix below the basic variables. This choice of pivot row is made to ensure that at the next step the basic solution is feasible.

* *
x_{1} x_{2} z_{1} z_{2}
z_{1} 2 1 1 0 4
z_{2}  2 3 0 1 6
Payoff 3 2 0 0 0
↑

Step 4 We need to perform the pivot operation, when the pivot element is a_{i,j}. This is the process of rewriting the problem in terms of the new basic variables, as we did going from the representation (1)-(3) to the representation (4)-(6). The procedure is to

(i) divide row i by a_{i,j};

(ii) add −(a_{k,j}/a_{i,j}) × row(i) to row k for each k ≠ i (including payoff row).

Notice that this operation preserves the property that the identity matrix is always embedded in the tableau under the basic variables (possibly after a rearrangement of the columns).

In the case of our example we obtain (the left-hand) tableau below, which should be compared with equations (4)-(6). At this stage we return to Step 1 and repeat the cycle. In the right-hand tableau we identify that the current b.f.s. is not optimal, that x_{2} should enter the basis and that z_{2} should leave:

\begin{aligned}& * & & & * \\ & x_{1} & x_{2} & z_{1} & z_{2} \\ x_{1} & 1 & \frac{1}{2} & \frac{1}{2} & 0 & 2 \\ z_{2} & 0 & 2 & −1 & 1 & 2 \\ Payoff & 0 & \frac{1}{2} & −\frac{3}{2} & 0 & −6 \end{aligned}  \begin{aligned}& * & & & * \\ & x_{1} & x_{2} & z_{1} & z_{2} \\ x_{1} & 1 & \frac{1}{2} & \frac{1}{2} & 0 & 2 \\ z_{2} & 0 & 2 & −1 & 1 & 2 \\ Payoff & 0 & \frac{1}{2} & −\frac{3}{2} & 0 & −6 \\ & & ↑ \end{aligned}

Performing the pivot operation we obtain

*  *
x_{1} x_{2} z_{1} z_{2}
x_{1}  1 0 \frac{3}{4} −\frac{1}{4}  \frac{3}{2}
x_{2}  0 1 −\frac{1}{2}  \frac{1}{2}  1
Payoff 0 0 −\frac{5}{4} −\frac{1}{4} −\frac{13}{2}

which corresponds to equations (7)-(9), and which is optimal from Step 1 above. We read off the optimal solution x_{1} = \frac{3}{2}, x_{2} = 1, z_{1} = z_{2} = 0, and the optimal value of the objective function is \frac{13}{2}, obtained as minus the bottom right-hand entry of the tableau. Remarks

1. By comparing the various simplex tableaux for this problem with the enumeration of the solutions to the dual problem in the previous chapter, it may be noted that, at each stage, in the payoff row of the tableau the dual variables at the relevant b.f.s. may be identified. This will be the case when the constraints in the primal problem are inequalities, however the order in which the dual variables appear, and their sign, may have to be deciphered, depending on the original formulation of the problem. In the typical formulation, as we have here, where we start from the b.f.s. where the slack variables are the basic variables then the optimal dual

28 variables will be minus the entries under the slack variables in the payoff row of the final tableau (see below and later). In this example, from the final tableau we can see that the optimal solution to the dual is λ_{1} = \frac{5}{4}, λ_{2} = \frac{1}{4}, and λ_{3} = v_{1} = 0, λ_{4} = v_{2} = 0. This can provide a useful check on your arithmetic as we must have, at the optimal solution, that b^{⊤}λ = c^{⊤}x, and here 4 (\frac{5}{4}) + 6 (\frac{1}{4}) = \frac{13}{2}.

2. Each step of the simplex algorithm just involves elementary operations on the rows of the tableau: dividing through a row by a constant or adding/subtracting a multiple of a row to/from another. If we compare the initial and final tableaux

\begin{aligned}& & & * & * \\ & x_{1} & x_{2} & z_{1} & z_{2} \\ z_{1} & 2 & 1 & 1 & 0 & 4 \\ z_{2} & 2 & 3 & 0 & 1 & 6 \\ Payoff & 3 & 2 & 0 & 0 & 0 \end{aligned}  \begin{aligned}& * & * \\ & x_{1} & x_{2} & z_{1} & z_{2} \\ x_{1} & 1 & 0 & \frac{3}{4} & −\frac{1}{4} & \frac{3}{2} \\ x_{2} & 0 & 1 & −\frac{1}{2} & \frac{1}{2} & 1 \\ Payoff & 0 & 0 & −\frac{5}{4} & −\frac{1}{4} & −\frac{13}{2} \end{aligned}

of the problem we have looked at, because the identity matrix is initially below the slack variables z_{1}, z_{2}, we can identify easily the total effect of these operations. By looking under z_{1} and z_{2} in the final tableau, we see that the first two rows have been pre-multiplied by the matrix

( \begin{matrix}\frac{3}{4} & −\frac{1}{4} \\ −\frac{1}{2} & \frac{1}{2} \end{matrix} )

and from considering the entries under z_{1}, z_{2} in the payoff row we see that the final payoff row has been formed by adding (−\frac{5}{4} × (row 1) − \frac{1}{4} × (row 2)) to the initial payoff row. Suppose now that the initial right-hand sides in the constraints are changed to 4+ϵ_{1} and 6+ϵ_{2}, then the new right-hand sides in the final tableau will be determined by

( \begin{matrix}\frac{3}{4} & −\frac{1}{4} \\ −\frac{1}{2} & \frac{1}{2} \end{matrix} ) ( \begin{matrix}4 + ϵ_{1} \\ 6 + ϵ_{2} \end{matrix} ) = ( \begin{matrix}\frac{3}{2} + \frac{3}{4}ϵ_{1} − \frac{1}{4}ϵ_{2} \\ 1 − \frac{1}{2}ϵ_{1} + \frac{1}{2}ϵ_{2} \end{matrix} )

and the new final tableau is

*  *
x_{1} x_{2} z_{1} z_{2}
x_{1}  1 0 \frac{3}{4} −\frac{1}{4}  \frac{3}{2} + \frac{3}{4}ϵ_{1} − \frac{1}{4}ϵ_{2}
x_{2}  0 1 −\frac{1}{2}  \frac{1}{2} 1 − \frac{1}{2}ϵ_{1} + \frac{1}{2}ϵ_{2}
Payoff 0 0 −\frac{5}{4} −\frac{1}{4} −\frac{13}{2} − \frac{5}{4}ϵ_{1} − \frac{1}{4}ϵ_{2}

One thing to note is that (apart from the changed value of the objective function) the payoff row is unchanged so the entries are still ⩽ 0; this tableau will be optimal for the revised problem so long as the new right-hand sides are ⩾ 0, that is the basic solution given by this tableau is feasible for the revised problem. So long as

\frac{3}{2} + \frac{3}{4}ϵ_{1} − \frac{1}{4}ϵ_{2} ⩾ 0, and 1 − \frac{1}{2}ϵ_{1} + \frac{1}{2}ϵ_{2} ⩾ 0,

the tableau is optimal; this will be true irrespective of whether the application of the simplex algorithm has taken you outside the feasible set in the intervening steps. This is because of the three necessary and sufficient conditions for optimality we had in the previous chapter. The other thing to note that the change in the optimum value is \frac{5}{4}ϵ_{1} + \frac{1}{4}ϵ_{2}, which is consistent with the shadow price interpretation of the optimal dual variables λ_{1} = \frac{5}{4} and λ_{2} = \frac{1}{4}, discussed in Chapter 1.

3.3 The two-phase method

There remains the question of how the simplex algorithm should be started if there is no obvious b.f.s from which to start the algorithm. The answer to this, somewhat paradoxically, is that the simplex algorithm itself may be used to generate an initial b.f.s.. This is done by setting up a linear programming problem (the Phase I problem) for which there is an obvious initial b.f.s. and which yields an optimal solution which will be an initial b.f.s. for the original problem (if one exists). Phase II is then the application of the simplex algorithm to the original problem starting from this initial b.f.s.. We will consider the example:

maximize x_{1} − 3x_{2} + 5x_{3}
subject to  x_{1} + x_{2} + x_{3} ⩽ 30
− x_{2} + 2x_{3} = 20
−x_{1} + 2x_{2} + x_{3} ⩾ 40
x_{1}, x_{2}, x_{3} ⩾ 0.

Add slack variables to the first and third constraints to put it in equation form and we

30 obtain

maximize x_{1} − 3x_{2} + 5x_{3}
subject to x_{1} + x_{2} + x_{3} + z_{1} = 30
− x_{2} + 2x_{3}  = 20
−x_{1} + 2x_{2} + x_{3} − z_{2} = 40
x_{1}, x_{2}, x_{3}, z_{1}, z_{2} ⩾ 0.

In the previous section we could start from the feasible solution with just the slack variables as basic; this cannot work here, for a start there is no slack variable appearing in the second constraint and, if we take x_{1} = x_{2} = x_{3} = 0, then we obtain z_{2} = −40 which is not feasible. The answer to the problem is to introduce what are known as artificial variables y_{1}, y_{2} into the constraints

\begin{aligned}x_{1} + x_{2} + x_{3} + z_{1} & = 30 \\ − x_{2} + 2x_{3}  + y_{1} & = 20 \\ −x_{1} + 2x_{2} + x_{3}  − z_{2} + y_{2} & = 40 \\ x_{1}, x_{2}, x_{3}, z_{1}, z_{2}, y_{1}, y_{2} & ⩾ 0, \end{aligned}

and then minimize y_{1} + y_{2} subject to these constraints, starting from the b.f.s. to this enlarged problem obtained by taking z_{1}, y_{1} and y_{2} basic, that is

x_{1} = x_{2} = x_{3} = z_{2} = 0, z_{1} = 30, y_{1} = 20, y_{2} = 40;

if there is a solution to this Phase I problem with y_{1} = y_{2} = 0 (y_{1}, y_{2} non-basic) then there is a b.f.s. to the original problem from which we can initiate the simplex algorithm for the original problem. If the optimal solution to the Phase I problem has optimal value which is strictly positive then there is no feasible solution to the original problem. We set this up in tableau form, and as a useful piece of bookkeeping during the Phase I algorithm, we include a row corresponding to the Phase II objective function (the objective function for the original problem). This avoids having to calculate the Phase II objective function in terms of the non-basic variables at the end of Phase I.

*  * *
x_{1} x_{2} x_{3} z_{1} z_{2} y_{1} y_{2}
1 1 1 1 0 0 0 30
0 −1 2 0 0 1 0 20
−1 2 1 0 −1 0 1 40
Phase II 1 −3 5 0 0 0 0  0
Phase I 0 0 0 0 0 1 1  0

We have written the Phase I objective function as y_{1} +y_{2} so the problem is a minimization; if you feel more comfortable maximizing, you may replace it by −y_{1} − y_{2}. Preliminary Step Notice first of all that the tableau above is not yet in the correct form to apply the simplex algorithm. The payoff row(s) should express the objective functions in terms of the non-basic variables so we need to subtract the second and third rows from the Phase I row to eliminate y_{1} and y_{2}.

*  * *
x_{1} x_{2} x_{3} z_{1} z_{2} y_{1} y_{2}
z_{1}  1 1 1  1 0 0 0 30
y_{1}  0 −1 2  0 0 1 0 20
y_{2}  −1 2 1  0 −1 0 1 40
Phase II 1 −3 5  0 0 0 0  0
Phase I 1 −1 −3  0 1 0 0 −60
↑

All we are doing here is expressing

y_{1} + y_{2} = 60 + x_{1} − x_{2} − 3x_{3} + z_{2}

from the second and third constraint. We are now ready to roll and solve this Phase I problem (remembering that we have set it up as a minimization and so we choose a negative element in the payoff row). Phase I We take two pivots, first introducing x_{3} and dropping y_{1} (pivot element marked

32 above) to get:

* *  *
x_{1} x_{2} x_{3} z_{1} z_{2} y_{1} y_{2}
z_{1}  1 \frac{3}{2}  0 1 0 −\frac{1}{2}  0 20
x_{3}  0 −\frac{1}{2}  1 0 0 \frac{1}{2}  0 10
y_{2}  −1 \frac{5}{2}  0 0 −1 −\frac{1}{2}  1 30
Phase II 1 −\frac{1}{2}  0 0 0 −\frac{5}{2}  0 −50
Phase I 1 −\frac{5}{2}  0 0 1 \frac{3}{2}  0 −30

↑

and then then pivoting on \frac{5}{2} to introduce x_{2} and drop y_{2}:

* * *
x_{1} x_{2} x_{3} z_{1} z_{2} y_{1} y_{2}
z_{1}  \frac{8}{5}  0 0 1 \frac{3}{5} −\frac{1}{5} −\frac{3}{5}  2
x_{3}  −\frac{1}{5}  0 1 0 −\frac{1}{5}  \frac{2}{5}  \frac{1}{5} 16
x_{2}  −\frac{2}{5}  1 0 0 −\frac{2}{5} −\frac{1}{5}  \frac{2}{5} 12
Phase II \frac{4}{5}  0 0 0 −\frac{1}{5} −\frac{13}{5}  \frac{1}{5} −44
Phase I  0 0 0 0 0 1 1  0

We are now at an optimal solution to Phase I; all the entries in the payoff row are ⩾ 0 (we are minimizing) and the optimal value is 0 so y_{1} = y_{2} = 0 and we have a b.f.s. of the original problem. If we had obtained an optimal solution to Phase I and the value was > 0, so that at least one of y_{1} > 0 or y_{2} > 0, then there is no feasible solution to the original problem. Phase II We may now drop the Phase I row and the columns corresponding to the artificial variables y_{1} and y_{2},

* * *
x_{1} x_{2} x_{3} z_{1} z_{2}
z_{1}  \frac{8}{5}  0 0 1 \frac{3}{5}  2
x_{3}  −\frac{1}{5}  0 1 0 −\frac{1}{5} 16
x_{2}  −\frac{2}{5}  1 0 0 −\frac{2}{5} 12
Phase II \frac{4}{5}  0 0 0 −\frac{1}{5} −44

↑ and we proceed to apply the simplex algorithm to this reduced tableau, introducing x_{1} and dropping z_{1} from the basis (remember we are now maximizing, so we choose a positive element in the payoff row).

* * *
x_{1} x_{2} x_{3} z_{1} z_{2}
x_{1}  1 0 0 \frac{5}{8}  \frac{3}{8}  \frac{5}{4}
x_{3}  0 0 1 \frac{1}{8} −\frac{1}{8}  \frac{65}{4}
x_{2}  0 1 0 \frac{1}{4} −\frac{1}{4}  \frac{25}{2}
Phase II 0 0 0 −\frac{1}{2} −\frac{1}{2} −45

This tableau is now optimal for the original problem with the optimal value being 45 occurring when x_{1} = \frac{5}{4}, x_{2} = \frac{25}{2} and x_{3} = \frac{65}{4}. Remark

If the dual variables corresponding to the three constraints for the problem of this section are λ_{1}, λ_{2} and λ_{3} then we must have λ_{1} ⩾ 0, λ_{3} ⩽ 0 while λ_{2} is unconstrained in sign. We can read off the optimal λ_{1} = \frac{1}{2} and λ_{3} = −\frac{1}{2} from under the slack variables in the final tableau and you may like to think about how you would see that λ_{2} = \frac{5}{2}.

3.4 Extreme points and basic feasible solutions

We will now fill in some of the details and proofs that were promised earlier in the course. We will discuss the case of the standard linear programming problem

maximize c^{⊤}x subject to Ax = b, x ⩾ 0.

Recall that we are making the following Assumptions

(i) A is an m × n matrix, n > m, with rank (A) = m; (ii) any m columns of A are linearly independent; and (iii) the problem is non-degenerate: b cannot be expressed as a linear combination of fewer than m columns of A (so that any b.f.s. has exactly m non-zero entries).

34 Degeneracy The importance of non-degeneracy for the simplex algorithm is the following: if, when we introduce a new variable into the basis, it has a positive value in the new b.f.s., because we have a strictly positive coefficient (when maximizing) for this variable in the expression for the objective function (the bottom row of the tableau), we get a strictly positive improvement in the objective function at the new b.f.s.. Hence, if the problem is non-degenerate, during each iteration the simplex algorithm will move to a strictly better b.f.s; there are only a finite number of basic feasible solutions and so the algorithm terminates after a finite number of steps. If the problem is degenerate and a basic variable is zero, then it is possible to go through an iteration and change the basis and get no improvement in the objective function – it is theoretically possible to cycle through a sequence of basic feasible solutions and return to the starting point, so the algorithm gets stuck. While this is a theoretical possibility, the situation is easily resolved, as even such a crude approach as randomizing the choice of pivot column will ensure that the algorithm breaks out of the loop.

We turn to the proofs of two results postponed from Chapter 2. Theorem 2.2 A point x is a basic feasible solution of Ax = b if and only if it is an extreme point of the feasible set {x : Ax = b, x ⩾ 0} for the linear programming problem. Proof. Let X_{b} = {x : Ax = b, x ⩾ 0}. Suppose that x is a b.f.s., so that x ∈ X_{b} and x has exactly m non-zero entries. Suppose that

x = θy + (1 − θ)z, y, z ∈ X_{b}, 0 < θ < 1.

Since y_{i} ⩾ 0 and z_{i} ⩾ 0, x_{i} = θy_{i} + (1 − θ)z_{i} implies that if x_{i} = 0 then necessarily y_{i} = z_{i} = 0, so that, by Assumption (iii), y and z are basic feasible solutions each with exactly m non-zero entries, which occur in the same positions. Since Ay = b = Az we have A(y − z) = 0; but this give a linear combination of m columns of A equal to zero and, using Assumption (ii), we deduce that y = z so that x is extreme in X_{b}.

Conversely, suppose x ∈ X_{b} is not a b.f.s., so that it has exactly r non-zero entries x_{i_{1}}, …, x_{i_{r}} > 0 for some r > m; by Assumption (i), the corresponding columns of A, a_{i_{1}}, …, a_{i_{r}}, must be linearly dependent so there exist (y_{i_{1}}, …, y_{i_{r}}) ≠ 0 with ∑_{j=1}^{r} y_{i_{j}}a_{i_{j}} = 0. We may extend (y_{i_{1}}, …, y_{i_{r}}) to the point y = (y_{1}, …, y_{n})^{⊤} (by setting the other entries equal to 0), to get Ay = 0 and y ≠ 0. It follows that, for ϵ > 0 sufficiently small, x±ϵy ⩾ 0 and A (x ± ϵy) = b so that x ± ϵy ∈ X_{b} and

x = \frac{1}{2} (x + ϵy) + \frac{1}{2} (x − ϵy) ,

showing that x is not extreme. □ Theorem 2.1 If the linear programming problem, maximize c^{⊤}x subject to Ax = b, x ⩾ 0, has a finite optimum then there is an optimal solution which is an extreme point of the feasible set. Proof. Let x be an optimal solution; firstly, suppose that x has exactly m non-zero entries then x is a b.f.s. and, by the previous result, it is necessarily an extreme point of X_{b}. So suppose that x has r non-zero entries where r > m and that x is not extreme in X_{b}; that is, x = θy + (1 − θ)z, for y, z ∈ X_{b}, y ≠ z, 0 < θ < 1. We will show that we can find an optimal solution with fewer than r non-zero entries; then we can repeat the argument until we get down to an optimal solution with m non-zero entries which is extreme. Since c^{⊤}x ⩾ c^{⊤}y, c^{⊤}x ⩾ c^{⊤}z and c^{⊤}x = θc^{⊤}y + (1 − θ)c^{⊤}z we must have c^{⊤}x = c^{⊤}y = c^{⊤}z, so that y and z are also optimal. As in the previous proof, x_{i} = 0 implies that y_{i} = 0 and z_{i} = 0, so that y and z have r, or fewer, non-zero entries which occur in the same positions as those in x. If either y or z have fewer than r non-zero entries we are done, otherwise we can choose a θ′ ∈ ℝ so that x′ = θ′y + (1 − θ′)z ⩾ 0 and x′ has r − 1, or fewer, non-zero entries. To do this, write x′ = z + θ′(y − z); since y ≠ z we can move θ′ from 0 (by the smallest amount possible, either in the positive or negative direction) until x′ has r − 1, or fewer, non-zero components. The point x′ will be again be optimal. This completes the argument. □

Note In fact this theorem can be strengthened to the case of maximizing a convex function f(x) over x ∈ X ⊆ ℝ^{n}, a compact convex set, to show that the maximum occurs at an extreme point of the set X. It may be shown that any point x ∈ X may be written as a convex combination x = ∑_{i=1}^{k} θ_{i}x_{i}, θ_{i} ⩾ 0, ∑_{i=1}^{k} θ_{i} = 1, of extreme points {x_{i}} of X. Then

f(x) ⩽ ∑_{i=1}^{k} θ_{i}f(x_{i}) ⩽ max_{1⩽i⩽k} f(x_{i}),

36 from which the conclusion follows.

3.5 Formal description of the simplex algorithm

We make the same three assumptions as in the previous section about the constraints Ax = b. Each stage of the algorithm determines a basis which is a subset B = {i_{1}, …, i_{m}} ⊆ {1, …, n}, corresponding to the indices of the basic variables, with N = {1, …, n} \B being the indices of the non-basic variables. After rearranging the columns of A and the elements of x, if necessary, we can rewrite A = (A_{B}, A_{N}), where A_{B}, A_{N} are the columns of A corresponding to B, N, respectively, and x = ( \begin{matrix}x_{B} \\ x_{N} \end{matrix} ) is the rearrangement of x, the constraints become

A_{B}x_{B} + A_{N}x_{N} = b.

By our assumptions, A_{B} is non-singular and we can determine the basic solution corresponding to B by setting x_{N} = 0 and solving for x_{B} = A_{B}^{−1}b. So B gives a b.f.s. if A_{B}^{−1}b ⩾ 0. If we partition c = ( \begin{matrix}c_{B} \\ c_{N} \end{matrix} ) in the same way the objective function becomes

f = c_{B}^{⊤}x_{B} + c_{N}^{⊤}x_{N}.

As we have seen the algorithm expresses the problem in terms of the non-basic variables at each stage. Rewriting the constraint we get x_{B} = A_{B}^{−1}b − A_{B}^{−1}A_{N}x_{N} and substituting that into the objective function yields

f = c_{B}^{⊤}A_{B}^{−1}b + (c_{N} − A_{N}^{⊤} (A_{B}^{−1})^{⊤} c_{B})^{⊤} x_{N}.  (1)

The complementary slackness condition in this problem is

0 = (c − A^{⊤}λ)^{⊤} x = (c_{B} − A_{B}^{⊤}λ)^{⊤} x_{B} + (c_{N} − A_{N}^{⊤}λ)^{⊤} x_{N}.

At this basic solution x_{N} = 0 and the components of x_{B} are positive (if it is a b.f.s.) so to ensure complementary slackness we take λ = (A_{B}^{−1})^{⊤} c_{B}. Notice that this choice of λ, as well as ensuring complementary slackness, gives the same values of the dual and primal objective solutions

h = b^{⊤}λ = b^{⊤} (A_{B}^{−1})^{⊤} c_{B} = f.

Dual feasibility for the problem is

0 ⩾ c − A^{⊤}λ = ( \begin{matrix}c_{B} \\ c_{N} \end{matrix} ) − ( \begin{matrix}A_{B}^{⊤} \\ A_{N}^{⊤} \end{matrix} ) (A_{B}^{−1})^{⊤} c_{B} = ( \begin{matrix}0 \\ c_{N} − A_{N}^{⊤}λ \end{matrix} ) ,

which reduces to the condition c_{N} − A_{N}^{⊤}λ ⩽ 0. If we substitute for λ into (1) we see that the primal objective function in terms of the non-basic variables is then

f = c_{B}^{⊤}A_{B}^{−1}b + (c_{N} − A_{N}^{⊤}λ)^{⊤} x_{N}.

Schematically, the simplex tableau may be expressed as *

x_{B}^{⊤}  x_{N}^{⊤}
I  A_{B}^{−1}A_{N}  A_{B}^{−1}b
Payoff  0  (c_{N} − A_{N}^{⊤}λ)^{⊤} −c_{B}^{⊤} (A_{B}^{−1}b)

The algorithm proceeds as follows:

(i) it maintains primal feasibility at each stage, that is, the right-hand sides in the tableau A_{B}^{−1}b ⩾ 0;

(ii) it has complementary slackness built in at each stage by the choice of λ; (iii) it seeks to satisfy the third of the three necessary and sufficient conditions for optimality which is dual feasibility, c_{N} − A_{N}^{⊤}λ ⩽ 0, which we see is the condition that the entries in the payoff row are ⩽ 0.

Finally, we can justify the assertion made earlier that, when the initial basic solution is obtained by taking the slack variables as the basic variables then the negative of the dual variables will be the entries under these variables in the tableau. Observe that in this case we would have A_{N} = I and c_{N} = 0 and it is then clear from the schematic tableau above that the entry in the payoff row under x_{N}^{⊤} is −λ^{⊤}.

6 April 2005

38