## You are here

Homesimplex algorithm

## Primary tabs

# 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},\ldots,x_{r}$ are basic variables in the following system of $r$ equations:

$\displaystyle x_{1}$ | $\displaystyle+$ | $\displaystyle a_{{1,r+1}}x_{{r+1}}+\cdots+a_{{1,n}}x_{n}=b_{1}$ | ||

$\displaystyle x_{2}$ | $\displaystyle+$ | $\displaystyle a_{{2,r+1}}x_{{r+1}}+\cdots+a_{{2,n}}x_{n}=b_{2}$ | ||

$\displaystyle\ldots$ | ||||

$\displaystyle x_{r}$ | $\displaystyle+$ | $\displaystyle a_{{r,r+1}}x_{{r+1}}+\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},\ldots,x_{m},-z$ and we seek to find nonnegative $x_{i}$ $i=1,\ldots,n$ such that $z$ is minimal. That is, we have

$\displaystyle x_{i}+\sum_{{j=m+1}}^{n}a_{{ij}}x_{j}$ | $\displaystyle=$ | $\displaystyle b_{i}\quad i=1,\ldots,m$ | ||

$\displaystyle-z+\sum_{{j=m+1}}^{n}c_{j}x_{j}$ | $\displaystyle=$ | $\displaystyle-z_{o}$ |

where $a_{{ij}},b_{j},c_{j},z_{o}$ are constants, and $b_{j}\geq 0,\quad j=1,\ldots,m$.

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

Step 1. Set $N=\{m+1,\ldots,n\}$ and $B=\{1,\ldots,m\}$. Put $c_{j}=0$ for $j\in B$.

Step 2. If there an index $j\in N$ such that $c_{j}<0$ then choose $s\in N$ such that

$c_{s}=\operatorname{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}}\leq 0$ for all $i$ then stop. The value of $z$
has no lower bound.
Else, let $\frac{b_{r}}{a_{{rs}}}=\operatorname{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,\ldots,m$, $i\neq 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.

## Mathematics Subject Classification

90C05*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff
- Corrections

## Comments

## cross-link to Nelder Mead

Maybe, one should add that the term "simplex algorithm" is also used to refer to the Nelder-Mead algorithm.

Simon

## Announced simplex algorithm object up for adoption

I've given up control of the simplex algorithm object. Hopefully now it can be adopted or transferred to someone who actually knows what this is talking about.