Simplex Algorithm - Standard Form

Standard Form

The transformation of a linear program to one in standard form may be accomplished as follows. First, for each variable with a lower bound other than 0, a new variable is introduced representing the difference between the variable and bound. The original variable can then be eliminated by substitution. For example, given the constraint

a new variable, y1, is introduced with

\begin{align} y_1 = x_1 - 5\\ x_1 = y_1 + 5 \end{align}

The second equation may be used to eliminate x1 from the linear program. In this way, all lower bound constraints may be changed to non-negativity restrictions.

Second, for each remaining inequality constraint, a new variable, called a slack variable, is introduced to change the constraint to an equality constraint. This variable represents the difference between the two sides of the inequality and is assumed to be nonnegative. For example the inequalities

\begin{align} x_2 + 2x_3 &\le 3\\ -x_4 + 3x_5 &\ge 2 \end{align}

are replaced with

\begin{align} x_2 + 2x_3 + s_1 &= 3\\ -x_4 + 3x_5 - s_2 &= 2\\ s_1,\, s_2 &\ge 0 \end{align}

It is much easier to perform algebraic manipulation on inequalities in this form. In inequalities where ≥ appears such as the second one, some authors refer to the variable introduced as a surplus variable.

Third, each unrestricted variable is eliminated from the linear program. This can be done in two ways, one is by solving for the variable in one of the equations in which it appears and then eliminating the variable by substitution. The other is to replace the variable with the difference of two restricted variables. For example if z1 is unrestricted then write

\begin{align} &z_1 = z_1^+ - z_1^-\\ &z_1^+,\, z_1^- \ge 0 \end{align}

The equation may be used to eliminate z1 from the linear program.

When this process is complete the feasible region will be in the form

It is also useful to assume that the rank of A is the number of rows. This results in no loss of generality since otherwise either the system Ax >= b has redundant equations which can be dropped, or the system is inconsistent and the linear program has no solution.

Read more about this topic:  Simplex Algorithm

Famous quotes containing the words standard and/or form:

    “Gentlemen, those confederate flags and our national standard are what has made this union great. In what other country could a man who fought against you be permitted to serve as judge over you, be permitted to run for reelection and bespeak your suffrage on Tuesday next at the poles.”
    —Laurence Stallings (1894–1968)

    “The form of act or thought mattered nothing. The hymns of David, the plays of Shakespeare, the metaphysics of Descartes, the crimes of Borgia, the virtues of Antonine, the atheism of yesterday and the materialism of to-day, were all emanation of divine thought, doing their appointed work. It was the duty of the church to deal with them all, not as though they existed through a power hostile to the deity, but as instruments of the deity to work out his unrevealed ends.”
    —Henry Brooks Adams (1838–1918)