This is the justi¬cation for the following method of calculating R\ for

matrices of low dimension. Reduce the matrix (R, I) to the form (I, T ) by a

sequence of elementary operations. Then T : R\. The so-called product form

of the inverse will also be used in the simplex method.

Remark 3.2. In reducing (6) to (9), we performed a sequence of elementary

operations, which in effect was a sequence of premultiplications of (6) by

elementary matrices. Thus,

E . . . E (R, S, d) : (I , W, d). (12)

N I

Since the sequence of elementary operations reduced R to I , we have that

I

R\ : E , . . . , E I. Hence, from (12) we have

N

W : R\S and d : R\d.

Substituting this into (10) gives

y : R\d 9 R\Sy .

P Q

4. PHASE II OF SIMPLEX METHOD

Our aim in this and the next section is to explain the essentials of the simplex

method; it is not to present the most current computer implementations of the

simplex method. In Section 7, where we discuss the revised simplex method, we

shall go into greater detail concerning the computations in current computer

codes. For more complete discussions of computational questions see Dantzig

[1963], Chvatal [1983], and Gass [1985].

´

We suppose that the problem is formulated as in relation (4) of Section 3.

Phase I of the simplex, which we will describe in Section 6, either determines

that the feasible set is empty or determines a basic feasible solution. We begin

our discussion of phase II with the assumption that by means of phase I, or

otherwise, we have obtained a basic feasible solution : ( , 0 ), where 0 is

, ,

the zero vector in RL\K. We denote the value of the objective function at by

. Thus, : 1b , 2. We call : ( , 0 ) the current basic feasible solution, the

,

matrix B associated with the current basis, and the current value of the

objective function. We abuse the precept for good terminology and also call

the current basis. The simplex method consists of a

the components of

sequence of iterations. In a given iteration we determine either that the current

basic feasible solution is optimal or that there is no optimal solution or we

determine a new basic feasible solution that does not decrease the value of the

objective function. In the last event, we repeat the iteration, with the new basic

feasible solution as the current one. Each iteration consists of four steps. We

shall illustrate the process using Example 1.1.

PHASE II OF SIMPLEX METHOD 235

Step 1. Express z and the basic variables x in terms of the nonbasic variables

x.

,

The equation in (4) of Section 3 can be written as

x

B N0 c

K x: (1)

,

bR bR 91 , 0

, z

where 0 is the zero vector in RK. If we multiply the augmented matrix

K

corresponding to the ¬rst m equations in (1) by B\ on the left, we see that (1)

is equivalent to

x

I B\N 0 B\c

K K x: (2)

,

bR bR ,

91 0

, z

where I is the m ; m identity, Setting x : and x : 0 in (2) gives

K , ,

: B\c. (3)

From (2) and (3) we get that

x: 9 B\Nx . (4)

,

From (2) and (4) we get that

2 ; 1b 9 bR B\N, x 2.

z : 1b,

, ,

Setting x : 0 gives

, ,

: 1b , 2 (5)

and so

z : ; 1b 9 bR B\N, x 2. (6)

, ,

Equations (4) and (6) express x and z in terms of x .

,

Let

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

HK> HL

, ,

where j , . . . , j are the indices of the components of x that constitute x .

K> L ,

Then we may write (6) as

L

z : ; 1d , x 2 : ; dx. (8)

GG

,,

NK> N N

236 SIMPLEX METHOD

Remark 4.1. Note that by virtue of (3) the right-hand side of (2) can be written

as ( , 0)R.

The dif¬cult calculation in (4) and (6) is the calculation of B\. The other

calculations involve straightforward matrix and vector”matrix multiplications.

We now present a second, seemingly different, method of obtaining x and z

in terms of x . Computer implementation of the second method turns out in

,

essence to be the same as the computer implementation of the previous

method. Our use of the second method is didactic. For small-scale problems

solved by hand this method is advantageous and will be the one used in our

illustrative example. The tableau method is a method that systematically

records the sequence of steps and calculations that we shall describe.

We again start with the augmented matrix of (1). By a sequence of

elementary operations applied to the ¬rst m rows of (1), we can transform this

matrix to an equivalent matrix

I D0 c

K K (9)

.

bR bR 91 0

,

Each of these operations can be effected by a premultiplication by an elemen-

tary matrix E . Since the sequence of operations transforms B to I, the product

G

of the elementary matrices associated with these transformations is equal to

B\, as was shown in the preceding section. Thus, the matrix (9) can also be

obtained by a premultiplication of the ¬rst m rows of the augmented coef¬cient

matrix (1) by the matrix B\. Hence, D : B\N and c : B\c, and we have,

as before, that (1) is equivalent to a system with augmented matrix

I B\N 0 c

K K (10)

,

bR bR 91 0

,

where c : B\c. From (10) we again get (3) and (4). Let us now suppose that

the columns of B are the columns j , . . . , j of A. If we successively multiply

K

row 1 of (10) by 9b and add the result to the last row, multiply row 2 of (10)

H

by 9b and add the result to the last row, and so on, then we transform (10)

H

into ‚

I B\N 0 c

K K (11)

.

0 bR 9 bR B\N 91 91b , c2

,

From the last row of this matrix and from the relation c : B\c, we

immediately obtain

z : 1b , B\c2 ; 1bR 9 bR B\N, x 2.

, ,

PHASE II OF SIMPLEX METHOD 237

Remark 4.2. From (11) and c : B\c we again get (3) and (5). Consequently,

the right-hand side of (11) can be written as ( , 9 )R. From this relation and

from (3) and (5) we again get (6).

We illustrate the preceding description of Step 1 using the second method.

Example 4.1. We ¬rst introduce slack variabless x , x , x and write the

problem as in (2) of Section 1. We then write the problem as a maximization

problem in the format of (4) of Section 3.

Maximize z subject to

9x 9x ;x : 91,

9x ;x ;x : 0,

(12)

x ; 2x ;x : 4,

9 x ; 2x 9 z : 0.

It is readily veri¬ed that : (1, 0, 0, 1, 3), which corresponds to the point (1, 0)

in Figure 6.1, is a basic feasible solution. The value of z at this point is 91.

Thus, x , x , x are the basic variables and x , x are the nonbasic variables.

The augmented coef¬cient matrix of (12) is

x x xxx z c

x 91 91 1 0 0 0 91

x 91 (13)

1010 0 0.

x 1 2001 0 4

91 2 0 0 0 91 0

Above each column of the matrix we have indicated the variable corresponding

to the column. At the left of the matrix we have listed the current basic

variables. The last column is the column of right-hand sides of (12). In the

tableau description of the simplex method the matrix (13) is the initial tableau.

The matrix B in (13) is the submatrix formed by the ¬rst three rows and

columns 1, 4, and 5. Thus

91 0 0

B : 91 1 0

101

To obtain the matrix corresponding to (11), we must ¬rst transform B to

the identity matrix by a sequence of elementary row operations on (13). From

the form of B it is clear that the most effective sequence of operations is the

following. (i) Multiply row 1 by 91. (ii) Add the transformed row 1 to row 2.

238 SIMPLEX METHOD

(iii) Add the negative of the transformed row 1 to row 3. To obtain the row

corresponding to the last row of (11), add the transformed row 1 to row 4. We

thus obtain

xx x xx z

x 1 1 91 0 0 0 1

x 0 2 91 1 0 (14)

0 1.

x 01 101 0 3

0 3 91 0 0 91 1

From this we read off

x :19x ;x ,

x : 1 9 2x ; x , (15)

x :39x 9x ,

and

z : 91 ; 3x 9 x , (16)

which are (4) and (6) for this example. Note that the last column of (14) gives

the current values of , , 9 in agreement with (4) and (6) and Remark

4.2.

Step 2. Check the current basic feasible solution for optimality.