Detached coefficient form

From Glossary

Jump to: navigation, search

Given the system LaTeX: Ax=b, we augment the objective equation: LaTeX: c^{T}x - z = 0. Then, detaching the variables, the form is:

LaTeX: \left[ \begin{array}{rrr}
A & 0 & b \\ c & {-1} & 0
\end{array} \right].

Upon multiplying LaTeX: Ax = b by the inverse of a basis, say LaTeX: B, where LaTeX: A=[B \; N], the detached coefficient form becomes

LaTeX: \left[
I & B^{-1}N & 0 & B^{-1}b \\
c_B & c_N & -1 & 0 
\end{array} \right],

where LaTeX: c=[c_{B} \; c_{N}] (conformal with the partition of the columns of LaTeX: A). Now if we subtract LaTeX: c_B times the first LaTeX: m rows from the last row, this becomes

LaTeX: \left[
I & B^{-1}N & 0 & B^{-1}b \\
0 & c_N - c_B B^{-1}N & -1 & -c_B B^{-1} b
\end{array} \right]

Recognizing that LaTeX: B^{-1}b is the vector of basic levels, and the associated objective value LaTeX: (z) is LaTeX: c_B B^{-1}b, we can drop the first LaTeX: m columns plus column LaTeX: n+1 (corresponding to LaTeX: z) and form the tableau associated with this basis (adding labels to identify the basic variables in the rows and nonbasic variables in the columns).

Personal tools