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:         4x₁+2x₂+y₁ = 400

2x₁+2x₂+y₂ = 240

2x₁+6x₂+y₃ = 480

Amount of coverage:                   2x₁+3x₂ -> max!

And the non-negativ condition:  X₁ ≥ 0, X₂ ≥ 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 x₂/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

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 x₂/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

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 a_ij^(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)