Page 413 - A Course in Linear Algebra with Applications

10.3: Basic Solutions and Extreme Points 397

Example 10.3.1
Consider the linear programming problem

maximize: z = 3x + 2y

(2x-y< 6
subject to: < 2x + y < 10
{ x,y>0

First transform the problem to canonical form by intro-
ducing slack variables u and v:
maximize: z = 3x + 2y

{ 2x — y + v = = 10 6
+ u
2x
+ y
x,y,u,v > 0
The matrix form of the constraints is

2 - 1 1 0 \ y 6
(
2 1 0 l) u - " I io

The coefficient matrix has rank 2 and each pair of columns
is linearly independent. Clearly there are (*) = 6 basic solu-
tions, not all of them feasible. In each such solution two of the
non-basic variables are zero. The basic solutions are listed in
the table below:

x y u v type z

0 0 6 10 feasible 0
0 10 16 0 feasible 20
3 0 0 4 feasible 9
5 0 - 4 0 infeasible 15
4 2 0 0 feasible 16
0 - 6 0 16 infeasible -12