Simplex-Algorithmen für parametrische lineare Optimierung

Simplex-Algorithmus für parametrische lineare Optimierung mit parametrischer rechter Seite (Sensitivitätsanalyse linearer Optimierungsprobleme)

Input Data: Lineares Optimierungsproblem mit rechter Seite (Bedingungsvektor + t*ß, ß ein beliebiger Vektor)

begin
Das um den Vektor ß erweiterte Anfangstableu wird mit t=0 aufgestellt. Der optimale Punkt wird für t=0 berechnet, wobei ß mittransformiert wird. Optimalitätsbereich für t berechnen.

while(zweite duale Stoppregel verletzt)

Führe dualen Austauschschritt für t = infimum und t = supremum aus, um somit alle Optimalitätsbereiche von t zu bestimmen. Bestimme einen optimalen Punkt in Abhängigkeit von t und den Bereich von t.

end

end

Output Data: Liste von Optimalitätsbereichen für alle t mit zugehörigen optimalen Punkten und optimalen Werten in Abhängigkeit von t

 

Simplex-Algorithmus für parametrische lineare Optimierung mit parametrischer Zielfunktionszeile (Sensitivitätsanalyse linearer Optimierungsprobleme)

Input Data: Parametrisches lineares Optimierungsproblem, parametrisierte Zielfunktion
begin
Das um einen Vektor erweiterte Anfangstableau wird für t=0 aufgestellt. Der hinzu”addierte” Vektor kommt in eine Zielfunktionszeile für sich – wird mit umgeformt aber nimmt auf die Auswahl des Pivotelements erstmal nicht Einfluss.
Berechne einen optimalen Punkt für t=0 und den dazugehörigen Optimalitätsbereich für t.
while(Stoppregel 2 verletzt)
Führe primalen Austauschschritt für t = infimum und t = supremum aus. Damit wird Schritt für Schritt der Optimalitätsbereich für t bestimmt.
Bestimme die optimale Punktmenge zu t=infimum und t=supremum als Verbindungsstrecke der berechneten Optimalpunkte.
end
end
Output Data: Liste von Optimalitätsbereichen für alle t mit zugehörigen optimalen Punkten und optimalen Werten.