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.

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