I.E. 2001   OPERATIONS RESEARCH

THE SIMPLEX METHOD: Development

Every Linear Program is in exactly one of the following states:
  1. Feasible with a unique optimum solution.
  2. Feasible with infinitely many optima.
  3. Feasible, with no optimum solution, because the objective is unbounded.
  4. Infeasible, and hence with no optimum solution.
Assume we are in States 1 or 2. Then the following are true:
  1. The LP has at least one optimal corner point (or extreme point).
    1. If in State 1, exactly one extreme point is optimal.
    2. If in State 2, at least two adjacent (neighboring) extreme points are optimal.
  2. The number of extreme points is finite.
  3. If the objective function at some extreme point is as good as or better than at all of its adjacent extreme point, then this extreme point is optimal for the LP.
It follows then that we can use the following iterative algorithmic procedure:

STEP 0 (Initialization): Find an initial extreme point and make it the current candidate (if one cannot be found the LP is in state 4, i.e. it is infeasible – so STOP).

STEP 1 (Stopping Criterion Check): Is the objective at the current extreme point better than it is at all of its adjacent (neighboring) extreme points? If so this must be the optimal extreme point (via C) – so STOP. If not, go to Step 2.

STEP 2 (Iterative Step): At least one of the adjacent extreme points is better – so make it the current candidate and go to Step 1.

QUESTIONS:

  1. How to find an initial extreme point?
  2. What is the algebraic characterization of an "extreme point?"
  3. What is the algebraic characterization of adjacent extreme points, i.e., how to move from an extreme point to one of its neighbors (in Step 2)?

 
Continue with next page...


Back to IE 2001 Web Documents page.