<<

. 56
( 59 .)



>>

G
G
x
subject to (A, I) : c, x . 0, y . 0.
y

Show how one obtains an initial basic feasible solution for the auxiliary
problem.

Exercise 6.3. Solve the following linear programming problems using the
simplex method:

(a) Maximize x ; 3x subject to
 
x ; 2x ; 7x - 4,
  
x ; 3x ; x - 5,
  
x . 0, i : 1, 2, 3.
G
(b) Maximize 3x 9 x subject to
 
x ; 2x . 2,
 
3x ; x - 3,
 
x - 4, x . 0. i : 1, 2, 3, 4.
G G
(c) Maximize 92x 9 x ; x ; x subject to
   
x 9 x ; 2x 9 x : 2,
   
2x ; x 9 3x ; x : 6,
   
x ; x ; x ; x : 7.
   

7. REVISED SIMPLEX METHOD

The revised simplex method does not differ from the simplex method in
principle, that is, in going from one basic solution to another in such a way
that the objective function is not decreased but differs in the manner in which
some of the computations are carried out. In describing the revised simplex
method, we assume, as we did in our description of the simplex method in
Section 4, that the problem has been formulated as in (4) of Section 3. The
reader will recall from Section 4 that at each iteration a basis B is determined
256 SIMPLEX METHOD


and the calculation of B\N is used to determine the entering and leaving
variable. The revised simplex method differs from the version of the simplex
method given in Section 4 in that a system (1) in Section 4 with current B is
not reduced to (11) in Section 4 and the current basis not given by (22) in
Section 4. In the revised simplex method the entering variable x is chosen as
O
before. If A is the column of A corresponding to x , then the updated basis B
O O
is obtained from B by replacing the column A of the leaving variable x by
GM GM
A . This procedure enables us to calculate (B)\ from B\ very easily and
O
expedites other calculations, as we shall show.
Before we present the steps in an iteration of the revised simplex method,
we take up the calculation of (B)\, the updated inverse. At the current
iteration I let the basis B be given by

B : (A . . . A ), (1)
G GK
where the A are columns of B. We then write
GG
N : (A . . . A ).
GK> GL
Let x be the entering variable at I, determined as in Section 4, and let A
O O
denote the column of N corresponding to x . Let the leaving variable x be
GM
O
determined as in Section 4. Let B denote the matrix obtained from B by
replacing the column A by A and let N denote the matrix obtained from N
GM O
by replacing column A by A . Thus
GM
O
B : (A . . . A A A . . . A ),
G GM\ O GM> GK (2)
N : (A ...A A A . . .A ).
GK> GO\ GM GO> GL
Hence
B\B : B\(A . . . A A A ...A )
G GM\ O GM> GK
10%0v 0%0
O
01%0v 0%0
O
: (3)
$$\$ $ $\$
00%0v 0%1
KO
: (e . . . e v e . . .e ),
M\ O M>
 K
where v : B\A . Note that v is the qth column of B\N associated with x
O O O O
and thus is as in Step 3(ii) of an iteration in the simplex method. From the way
is determined we have that v 9 0, and hence the matrix on the right in (3)
MO
is nonsingular. If we multiply both sides of (3) by B on the left, we get that

B : B(e . . . e v e . . . e ).
M\ O M>
 K
REVISED SIMPLEX METHOD 257


Since B is the product of nonsingular matrices, it is nonsingular and so is a
basis. We also get

(B)\ : (e . . .e v e . . . e )\B\. (4)
M\ O M>
 K
It is readily veri¬ed that multiplying the matrix on the right-hand side of the
following by the matrix on the right-hand side of (3) gives the m ; m identity
matrix. Hence

0 % 0 \
10%0 v 10%0 0%0
O O
01%0 v 0%0 01%0 0%0
O O
$$\$ $ \ $$\$ $ $\
: ,
00%0 v 00%0 0%1
KO KO
! !
col col

(5)

where

v 1
: 9 GO , i : 1, . . . , m, i" , : .
GO MO
v v
MO MO
The matrix on the right in (5) is called an eta matrix and will be denoted by
E . Thus we may write (4) as

(B)\ : E B\, (6)

which updates B\ for the next iteration.
We summarize this discussion in the following lemma

L 7.1. L et B be a basic matrix as in (1) and let B be a matrix as in (2).
T hen B is basic and (6) holds, where E is the matrix on the right in (5).

Remark 7.1. In the various calculations in the simplex method the essential
matrix is B\, not B. The matrix B is needed, in principle, only to calculate
B\. Equation (6) enables us to calculate (B)\ from B\ without knowing B
or B. It is this fact that underlies the revised simplex method. Also note that
an eta matrix differs from an identity matrix in one column.

We now present a generic revised simplex method. Most computer codes for
solving linear programming problems use the revised simplex method. Codes
used in practice incorporate various modi¬cations to improve accuracy, reduce
the number of iterations needed, decrease the running time, and so on. For
details the reader is referred to Chvatal [1983], Dantzig [1963], Gass [1985],
´
and Murtagh [1981].
258 SIMPLEX METHOD


As in our presentation of the simplex method we assume that the problem
is in canonical form: Maximize z subject to

Ax : c, 1b, x2 9 z : 0, x . 0. (7)

Let the initial stage or iteration of phase II be called the zeroth iteration. At
the kth iteration, k : 0, 1, 2, . . . , let B(k) denote the basis, let N(k) denote the
submatrix of A complementary to B(k), let x denote the vector of basic
I
,0 )
variables, let x denote the vector of nonbasic variables, let (k):(
,I I ,I
be the corresponding basic feasible solution, and let (k) be the current value
of the objective function. Equations (4)”(6) from Section 4 yield, for k :
0, 1, 2, . . . ,

: 9 [B(k)]\N(k)x N(k) ,
x
I I
(k) : 1b , 2, (8)
I I
z : (k) 9 1b 9 bR [B(k)]\N(k), x 2.
,I I ,I
From Lemma 7.1 we get that

[B(k ; 1)]\ : E k : 0, 1, 2, . . . ,
[B(k)]\,
I>
where E is an approximate eta matrix. Proceeding inductively, we get
I>
[B(k ; 1)]\ : E (E (. . . E (E [B(0)]\) . . .)). (9)
I> I 
A sequential ¬le in the computer storing the matrices E , E , . . . , E is called
I> I 
an eta ¬le. The calculation as indicated in (9) (from right to left) is called a
forward transformation. The matrix [B(0)]\ is calculated using elementary
matrices as in (11) from Section 3.
We now present the steps in the kth iteration, k . 1, of our generic revised
simplex algorithm. In essence, the steps mirror the steps of the simplex
method as presented in Section 4. Some of the calculations are different and
Step 1 of the simplex method is deleted. For typographical convenience we will
replace the designations B(k), N(k), x , x , . . . of the current quantities by
I ,I
B, N, x , x , . . . . The updated quantities B(k ; 1), N(k ; 1), x ,x ,...
I> , I>
,
will be designated as B, N, x , x , . . . . As in (7) from Section 4 let
Y ,Y
d : b 9 bR B\N : (d . . . d ), (10)
GK> GL
, ,
where i , . . . , i are the components of x that constitute x . We may then
K> L ,
write the last equation in (8) as

L
z : ; 1d , x 2 : ;  dx.
GG
,,
NK> N N
REVISED SIMPLEX METHOD 259


Step 1. Calculate d . This is done in two steps.
,
(i) Calculate

: bR E E . . . E [B(0)]\
I I\ 
from left to right, that is, as

(. . . ((b R E )E ) . . .)E )[B(0)]\.
I I\ 
This backward transformation involves repeated multiplications of a vector by
a matrix, whereas the forward calculation (from right to left) involves
repeated multiplications of matrices. Clearly, the backward transform-
ation involves fewer operations.
(ii) Calculate

d : b 9 1 , A 2, j : m ; 1, . . . , n,
GH GH GH
where the i are the indices of the nonbasic variables at the kth stage and the
H
A are the corresponding columns of N.
GH
Step 2. If all the d are less than or equal to zero, the current basic feasible
G
solution is optimal Hand the algorithm terminates. If the algorithm terminates,
then we use (8) to calculate , the optimal value.

If the algorithm does not terminate at Step 2, we go to Step 3.

Step 3. Choose an entering variable.

Choose an index i such that d 9 0. This may be done according to the
GH
H
smallest index rule, the max d rule, or any other rule, as long as d 9 0. We

<<

. 56
( 59 .)



>>