,

then the current basic feasible solution is optimal and the process terminates.

To see that this is so, recall that by Remark 3.1 we need only consider basic

feasible solutions in our search for the optimal solution. The current basic

feasible solution is the unique basic feasible solution with x : 0 . Thus any

, ,

other basic feasible solution will have at least one of the components of x

,

positive. But since d - 0, we have from (8) that the value of the objective

,

function will either decrease or be unchanged. Thus the current basic feasible

solution is optimal.

In our example, we see from (16) that the current solution is not optimal.

Step 3. If the current basic feasible solution is not optimal, either determine a

new basis and corresponding basic feasible solution that does not decrease the

current value of z or determine that z is unbounded and that therefore the

problem has no solution.

We ¬rst motivate Step 3 using Example 4.1.

PHASE II OF SIMPLEX METHOD 239

From (16) we see that if we keep the value of x at zero and increase the

value of x , then we shall increase the value of z. The variables x , x , x , x ,

x must satisfy (15) and the condition x . 0, i : 1, . . . , 5, for feasibility. Setting

G

x : 0 in (15) and taking into account the requirement that x , x , and x must

be nonnegative give the following inequalities that x must satisfy:

1 9 x . 0, 1 9 2x . 0, 3 9 x . 0.

For all three of these inequalities to hold we can only increase the value of x

to . If x : and x : 0, then from (15) we get that x : , x : 0, and

x : . We now have another feasible solution (, , 0, 0, ). This corresponds

to the point (, ) in Figure 6.1. The value of z is increased from 91 to .

We next show that this solution is basic. The matrix corresponding to the

system (15) is the submatrix of (14) consisting of the ¬rst three rows of (14).

The matrix B corresponding to (, , 0, 0, ) is the matrix formed by taking

columns 1, 2, and 5 of this submatrix. Thus

110

B: 0 2 0 .

011

Since the columns of B are linearly independent, the point (, , 0, 0, ) is a

basic feasible solution.

In summary, the original basic variable x whose value was 1 is now a

nonbasic variable and the original nonbasic variable x is now a basic variable

with value . The variable x is said to be the leaving variable or to leave the

basis and the variable x is said to be the entering variable or to enter the basis.

Before presenting Step 3 in general, we call attention to another possible

situation. Suppose that we have an example such that instead of (15) we arrived

at a system

x :1; x ;x ,

x :1; x ;x ,

x :3; x ;x ,

with z as in (16) and where , , and are all nonnegative. If we set x : 0 and

let x : t, then we obtain feasible solutions for all t 9 0. If we let t ; -, we

get that z ; -. Thus, the objective function is unbounded and the problem has

no solution.

We now describe Step 3, which we break up into two substeps, for the

general problem.

Step 3(i). Choose the nonbasic variable that will enter the new basis.

240 SIMPLEX METHOD

Let d be as in (7). Since the current basic feasible solution is not optimal,

,

at least one of the components of d is positive. Choose the component of d

, ,

that is the largest. If there is more than one such component, choose the one

with the smallest index. Suppose that the component of d that is chosen is the

,

qth component of x : (x , . . . , x ). The variable x will enter the basis. The

L O

column of A corresponding to x is A .

O O

Step 3(ii). Determine that the problem has no solution or choose the basic

variable that will leave the basis.

Let v be the column of B\N corresponding to x . Then v : B\A . Let

O O O O

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

GK G GK

G

and let v : (v , . . . , v ). Set x : t, where t . 0 and let the other components

O O KO O

of x remain at zero. For the resulting vector to be a feasible solution, x must

,

satisfy the conditions (4) and x . 0. Equation (4) becomes

x: 9 tv . (18)

O

Thus, the condition x . 0 imposes the restrictions

tv - , r : 1, . . . , m. (19)

GP

PO

From (8) we get that

z : ; d t. (20)

O

Since is feasible, . 0, and so . 0 for all r : 1, . . . , m. Hence if v - 0

G PO

for all r : 1, . . . , m, then (18) and (19) Phold for all t . 0. Since d 9 0, it follows

O

that z is unbounded above and the problem has no solution.

If not all of the v are nonpositive, let

PO

GP : r : 1, . . . , m and v 9 0 .

t* : min (21)

PO

v

PO

denote the smallest index r at which the minimum is achieved. Let

Let

x : t* and let

O

: 9 t*v , i "i ,

GP GP PO P M

: t*

O (22)

: 0,

GM

: 0 all other indices.

G

PHASE II OF SIMPLEX METHOD 241

Let denote the vector whose coordinates are given by (22). Thus

: ( , . . . , , 0, , . . . , , 0, . . . , 0, t*, 0, . . . , 0),

G GM\ GM> GK

where t* is the qth coordinate of . It follows from the way was constructed

that is a feasible solution. We shall show that is also basic.

We can write as : ( , ) with

Y,

: ( , . . . , , t*, , . . . , ), : 0.

Y G GM\ GM> GK ,Y

We shall show that the coordinate variables of

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

G GM\ O GM> GK

Y

are a basis. Since x is obtained from x by replacing x by x , this will also

GM

Y O

justify our saying that x enters the basis and x leaves the basis.

GM

O

From (17) we get that the matrix I in (2) and (9) is

K

(e . . . e e e . . . e ),

GM\ GM GM> GK

G

where e is the vector whose i th component is 1 and whose other components

GH H

are zero. Let

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

G GM\ O GM> GK

That is, B is the matrix obtained from I by replacing the i th column by v .

K M O

Let N be the matrix obtained from B\N by replacing column v by e . Let

G

O

x be as in (23) and let x be the vector obtained from x by replacing Nx by

Y ,Y , O

x . Let d denote the qth coordinate of the vector d de¬ned in (7) and let d

GM O , ,Y

denote the vector obtained from d by replacing the qth coordinate of d by

, ,

0. The system of equations

x

Y

%e %e N 0 B\c

e ve

G GN\ O GN> GK K x: (24)

,Y

0% d %0d 91 9

0 0

O ,Y z

is equivalent to the system whose augmented matrix is (11), since (24) is

obtained from (11) by a reordering of the variables.

We assert that the matrix B is a basis and hence that the variables x are

Y

basic. To prove this, we must show that the columns of B are linearly

independent. By (21) and the de¬nition of the index , the i th component of

M

v is positive. The i th component of each of the other columns of B is zero.

O M

Hence v cannot be written as a linear combination of the other columns of B.

O

Since the remaining columns of B are linearly independent, it follows that all

the columns of B are linearly independent. Hence the coordinate variables of

242 SIMPLEX METHOD

x are a basis, and the vector is a basic feasible solution. From (20) we get

Y

that

: ; d t*.

O

Since d . 0 and t . 0, it follows that the value of the objective function is not

O

decreased.

We say that in Step 3 we have updated the unprimed quantities to the

primed quantities. The primed, or updated, quantities are the ˜˜new™™ or

˜˜updated current™™ quantities.

Remark 4.3. In Step 3(i) we choose the entering variable x to be the variable

O

corresponding to the largest component of d . Upon examining Step 3, it

,

should be clear that the choice of entering variable could be any variable

corresponding to a positive component of d . The choice of largest component

,

was motivated by the fact that at a given iteration this choice would appear to

result in the largest increase in the value of z.

Step 4. Return to Step 1 using the updated current quantities and start the

next iteration.

We now illustrate Steps 3 and 4 using Example 4.1.

Step 3(i). From (14) we see that d : (d , d ) and that d 9 0 and d : 0. Thus,

,

we take x as the entering variable. The entering column v is the second

O

column of (14), and d : d : 3.

O

Step 3(ii). By Remark 4.2, the entries in the last column of (14) give

) : ( , , ) : (1, 1, 3), : 91.

( , ,

G G‚ G

From this and the fact that the ¬rst three entries in column 2 are positive, we

get that

1

G : : 1, G‚ : : , G : : 3.