Parametrische lineare Optimierung

Grundlage der parametrische Optimierung ist die Sensitivitätsanalyse. Bei dieser wird der Einfluss für kleine Störungen der Eingangsgrößen untersucht. Es wird also untersucht, wie sich beispielsweise der optimale Punkt x* mit dem Optimalwert z* bei einer kleinen Störung der Zielfunktion oder der rechten Seite verändert. Bei der parametrische linearen Optimierung werden nun aber zusätzlich auch Aussagen über große Änderungen der Eingangsdaten gemacht.

Grundlage der parametrische Optimierung ist die Sensitivitätsanalyse. Bei dieser wird der Einfluss für kleine Störungen der Eingangsgrößen untersucht. Es wird also untersucht, wie sich beispielsweise der optimale Punkt x* mit dem Optimalwert z* bei einer kleinen Störung der Zielfunktion oder der rechten Seite verändert. Bei der parametrische linearen Optimierung werden nun aber zusätzlich auch Aussagen über große Änderungen der Eingangsdaten gemacht.

Variation der rechten Seite

Soll die rechte Seite eine große Änderung wiederfahren, also variiert werden, dann steht die Eingangsgröße b im Mittelpunkt. Nachfolgend wird davon ausgegangen, dass nicht alle Einträge von b variiert werden, sondern lediglich nur ein Eintrag. Für diese eindimensionale Änderung addiert man zum Eintrag b einfach noch einen eindimensionalen Parameter mal einem konstanten Vektor hinzu. So ändert sich der Eintrag b2 beispielsweise in b2 + tß. Dabei ist der konstante Vektor ß letztendlich die Zahl, um die das b geändert werden soll (z.B. b2 + tß = 200 + 40t).

Damit ergibt sich ein vom eindimensionale Parameter t abhängiges lineares Optimierungsproblem der Form:

P(t): max cTx s.t. Ax ≤ b * tß, x ≥ 0
Sowie die optimale Menge, wie auch der optimale Wert sind von t abhängig. Weiter ist zu beachten, dass in Abhängigkeit von t mehrere und vor allem verschiedene Optimalitätsbereiche existieren, in denen der optimale Punkt eine feste Basis besitzt. Diese Bereiche lassen sich mit Hilfe eines erweiterten Simplex-Tableaus ermitteln. Statt einer rechten Seite, hat man nun nämlich zwei rechte Seiten. Neben der b-Spalte wird eine weitere Spalte, nämlich der ß-Spalte, ergänzt. Nun kann man das schon bekannte Simplex-Verfahren ausführen, in dem die zusätzliche ß-Spalte mit transformiert wird, ohne jedoch Einfluss auf die Auswahl des Pivotelements zu haben.

Variation der Zielfunktion

Die Änderung der Zielfunktion verläuft formal genau so wie die Variation der rechten Seite. Sprich c ist nun c(t) = c + tϒ Damit ergibt sich als neues Optimierungsproblem die Form:

P(t): max (c+ tϒ)Tx s.t. Ax ≤ b, x ≥ 0
Auch hier existieren wieder in Abhängigkeit von t verschiedene Optimalitätsbereiche. Und auch hier kann man diese wieder mit Hilfe des erweiterten Simplex-Tableaus ermitteln. Statt eine zusätzlich Spalte, hat man nun aber eine zusätzlich Zeile, nämlich eine zweite Zielfunktionszeile. Auch diese hat aber wiederum keinen Einfluss auf die Wahl des Pivotelements.