Introduction to Algorithms, Third Edition

Termination:
The
while
loop can terminate in one of two ways. If it terminates
because of the condition in line 3, then the current basic solution is feasible and
line 17 returns this solution. The other way it terminates is by returning “un-
bounded” in line 11. In this case, for each iteration of the
for
loop in lines 5–8,
when line 6 is executed, we find that
a
i e
0
. Consider the solution
N
x
defined as
N
x
i
D
1
if
i
D
e ;
0
if
i
2
N
f
e
g
;
b
i
P
j
2
N
a
ij
N
x
j
if
i
2
B :
We now show that this solution is feasible, i.e., that all variables are nonneg-
ative. The nonbasic variables other than
N
x
e
are
0
, and
N
x
e
D 1
> 0
; thus all
nonbasic variables are nonnegative. For each basic variable
N
x
i
, we have
N
x
i
D
b
i
X
j
2
N
a
ij
N
x
j
D
b
i
a
i e
N
x
e
:
The loop invariant implies that
b
i
0
, and we have
a
i e
0
and
N
x
e
D 1
> 0
.
Thus,
N
x
i
0
.
Now we show that the objective value for the solution
N
x
is unbounded. From
equation (29.42), the objective value is
´
D
C
X
j
2
N
c
j
N
x
j
D
C
c
e
N
x
e
:
Since
c
e
> 0
(by line 4 of S
IMPLEX
) and
N
x
e
D 1
, the objective value is
1
,
and thus the linear program is unbounded.
It remains to show that S
IMPLEX
terminates, and when it does terminate, the
solution it returns is optimal. Section 29.4 will address optimality. We now discuss
termination.