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)

    “When I was young my teachers were the old.
    I gave up fire for form till I was cold.”
    —Robert Frost (1874–1963)