<<

. 55
( 59 .)



>>

candidate for leaving the basis B. Yet, we chose x with t 9 r to leave the basis,
R
in contradiction to the smallest index rule.

Remark 5.2. Computational experience indicates that using the smallest sub-
script rule or the lexicographic rule instead of the max d rule considerably
G
increases the time required for the simplex method or the revised simplex
method to ¬nd an optimal solution. Since very few instances of cycling have
been reported, some computer codes do not incorporate any anticycling
routines. Other computer codes introduce an anticycling routine only after a
sequence of speci¬ed length of degenerate bases occurs. The anticycling routine
will then lead to a nondegenerate basis, at which point the use of the largest
coef¬cient rule can be resumed.

Exercise 5.1. Carry out the iterations of the simplex method for Example 5.1
and show that cycling occurs at the sixth iteration. Note: :( , , ) :

(0, 0, 1) is a basic feasible solution.

Exercise 5.2. Solve the problem in Example 5.1 using the simplex method and
Bland™s rule.
PHASE I OF SIMPLEX METHOD 251


6. PHASE I OF SIMPLEX METHOD

As noted in Section 3, phase I of the simplex method either determines a basic
feasible solution or determines that none exists, in which case the problem has
no optimal solution.
We begin with the linear programming problem in standard form (SLP):

Maximize 1b, x2
(1)
subject to Ax - c, x . 0.

Let us ¬rst suppose that the vector c is nonnegative. We then put the problem
in canonical form (CLP) by adjoining a vector of slack variables,

x : (x , . . . , x ), x . 0, i : 1, . . . , m,
1 L> L>K L>G
and write the problem as

Maximize 1b, x2
(2)
x
subject to (A, I) : c, x . 0, x . 0.
1
x
1
Since c . 0, the vector (x, x ) : (0 , c), where 0 is the zero vector in RL, is a
Q L L
basic feasible solution for the problem in (2). We then immediately pass to
phase II with initial basic feasible solution ( , ) : (0 , c).
1 L
If some of the components of c are negative, the vector (0 , c) is still a basic
L
solution of the system of equations in (2), but it is not feasible. We therefore
resort to another device and introduce an auxiliary problem.

Auxiliary Problem
Minimize x subject to

x
(A, I, 9e) x : c
1 (3)
x

x . 0, x . 0, x . 0,
1 
where e : (1, . . . , 1) and I is the m ; m identity matrix.
In component form the system in (3) is

L
 a x ;x 9x :c , i : 1, . . . , m,
GH H L>G  G
H
x . 0, j : 0, 1, . . . , n ; m.
H
252 SIMPLEX METHOD


A vector ( , ) is feasible for relation (2) if and only if ( , , 0) is feasible for
1 1
the auxiliary problem. Therefore, ( , ) is feasible for relation (2) if and only if
1
( , , 0) is optimal for the auxiliary problem.
1
If we write the objective function of the auxiliary problem as ˜˜Maximize
w : 9x ,™™ then the auxiliary problem becomes a linear programming problem

in canonical form to which we can apply phase II of the simplex method,
provided we can get an initial basic feasible solution. A basic solution to the
system (3) is ( , , ) : (0, c, 0). This solution, however, is not feasible since
1
some components of c are negative. We can obtain a basic feasible solution
from this solution by replacing an appropriate basic variable by x . Before we

do this in general, we shall illustrate using Example 4.1.
In solving Example 4.1, we obtained an initial feasible solution from Figure
6.1. We now ignore the ¬gure and write the auxiliary problem in canonical
form: Maximize w : 9x subject to

9x 9x ;x 9 x : 91,
   
9x ;x ;x 9 x : 0,
    (4)
x ; 2x ; x 9 x : 4,
   
x . 0, i : 0, 1, . . . , 5.
G
The vector ( , , , , , ) : (0, 0, 0, 91, 0, 4) is a basic solution but is

not feasible. The only negative entry on the right-hand side is 91 and occurs
in the ¬rst equation. Therefore, if in the augmented coef¬cient matrix of (4) we
pivot on x in row 1, then the right-hand side of the resulting system should

be positive. Performing the indicated pivot gives

xx x xxxc
     
1 1 91 0 0 1 1
(5)
0 2 91 1 0 0 1
2 3 91 0 1 0 5

Thus, ( , , , , , ) : (1, 0, 0, 0, 1, 5) is a basic feasible solution. From

(5) we also get that

w : 9x : 91 ; x ; x 9 x . (6)
   
We can now start phase II for the problem of minimizing (6) subject to the
constraining equations given by (5). We leave this to the reader and return to
the general situation.
We now obtain a system equivalent to (3) and having a basic feasible
solution. Let c denote the most negative component of c. Thus,
N
c : min+c : i : 1, . . . , m,.
N G
PHASE I OF SIMPLEX METHOD 253


If there are more than one such components, choose the one with smallest
index. Next, pivot on x in the pth row of the system (3). The result will be an

equivalent system
x
(A, e , . . . , e , 9e, e , . . . , e , e ) x : c, (7)
 N\ N> KN 1
x

where e : (1, . . . , 1) and

c : 9c . 0, c : c 9 c . 0, i : 1, . . . , p 9 1, p ; 1, . . . , m.
N G
N G N
The system (7) in component form is
L
 a x 9 x ; x : c , i " p,
GH H G
L>N L>G
H
L
 a x 9 x ; x : c .
NH H N
L>N 
H
Thus a basic feasible solution to (7) is

: c , : c, i : 1, . . . , p 9 1, p ; 1, . . . , m,
N G
 L>G (8)
: 0, i : 1, . . . , n, n ; p,
G
and
L
w : 9x : 9c 9 x ;  a x . (9)
N NH H
 L>N
H
The basic variables are

x ,...,x ,x ,x ,...,x (10)
.
L>N\  L>N> L>K
L>
We have transformed the auxiliary problem (3) to the following problem.
Maximize w as given in (9) subject to (8) and x . 0, i : 0, 1, . . . , n ; m. For
G
this problem we have determined a basic feasible solution given by (8) with
basic variables given by (10). We can now apply phase II to the problem in
this form. If we incorporate an anticycling subroutine in our implementation
of Phase II, then according to Lemma 5.1, we shall, in a ¬nite number of steps,
determine that the auxiliary problem either has no solution or determine an
optimal solution to the auxiliary problem. If the auxiliary problem has no
solution, then the original linear programming problem (1) has no feasible
solution. For, as we saw, a vector ( , ) is feasible for the original problem if
1
and only if ( , , 0) is optimal for the auxiliary problem.
1
The remaining alternative is that the auxiliary problem has a solution. We
now explore the possibilities for this alternative. The variable x is basic

initially. In applying phase II of the simplex method to the auxiliary problem,
254 SIMPLEX METHOD


we note that our rule for choosing the leaving variable is such that if at some
iteration x is a candidate for leaving the basis, then x will be chosen to be
 
the leaving variable. If at some iteration I the variable x leaves the basis, then
I 
at the iteration I , the variable x will have the value zero. The solution
I> 
( , , ) of the constraining equations at I will also be a solution of (3).
1 I>
Hence if : 0, then w : 0 and ( , ) is optimal for relation (1). Thus, if x
 1 
ever leaves the basis at an iteration I , at the next iteration I , we will have
I I>
a solution to the auxiliary problem and hence a basic feasible solution for
relation (2). We can then begin phase II with this basic feasible solution.
An optimal solution could also conceivably occur under the following
circumstances:

(i) x basic, w : 0, and

(ii) x basic, w " 0.

If (ii) occurs, then the original problem has no feasible solution. We now show
that (i) is impossible. If (i) did occur, then x : 9w : 0. Since the previous

iteration did not end in an optimal solution, x " 0 at the start of the previous

iteration and became zero in the previous iteration. If this happened, then x

was a candidate for leaving the basis but did not do so. This contradicts the
rule for determining whether x leaves the basis.

The next lemma follows from the discussion in this section.

L 6.1. If an anticycling routine is included, then phase I of the simplex
method either determines that no feasible solution exists or determines a basic
feasible solution.

Lemmas 5.1 and 6.1 imply the following.

T 6.1. T he simplex method incorporating an anticycling routine applied
to a linear programming problem determines one of the following in a ¬nite
number of iterations:

(i) No feasible solutions exist.
(ii) T he problem does not have an optimal solution.
(iii) An optimal solution.

Exercise 6.1. Complete the solution of the illustrative example.

Exercise 6.2. Let the linear programming problem be given originally in
canonical form:

Maximize 1b, x2
subject to Ax : c, x . 0.
REVISED SIMPLEX METHOD 255


Show that an appropriate auxiliary problem for phase I is

K
Maximize w : 9  y

<<

. 55
( 59 .)



>>