next up previous
Next: The Simplex Algorithm Up: An algebraic characterization of Previous: Basic Feasible Solutions: An


Returning to the prototype example, it is easy to see that its ``standard form'' formulation is as follows:






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 tex2html_wrap_inline1965 implies that tex2html_wrap_inline1967 (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 tex2html_wrap_inline1457 and tex2html_wrap_inline1461 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 tex2html_wrap_inline1457 . Hence, at this point, tex2html_wrap_inline1981 , and the corresponding basis consists of variables tex2html_wrap_inline1461 and tex2html_wrap_inline1985 . To compute the values for these variables, we solve the system of equations:



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



we obtain: tex2html_wrap_inline2005 . 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. tex2html_wrap_inline1517 .

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.

next up previous
Next: The Simplex Algorithm Up: An algebraic characterization of Previous: Basic Feasible Solutions: An

UAL Data
Fri Jun 20 15:03:05 CDT 1997