|
The simplex algorithm is used as part of the simplex method (due to George B. Dantzig) to solve linear programming problems. The algorithm is applied to a linear programming problem that is in canonical form.
A canonical system of equations has an ordered subset of variables (called the basis) such that for each , the basic variable has a unit coefficient in the
equation and zero coefficient in the other equations.
As an example
are basic variables in the following system of equations:
The simplex algorithm is used as one phase of the simplex method.
Suppose that we have a canonical system with basic variables
and we seek to find nonnegative
such that is minimal. That is, we have
where
are constants, and
.
Notice that if we set
we will have a feasible solution with . Hence, any optimal solution will have
. The algorithm can now be described as follows:
Step 1. Set
and
. Put for .
Step 2. If there an index such that then choose such that
else stop. The solution is given by for and for , .
Step 3. If
for all then stop. The value of has no lower bound. Else, let
. If there is more than one choice for it does not matter which one is chosen unless . This is the so-called degenerate case. In this case, one can choose uniformly at random from among those for which .
Step 4. (Pivot on ). Multiply the equation by
and for each
, replace equation by the sum of equation and the (replaced) equation multiplied by . Replace the equation for by the sum of the
equation for and the (replaced) equation multiplied by . Note: The replacement operations of course change the coefficients and . As the algorithm proceeds it is of course necessary to use the changed coefficients.
Step 5. (Update and ) Put into and into and remove from and from . Go to step 2.
There are examples where the algorithm does not terminate in a finite number of steps; but if there is non-degeneracy at each iteration, the algorithm will terminate in a finite number of steps.
|