Mathematische Methoden werden erfolgreich zur Verbesserung vieler praktischer Vorgänge eingesetzt und helfen dabei, kostbare Ressourcen einzusparen. Als sehr schwierig erwies es sich bisher, zeitabhängige Prozesse mit diskreten Entscheidungen wie der Auswahl eines geeigneten Ganges zu kombinieren.
Jeder Mensch, der nicht den Charakter meines Stiefvaters Rolf teilt und schon viele Minuten vor der Ankunft des Zuges geduldig am Bahnsteig wartet, wird wissen, wie man mit einem Auto in kürzestmöglicher Zeit von einem Punkt A (Wohnung) zu einem Punkt B (Bahnhof) kommt. Und dabei noch berücksichtigt, am Punkt B zum Stehen zu kommen, um das Herausspringen aus dem fahrenden Auto zu vermeiden. Man tritt das Gaspedal bis zum Anschlag durch und verharrt so, bis der Moment gekommen ist, blitzartig auf die Bremse zu wechseln. Diese wird nun ebenso durchgedrückt, um das Auto haargenau und mit quietschenden Reifen am Punkt B zum Stehen zu bringen. Die Reihenfolge der Gänge ist klar, und auch die Zeitpunkte, an denen man schalten sollte, wird ein geübter Fahrer recht gut bestimmen.
Weniger sagt die menschliche Erfahrung darüber aus, wie man möglichst wenig Energie auf einer solchen Fahrt verbraucht, beispielsweise unter der zusätzlichen Einschränkung, gemütliche drei Minuten vor Eintreffen des Zuges am Bahnhof zu sein. Spätestens wenn kompliziertere Beschränkungen berücksichtigt werden müssen, sind durch mathematische Optimierungsmethoden gefundene den auf Erfahrung basierenden Fahrweisen überlegen. Solche zusätzlichen Beschränkungen könnten ein Benzinvorrat oder der ungeliebte Radarkasten auf halber Strecke sein. Relevant ist Optimierung für viele Beispiele des täglichen Lebens, die Ressourcen verbrauchen oder Kosten verursachen. Schon kleine Verbesserungen des Betriebs von U-Bahnen, Raum- kapseln, Destillationskolonnen, Katalysatoren oder Reaktoren sind oft bares Geld wert bzw. schonen die Umwelt.
Die mathematische Disziplin der Optimalen Steuerung widmet sich der Frage, wie man solche „Prozesse” derart beeinflusst, dass das bestmögliche Ergebnis herauskommt. Sie stützt sich auf drei Grundpfeiler: Modellierung, Simulation und Optimierung.
Die Modellierung beschäftigt sich damit, ein mathematisches Modell für einen realen Vorgang zu erstellen. Dieses basiert auf Wissen aus dem jeweiligen Anwendungsgebiet. So ist spätestens seit Newton bekannt, dass die Beschleunigung die zweite Ableitung der zurückgelegten Strecke ist, welche sich daher bei festem Anfangszustand und gegebener Beschleunigung berechnen lässt. Andere Beispiele sind bekannte Erhaltungssätze, die oftmals physikalischen oder chemischen Modellen zugrunde liegen. Alle solche Modelle sind natürlich nur Näherungen der Wirklichkeit und vereinfachen an der ein oder anderen Stelle. Von der Berücksichtigung von Reibungskräften bis zu Wechselwirkungen auf Atomebene kann ein solches Modell beliebig verfeinert werden. Eine wichtige Aufgabe des Modellierers ist es, die richtige Mischung zwischen Einfachheit des mathematischen Modells und einer genügend genauen Beschreibung der Wirklichkeit zu finden.
Ausgehend von einem mathematischen Modell lassen sich verschiedene Szenarien durchspielen. Dies nennt man Simulation. Man legt alles fest, was irgendwie beeinflussbar ist. In unserem Beispiel sind dies der Anfangszustand (Auto steht am Punkt A) und die Beschleunigung des Autos, abhängig von der Zeit. Nun lassen sich per Hand oder per Computer die Modellgleichungen lösen, und man analysiert, was passiert.
Stimmen Simulation und Realität überein, so kann man mit der Optimierung beginnen. Hier geht es nun darum, die beeinflussbaren Größen, auch Variablen genannt, so zu bestimmen, dass ein bestimmtes Kriterium minimiert wird. Dies ist häufig die benötigte Zeit oder Energie. Wenn genau zwei Größen zu bestimmen sind, entspricht dies anschaulich der Suche nach dem tiefsten Punkt eines Gebirges. Für jede mögliche Belegung der beiden Variablen lassen sich die zugehörigen Kosten berechnen. Stellt man diese grafisch in einem dreidimensionalen Diagramm dar, so erhält man ein Gebirge, dessen tiefster Punkt der gesuchten Lösung entspricht, da an diesem die Kosten minimal sind.
In der Praxis ist es allerdings zu aufwendig, das Gebirge komplett zu berechnen. Um den tiefsten Punkt mathematisch zu bestimmen, geht man daher so vor, wie dies auch ein Wandersmann tun könnte: Ausgehend von einem beliebigen Punkt geht man so lange bergab, bis es nicht mehr tiefer geht – zumindest nicht in der Umgebung des Standortes. Mathematisch wird dies mithilfe der Ableitungen einer Funktion festgestellt, die erste Ableitung einer Funktion gibt ja gerade deren Steigung an. Gibt es mehr als zwei Größen, so wird es anschaulich etwas komplizierter und nur geübte Star Trek Fans, die es gewohnt sind, in mehr als drei Dimensionen zu denken, finden sich noch zurecht. Mathematisch ändert sich glücklicherweise nichts, und das Abstiegskonzept kann übernommen werden. Dies ist anders, wenn die Variablen sich mit der Zeit ändern dürfen wie in dem Beispiel der Position des Gaspedals. Eine Möglichkeit, mit solchen zeitabhängigen Variablen umzugehen, besteht in der Unterteilung des betrachteten Zeitintervalles in Teilabschnitte. In jedem Teilabschnitt ist der Wert der Variablen, zum Beispiel die Position des Gaspedals, dann konstant und man hat wieder eine feste Anzahl von Größen für die Optimierung.
Mithilfe dieser grob skizzierten Vorgehensweise wurden seit der Mitte des letzten Jahrhunderts viele praktische Probleme gelöst – die gesamte Raumfahrt wäre undenkbar ohne Methoden der Optimalen Steuerung. Was in diesen Modellen nicht berücksichtigt werden konnte, sind ganzzahlige Entscheidungen. Während ein Gaspedal jede Stellung zwischen Bodenplatte und jungfräulicher Stellung einnehmen kann, ist dies bei Gangschaltungen anders. Hier ist der Hebel entweder im zweiten oder im dritten Gang, aber nicht dazwischen. Ähnliche Einschränkungen gibt es bei Ventilen, die entweder offen oder geschlossen sind und ganz allgemein bei Entscheidungen, ob etwas gemacht wird oder nicht. Mathematisch stellen solche ganzzahlig oder diskret genannten Variablen eine erhebliche Erschwerung der Optimierung dar. Dies mag auf den ersten Blick überraschen, stehen doch nur begrenzt viele Möglichkeiten zur Verfügung, die man theoretisch alle ausprobieren kann. Anschaulich existieren keine Gebirge mehr, sondern nur noch räumlich getrennte Säulen, deren Höhe verglichen werden muss. Doch die Anzahl der Möglichkeiten (Säulen) wächst enorm schnell, wenn sich die Anzahl der Variablen erhöht. Dies ist in der ganzzahligen Optimalen Steuerung der Fall, insbesondere um genau entscheiden zu können, wann und wie oft umgeschaltet werden soll. Eine Behandlung dieser Variablen durch Ausprobieren scheidet also wegen der immensen Anzahl an Möglichkeiten aus.
Der neue Ansatz, den ich in meiner Arbeit entwickelt habe, beruht nun darauf, dass optimale Lösungen häufig Extremwerte annehmen – wie in dem oben genannten Beispiel mit maximaler Beschleunigung beziehungsweise maximalem Bremsen. Um dies auszunutzen, erlauben wir temporär Kombinationen der ganzzahligen Variablen – also Lösungen, die sich als Summe aus ganzzahligen Lösungen darstellen lassen. Eine Schaltung, die zu 23 Prozent im zweiten Gang und zu 77 Prozent im dritten ist, wäre demnach mathematisch zulässig – unabhängig davon, ob dies technisch Sinn ergibt oder nicht. Wichtig ist, dass sich die Gewichtungen zu 100 Prozent aufaddieren. Das wichtigste theoretische Resultat meiner Arbeit sagt nun aus, dass man das Ergebnis einer jeden solchen Kombination auch durch das Hin- und Herschalten zwischen den ganzzahligen Werten beliebig genau annähern kann. Anschaulich klar ist dies für unser Auto-Beispiel. Man kann eine bestimmte Geschwindigkeit halten, indem man das Gaspedal konstant in einer bestimmten Position hält. Man kann sich dieser Geschwindigkeit aber auch durch abwechselndes Durchdrücken und Rollen lassen annähern. Je häufiger man wechselt, umso genauer. Im übrigen eine Fahrweise, die mir als Beifahrer häufig Übelkeit verursacht.
In der Arbeit wird bewiesen, dass dies für eine sehr allgemeine Problemklasse und nicht nur für den genannten Sonderfall gilt. Dadurch ergibt sich die Möglichkeit, das beste Ergebnis einer ganzzahligen Lösung durch das Lösen eines nicht ganzzahligen Problems effizient zu bestimmen. In der Arbeit werden Methoden präsentiert, um schnell ganzzahlige, praktisch realisierbare Lösungen zu berechnen. Die Güte solcher Lösungen kann mit dem bestimmten bestmöglichen Wert verglichen werden. Ist sie gut genug, so kann man das Problem als gelöst betrachten. Andernfalls werden weitere Optimierungsläufe gestartet. Die in der Arbeit behandelten repräsentativen praktischen Probleme lassen sich derart vergleichsweise schnell lösen, obwohl sich mitunter komplizierte Schaltstrukturen ergeben und sie von einem theoretischen Standpunkt aus betrachtet in eine sehr schwere Problemklasse gehören. Die Methoden wurden im Rahmen der Arbeit in Software umgesetzt. Mit ihrer Hilfe wurden Fahrten von Zügen der New Yorker U-Bahn, die gezielte Beeinflussung von dynamisch kodierten Informationen in Zellen und der Betrieb einer Destillationskolonne (also eines physikalischen Verfahrens zur Trennung von Stoffgemischen) optimiert. Bei letztgenannter Anwendung wurde erstmals untersucht, wie weit man den Gewinn des Verfahrens erhöhen kann, wenn man zeitlich variable Verschaltungen der Anlage zulässt. Die ganzzahligen Entscheidungen bestehen in der Frage, auf welche Böden der Kolonne die Flüsse verschiedener Reservoirs durch ein Ventil gelenkt werden.
Zusammenfassend lässt sich sagen, dass die Arbeit einen Beitrag dazu leistet, dass mehr und mehr Probleme der Optimalen Steuerung lösbar sind – und mir in Zukunft ermöglicht, die Abfahrt zum Bahnhof noch ein wenig länger hinauszuzögern … ■
Text: Sebastian Sager
