<<

. 52
( 59 .)



>>

If every component of the vector d de¬ned in (7) is nonpositive (i.e., -0),
,
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

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

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.

<<

. 52
( 59 .)



>>