Content deleted Content added
→Linear-fractional programming: unwinding contorted sentence |
m General fixes and Typo fixing, typo(s) fixed: in it's → in its, For example → For example, (2) using AWB |
||
Line 48:
The second equation may be used to eliminate <math>x_1</math> 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
:<math> \begin{align}
x_2 + 2x_3 &\le 3\\
Line 63:
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 <math>z_1</math> is unrestricted then write
:<math>\begin{align}
&z_1 = z_1^+ - z_1^-\\
Line 85:
</math>
The first row defines the objective function and the remaining rows specify the constraints. (Note, different authors use different conventions as to the exact layout.) If the columns of A can be rearranged so that it contains the [[identity matrix]] of order ''p'' (the number of rows in A) then the tableau is said to be in ''canonical form''.<ref>{{harvtxt|Murty|1983|loc=section 2.3.2}}</ref> The variables corresponding to the columns of the identity matrix are called ''basic variables'' while the remaining variables are called ''nonbasic'' or ''free variables''. If the values of the nonbasic variables are set to 0, then the values of the basic variables are easily obtained as entries in ''b'' and this solution is a basic feasible solution. The algebraic interpretation here is that the coefficients of the linear equation represented by each row are either <math>0</math>, <math>1</math>, or some other number. Each row will have <math>1</math> column with value <math>1</math>, <math>p-1</math> columns with coefficients <math>0</math>, and the remaining columns with some other coefficients (these other variables represent our non-basic variables). By setting the values of the non-basic variables we ensure in each row that the value of the variable represented by a <math>1</math> in
Conversely, given a basic feasible solution, the columns corresponding to the nonzero variables can be expanded to a nonsingular matrix. If the corresponding tableau is multiplied by the inverse of this matrix then the result is a tableau in canonical form.<ref>{{harvtxt|Murty|1983|loc=section 3.12}}</ref>
Line 117:
Since the entering variable will, in general, increase from 0 to a positive number, the value of the objective function will decrease if the derivative of the objective function with respect to this variable is negative. Equivalently, the value of the objective function is decreased if the pivot column is selected so that the corresponding entry in the objective row of the tableau is positive.
If there is more than one column so that the entry in the objective row is positive then the choice of which one to add to the set of basic variables is somewhat arbitrary and several ''entering variable choice rules''<ref name="Murty66">{{harvtxt|Murty|1983|p=66}}</ref> such as [[Devex algorithm]]<ref>
If all the entries in the objective row are less than or equal to 0 then no choice of entering variable can be made and the solution is in fact optimal. It is easily seen to be optimal since the objective row now corresponds to an equation of the form
| |||