G

x

subject to (A, I) : c, x . 0, y . 0.

y

Show how one obtains an initial basic feasible solution for the auxiliary

problem.

Exercise 6.3. Solve the following linear programming problems using the

simplex method:

(a) Maximize x ; 3x subject to

x ; 2x ; 7x - 4,

x ; 3x ; x - 5,

x . 0, i : 1, 2, 3.

G

(b) Maximize 3x 9 x subject to

x ; 2x . 2,

3x ; x - 3,

x - 4, x . 0. i : 1, 2, 3, 4.

G G

(c) Maximize 92x 9 x ; x ; x subject to

x 9 x ; 2x 9 x : 2,

2x ; x 9 3x ; x : 6,

x ; x ; x ; x : 7.

7. REVISED SIMPLEX METHOD

The revised simplex method does not differ from the simplex method in

principle, that is, in going from one basic solution to another in such a way

that the objective function is not decreased but differs in the manner in which

some of the computations are carried out. In describing the revised simplex

method, we assume, as we did in our description of the simplex method in

Section 4, that the problem has been formulated as in (4) of Section 3. The

reader will recall from Section 4 that at each iteration a basis B is determined

256 SIMPLEX METHOD

and the calculation of B\N is used to determine the entering and leaving

variable. The revised simplex method differs from the version of the simplex

method given in Section 4 in that a system (1) in Section 4 with current B is

not reduced to (11) in Section 4 and the current basis not given by (22) in

Section 4. In the revised simplex method the entering variable x is chosen as

O

before. If A is the column of A corresponding to x , then the updated basis B

O O

is obtained from B by replacing the column A of the leaving variable x by

GM GM

A . This procedure enables us to calculate (B)\ from B\ very easily and

O

expedites other calculations, as we shall show.

Before we present the steps in an iteration of the revised simplex method,

we take up the calculation of (B)\, the updated inverse. At the current

iteration I let the basis B be given by

B : (A . . . A ), (1)

G GK

where the A are columns of B. We then write

GG

N : (A . . . A ).

GK> GL

Let x be the entering variable at I, determined as in Section 4, and let A

O O

denote the column of N corresponding to x . Let the leaving variable x be

GM

O

determined as in Section 4. Let B denote the matrix obtained from B by

replacing the column A by A and let N denote the matrix obtained from N

GM O

by replacing column A by A . Thus

GM

O

B : (A . . . A A A . . . A ),

G GM\ O GM> GK (2)

N : (A ...A A A . . .A ).

GK> GO\ GM GO> GL

Hence

B\B : B\(A . . . A A A ...A )

G GM\ O GM> GK

10%0v 0%0

O

01%0v 0%0

O

: (3)

$$\$ $ $\$

00%0v 0%1

KO

: (e . . . e v e . . .e ),

M\ O M>

K

where v : B\A . Note that v is the qth column of B\N associated with x

O O O O

and thus is as in Step 3(ii) of an iteration in the simplex method. From the way

is determined we have that v 9 0, and hence the matrix on the right in (3)

MO

is nonsingular. If we multiply both sides of (3) by B on the left, we get that

B : B(e . . . e v e . . . e ).

M\ O M>

K

REVISED SIMPLEX METHOD 257

Since B is the product of nonsingular matrices, it is nonsingular and so is a

basis. We also get

(B)\ : (e . . .e v e . . . e )\B\. (4)

M\ O M>

K

It is readily veri¬ed that multiplying the matrix on the right-hand side of the

following by the matrix on the right-hand side of (3) gives the m ; m identity

matrix. Hence

0 % 0 \

10%0 v 10%0 0%0

O O

01%0 v 0%0 01%0 0%0

O O

$$\$ $ \ $$\$ $ $\

: ,

00%0 v 00%0 0%1

KO KO

! !

col col

(5)

where

v 1

: 9 GO , i : 1, . . . , m, i" , : .

GO MO

v v

MO MO

The matrix on the right in (5) is called an eta matrix and will be denoted by

E . Thus we may write (4) as

(B)\ : E B\, (6)

which updates B\ for the next iteration.

We summarize this discussion in the following lemma

L 7.1. L et B be a basic matrix as in (1) and let B be a matrix as in (2).

T hen B is basic and (6) holds, where E is the matrix on the right in (5).

Remark 7.1. In the various calculations in the simplex method the essential

matrix is B\, not B. The matrix B is needed, in principle, only to calculate

B\. Equation (6) enables us to calculate (B)\ from B\ without knowing B

or B. It is this fact that underlies the revised simplex method. Also note that

an eta matrix differs from an identity matrix in one column.

We now present a generic revised simplex method. Most computer codes for

solving linear programming problems use the revised simplex method. Codes

used in practice incorporate various modi¬cations to improve accuracy, reduce

the number of iterations needed, decrease the running time, and so on. For

details the reader is referred to Chvatal [1983], Dantzig [1963], Gass [1985],

´

and Murtagh [1981].

258 SIMPLEX METHOD

As in our presentation of the simplex method we assume that the problem

is in canonical form: Maximize z subject to

Ax : c, 1b, x2 9 z : 0, x . 0. (7)

Let the initial stage or iteration of phase II be called the zeroth iteration. At

the kth iteration, k : 0, 1, 2, . . . , let B(k) denote the basis, let N(k) denote the

submatrix of A complementary to B(k), let x denote the vector of basic

I

,0 )

variables, let x denote the vector of nonbasic variables, let (k):(

,I I ,I

be the corresponding basic feasible solution, and let (k) be the current value

of the objective function. Equations (4)”(6) from Section 4 yield, for k :

0, 1, 2, . . . ,

: 9 [B(k)]\N(k)x N(k) ,

x

I I

(k) : 1b , 2, (8)

I I

z : (k) 9 1b 9 bR [B(k)]\N(k), x 2.

,I I ,I

From Lemma 7.1 we get that

[B(k ; 1)]\ : E k : 0, 1, 2, . . . ,

[B(k)]\,

I>

where E is an approximate eta matrix. Proceeding inductively, we get

I>

[B(k ; 1)]\ : E (E (. . . E (E [B(0)]\) . . .)). (9)

I> I

A sequential ¬le in the computer storing the matrices E , E , . . . , E is called

I> I

an eta ¬le. The calculation as indicated in (9) (from right to left) is called a

forward transformation. The matrix [B(0)]\ is calculated using elementary

matrices as in (11) from Section 3.

We now present the steps in the kth iteration, k . 1, of our generic revised

simplex algorithm. In essence, the steps mirror the steps of the simplex

method as presented in Section 4. Some of the calculations are different and

Step 1 of the simplex method is deleted. For typographical convenience we will

replace the designations B(k), N(k), x , x , . . . of the current quantities by

I ,I

B, N, x , x , . . . . The updated quantities B(k ; 1), N(k ; 1), x ,x ,...

I> , I>

,

will be designated as B, N, x , x , . . . . As in (7) from Section 4 let

Y ,Y

d : b 9 bR B\N : (d . . . d ), (10)

GK> GL

, ,

where i , . . . , i are the components of x that constitute x . We may then

K> L ,

write the last equation in (8) as

L

z : ; 1d , x 2 : ; dx.

GG

,,

NK> N N

REVISED SIMPLEX METHOD 259

Step 1. Calculate d . This is done in two steps.

,

(i) Calculate

: bR E E . . . E [B(0)]\

I I\

from left to right, that is, as

(. . . ((b R E )E ) . . .)E )[B(0)]\.

I I\

This backward transformation involves repeated multiplications of a vector by

a matrix, whereas the forward calculation (from right to left) involves

repeated multiplications of matrices. Clearly, the backward transform-

ation involves fewer operations.

(ii) Calculate

d : b 9 1 , A 2, j : m ; 1, . . . , n,

GH GH GH

where the i are the indices of the nonbasic variables at the kth stage and the

H

A are the corresponding columns of N.

GH

Step 2. If all the d are less than or equal to zero, the current basic feasible

G

solution is optimal Hand the algorithm terminates. If the algorithm terminates,

then we use (8) to calculate , the optimal value.

If the algorithm does not terminate at Step 2, we go to Step 3.

Step 3. Choose an entering variable.

Choose an index i such that d 9 0. This may be done according to the

GH

H

smallest index rule, the max d rule, or any other rule, as long as d 9 0. We