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

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s