Unter- und Obergrenzen

m Zusammenhang mit dem Simplex-Algorithmus können in einigen Fällen Untergrenzen der Form x_j ≥ l_j einzelner Variablen oder Obergrenzen der Form x_j ≤ u_j einzelner Variablen auftreten. Diese kann man als zusätzliche Restriktionen, was relativ aufwändig ist, oder durch Koordinatentransformation/-verschiebung behandeln.

Untergrenzen

Treten Untergrenzen der Form x_j ≥ l_j auf, so werden diese vor der Umrechnung des Tableaus durch Koordinatenverschiebung berücksichtigt. Dazu wird die Variable x_j durch die Gegenvariable x_j’ = x_j – l_j ersetzt und die Bedingung x_j ≥ l_j wird zur Nichtnegativitätsbedingung x_j’ ≥ 0.

Für die restlichen Gleichungen (Restriktionen und Zielfunktion) treten durch die Transformation ebenfalls Änderungen auf.

Vor Transformation

y_i + ∑_j a_ij x_j= b_i

Nach Transformation

y_i + ∑_j a_ij (x_j’ + l_j) = b_i</br>

y_i + ∑_j a_ij x_j’ = b_i - ∑_j a_ij l_j

Wie aus obiger Gleichung ersichtlich, treten nur Änderungen für die rechte Seite des Tableaus auf. Die Variable b_i wird duch b_i’ = b_i - ∑_j a_ij l_j ersetzt.

Zur Bestimmung der Optimallösung verwendet man die bekannten Rechenreglen für Phase 2 des Simplex-Algorithmus.

Nach der Bestimmung der Optimallösung muss die Koordinatentransformation Rückgängig gemacht werden, um die Werte der ursprünglichen Variablen zu ermitteln. Dies geschieht nach der Formel x_j = x_j’ + l_j.

Obergrenzen

Treten Obergrenzen der Form x_j ≤ u_j auf, so werden diese durch Koordinatentransformation während der Umrechnung des Tableaus berücksichtigt. Eine Obergrenze bildet mit der Nichtnegativitätsbedingung einen Korridor im zulässigen Lösungsbereich, der dann durch zwei parallele Geraden begrenzt ist. Sobald eine Variable x_j bzw. y_i die Obergrenze überschreitet, wird sie durch ihre Gegenvariable x_j‾ = u_j - x_j bzw. y_i‾ = u_j *- y_i ersetzt. Für die Grenzen gilt dann nach der Transformation x_j‾ ≤ u_j und x_j‾ ≥ 0 bzw. y_i‾ ≤ u_i* und y_i‾ ≥ 0

Auch bei der Behandlung von Obergrenzen treten Änderungen der restlichen Gleichungen auf. Im Gegensatz zu den Untergrenzen muss aber unterschieden werden, ob eine Basisvariable oder eine Nichtbasisvariable ersetzt wird.

• Ersetzen einer Nichtbasisvariable in Spalte j:

Die Variable b_i der rechten Seite wird durch b_i‾ = b_i - a_ij u_j ersetzt und das Vorzeichen der Elemente der Spalte j wird getauscht.

• Ersetzen einer Basisvariable in Zeile i

Die Variable b_i der rechten Seite wird durch b_i‾ = u_i* - b_i ersetzt und das Vorzeichen der Elemente der Zeile i wird getauscht.

Auch bei den Rechenregeln für Simplex-Tableaus treten Änderungen auf. Die Pivot-Spalte wird wie gewohnt gewählt.</br> Zur Auswahl der Pivot-Zeile müssen die folgenden 3 Kriterien geprüft werden:

Q₁ = min ( b_i/a_is ) ∀ a_is > 0 (wie bisher)

Q₂ = min ( (b_i - u_i*)/ a_is) ∀ a_is < 0

Q₃ = u_s

Je nachdem, welcher der drei Werte am kleinsten ist, werden unterschiedliche Operationen durchgeführt.

• Ist Q₁ am kleinsten, führt man eine normale Simplex-Iteration nach den bekannten Regeln durch.</br>

• Ist Q₂ am kleinsten, muss die Basisvariable der Pivot-Zeile nach den oben beschriebenen Regeln ersetzt werden. Dann führt man eine normale Simplex-Iteration durch.</br>

• Ist Q₃ am kleinsten, muss die Nichtbasisvariable der Pivot-Spalte nach den oben beschriebenen Regeln ersetzt werden. Es wird keine Simplex-Iteration durchgeführt.

Nach der Bestimmung der Optimallösung muss die Koordinatentransformation Rückgängig gemacht werden, um die Werte der ursprünglichen Variablen zu ermitteln. Dies geschieht nach der Formel x_j = u_j - x_j‾.

Unter- und Obergrenzen

Treten Unter- und Obergrenzen auf, so werden die Untergrenzen wie oben beschrieben vor der Optimierungsrechnung und die Obergrenzen wie oben beschrieben während der Optimierungsrechnung jeweils durch Koordinatentransformation berücksichtigt.

Nach der Bestimmung der Optimallösung muss die Koordinatentransformation Rückgängig gemacht werden, um die Werte der ursprünglichen Variablen zu ermitteln. Dies geschieht in zwei Schritten nach den Formeln x_j’ = u_j - x_j’‾ und x_j = x_j’ + l_j.

Beispiel:

Folgendes Simplex-Problem soll unter der Berücksichtigung der unteren Grenzen

x₁ ≥ 4, x₂ ≥ 5 und x₃ ≥ 7

sowie der oberen Grenzen

x₁ ≤ 8, x₂ ≤ 7 und x₃ ≤ 15

gelöst werden.

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

Abb. 1

Im ersten Schritt trägt man die Untergrenzen in die Zeile LB und die Obergrenzen abzüglich der Untergrenzen in die Zeile UB`. Dann beginnt man mit der Koordinatentransformation zur Berücksichtigung der Untergrenzen, indem man die Nichtbasisvariablen x_j duch ihre entsprechenden Gegenvariablen x_j’ ersetzt und die Werte der rechten Seite nach der Formel b_i’ = b_i - ∑_j a_ij l_j umrechnet. Für die Zeile y₀ beträgt b₀’ zum Beispiel b₀’= 0 - (-20*7) – (-26*5) – (-36*4) = 414. Für die Zeile y₁ gilt entsprechend b₁’ = 122- (3*7) - (6*5) – (5*4) = 51 Für die Zeilen y₂ und y₃ folgt entsprechend b₂’ = 58 und b₃’= 84.

Nach der Koordinatentransformation folgt für das Simplex-Tableau also

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

Abb. 2

Im nächsten Schritt bestimmt man die Pivot-Spalte nach den bekannten Kriterien, in diesem Fall also die Spalte x₁´ = -36. Nun werden für diese Spalte die drei Kriterien zur Auswahl der Pivot-Zeile überprüft.

Q₁ = min ( b_i/a_is )= min (51/5; 58/7; 84/10) =min (10,2; 8,29; 8,4) = 8,29

Q₂ = min ( (b_i - u_i*)/ a_is) = min (∞; ∞; ∞;) = ∞

Q₃ = u_s = 4

Das Minimum von Q₁, Q₂ und Q₃ liegt also bei Q₃. Nach den oben beschriebenen Regeln wird in diesem Fall also eine Koordinatentransformation der Nichtbasisvariable der Pivot-Spalte durchgeführt, die rechte Seite nach der Formel b_i‾ = b_i - a_ij l_j umgerechnet und das Vorzeichen der Elemente der Spalte 1 getauscht.

Aus x₁’ wird also x₁’‾, aus b_o’ = 414 wird b_o’‾ = 414 – (-36*4) = 558, aus b₁’ = 51 wird b₁’‾ = 51 – (5*4) = 31. Für die restlichen Zeilen erfolgt die Umrechnung entsprechend.

Da eine Nichtbasisvariable transformiert wurde, erfolgt keine Simplex-Iteration.

Somit gilt für das Simplex-Tableau

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

Abb. 3

Da die Optimallösung noch nicht erreicht ist, wählt man als nächste Pivot-Spalte die Spalte x₂’ = -26 und überprüft wieder die Kriterien zur Auswahl der Pivot-Zeile.

Q₁ = min (31/6; 30/5; 44/8) = min (5,17; 6; 5,5) = 5,5

Q₂ = min (∞; ∞; ∞;) = ∞

Q₃ = u_s = 2

Das Minimum von Q₁, Q₂ und Q₃ liegt also wieder bei Q₃. Es wird wieder eine Koordinatentransformation der Nichtbasisvariable der Pivot-Spalte durchgeführt, die rechte Seite nach der Formel b_i‾ = b_i - a_ij l_j umgerechnet und das Vorzeichen der Elemente der Spalte 2 getauscht.

Aus x₂’ wird also x₂’‾, aus b_o = 558 wird b_o’‾ = 558 – (-26*2) = 610, aus b₁’ = 31 wird b₁’‾ = 31 – (6*2) = 19. Für die restlichen Zeilen erfolgt die Umrechnung entsprechend.

Da eine Nichtbasisvariable transformiert wurde, erfolgt keine Simplex-Iteration.

Somit gilt für das Simplex-Tableau

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

Abb. 4

Da die Optimallösung noch nicht erreicht ist, wählt man als nächste Pivot-Spalte die Spalte x₃’ = -20 und überprüft wieder die Kriterien zur Auswahl der Pivot-Zeile.

Q₁ = min (19/3; 20/4; 28/5) = min (6,33; 5; 5,6) = 5

Q₂ = min (∞; ∞; ∞;) = ∞

Q₃ = u_s = 8

Das Minimum von Q₁, Q₂ und Q₃ liegt also bei Q₁. In diesem Fall wird eine Simplex-Iteration mit Spalte x₃ als Pivot-Spalte und Zeile y₂ als Pivot-Zeile ( Minimum von Q₁ in Zeile y₂) nach den Rechenreglen für Phase 2 durchgeführt.

Somit folgt für das Simplex-Tableau

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

Abb. 5

Dieses Tableau stellt die Optimallösung dar. Nun müssen noch die Koordinatentransformationen Rückgängig gemacht werden.

x₁’‾ = 0 ⇒ x₁ = l₁ + u₁* = 4 + 4= 8

x₂’‾ = 0 ⇒ x₂ = l₂ + u₂* = 5 + 2= 7

x₃’ = 5 ⇒ x₃ = l₃ + 5 = 7 + 5= 12

y₀ = 710

y₁ = 4
y₂ = 0
y₃ = 3

Literatur

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

Vorlesung/Lecture

Sie können Sich zu diesem Themengebiet eine Vorlesung ansehen.

Unter- und Obergrenzen (English)