7-Optimization Page 209 Wednesday, February 4, 2004 12:50 PM
Optimization 209A feasible basic solution is a solution xˆ ≡ ( xˆ 1 ... xˆ n ) ∈ B with the following
additional properties. For each solution x consider the set I of indices such
that the respective variables are strictly positive: I(x) ≡ (i: xi > 0), with x ∈
B. A feasible basic solution x is a feasible solution such that the set
{ Ai: i ∈ I () xˆ } of columns of the matrix A are linearly independent. There-
fore, the components xˆ i , i ∈ I () xˆ are the unique solutions of the system∑ Aixi = bi
i ∈ I () xˆIn fact, it is possible to demonstrate the following two important
results:■ If an LP has a bounded optimal solution, then there exists an extreme
point, that is, a minimum or maximum, of the feasible (on one of the
vertices) region, which is optimal.
■ Extreme points of the feasible region of an LP correspond to basic fea-
sible solutions of the standard form representation of the problem.The first result implies that in order to obtain an optimal solution of
an LP, we can constrain our search on the set of the extreme points of its
feasible region. The second result implies that each of these points is
determined by selecting a set of basic variables, with cardinality equal to
the number of the constraints of the LP and the additional requirement
that the (uniquely determined) values of these variables are nonnegative.
This further implies that the set of extreme points for an LP with m con-
straints and N variables in its standard form representation can have only a
finite number of extreme points. A naive approach to the problem would be
to enumerate the entire set of extreme points and select one which minimizes
the objective function over this set. However, for reasonably sized LP prob-
lems, the set of extreme points, even though finite, can become extremely
large. Hence a more systematic approach to organize the search is needed.
The simplex algorithm provides such a systematic approach.
The algorithm starts with an initial basic feasible solution and tests its
optimality. If an optimality condition is verified, then the algorithm termi-
nates. Otherwise, the algorithm identifies an adjacent feasible solution
with a better objective value. The optimality of this new solution is tested
again and the entire scheme is repeated until an optimal solution is found.
The algorithm will terminate in a finite number of steps except in special
pathological cases. In other words, the simplex algorithm starts from
some initial extreme point and follows a path along the edges of the feasi-
ble region towards an optimal extreme point, such that all the intermedi-