Linear optimization: Pivot selection rules 2

Introduction

During the 1940`s George Dantzig discovered that many practical restriction problems can be solved by linear programming. He differed the problem in an objective function and restrictions.
Later, during the 1990`s John Forrest and Donald Goldfarb achieved great progress in solving simplex algorithms by introducing the pivot selection rules.

Example

An organization produces two products: A, B with three different machines: X, Y, Z.
The proceeds of the sale are about 2000 MU (monetary units) per unit and causes direct costs of 1400 MU per unit. Product B generates benefits of 6000 MU per unit and creates direct costs of 5000 MU per unit.
The fixed costs of the production are about 72000 MU each month.
Machine X has a maximal capacity of 340 manufacturing hours per month, machine Y has a capacity about 300 manufacturing hours and machine Z is able to run 360 hours per month.
To fabricate product A, the machines X and Y both need two hours per unit. To build up product B machine X runs four hours, machine Y two hours and machine Z is used six hours per unit.

The objective function describes the aim of the optimization: we want to maximize the proceed less the costs per unit, so we try to find the point, at which the fixed costs are egalised.

e_j: proceed per unit

k_j: costs per unit

x_A: units of product A

x_B: units of product B

Objective function

Max DB = ∑_j (( e_j– k_j ) x_j ) - k_f = (2000 MU – 1400 MU) x_A + (6000 MU - 5000 MU) x_B = 600 x_A + 1000 x_B = 72000

Restrictions

2x_A + 4x_B ≤ 340

bzw. y₁ + 2x_A + 4x_B = 340

2x_A + 2x_B ≤ 300

bzw. y₂ + 2x_A + 2x_B = 300

6x_B ≤ 360

bzw. y₃ + 6x_B = 360

Summary of the algorithm

1. Selection of the pivot column: selection of the restriction variable which should be transformed

   • STEEPEST-UNIT-ASCENT: column including the absolute highest negative coefficient of the objective function
   • GREATEST-CHANGE: column including the absolute highest product of the most negative coefficient of the objective function and the lowest positive quotient of the right side and the element of the appropriate column

2. Selection of the pivot row: selection of the row including the smallest positive quotient of right side and the element of the pivot column
3. Pivot element: intersection of pivot row and pivot column
4. Exchange of non-basis-variable and basis-variable
5. Solving the simplex table by using calculation rules
6. Repeat step 1, if solution is not the optimum.

Calculation rules for simplex-tables

Pivot-element: a_rs^* = 1/a_rs

Pivot-row: a_rj^* = a_rj/a_rs

Pivot-column: a_is^* = - a_is/a_rs

Remaining elements: a_ij^* = a_ij - a_rj*a_is/a_rs =a_ij - a_is a_rj^*

Calculation

Variables without star indicate the old matrix-elements before the translation, variables with star indicate elements after the translation.
We have the following simplex table in our example:

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

Image 1: origin table

The simplex table shows the mathematical equations of our example. For example the second row means: y₁ + 2x₁ + 4x₂ = 340..

Selection of pivot-column by using Steepest-Unit-Ascent

By using the Steepest-Unit-Ascent the column including the absolute greatest negative coefficient of the objective function is pivot column you have to select. By using this selection method those non-basis-variable, which makes the earning of the greatest profit possible get in the basis; in our example the column x₂ including –1000. The pivot row is the row with the smallest non negative quotient of the elements of the right side and the elements of the pivot column. In our example is the quotient of the first row is: 340/4 = 85, for the second row it is: 300/2 = 150 and for the third row: 360/6 = 60. So the pivot row is the last row. Therefore the pivot element is the intersection of pivot row and pivot column.

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

Image 2: selection of the pivot-element

At the beginning we exchange the non-basis-variable and the basis-variable of the pivot element. In our example we exchange xB and y3. The new pivot element is the inverse of the old element: 1/6. The new pivot column is calculated by dividing the old column element by the pivot element with exchanged signature. In the second row: –2/6=-1/3, in the first column: –4/6=-2/3, in the row of the objective function: –1000/6=-500/3. The new pivot row is calculated by dividing the old row element by the pivot element. In the first column: 0/6=0, in the last column (right side): 360/6=60.

Therefore the new table looks like this:

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

Image 3: Iteration step 1.1

During the next step, you calculate the rest of the elements by subtracting the old element from the previous element of the column. Then you have to multiply the result by the new element of the row. It could be helpful to note the elements at the edge of the table.

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

Image 4: Iteration step 1.2

We calculate for the first column and the row of the objective function the new value: -600 - (-1000*0) = -600. For the last column (right side) and the row of the objective function, we calculate: -72000 - (-1000 * 60) = -12000. For the first row and the first column: 2 - (0*4) = 2; and so on.

Now we are at the end of our first iteration. Since the table still has negative coefficients in our objective function, we haven`t found the optimal solution so far and we have to repeat step one of the simplex - iteration. The conversion has to be executed like before.

Therefore we get the following table:

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

Image 5: Iteration step 2 and 3

This table shows the optimal solution, because we have only positive coefficients in our objective function. Furthermore the solution is admissible, since the values of the right side have also only positive prefixes. It is possible to interpret the optimal solution as follows: The basic variables are: z = 26000, x_A= 130, x_B = 20 und y₃ = 240. That means that we produce 130 units of product A and 20 units of product B. By using this production program we achieve the maximum of product profitability: 26000 MU. Machine 3 has a not used capacity of 240 hours. The non - basis - variables y1 and y2 get the value zero. The whole capacity of machine 1 and 2 is used. So the two machines are a shortage restrictions.

Selection of the pivot column by using Greatest Change

By using Greatest Change the column including the absolute greatest product of negative objective function coefficient and the smallest positive quotient of the right side and the element of the appropriate column is the pivot column you have to select. By this way of selection, the non - basis - variables which generate the highest profit get in the basis.

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

Image 6: Selection of the pivot element

To select the pivot column you calculate for each element the quotient of element of the right side and the element of the appropriate row. So we get for the first row and first column: 340/2 = 170; for the first row and second column: 340/4 =85; for the second row and the first column: 300/2 = 150 and so on. The appropriate values are displayed in the table as exponents. Now we calculate for each column the product of the smallest „exponent“ and coefficient of the objective function. The column including the greatest product is now selected as pivot column. For the first column: 150 * l-600l = 90000; for the second column: 60 * l-1000l = 60000. So you choose the first column and raise the profit to 18000 MU. As known, we select now the row of the smallest non negative quotient of the elements of the right side and the elements of the pivot column as pivot row. In our example: the second row. The pivot element is the intersection of the first column and the second row. Now we go on as explained in the Steepest - Unit - Ascent.

Therefore we have the following tables:

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

Image 7: Iteration step 1

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

Image 8: Iteration step 2

This table shows the optimal solution. With Greatest - Change we can achieve the optimal solution in many cases much faster. The interpretation of the table is the same as the optimal solution of Steepest - Unit - Ascent.

A brief solution with simplex iteration

1. Selection of the Pivot element
2. Calculating the Pivot row
3. Calculating the Pivot column
4. Calculating the remaining element
5. calculation rules for simplex-tables

References

Müller-Merbach (1973): Operations Research, Kapitel 4.1 - 4.2.7

https://bisor.wiwi.uni-kl.de/orwiki/index.php?title=Einf%C3%BChrung_in_den_Simplex-Algorithmus