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.
|Date of creation||2013-03-22 13:35:21|
|Last modified on||2013-03-22 13:35:21|
|Last modified by||Mathprof (13753)|