Page 396 - A Course in Linear Algebra with Applications

380 Chapter Ten: Linear Programming

10.2 The Geometry of Linear Programming

Valuable insight into the nature of the linear program-
ming problem is gained by adopting a geometrical point of
view and regarding the problem as one about n-dimensional
space.
We will identify an n-column vector X with a point

(x 1,x 2,...,x n)

n
in n-dimensional space and denote the latter by R . The set
of points X such that

a\Xi + • • • + a nx n — b,

where the real numbers <2j,6 are not all zero, is called a hy-
n
perplane in R . Thus a hyperplane in R 2 is a line and a
hyperplane in R 3 is a plane.
Let A = (ai a 2 ... a n ); thus the equation of the hyper-
plane is AX = b: let us call it H. Then H divides R n into
two halfspaces

= {X eK n \AX < b}
H 1

and
n
= {XeR \AX> b}.
H 2
Clearly
R n = ff!U H 2 and H = H 1nH 2.

In a linear programming program in x\,..., x n, each con-
straint requires the point X to lie in a half space or a hyper-
plane. Thus the set of feasible solutions corresponds to the
points lying in all of the half spaces or hyperplanes correspond-
ing to the constraints. In this way we obtain a geometrical
picture of the set of feasible solutions of the problem.