# simplex algorithm

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 $i$, the ${i}^{th}$ basic
variable has a unit coefficient in the ${i}^{th}$ equation and zero coefficient
in the other equations.

As an example ${x}_{1},\mathrm{\dots},{x}_{r}$ are basic variables in the following system of $r$ equations:

${x}_{1}$ | $+$ | ${a}_{1,r+1}{x}_{r+1}+\mathrm{\cdots}+{a}_{1,n}{x}_{n}={b}_{1}$ | ||

${x}_{2}$ | $+$ | ${a}_{2,r+1}{x}_{r+1}+\mathrm{\cdots}+{a}_{2,n}{x}_{n}={b}_{2}$ | ||

$\mathrm{\dots}$ | ||||

${x}_{r}$ | $+$ | ${a}_{r,r+1}{x}_{r+1}+\mathrm{\cdots}+{a}_{r,n}{x}_{n}={b}_{r}$ |

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

Suppose that we have a canonical system with basic variables ${x}_{1},\mathrm{\dots},{x}_{m},-z$ and we seek to find nonnegative ${x}_{i}$ $i=1,\mathrm{\dots},n$ such that $z$ is minimal. That is, we have

${x}_{i}+{\displaystyle \sum _{j=m+1}^{n}}{a}_{ij}{x}_{j}$ | $=$ | ${b}_{i}\mathit{\hspace{1em}}i=1,\mathrm{\dots},m$ | ||

$-z+{\displaystyle \sum _{j=m+1}^{n}}{c}_{j}{x}_{j}$ | $=$ | $-{z}_{o}$ |

where ${a}_{ij},{b}_{j},{c}_{j},{z}_{o}$ are constants, and ${b}_{j}\ge 0,j=1,\mathrm{\dots},m$.

Notice that if we set ${x}_{m+1}=0,\mathrm{\dots},{x}_{n}=0$ we will have a feasible solution with $z={z}_{o}.$. Hence, any optimal solution will have $z\le {z}_{o}$. The algorithm can now be described as follows:

Step 1. Set $N=\{m+1,\mathrm{\dots},n\}$ and $B=\{1,\mathrm{\dots},m\}$. Put ${c}_{j}=0$ for $j\in B$.

Step 2. If there an index $j\in N$ such that $$ then choose $s\in N$ such that

$${c}_{s}={\mathrm{min}}_{j\in N}{c}_{j}$$ |

else stop. The solution is given by ${x}_{i}=0$ for $i\in N$ and ${x}_{i}={b}_{i}$ for $i\in B$, $z={z}_{o}$.

Step 3. If ${a}_{is}\le 0$ for all $i$ then stop. The value of $z$
has no lower bound.
Else, let $\frac{{b}_{r}}{{a}_{rs}}={\mathrm{min}}_{{a}_{is}>0}\frac{{b}_{i}}{{a}_{is}}$.
If there is more than one choice for $r$ it does not matter which one
is chosen *unless* ${b}_{i}=0$. This is the so-called degenerate case.
In this case, one can choose uniformly at random from among those
$i$ for which ${b}_{i}=0$.

Step 4. (Pivot on ${a}_{rs}$). Multiply the ${r}^{th}$ equation by $\frac{1}{{a}_{rs}}$ and for each $i=1,\mathrm{\dots},m$, $i\ne r$ replace equation $i$ by the sum of equation $i$ and the (replaced) equation $r$ multiplied by $-{a}_{is}$. Replace the equation for $z$ by the sum of the equation for $z$ and the (replaced) equation $r$ multiplied by $-{c}_{s}$. Note: The replacement operations of course change the coefficients ${a}_{ij}$ and ${c}_{j}$. 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 |