2

Hence t* : and x is the leaving variable. The new, or updated, basic

variables are (x , x , x ) and the updated nonbasic variables are x and x .

From (22) we get the updated basic feasible solution:

: : 1 9 (1) : , : :

G O

: 0, : : 0, : : 3 9 (1) : .

G‚ G

PHASE II OF SIMPLEX METHOD 243

From (20) we get

: (91) ; 3() : .

These calculations, however, are unnecessary as we will get them automatically

in Step 1 of the next iteration.

Step 4. We go to Step 1 and start the next iteration using the updated data.

We do so dropping the primes that indicated updated data. The variables

x , . . . , x , z satisfy the system of equations represented by (14). We rewrite (14)

with the labeling of the new basic variables:

xx x xx z

x 1 1 91 0 0 0 1

x 0 2 91 1 0 (25)

0 1.

x 01 101 0 3

0 3 91 0 0 91 1

Step 1 requires us to transform (25) into a form corresponding to (11). The

matrix B is now

110

B: 0 2 0 .

011

Thus, to achieve the desired result, we apply the following sequence of

transformations to (25).

Multiply row 2 by .

(i)

(ii) Add the negative of the new row 2 to row 1.

(iii) Add the negative of the new row 2 to row 3.

(iv) Multiply the new row 2 by 93 and add the resulting row to row 4.

We get

x

x x x x z

0 9 9 0

x 1 0

0 1 9 0 .

x (26)

0

9 1

x 00 0

9 0 91 9

00

From (26) we can read off, if we desire, the basic variables (x , x , x ) :

(x , x , x ) and z in terms of the nonbasic variables (x , x ). By Remark 4.3

G G‚ G

the last column of (26) gives

: , : , : , :

244 SIMPLEX METHOD

for , the current basic feasible solution, and , the current value of the

objective functions. Note that we have agreement with the previous calculation

of these quantities. The current basic feasible solution corresponds to the point

(, ) in Figure 6.1. The current value : is greater than the previous current

value of 91.

Before proceeding to Step 2, we introduce some terminology and comment

on the carrying out of Step 1 in general. The entry a in row 2, column 2 in

this example is called the pivot and the position in the matrix is called the pivot

position. In performing the sequence of elementary operations used to obtain

(26) from (25), we say that we have pivoted on the element a .

In our example the pivot was the entry in the row and column of the

entering variable. We now show that in each iteration after the initial iteration

we always pivot on the element in the row and column of the entering variable.

The system (24) gives the relationship among the variables x , x , and z at

Y ,Y

the end of Step 4 of each iteration. It expresses z and each component of

x : (x . . . x , x , x ...x )

G GN\ O GN> GK

Y

except x in terms of the components of x and the variable x . Step 1 of the

O ,Y O

current iteration requires that x and z be expressed in terms of the compo-

Y

nents of x . This will be achieved if we express x in terms of the components

,Y O

of x and do so in a way that does not destroy the already established

,Y

expressions of z and the x , j : 1, . . . , m, j " , in terms of x and x . We

G O ,Y

assert that pivoting on row iH , the entering row, and on column i (column v ),

M M O

the entering column, achieves this.

By the de¬nition of and (21), we have that v 9 0. Hence in (24) we may

GM

multiply row i by 1/v and obtain a row with entry 1 in the (i , i ) position.

GM

M MM

If we now multiply row i by 9v and add to row 1, the resulting ¬rst row

M O

will have a zero in the i th position; that is, the column vector v now has a 1

M O

in the i entry and a zero in the ¬rst position. Since each of the vectors e ,

GH

M

j : 1, . . . , m, j " , has a zero in the i th entry, the ¬rst entries of these vectors

M

are not changed. Similarly, if for each i : 2, . . . , m, i " , we multiply row i by

M

9v and add the resulting row to row i, then the resulting ith row will have

GO

a zero in the i th position. Each of the vectors e , j : 1, . . . , m, j " , will have

G

M

ith entries unchanged. Finally, if we multiply Hrow i by 9d and add the

M O

resulting row to the last row of (24), then we shall get a system

x

Y

I N 0 c

K K x: .

d 91 ,Y 9

0

,

Y z

This system expresses x and z in terms of x .

Y ,Y

We now return to Step 2 and (26) of the current iteration. Since d :

,

(, 9), the current basic feasible solution is not optimal. The current value

: is an improvement, however.

TERMINATION AND CYCLING 245

Step 3(i). Since d 9 0 and d : 0, we take x to be the entering variable.

Step 3(ii). The column corresponding to x is the third column of (26). Since

the only positive entry in this column is the entry in row 3 corresponding to

x , the variable x will be leaving variable. We rewrite the matrix (26) with the

updated basic variables indicated on the left:

x x x x x z

0 9 9 0

x 1 0

1 9 0 .

x 0 0

9 1

x 0 0 0

9 0 91 9

0 0

We now follow Step 4 and begin another iteration with Step 1. We follow

our pivot rule and pivot on in row 3, column 3. This will result in a matrix

x xx x x z

0 0 9

x 1 0

.

x 0 10 0

0 1 9

x 0 0

0 0 9 9 91 9

0

Step 2. d : (9, 9). All components of d are negative, so the current basic

, ,

feasible solution is optimal. From the last column we get that

: ( , , ) : (, , )

and that the value of the objective function is : . This solution corresponds

to the point (, ) in Figure 6.1.

5. TERMINATION AND CYCLING

In Section 4 we showed that each iteration of the simplex method results in a

value of the objective function that is greater than or equal to the value of the

objective function at the preceding iteration. If we could show that each

iteration produces a value of the objective function that is strictly greater than

the value at the preceding iteration, then the simplex method would terminate

at an optimal solution in a ¬nite number of steps, for then no basic feasible

solution could appear in different iterations and there are a ¬nite number of

basic feasible solutions. Unfortunately, it is not true that each iteration

246 SIMPLEX METHOD

produces a value of the objective function that is strictly greater than the

preceding value, as the following simple example shows.

Let us suppose that at the end of Step 2 of an iteration we had arrived at a

system given by

xx x xx z

x 11 100 0 1

x 0 2 91 1 0 0 0.

x 01 101 0 3

0 3 91 0 0 91 1

Then the entering variable is x and the entering column v is the second

O

column. Recalling that the last column gives ( , 9 ), we get that

1 0 3

G : : .

G : : , G‚ : : : 0, (1)

v v v v v v

1 2 1

Thus t* : 0 and the leaving variable is x . It then follows from (4.20) that