Editing Simplex algorithm (section)

==Algorithm==
Let a linear program be given by a canonical tableau. The simplex algorithm proceeds by performing successive pivot operations each of which give an improved basic feasible solution; the choice of pivot element at each step is largely determined by the requirement that this pivot improves the solution.

===Entering variable selection===
Since the entering variable will, in general, increase from 0 to a positive number, the value of the objective function will decrease if the derivative of the objective function with respect to this variable is negative. Equivalently, the value of the objective function is increased if the pivot column is selected so that the corresponding entry in the objective row of the tableau is positive.

If there is more than one column so that the entry in the objective row is positive then the choice of which one to add to the set of basic variables is somewhat arbitrary and several ''entering variable choice rules''<ref name="Murty66">{{harvtxt|Murty|1983|p=66}}</ref> such as [[Devex algorithm]]<ref>Harris, Paula MJ. "Pivot selection methods of the Devex LP code." Mathematical programming 5.1 (1973): 1–28</ref> have been developed.

If all the entries in the objective row are less than or equal to 0 then no choice of entering variable can be made and the solution is in fact optimal. It is easily seen to be optimal since the objective row now corresponds to an equation of the form 
:<math display="block">z(\mathbf{x})=z_B+\text{non-positive terms corresponding to non-basic variables}</math>

By changing the entering variable choice rule so that it selects a column where the entry in the objective row is negative, the algorithm is changed so that it finds the minimum of the objective function rather than the maximum.

===Leaving variable selection===
Once the pivot column has been selected, the choice of pivot row is largely determined by the requirement that the resulting solution be feasible. First, only positive entries in the pivot column are considered since this guarantees that the value of the entering variable will be nonnegative. If there are no positive entries in the pivot column then the entering variable can take any non-negative value with the solution remaining feasible. In this case the objective function is unbounded below and there is no minimum.

Next, the pivot row must be selected so that all the other basic variables remain positive. A calculation shows that this occurs when the resulting value of the entering variable is at a minimum. In other words, if the pivot column is ''c'', then the pivot row ''r'' is chosen so that
:<math>b_r / a_{rc}\,</math>

is the minimum over all ''r'' so that ''a''<sub>''rc''</sub> > 0. This is called the ''minimum ratio test''.<ref name="Murty66"/> If there is more than one row for which the minimum is achieved then a ''dropping variable choice rule''<ref>{{harvtxt|Murty|1983|p=67}}</ref> can be used to make the determination.

===Example===
{{see also|Revised simplex algorithm#Numerical 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 &\le 10\\
  2 x + 5 y + 3 z &\le 15\\
  x,\,y,\,z &\ge 0
\end{align}</math>

With the addition of slack variables ''s'' and ''t'', this is represented by the canonical tableau
:<math>
  \begin{bmatrix}
    1 & 2 & 3 & 4 & 0 & 0 &  0 \\   
    0 & 3 & 2 & 1 & 1 & 0 & 10 \\
    0 & 2 & 5 & 3 & 0 & 1 & 15
  \end{bmatrix}
</math>

where columns 5 and 6 represent the basic variables ''s'' and ''t'' and the corresponding basic feasible solution is 
:<math>x=y=z=0,\,s=10,\,t=15.</math>

Columns 2, 3, and 4 can be selected as pivot columns, for this example column 4 is selected. The values of ''z'' resulting from the choice of rows 2 and 3 as pivot rows are 10/1&nbsp;=&nbsp;10 and 15/3&nbsp;=&nbsp;5 respectively. Of these the minimum is 5, so row 3 must be the pivot row. Performing the pivot produces
:<math>
  \begin{bmatrix}
    1 &            -\frac{2}{3} &             -\frac{11}{3} & 0 & 0 & -\frac{4}{3} & -20 \\   
    0 &  \frac{7}{3} &   \frac{1}{3} & 0 & 1 &  -\frac{1}{3} &  5 \\
    0 &  \frac{2}{3} &   \frac{5}{3} & 1 & 0 &  \frac{1}{3} & 5
  \end{bmatrix}
</math>

Now columns 4 and 5 represent the basic variables ''z'' and ''s'' and the corresponding basic feasible solution is 
:<math>x=y=t=0,\,z=5,\,s=5.</math>

For the next step, there are no positive entries in the objective row and in fact
:<math display="block">Z = -20 + \frac{2}{3}x+\frac{11}{3}y+\frac{4}{3}t</math>
so the minimum value of ''Z'' is&nbsp;&minus;20.