
The Simplex Method 85
will lead to a decrease in the objective function.
Feasibility of a Descent Direction
A fundamental issue not addressed yet is whether the resultant vector
x
new
= x
current
+ αd
q
is feasible for the linear program in standard form. In
particular, x
new
is feasible if the following conditions hold
(1) Ax
new
= b and (2) x
new
≥ 0.
To show that (1) holds, consider that Ax
new
= A(x
current
+ αd
q
) =
Ax
current
+ αAd
q
. Thus, if Ad
q
= 0, then (1) will hold. Now, by the par-
tition implied by x
current
,
Ad
q
=
B N
−B
−1
N
q
e
q
= −BB
−1
N
q
+ N e
q
= −N
q
+ N
q
= 0.
To show (2) without loss of generality, assume that d
q
is a descent direction.
Then, we need
x
new
= x
current ...