
Geometry of Linear Programming 63
FIGURE 2.13
Feasible set (2.4).
2.3.2 Degeneracy
An extreme point x ∈ P = {x ∈ R
n
|Ax = b, x ≥ 0} is a geometric entity
and has a corresponding representation as a basic feasible solution. A natural
question to ask is whether this correspondence is one to one. It is clear that a
given basic feasible solution will correspond to a unique extreme point. But,
for an extreme point x, is there a unique representation as a basic feasible
solution? This is not the case as Example 2.17 above illustrates that several
basic feasible solutions can correspond to the same extreme point. The feasible
set in Example 2.17 is graphed in ...