s.t.

This formulation involves four variables and two technological constraints. Therefore, any basic solution will be defined by selecting a basis of two variables, with the remaining two being set equal to zero. For example, selecting as basis the variable set implies that (since they are the remaining non-basic variables). This further implies that the considered basic solution corresponds to the extreme point of the LP feasible region defined by the binding of the two technological constraints. Finally, the values of the two basic variables and are obtained by solving the system of equations:

which results from the technological constraints in ``standard form'', by eliminating the non-basic variables.

On the other hand, consider the extreme point *B* of the feasible
region, which is the optimal solution of this example LP. It has been
already shown (cf. previous example) that this point is defined by the
binding of the second technological constraint and the sign
restriction imposed on variable . Hence, at this point, , and the corresponding *basis* consists of variables
and . To compute the values for these variables, we solve the
system of equations:

Finally, the basic solution defined by the basis
implies that , and therefore, the corresponding point
on the -plane, *F*, is defined by the binding of second
technological constraint and the sign restriction of variable
. Solving the system of equations:

we obtain: . This
basic solution is not feasible, which is also reflected in
Figure 2 by the fact that point *F* is not an extreme
point of the feasible region. .

In the example above, extreme points *B* and *C* are *adjacent*,
in the sense that they are linked by one edge of the feasible
region. This reflects in the structure of the corresponding bases by
the fact that they differ in only one binding constraint. This
observation generalizes to the *n*-dimensional case: extreme points
connected by *``edges''* of the feasible region have *n*-1 common
binding constraints, and therefore, their corresponding *bases*
will differ in one variable only. Hence, we have the following
definition:

The characterization of the extreme points of the feasible region of an LP as basic feasible solutions for its ``standard form'' representation provides the analytical means for organizing the search for an optimal extreme point performed by the Simplex algorithm. The details of this algorithm is the topic of the next section.

Fri Jun 20 15:03:05 CDT 1997