Page 405 - A Course in Linear Algebra with Applications

10.2: The Geometry of Linear Programming 389

same argument P cannot lie in the interior of the line. There-
fore P is a point of intersection of two lines and hence it is an
extreme point of S.

We can now summarize the possible situations for a linear
programming problem with set of feasible solutions S.
(a) S is empty: the problem has no solutions;
(b) S is non-empty and bounded: in this case the problem
has an optimal solution and it occurs at an extreme point
of S.
(c) S is unbounded: here optimal solutions need not exist,
but, if they do, they occur at extreme points of S.

We will see in 10.3 that if S is non-empty and bounded,
then it has a finite number of extreme points. By computing
the value of the objective function at each extreme point one
can find an optimal solution of the problem. We conclude
with two examples.

Example 10.2.2

maximize: z = 2x + 3y

( x+y > 1
subject to: < x — y > — 1
(x,y>0

Here the set of feasible solutions S corresponds to the region
of the xy-plane bounded by the lines x + y = 1, x — y = —1,
x — 0, y = 0. Clearly it is unbounded and z can be arbitrary
large at points in S. Thus no optimal solutions exist.