Simplex algorithm: Difference between revisions

Revision as of 12:38, 28 November 2014

Revision as of 15:25, 2 December 2014

Line 38:

:<math>x_1 \ge 5</math>

a new variable, ''y''<submath>1y_1</submath>, is introduced with

:<math> \begin{align} y_1 = x_1 - 5\\x_1 = y_1 + 5 \end{align}</math>

The second equation may be used to eliminate ''x''<submath>1x_1</submath> 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

Line 58:

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 {{anchor|Surplus variable}}''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 ''z''<submath>1z_1</submath> is unrestricted then write

:<math>\begin{align}

&z_1 = z_1^+ - z_1^-\\

Line 64:

\end{align}</math>

The equation may be used to eliminate ''z''<submath>1z_1</submath> from the linear program.

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

:<math>\mathbf{A}\mathbf{x} = \mathbf{b},\, x_i \ge 0</math>

It is also useful to assume that the rank of '''<math>\mathbf{A'''}</math> is the number of rows. This results in no loss of generality since otherwise either the system '''Ax'''&nbsp;<math>=&nbsp;'''\mathbf{A}\mathbf{x} \ge \mathbf{b'''}</math> has redundant equations which can be dropped, or the system is inconsistent and the linear program has no solution.<ref>{{harvtxt|Murty|1983|p=173}}</ref>

==Simplex tableaux==