Augmented form (slack form)

Linear programming problems must be converted into augmented form before being solved by the simplex algorithm. This form introduces non-negative slack variables to replace inequalities with equalities in the constraints. The problem can then be written in the following block matrix form:

Maximize Z in:
  \begin{bmatrix}     1 & -\mathbf{c}^T & 0 \\     0 & \mathbf{A} & \mathbf{I}   \end{bmatrix}   \begin{bmatrix}     Z \\ \mathbf{x} \\ \mathbf{x}_s   \end{bmatrix} =    \begin{bmatrix}     0 \\ \mathbf{b}   \end{bmatrix}
 \mathbf{x}, \, \mathbf{x}_s \ge 0

where \mathbf{x}_s are the newly introduced slack variables, and Z is the variable to be maximized.

Example

The example above is converted into the following augmented form:

maximize  S_1 x_1 + S_2 x_2\, (objective function)
subject to  x_1 + x_2 + x_3 = A\, (augmented constraint)
 F_1 x_1 + F_2 x_2 + x_4 = F\, (augmented constraint)
 P_1 x_1 + P_2 x_2 + x_5 = P\, (augmented constraint)
 x_1,x_2,x_3,x_4,x_5 \ge 0

where x_3,x_4,x_5\, are (non-negative) slack variables, representing in this example the unused area, the amount of unused fertilizer, and the amount of unused insecticide.

In matrix form this becomes:

Maximize Z in:
  \begin{bmatrix}     1 & -S_1 & -S_2 & 0 & 0 & 0 \\     0 &   1    &   1    & 1 & 0 & 0 \\     0 &  F_1  &  F_2  & 0 & 1 & 0 \\     0 &  P_1    & P_2 & 0 & 0 & 1 \\   \end{bmatrix}   \begin{bmatrix}     Z \\ x_1 \\ x_2 \\ x_3 \\ x_4 \\ x_5   \end{bmatrix} =    \begin{bmatrix}     0 \\ A \\ F \\ P   \end{bmatrix}, \,   \begin{bmatrix}     x_1 \\ x_2 \\ x_3 \\ x_4 \\ x_5   \end{bmatrix} \ge 0.