Editing Simplex algorithm (section)

==Simplex tableau==
A linear program in standard form can be represented as a ''tableau'' of the form 
:<math>
  \begin{bmatrix}
    1 & -\mathbf{c}^T & 0 \\
    \mathbf{0} & \mathbf{A} & \mathbf{b}
  \end{bmatrix}
</math>

The first row defines the objective function and the remaining rows specify the constraints. The zero in the first column represents the zero vector of the same dimension as the vector <math>\mathbf{b}</math> (different authors use different conventions as to the exact layout). If the columns of <math>\mathbf{A}</math> can be rearranged so that it contains the [[identity matrix]] of order <math>p</math> (the number of rows in <math>\mathbf{A}</math>) then the tableau is said to be in ''canonical form''.<ref>{{harvtxt|Murty|1983|loc=section 2.3.2}}</ref> The variables corresponding to the columns of the identity matrix are called ''basic variables'' while the remaining variables are called ''nonbasic'' or ''free variables''. If the values of the nonbasic variables are set to 0, then the values of the basic variables are easily obtained as entries in <math>\mathbf{b}</math> and this solution is a basic feasible solution. The algebraic interpretation here is that the coefficients of the linear equation represented by each row are either <math>0</math>, <math>1</math>, or some other number. Each row will have <math>1</math> column with value <math>1</math>, <math>p-1</math> columns with coefficients <math>0</math>, and the remaining columns with some other coefficients (these other variables represent our non-basic variables). By setting the values of the non-basic variables to zero we ensure in each row that the value of the variable represented by a <math>1</math> in its column is equal to the <math>b</math> value at that row.

Conversely, given a basic feasible solution, the columns corresponding to the nonzero variables can be expanded to a nonsingular matrix. If the corresponding tableau is multiplied by the inverse of this matrix then the result is a tableau in canonical form.<ref>{{harvtxt|Murty|1983|loc=section 3.12}}</ref>

Let 
:<math>
  \begin{bmatrix}
    1 & -\mathbf{c}^T_B & -\mathbf{c}^T_D & 0 \\
    0 & I & \mathbf{D} & \mathbf{b}
  \end{bmatrix}
</math>

be a tableau in canonical form. Additional [[Elementary matrix#Row-addition transformations|row-addition transformations]] can be applied to remove the coefficients {{SubSup|'''c'''|''B''|T|s=0}} from the objective function. This process is called ''pricing out'' and results in a canonical tableau
:<math>
  \begin{bmatrix}
    1 & 0 & -\bar{\mathbf{c}}^T_D & z_B \\
    0 & I & \mathbf{D} & \mathbf{b}
  \end{bmatrix}
</math>

where ''z''<sub>''B''</sub> is the value of the objective function at the corresponding basic feasible solution. The updated coefficients, also known as ''relative cost coefficients'', are the rates of change of the objective function with respect to the nonbasic variables.<ref name="NeringTucker" >
Evar D. Nering and [[Albert W. Tucker]], 1993, ''Linear Programs and Related Problems'', Academic Press. (elementary<!-- but profound -->)</ref>