
Geometry of Linear Programming 53
FIGURE 2.11
Unbounded LP (2.3).
We first define a geometric entity that will correspond to the notion of
a corner point for any dimension. Recall that in two dimensions, a corner
point of a feasible set P of a linear program should not lie in the interior of
P and should not lie in the interior of any line segment on the edge of P . A
mathematical representation of this requirement is embodied in the definition
of an extreme point. First, we need the following.
Definition 2.10
A convex combination of vectors x
1
, x
2
, ..., x
k
∈ R
n
is a linear combination
P
k
i=1
λ
i
x
i
of these vectors such that
P
k
i=1
λ
i
= 1 and λ
i
≥ 0 for i = 1, ...,