Linear optimization: Pivot selection rules 1
Inhaltsverzeichnis
Theory
The Pivotelement is a specific element in the Simplex-Tableau. To find an optimal solution for linear problems this kind of tableaus can be used. While a linear problem is given the Simplex-Tableau helps to determine unknown variables with the objective of maximizing a preexisting function f. For solving this problem the tableau is renewed based on the Pivotelement as long as the solution is not optimal.
Example
There are three inequalities with three unknown variables x1, x2 and x3:
(1) x1 + x2 ≤ 18
(2) 2*x1 + x2 ≤ 26
(3) x1 + x2 + x3 ≤ 12
If you transfer them into a Simplextableau it looks as follows :
Solution
Now the question arises how the Pivotelement should be chosen. There are four criteria which the Pivotelement has to confirm.
(1) The Pivotelement must be in a column with a negative value in their first row.
(2) If there is more than one column which fits criterion (1) you can choose any of them.
(3) The Pivotelement has to be higher than zero.
(4) If there are several elements higher than zero the element with the lowest quotient by dividing the different elements by the elements in their particular output-column has to be choosen.
Referred to our example there could be a Pivot in column 1 because there is a negative element in its first row. You have to determine the different quotients because there several elements higher than zero in this column :
18/1 = 18
26/2 = 13
12/1 = 12 -> lowest quotient -> 1 is the Pivotelement
If the first row only consists of positive elements the solution is optimal and you don’t have to find any Pivotelement.
