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 SimplexAlgorithm 2013-03-22 13:35:21 2013-03-22 13:35:21 Mathprof (13753) Mathprof (13753) 22 Mathprof (13753) Algorithm msc 90C05 simplex method