Example:
Returning to the prototype example, it is easy to see that its ``standard form''
formulation is as follows:
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 Figure2
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.
|
