<<

. 53
( 59 .)



>>

v v v v v v
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

<<

. 53
( 59 .)



>>