simplex algorithm

The simplex algorithm is used as part of the simplexmethod (due to George B. Dantzig) to solve linear programming problems.The algorithm is applied to a linear programming problem thatis 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}$ basicvariable has a unit coefficient in the $i^{th}$ equation and zero coefficientin the other equations.

As an example $x_1,\mathrm{\dots },x_r$ are basic variables in the followingsystem 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 feasiblesolution 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 thenchoose $s\in N$ such that

$$c_s={\min }_{j\in N}{c}_j$$

elsestop. 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}}={\min }_{a_{is}>0}\frac{b_i}{a_{is}}$.If there is more than one choice for $r$ it does not matter which oneis 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$ bythe sum of the equation for $z$ and the (replaced) equation$r$ multiplied by $-c_s$. Note: The replacement operations of coursechange the coefficients $a_{ij}$ and $c_j$. As the algorithm proceedsit 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 finitenumber of steps; but if there is non-degeneracy at each iteration,the algorithm will terminate in a finite number of steps.