Linear optimization: Pivot selection rules 3
Linear Optimization: Pivot selection rules
Theory
Linear programming (LP, or linear optimization) is a mathematical method for determining a way to achieve the best outcome (such as maximum profit or lowest cost) in a given mathematical model for some list of requirements represented as linear relationships. Linear programming is a specific case of mathematical programming (mathematical optimization).
The pivot or pivot element is the element of a matrix, or an array, which is selected first by an algorithm (e.g. Gaussian elimination, simplex algorithm, etc.), to do certain calculations. In the case of matrix algorithms, a pivot entry is usually required to be at least distinct from zero, and often distant from it; in this case finding this element is called pivoting. Pivoting may be followed by an interchange of rows or columns to bring the pivot to a fixed position and allow the algorithm to proceed successfully, and possibly to reduce round-off error.
The pivot is the first element chosen by an algorithm to solve an optimization problem.
The basic idea of Gaussian elimination is to change the system of equations by a fixed solution set. The standard process to solve this system is to create an upper triangle matrix. So the bottom left corner is equal to zero, while the rest is filled with the coefficients. Now you can easily solve the system of equations from bottom-up. Now the last row is a simple equation with just one unknown. By putting the solution of the last row in the second last row you create another simple equation with just one unknown, and so on. By transferring the original matrix into an upper triangle matrix you usually start with the first coefficient in the left upper corner. This is the pivot element.
Presentation of the Problem
In some cases the system of equations is very hard to transfer in an upper triangle matrix, which is required for Gaussian elimination. If the coefficient is zero, the standard algorithm isn´t useful.
By solving the problem with computers the round-off error can be extremely high. The reason is the reduced decimal places of fraction numbers.
By using the pivot element in simplex-methods you have to be sure, that your solution is in the regular solution set.
Example
There is a graphical solution for linear optimization. In reality there are several hundred factors. So it is necessary to use an algorithm like the simplex – algorithm. The following tables describe the way to use.
There are three equations: 4x1+2x2+y1 = 400
2x1+2x2+y2 = 240
2x1+6x2+y3 = 480
Amount of coverage: 2x1+3x2 -> max!
And the non-negativ condition: X1 ≥ 0, X2 ≥ 0
|
X1 |
X2 |
Y1 |
Y2 |
Y3 |
DB |
RS |
|
4 |
2 |
1 |
0 |
0 |
0 |
400 |
|
2 |
2 |
0 |
1 |
0 |
0 |
240 |
|
2 |
6 |
0 |
0 |
1 |
0 |
480 |
|
-2 |
-3 |
0 |
0 |
0 |
1 |
0 |
The solution is ideal, if the last line doesn’t contain negative numbers.
The pivot column is the second one because of the highest negative number in the last line.
The pivot line is the third one because there is the smallest quotation x2/RS = 80.
So the pivot element is six.
It is necessary to create a unit vector in column two.
- Multiply the third line with 1/6
- -2 * third line + first line
- -2 * third line + second line
- 3 * third line + fourth line
|
X1 |
X2 |
Y1 |
Y2 |
Y3 |
DB |
RS |
|
10/3 |
0 |
1 |
0 |
-1/3 |
0 |
240 |
|
4/3 |
0 |
0 |
1 |
-1/3 |
0 |
80 |
|
1/3 |
1 |
0 |
0 |
-1/6 |
0 |
80 |
|
-1 |
0 |
0 |
0 |
1/2 |
1 |
240 |
The last line also contains a negative number. So it is necessary to repeat the process again.
The pivot column is the first one.
The pivot line is the second because of the smallest quotation x2/RS = 60
The pivot element is 4/3.
It is again necessary to create an unite vector in column one
- Multiply the second line with 3/4
- -10/3 * second line + first line
- -1/3 * second line + third line
- 1* second line + forth line
|
X1 |
X2 |
Y1 |
Y2 |
Y3 |
DB |
RS |
|
0 |
0 |
1 |
-5/2 |
1/2 |
0 |
40 |
|
1 |
0 |
0 |
3/4 |
-1/4 |
0 |
60 |
|
0 |
1 |
0 |
-1/4 |
1/4 |
0 |
60 |
|
0 |
0 |
0 |
3/4 |
1/4 |
1 |
300 |
In table three doesn’t exist negative numbers in the last line. So it is the optimum solution.
Detailed Solution process with explanation
The element aij(k-1) which is used for elimination is called pivot element. The k is used for number of the step; i represent the row and j the column. In the algorithm the pivot element is used to create a unit vector. Therefore it has to be different from zero.
To be sure, that the round-off error is reduced, it is useful to choose an element which is according to amount very high.
1.Column Pivot Selection: Choose in k-step the k-column. Now choose the maximal according to amount element in the column.
2.Row Pivot Selection: Choose in the k-step the k-row. Now chose the maximal according to amount element in the row.
3.Total Pivot Selection: Choose the maximal according element.
4.Diagonal Pivot Selection: Choose in the k-step the k-row and the k-column.
Be sure, that your pivot element isn´t used in previous steps.
Sources
http://en.wikipedia.org/wiki/Linear_programming
http://en.wikipedia.org/wiki/Pivot_element
http://de.wikipedia.org/wiki/Pivotelement
Produktionswirtschaft: Einführung in das industrielle Produktionsmanagement, Hans Corsten; Ralf Gössinger, 12.Auflage 2009
http://www.google.de/url?sa=t&rct=j&q=%22wir%20beginnen%20mit%20linearen%20gleichungssystemen%22&source=web&cd=2&ved=0CDQQFjAB&url=http%3A%2F%2Fwww.scai.fraunhofer.de%2Ffileadmin%2FArbeitsgruppeTrottenberg%2FSS07%2Fkap1.pdf&ei=opbNUYPCGeSl4AT4ooDIBQ&usg=AFQjCNGitebxJX7hJA4Ht3d3qTHktonK-g&bvm=bv.48572450,d.bGE&cad=rja (SCAI Fraunhofer, Arbeitsgruppe Trottenberg)
--aust (Diskussion) 18:22, 30. Jun. 2013 (CEST)
--brenz (Diskussion) 18:24, 30. Jun. 2013 (CEST)