Glossar · approach

Robuste Optimierung

Mathematischer Optimierungsansatz, der unsichere Parameter durch eine Unsicherheitsmenge statt durch eine Wahrscheinlichkeitsverteilung modelliert und Lösungen sucht, die gegenüber der schlechtesten Realisierung in dieser Menge zulässig bleiben.

Robust OptimizationROWorst-Case-OptimierungMengenbasierte UnsicherheitsoptimierungBudgetierte Unsicherheit

Die robuste Optimierung behandelt Situationen, in denen die Wahrscheinlichkeitsverteilung unsicherer Parameter unbekannt oder unzuverlässig ist, indem sie annimmt, dass die Parameter jeden Wert in einer Unsicherheitsmenge U annehmen können, und eine Lösung sucht, die auch im schlechtesten Fall zulässig bleibt. Die erste Formulierung von Soyster (1973) verwendet eine Box-Unsicherheitsmenge und liefert sehr konservative Lösungen. Ben-Tal und Nemirovski (1998, 1999, 2000) führten ellipsoide Unsicherheitsmengen ein, die Konservativität und Performance ausbalancieren und sich auf konische quadratische Programme (SOCP) reduzieren. Bertsimas und Sim (2003, 2004) schlugen budgetierte Unsicherheit vor, bei der höchstens Γ Parameter pro Restriktion gleichzeitig ihren schlechtesten Wert annehmen; das resultierende Modell ist ein LP gleicher Grösse wie das nominale LP und ist die praktisch am häufigsten eingesetzte Variante. Adjustable Robust Optimization (Ben-Tal Goryashko Guslitzer Nemirovski 2004) erlaubt Anpassung der Zweitstufenentscheidungen an die realisierte Unsicherheit, meist über affine Entscheidungsregeln. Distributionally Robust Optimization (DRO) optimiert den schlechtesten erwarteten Wert über eine Familie von Verteilungen und verbindet stochastische und robuste Paradigmen. Im Vergleich zur stochastischen Programmierung benötigt die robuste Optimierung keine Verteilungsinformation, ist jedoch konservativer. Literatur: Ben-Tal El Ghaoui Nemirovski (2009), Bertsimas Brown Caramanis (2011).

Örnek

Ein Textilunternehmen verteilt Rohstoffbestellungen auf drei Lieferanten, deren Stückpreise um plus/minus 15 Prozent schwanken können, ohne dass eine Verteilung vorliegt. Ein budgetiertes Modell (Bertsimas-Sim) mit Γ = 2 nimmt an, dass höchstens zwei Lieferanten gleichzeitig ihren schlechtesten Preis erreichen; die Lösung verteilt 45 / 35 / 20 Prozent statt Single-Sourcing. Die Nominalkosten steigen um 3 Prozent, die Worst-Case-Kosten sinken jedoch um 18 Prozent — ein bilanzschützendes Beschaffungsportfolio gegen Preisschocks.