Linear Programming - Augmented Form (slack Form)

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:
\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}
x, xs ≥ 0

where xs are the newly introduced slack variables, and Z is the variable to be maximized.

Read more about this topic:  Linear Programming

Famous quotes containing the words augmented and/or form:

    “Another success is the post-office, with its educating energy augmented by cheapness and guarded by a certain religious sentiment in mankind; so that the power of a wafer or a drop of wax or gluten to guard a letter, as it flies over sea over land and comes to its address as if a battalion of artillery brought it, I look upon as a fine meter of civilization.”
    —Ralph Waldo Emerson (1803–1882)

    “Touch me not.”
    —Bible: New Testament Jesus, in John, 20:17.

    Spoken to Mary Magdalene, after Jesus has risen from the dead and made himself known to her. The words are best known in the Latin form in which they appear in the Vulgate: Noli me tangere.