Editing Simplex algorithm (section)

==Finding an initial canonical tableau==
In general, a linear program will not be given in the canonical form and an equivalent canonical tableau must be found before the simplex algorithm can start. This can be accomplished by the introduction of ''artificial variables''. Columns of the identity matrix are added as column vectors for these variables. If the b value for a constraint equation is negative, the equation is negated before adding the identity matrix columns.  This does not change the set of feasible solutions or the optimal solution, and it ensures that the slack variables will constitute an initial feasible solution.  The new tableau is in canonical form but it is not equivalent to the original problem. So a new objective function, equal to the sum of the artificial variables, is introduced and the simplex algorithm is applied to find the minimum; the modified linear program is called the ''Phase&nbsp;I'' problem.<ref>{{harvtxt|Murty|1983|p=60}}</ref>

The simplex algorithm applied to the Phase I problem must terminate with a minimum value for the new objective function since, being the sum of nonnegative variables, its value is bounded below by 0. If the minimum is 0 then the artificial variables can be eliminated from the resulting canonical tableau producing a canonical tableau equivalent to the original problem. The simplex algorithm can then be applied to find the solution; this step is called ''Phase&nbsp;II''. If the minimum is positive then there is no feasible solution for the Phase I problem where the artificial variables are all zero. This implies that the feasible region for the original problem is empty, and so the original problem has no solution.<ref name="DantzigThapa1"/><ref name="NeringTucker"/><ref name="Padberg"/>

===Example===
Consider the linear program
:Minimize
::<math>Z = -2 x - 3 y - 4 z\,</math>

:Subject to
::<math>\begin{align}
 3 x + 2 y + z &= 10\\
 2 x + 5 y + 3 z &= 15\\
 x,\, y,\, z &\ge 0
\end{align}</math>

It differs from the previous example by having equality instead of inequality constraints. The previous solution <math>x=y=0\, , z=5</math> violates the first constraint. 
This new problem is represented by the (non-canonical) tableau
:<math>
  \begin{bmatrix}
    1 & 2 & 3 & 4 &  0 \\   
    0 & 3 & 2 & 1 & 10 \\
    0 & 2 & 5 & 3 & 15
  \end{bmatrix}
</math>

Introduce artificial variables ''u'' and ''v'' and objective function ''W''&nbsp;=&nbsp;''u''&nbsp;+&nbsp;''v'', giving a new tableau
:<math>
  \begin{bmatrix}
    1 & 0 & 0 & 0 & 0 & -1 & -1 &  0 \\  
    0 & 1 & 2 & 3 & 4 &  0 &  0 &  0 \\   
    0 & 0 & 3 & 2 & 1 &  1 &  0 & 10 \\
    0 & 0 & 2 & 5 & 3 &  0 &  1 & 15
  \end{bmatrix}
</math>

The equation defining the original objective function is retained in anticipation of Phase II.

By construction, ''u'' and ''v'' are both basic variables since they are part of the initial identity matrix. However, the objective function ''W'' currently assumes that ''u'' and ''v'' are both&nbsp;0. In order to adjust the objective function to be the correct value where ''u''&nbsp;=&nbsp;10 and ''v''&nbsp;=&nbsp;15, add the third and fourth rows to the first row giving
:<math>
  \begin{bmatrix}
    1 & 0 & 5 & 7 & 4 & 0 & 0 & 25 \\  
    0 & 1 & 2 & 3 & 4 & 0 & 0 &  0 \\   
    0 & 0 & 3 & 2 & 1 & 1 & 0 & 10 \\
    0 & 0 & 2 & 5 & 3 & 0 & 1 & 15
  \end{bmatrix}
</math>

Select column 5 as a pivot column, so the pivot row must be row 4, and the updated tableau is 
:<math>
  \begin{bmatrix}
    3 & 0 &  7 &   1 & 0 & 0 & -4 &   15 \\  
    0 & 3 & -2 & -11 & 0 & 0 & -4 & -60 \\   
    0 & 0 &  7 &   1 & 0 & 3 & -1 &   15 \\
    0 & 0 &  2 &   5 & 3 & 0 &  1 &   15
  \end{bmatrix}
</math>

Now select column 3 as a pivot column, for which row 3 must be the pivot row, to get
:<math>
  \begin{bmatrix}
    7 & 0 & 0 & 0 & 0 & -7 & -7 & 0 \\  
    0 & 7 & 0 & -25 & 0 &  2 & -10 & -130 \\   
    0 & 0 & 7 &   1 & 0 &  3 &  -1 &   15 \\
    0 & 0 & 0 & 11 & 7 & -2 &   3 &   25
  \end{bmatrix}
</math>

The artificial variables are now 0 and they may be dropped giving a canonical tableau equivalent to the original problem:
:<math>
  \begin{bmatrix}
    7 & 0 & -25 & 0 &  -130 \\   
    0 & 7 &   1 & 0 &    15 \\
    0 & 0 &  11 & 7 &    25 
  \end{bmatrix}
</math>

This is, fortuitously, already optimal and the optimum value for the original linear program is&nbsp;−130/7. This value is "worse" than -20 which is to be expected for a problem which is more constrained.