<<

. 51
( 59 .)



>>



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.

<<

. 51
( 59 .)



>>