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.