Pivot

From Glossary

Jump to: navigation, search

This is the algebra associated with an iteration of Gauss-Jordan elimination, using the forward transformation. The tableaux for a pivot on element LaTeX: a(p,q) LaTeX: (\ne 0), which means nonbasic variable LaTeX: x_q enters the basis in exchange for basic variable LaTeX: x_p, are as follows:

Before pivot:

LaTeX: 
\begin{array}{ll|ll}
Basic & & \multicolumn{2}{c}{Nonbasic} \\
Var. & Level & x_j & x_q \\
\hline \hline
x_i & b_i & a(i,j) & a(i,q) \\
x_p & b_p & a(p,j) & a(p,q)^* \\
\hline \hline
obj & -z & d_j & d_q  \\
\hline \hline
\end{array}

After pivot:

LaTeX: 
\begin{array}{ll|lr}
Basic & & \multicolumn{2}{c}{Nonbasic} \\
Var. & Level & x_j & x_q \\
\hline \hline
x_i & b_i - b_p a(i,q)/a(p,q) & a(i,j) - a(i,q)a(p,j)/a(p,q) & -a(i,q)/a(p,q) \\
x_q & b_p/a(p,q) & a(p,j)/a(p,q) & 1/a(p,q) \\
\hline \hline
obj & -a - b_p d_q/a(p,q) & d_j - a(p,j)d_q/a(p,q) & -d_q/a(p,q) \\
\hline \hline
\end{array}


A pivot is primal degenerate if the associated basic solution LaTeX: (x) does not change (i.e., the nonbasic variable enters the basis, but its level remains at the same bound value, in which case no basic variable changes level). Similarly, the pivot is dual degenerate if the associated dual solution (i.e., pricing vector and reduced costs) does not change. For dealing with degenerate pivots, see Bland's rule and the TNP rule.


Views
Personal tools