Basic Feasible Solutions: An algebraic
characterization of extreme points for LP's in ``standard form''
For LP's in ``standard form'' the previous characterization of extreme points
as the solution of n linearly independent binding constraints, which is,
furthermore, a feasible point, can become even more concise. Consider, for
instance, the LP
with m technological constraints and n variables. In ``standard
form'', it becomes:
where I is the
identity matrix, and
is the vector of slack variables. It is interesting to notice that for
every binding constraint from the m+n constraints of the original
formulation (Eq.25),
one of the m+n variables of the ``standard form'' formulation must
be equal to 0. Specifically, if the i-th technological constraint is
binding, the corresponding slack variable
. Similarly, if one of the sign restriction constraints is binding, then the
corresponding varialbe
. Since an extreme point of the feasible region of formulation25
requires n binding constraints for its definition, it follows that n
from the n+m variables in the corresponding solution of the
``standard form'' formulation (Eq.26)
must be equal to zero. Furthermore, since this point is uniquely defined, the
system of equations defined by the m technological constraints in the
``standard form'' formulation and the m remaining variables, must have a
unique solution. In other words, the columns of the ``standard form''
formulation corresponding to these m variables must be linearly
independent (and their determinant must have a nonzero value). Finally, since
the extreme point considered belongs in the feasible region of the problem, it
follows that the unique solution of the aforementioned system of m
equations in the m nonzero variables must be nonnegative (to meet the
sign restrictions required by ``standard form'').
The structure of the ``standard form'' solutions corresponding to extreme
points of the original feasible region (i.e., that defined with respect to the
primary LP variables
), described for the example above, actually applies to any other LP in
``standard form''. We formally characterize this structure through the
definition of basic feasible solutions for LP's in ``standard form''
(taken from Winston, ``Introduction to Mathematical Programming'').
|
