Sprungmarken

Servicenavigation

Hauptnavigation

Sie sind hier:

Hauptinhalt

Algorithmen zur diskreten Optimierung unter Unsicherheit

 

Reale Entscheidungsprobleme müssen in der Regel auf der Grundlage unvollständiger Informationen gelöst werden. Solche Unsicherheiten können aus folgenden Gründen auftreten:

 

  • Die Beziehungen zwischen den Eingriffs- und den Ergebnisparametern sind nicht exakt bekannt und werden auf Basis von Beobachtungen des Systemverhaltens in der Vergangenheit modelliert.

  • Eine vollständige Datenerhebung ist zu aufwendig.

  • Die Systemeigenschaften ändern sich zeitlich in nur partiell vorhersagbarer Weise.

  • Das System unterliegt externen Einflüssen. Hierzu gehören auch menschliche Eingriffe und Nutzeranforderungen, die entweder nur abgeschätzt werden können oder sich erst im Zeitverlauf manifestieren, sodass Entscheidungen nur auf Grundlage vorhandener Information getroffen werden dürfen (Nichtantizipativität).

 

Die beiden letztgenannten Formen von Unsicherheit resultieren aus einem wesentlichen Charakteristikum realer Entscheidungsprobleme: ihrer Dynamik. Fast immer werden technische Systeme für künftige, nicht exakt bekannte oder vorhersehbare Anforderungen geplant. Zudem beeinflussen auch kurzfristige Betriebsentscheidungen das Verhalten des Systems in der Zukunft, in der die Anforderungen an das System und seine Leistungsfähigkeit nicht exakt bekannt sind. Dadurch tritt eine immanente Unsicherheit auf, die sich mit fortschreitender Zeit realisiert.

Ausgangspunkt der Entwicklung eines mathematischen Modells zur Optimierung unter Unsicherheit ist ein Optimierungsproblem, dessen Daten mit Unsicherheit behaftet sind. Hinzu kommen Bedingungen an die Verfügbarkeit von Information über die unsicheren Daten: Sind sämtliche Entscheidungen zu treffen, bevor die unsicheren Daten bekannt werden oder besteht die Möglichkeit/Notwendigkeit, nach Beobachtung der Daten weitere Entscheidungen zu tätigen? Dieser Zyklus von Entscheidung, Beobachtung und Entscheidung beschränkt sich oft nicht auf einen Durchlauf - insbesondere bei der Optimierung über längere Zeithorizonte.

Zugänge zur Optimierung unter Unsicherheit unterscheiden sich nach der Art, in der die Dateninformation vorliegt. In der stochastischen Optimierung gibt es explizite Wahrscheinlichkeitsverteilungen, in der robusten Optimierung Datenintervalle, während in der Online Optimierung das Worst-Case-Verhalten von Algorithmen betrachtet wird. Gegenüber der deterministischen Optimierung führt die Optimierung unter Unsicherheit zu völlig neuen Fragestellungen: Schon der Begriff der Optimalität einer Lösung ist beim Auftreten von Unsicherheiten nicht mehr eindeutig. So kann eine Lösung, deren Erwartungswert optimal ist, in der Praxis ungeeignet sein, sofern sie in gewissen nicht auszuschließenden Fällen zu einem unakzeptablen Systemverhalten führt. Beispiele dafür sind der Bankrott eines Unternehmens im Fall niedriger Nachfrage, der Zusammenbruch eines Stromnetzes bei unerwartet hohem Verbrauch oder hoher Einspeisung - beispielsweise von Windenergie - sowie falsche Sendungsabmaße bei Abholaufträgen. Diese Abwägung zwischen Risiko und Erwartungswert einer Lösung kann zu einem multikriteriellen Optimierungsproblem führen. Weitere Zielkonflikte können hinzukommen. Es gibt verschiedene Ansätze, multikriterielle Probleme zu optimieren. Sehr oft wird das multikriterielle Problem auf ein monokriterielles Problem abgebildet. Die Abbildung erfolgt durch eine Gewichtung der Kriterien oder durch die Definition eines Hauptkriteriums, das die Zielfunktion bestimmt und die Definition von zusätzlicher Nebenbedingungen, die festlegen, dass weitere Kriterien eine Mindestgüte erreichen müssen. Dieser methodische Ansatz wird auch im GK genutzt. In der Praxis erfordert die Umwandlung eines multikriteriellen Problems in ein monokriterielles Problem eine Interaktion mit dem Nutzer und sollte nicht ad hoc z. B. durch eine willkürliche Vorgabe von Gewichten für die einzelnen Kriterien erfolgen. Unter Einbeziehung des Nutzers wird die Umwandlung schrittweise durchgeführt, indem unter Umständen zwischen der algorithmischen Analyse und Nutzerentscheidungen iteriert wird. Die zugehörige Methodik wird auch in den Forschungsarbeiten im Bereich Methodik und Benutzerinteraktion bearbeitet.