Page 404 - A Course in Linear Algebra with Applications

388 Chapter Ten: Linear Programming

and X = (1 — c m)Y + c mX m is an interior point of the line
segment joining Y and X m. Hence X is not an extreme point
of S, which completes the proof.

It is now time to explain the connection between optimal
solutions of a linear programming problem and the extreme
points of the set of feasible solutions.

Theorem 10.2.5 (The Extreme Point Theorem)
Let S be the set of all feasible solutions of a linear program-
ming problem.
(i) If S is non-empty and bounded, then there is an
optimal solution.
(ii) If an optimal solution exists, then it occurs at an
extreme point of S.

Here a subset S of R n is said to be bounded if there exists
2
a positive number d such that — d < Xi < d, for i — 1, ,..., n
and all (xi,X2,... ,x n) in S.

Proof of Theorem 10.2.5
Suppose that we have a maximization problem. For simplicity
we will assume throughout that S is bounded and n = 2:
thus S can be visualized as a region of the plane bounded by
straight lines corresponding to the constraints.
Let z = f(x, y) — ex + dy be the objective function: we
can assume c and d are not both 0. Since S is bounded and /
is continuous in 5*, a standard theorem from calculus can be
applied to show that / has an absolute maximum in S. This
establishes (i).
Next assume that there is an optimal solution. By an-
other standard theorem, if P(x, y) is a point of P which is an
/
absolute maximum of , then either P is a critical point of
S or else it lies on the boundary of S. But / has no critical
points: for f x = c, f y = d, so f x and f y cannot both vanish.
Thus P lies on the boundary of S and so on a line. By the