Editing Linear programming (section)

== Augmented form (slack form) ==
Linear programming problems can be converted into an ''augmented form'' in order to apply the common form of the [[simplex algorithm]]. This form introduces non-negative ''[[slack variable]]s'' to replace inequalities with equalities in the constraints. The problems can then be written in the following [[block matrix]] form:
: Maximize <math>z</math>:
: <math>
  \begin{bmatrix}
    1 & -\mathbf{c}^\mathsf{T} & 0 \\
    0 & \mathbf{A} & \mathbf{I}
  \end{bmatrix}
  \begin{bmatrix}
    z \\ \mathbf{x} \\ \mathbf{s}
  \end{bmatrix} =
  \begin{bmatrix}
    0 \\ \mathbf{b}
  \end{bmatrix}
</math>
:<math>\mathbf{x} \ge  0, \mathbf{s} \ge 0</math>
where <math>\mathbf{s}</math> are the newly introduced slack variables, <math>\mathbf{x}</math> are the decision variables, and <math>z</math> is the variable to be maximized.

=== Example ===
The example above is converted into the following augmented form:
:{|
|-
| colspan="2" | Maximize: <math>S_1\cdot x_1+S_2\cdot x_2</math>
| (objective function)
|-
| subject to:
| <math>x_1 + x_2 + x_3 = L</math>
| (augmented constraint)
|-
|
| <math>F_1\cdot x_1+F_2\cdot x_2 + x_4 = F</math>
| (augmented constraint)
|-
|
| <math>P_1\cdot x_1 + P_2\cdot x_2 + x_5 = P</math>
| (augmented constraint)
|-
|
| <math>x_1,x_2,x_3,x_4,x_5 \ge 0.</math>
|}
where <math>x_3, x_4, x_5</math> are (non-negative) slack variables, representing in this example the unused area, the amount of unused fertilizer, and the amount of unused pesticide.

In matrix form this becomes:
: Maximize <math>z</math>:
: <math display=block>
  \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 \\ L \\ F \\ P
  \end{bmatrix}, \,
  \begin{bmatrix}
    x_1 \\ x_2 \\ x_3 \\ x_4 \\ x_5
  \end{bmatrix} \ge 0.
</math>