simplex algorithm

The simplex algorithm is used as part of the simplex method (due to George B. Dantzig) to solve linear programming problems. The algorithmMathworldPlanetmath 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 i, the ith basic variable has a unit coefficient in the ith equation and zero coefficient in the other equations.

As an example x1,,xr are basic variables in the following system of r equations:

x1 + a1,r+1xr+1++a1,nxn=b1
x2 + a2,r+1xr+1++a2,nxn=b2
xr + ar,r+1xr+1++ar,nxn=br

The simplex algorithm is used as one phase of the simplex method.

Suppose that we have a canonical system with basic variables x1,,xm,-z and we seek to find nonnegative xi i=1,,n such that z is minimal. That is, we have

xi+j=m+1naijxj = bii=1,,m
-z+j=m+1ncjxj = -zo

where aij,bj,cj,zo are constants, and bj0,j=1,,m.

Notice that if we set xm+1=0,,xn=0 we will have a feasible solution with z=zo.. Hence, any optimal solution will have zzo. The algorithm can now be described as follows:

Step 1. Set N={m+1,,n} and B={1,,m}. Put cj=0 for jB.

Step 2. If there an index jN such that cj<0 then choose sN such that


else stop. The solution is given by xi=0 for iN and xi=bi for iB, z=zo.

Step 3. If ais0 for all i then stop. The value of z has no lower bound. Else, let brars=minais>0biais. If there is more than one choice for r it does not matter which one is chosen unless bi=0. This is the so-called degenerate case. In this case, one can choose uniformly at random from among those i for which bi=0.

Step 4. (Pivot on ars). Multiply the rth equation by 1ars and for each i=1,,m, ir replace equation i by the sum of equation i and the (replaced) equation r multiplied by -ais. Replace the equation for z by the sum of the equation for z and the (replaced) equation r multiplied by -cs. Note: The replacement operations of course change the coefficients aij and cj. As the algorithm proceeds it is of course necessary to use the changed coefficients.

Step 5. (Update B and N) Put s into B and r into N and remove s from N and r from B. 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.

Title simplex algorithm
Canonical name SimplexAlgorithm
Date of creation 2013-03-22 13:35:21
Last modified on 2013-03-22 13:35:21
Owner Mathprof (13753)
Last modified by Mathprof (13753)
Numerical id 22
Author Mathprof (13753)
Entry type Algorithm
Classification msc 90C05
Synonym simplex method