Example:
We demonstrate the findings of the above discussion on the feasible region of
the prototype example, which for convenience is reproduced in Figure11.
Figure 11: The feasible region of the prototype example LP
As we can see in the figure, each of the extreme points of this region
corresponds to the binding of a pair of the LP constraints, i.e.,
- point A corresponds to the binding of the two sign restriction
constraints,
- point B corresponds to the binding of the second technological
constraint and the sign restriction of variable
,
- point C corresponds to the binding of both technological constraints,
and
- point D corresponds to the binding of the first technological constraint
and the sign restriction of variable
.
Notice, however, that points E and F, even though they are defined by the
binding of the constraint pairs (tech. con. 1, sign res. of
) and (tech. con. 2, sign res. of
), respectively, are not extreme points of the feasible region just because they
are infeasible (i.e., some other LP constraints are violated). Hence, having
n linearly independent constraints binding at certain point is a
necessary condition for it to be an extreme point of the feasible region,
but not sufficient.
Finally, it should be easy to see that for an n-var LP, n is
the minimum number of constraints binding at an extreme point. If more
than this minimum number of constraints are binding to an extreme point, the
point (and the corresponding solution) are characterized as degenerate.
Degeneracy can complicate the search for the optimal solution carried
out by the Simplex method.
|
