An algebraic characterization of the solution search space: Basic Feasible Solutions

In the previous section we showed that if an LP has a (bounded) optimal solution, then it has (at least) one which corresponds to an extreme point of its feasible region. To exploit this result algorithmically, we need an algebraic characterization of the extreme point concept. This is the topic of this section.

The starting point of this discussion is the observation made at the end of the previous section, that at an extreme point, the set of binding constraints is such that it characterizes the point uniquely. Let's try to investigate what is the algebraic structure implied by this statement. Also, staying close to the general spirit of our discussion, let's examine this issue in an inductive manner.

• We know that in the 1-dim space, i.e., on the line of real numbers, a point can be identified uniquely by an equation a X = b, where .
• In the 2-dim space, a linear equation defines a line, i.e., a subspace with 1 ``degree of freedom'', while the definition of a unique point requires a system of two linear equations:

  

  

  with a unique solution, i.e., with

  

  Such a system of equations is characterized as linearly independent, and geometrically, it corresponds to two intersecting straight lines.

• In the 3-dim space, a linear equation corresponds to a plane perpendicular to the vector . A system of two linear equations:

  

  

  for which:

  

  corresponds to the intersection of two planes, i.e., a straight line.

  Defining a unique point in the 3-dim space requires three linearly independent equations, i.e.,

  

  

  

  with

  

• In a similar fashion, in the n-dim space, a point is uniquely defined by n linear equations which are linearly independent, i.e.,

  

  

  

  

  with

  

• Example:
• LP's in ``standard form''
• Basic Feasible Solutions: An algebraic characterization of extreme points for LP's in ``standard form''
• Example: