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)

    “At all events, as she, Ulster, cannot have the status quo, nothing remains for her but complete union or the most extreme form of Home Rule; that is, separation from both England and Ireland.”
    —George Bernard Shaw (1856–1950)