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.