Page 397 - A Course in Linear Algebra with Applications

10.2: The Geometry of Linear Programming 381

Example 10.2.1

Consider the simple linear programming problem in standard
form:

laximi ze: z = x + y
(2x+ y < 3
to: < x + 2y < 3
x,y>0
The set S of feasible solutions is the region of the plane which
is bounded by the lines 2x + y = 3, x + 2y = 3, x = 0, y = 0

The objective function z = x + y corresponds to a plane
in 3-dimensional space. The problem is to find a point of S
at which the height of the plane above the xj/-plane is largest.
Geometrically, it is clear that this point must be one of the
"corner points" (0,0), (f ,0), (1,1), (0, §). The largest value of
z — x + y occurs at (1,1). Therefore x = 1 = y is an optimal
solution of the problem.
The next step is to investigate the geometrical properties
of the set of feasible solutions. This involves the concept of
convexity.