Parametrische Optimierung

Erläuterung an einem Beispiel

Parameter p als Primalwert

Das erste Simplex-Tableau zeigt die Ausgangslösung. Der Primalwert von y₄ beträgt 0. Mit Hilfe der gewöhnlichen Auswahlkriterien für das Pivot-Element und der anschließenden Umrechnung des Tableaus erhält man die erste Optimallösung, die im zweiten Tableau dargestellt ist.

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

Abb. 1: erstes Tableau

An diesem Tableau ist nun zu untersuchen, wie weit der Parameter p ansteigen darf, ohne dass sich eine Veränderung der Optimallösung ergibt. Dabei bilden die Leerlaufkapazitäten von y₂ und y₃ mögliche Restriktionen, weil diese durch die Vergrößerung des Parameters p ab einem bestimmten p negativ werden. In diesem Fall wird y₃ mit p=36 zuerst negativ und bildet somit die Restriktion, d.h. es würde gegen die Nichtnegativitätsbedingung verstoßen. Im zweiten Tableau findet sich also die Optimallösung für den Bereich 0 ≤ p ≤ 36.

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

Abb. 2: zweites Tableau

Die Auswahl des Pivot-Elementes erfolgt nun auf folgende Weise: Die Pivot-Zeile wird durch den Verstoß gegen die Nichtnegativitätsbedingung (hier y₃) bestimmt. Die Pivot-Spalte wird nach folgender Regel bestimmt: das Element mit dem absolut kleinsten Quotienten aus dem Zielfunktionskoeffizienten und dem negativen Element der Pivot-Zeile. (hier: Min(20/-6 = -3,33; 80/-1 = -80)).

Anschließend erfolgt eine normale Umrechnung des Simplex-Tableaus. Hieraus ergibt sich für y₂ die nächste Restriktion mit p=78, so daß im dritten Tableau die Optimallösung für 36 ≤ p ≤ 78 dargestellt ist. Die Auswahl des Pivot-Elementes erfolgt nach den oben dargestellten Regeln.

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

Abb. 3: drittes Tableau

Im vierten Tableau bildet die erste Zeile mit y1 die Restriktion. Bei p=82,4 wird hier die Nichtnegativitätsbedingung verletzt. Tableau vier stellt also die Optimallösung für 78 ≤ p ≤ 82,4 dar.

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

Abb. 4: viertes Tableau

Nach der letzten Iteration ist erkennbar, daß der Zielfunktionswert unabhängig von p 6320 beträgt. Es gibt für p>82,4 kein Element der rechten Seite, das negativ werden kann, daß heißt, im fünften Tableau ist die Optimallösung für p>82,4 dargestellt.

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

Abb. 5: fünftes Tableau

Die Veränderungen der Basis- und Nichtbasis-Variablen in Abhängigkeit von dem Parameter p sind in der beiliegenden Graphik veranschaulicht.

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

Abb. 6: graphische Verarnschaulichung der Lösung

Parameter q als Zielfunktionskoeffizient

Im zweiten Teil der Übungsaufgabe wird nun der Zielfunktionskoeffizient von x₁ durch den Parameter q (der von 0 bis -1000 laufen soll) ersetzt.

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

Abb. 7: erstes Tableau

In Tableau 1 ist zunächst die Ausgangslösung dargestellt (q=0). Mit Hilfe der bekannten Auswahlkriterien wird das Pivot-Element bestimmt und eine normale Simplex-Umrechnung durchgeführt, deren Ergebnis in Tableau 2 dargestellt ist.

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

Abb. 8: zweites Tableau

Dieses Tableau stellt aber noch keine Optimallösung dar, weil der Term q-160 immer negativ ist und somit ein negativer Zielfunktionskoeffizient vorhanden ist. Eine weitere Iteration (Pivot-Element wird nach den bekannten Kriterien ausgewählt) erhält man Tableau 3.

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

Abb. 9: drittes Tableau

In diesem dritten Tableau wird sichtbar, daß sowohl die beiden Zielfunktionskoeffizienten als auch der Zielfunktionswert von dem Parameter q abhängen. Wie weit darf also q fallen, ohne daß eine weitere Simplex-Iteration notwendig wird? Diese Frage ist äquivalent mit der Frage, wann einer der beiden Zielfunktionskoeffizienten durch q wieder negativ wird. Dies ist ab q=-800/3 (Spalte von y₃) der Fall. Daraus ist ersichtlich, daß im dritten Tableau die Optimallösung für 0 > q > -800/3 dargestellt ist. Anschließend bildet die Spalte, in der der Zielfunktionskoeffizient negativ würde, die Pivot-Spalte. Die Pivot-Zeile wird wie sonst über den kleinsten positiven Quotienten aus rechter Seite und Spaltenelement ermittelt.

Mit der entsprechenden Umrechnung erhält man das vierte Tableau. Der Zielfunktionskoeffizient der Spalte von y₂ wird bei q= -320 negativ, so daß diese Spalte die Restriktion bildet und zur Pivot-Spalte wird. Im Tableau ist also die Optimallösung für den Bereich -800/3 > q > -320 zu finden.

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

Abb. 10: viertes Tableau

Durch die letzte Iteration erhält man das fünfte Tableau. Beide Zielfunktionswerte sind so von q abhängig, daß sich immer positive Werte ergeben, d.h. q kann unbegrenzt fallen, ohne daß sich eine qualitative Änderung ergibt. Die Optimallösung ist damit für q < -320 im Tableau dargestellt. Zum Beispiel erhält man für q= -1000 einen Zielfunktionswert von 15.466,67.

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

Abb. 11: fünftes Tableau

Vorlesung/Lecture

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

Sensitivitätsanalyse und Parametrische Optimierung (English)