# Simplex algorithm

The simplex algorithm works as follows:

1. transform the LP to standard form as $\max c^Tx$, s.t. $Ax=b,x\ge 0$.
2. find an initial feasible solution
3. repeat until all coefficients of variable in cost are $\le 0$.
1. choose an entering variable whose coefficient is positive in the objective function
2. determine the leaving variable
3. rewrite the equations

Example: $\max z=5x_1+4x_2+3x_3$ s.t.

\begin{aligned} 2x_1+3x_2+x_3 & \le 5\\ 4x_1+x_2+2x_3 & \le 11\\ 3x_1+4x_2+2x_3 & \le 8\\ x_1,x_2,x_3 & \ge 0 \end{aligned}

Step 1: add slack variables to make the constrains standard:

\begin{aligned} 2x_1+3x_2+x_3+x_4 & = 5\\ 4x_1+x_2+2x_3+x_5 & = 11\\ 3x_1+4x_2+2x_3+x_6 &= 8\\ x_1,x_2,x_3,x_4,x_5,x_6 &\ge 0 \end{aligned}

Step 2: find initial solution $x=(0,0,0,5,11,8)$. The objective function $z=0$.

Step 3: iterate:

1. choose $x_1$ as the entering variable. Rewrite the constrains as follows: \begin{aligned} x_4&=5-2x_1-3x_2-x_3,\qquad x_1\le\frac{5}{2}\\ x_5&=11-4x_1-x_2-2x_3,\qquad x_1\le\frac{11}{4} \\ x_6&=8-3x_1-4x_2-2x_3,\qquad x_1\le \frac{8}{3}\end{aligned}. So the maximum value $x_1$ can increase is $\frac{5}{2}$ and $x_4$ is the leaving variable. Rewrite the constrains as        \begin{aligned} x_1&=\frac{5}{2}-\frac{3}{2}x_2-\frac{1}{2}x_3-\frac{1}{2}x_4\\ x_5&=1+5x_2+2x_4\\ x_6&=\frac{1}{2}+\frac{1}{2}x_2-\frac{1}{2}x_3+\frac{3}{2}x_4 \end{aligned}. The objective function $z=\frac{25}{2}-\frac{7}{2}x_2+\frac{1}{2}x_3-\frac{5}{2}x_4$.
2. choose $x_3$ as the entering variable. From first and third constrains we get $x_3\le 5$ and $x_3\le 1$. So the maximum value $x_3$ can increase is 1 and $x_6$ is the leaving variable. Rewrite the constrains as \begin{aligned} x_1 &= 2-2x_2-2x_4+x_6\\ x_3 &= 1+x_2+3x_4-2x_6\\ x_5 &= 1+5x_2+2x_4\end{aligned}. The objective function $z=13-3x_2-x_4-x_6$. Since the coefficients are negative, the optimal value is 13 and $x_1=2, x_2=0, x_3=1$.

Sometimes the initial solution cannot be found by setting the variables to zero. Consider the following constrains:

\begin{aligned} x_1+x_2 &\ge 1\\ 2x_1-x_2 &\ge 1\\ x_1,x_2 &\ge 0 \end{aligned}

After adding slack variables, they become

\begin{aligned} x_1+x_2-x_3 &= 1\\ 2x_1-x_2-x_4 &= 1\\ x_1,x_2,x_3,x_4 &\ge 0 \end{aligned}

However we cannot set $x_1=x_2=0$ because $x_3, x_4$ should be nonnegative. So we add yet another two artificial variables $y_1,y_2$ to construct another LP: $\min y_1+y_2$ s.t.

\begin{aligned} x_1+x_2-x_3+y_1 &= 1\\ 2x_1-x_2-x_4+y_2 &= 1\\ x_1,x_2,x_3,x_4,y_1,y_2 &\ge 0 \end{aligned}

If the original LP is feasible, then $\min y_1+y_2=0$ and we also get an initial feasible solution. If $\min y_1+y_2>0$, then original LP is not feasible.

So the general Simplex Algorithm consists of two phases:

1. Phase I: minimize the sum of artificial variables using the algorithm described above
2. if the minimum is not zero, LP is not feasible, otherwise
3. Phase II: solve the LP using the initial feasible solution found in Phase I