Dynamische Programmierung ist eine Methode zum algorithmischen Lösen eines Optimierungsproblems durch Aufteilung in Teilprobleme und systematische Speicherung von Zwischenresultaten. Der Begriff wurde in den 1950er Jahren von dem amerikanischen Mathematiker Richard Bellman eingeführt, der diese Methode auf dem Gebiet der Regelungstheorie anwandte. In diesem Zusammenhang wird auch oft von Bellmans Prinzip der dynamischen Programmierung gesprochen. Der Mathematiker Richard Bellman erfand in den 1950er Jahren bei der RAND Corporation, einem Think Tank der US Air Force, die Optimierungsmethode der Dynamischen Programmierung für ökonomische Modelle mit diskreter Zeitdimension[1]. Man vermutete, Bellman könnte 10 Jahre nach Dantzigs Linearer Programmierung dessen Erfolg mit einem neuen Ansatz wiederholen. Dieser Ansatz bezog die Zeitdimension wirtschaftlichen Handelns explizit ein und zerlegte den zukünftigen Zeitablauf in verschiedene Perioden, in denen jeweils verschiedene Politikoptionen gewählt werden konnten. In einem Aufsehen erregenden, weil kontraintuitiven Vorgehen bestimmte Bellman zunächst in der Endperiode die optimale Politik und arbeitete sich schrittweise von dort zum Gegenwartszeitpunkt zurück (Rückwärtsrekursion). In jüngerer Zeit kritisierte Richard Vahrenkamp, dass die Dynamic Programmierung nur ein mathematisches Modell darstellt ohne Anwendungen in empirischen Projekten [2]. Wie mit der Methode der Linearen Programmierung konnte man auch mit der Dynamischen Programmierung optimale Lösungen wegen der aufwendigen Berechnungen nur mit Hilfe des Computers ermitteln. Christoph Schneeweiss wies im Jahre 1979 auf den hohen Hauptspeicherbedarf der Rückwärtsrekursion hin, der mit dem damaligen Technologiestand der Computertechnik nur für sehr kleine Modelle befriedigt werden konnte[3]. Damit war die Dynamische Programmierung gar nicht in der Lage, Berechnungsprogramme für die weltweite Ersatzteilversorgung der Air Force zu leisten, wie Judith Klein in ihrer Studie zur Cold War Dynamic Programming unterstellte[4].
Dynamische Programmierung kann erfolgreich eingesetzt werden, wenn ein Optimierungsproblem aus vielen gleichartigen Teilproblemen besteht und eine optimale Lösung des Problems sich aus optimalen Lösungen der Teilprobleme zusammensetzt. Dies nennt man Optimalitätsprinzip von Bellman. In der dynamischen Programmierung werden zuerst die optimalen Lösungen der kleinsten Teilprobleme direkt berechnet und dann geeignet zu einer Lösung eines nächstgrößeren Teilproblems zusammengesetzt. Dieses Verfahren setzt man fort, bis das ursprüngliche Problem gelöst wurde. Einmal berechnete Teilergebnisse werden in einer Tabelle gespeichert. Bei nachfolgenden Berechnungen gleichartiger Teilprobleme wird auf diese Zwischenlösungen zurückgegriffen, anstatt sie jedes Mal neu zu berechnen, was zu einer Senkung der Laufzeit führt. Wird die dynamische Programmierung konsequent eingesetzt, vermeidet sie kostspielige Rekursionen, weil bekannte Teilergebnisse wiederverwendet werden.
In der Regelungstheorie und verwandten Gebieten kann man das Prinzip der dynamischen Programmierung einsetzen, um etwa eine Gleichung herzuleiten (Hamilton-Jacobi-Bellman-Gleichung), deren Lösung den optimalen Wert ergibt. Die Argumentation ist dabei etwa folgende: Wenn das Problem zeitabhängig ist, kann man den optimalen Wert des Zielfunktionals zu einem bestimmten Zeitpunkt betrachten. Man fragt sich dann, welche Gleichung die optimale Lösung erfüllen muss, damit das Zielfunktional auch zu einem späteren Zeitpunkt optimal bleibt, dies führt zur Hamilton-Jacobi-Bellman-Gleichung. Damit kann man das Problem in Zeitschritte einteilen, anstatt es auf einmal lösen zu müssen.
In der Physik war dieses Prinzip schon seit Langem bekannt, allerdings nicht unter diesem Namen. Der Übergang von einer globalen (alle Zeitpunkte gleichzeitig) zu einer zeitabhängigen (dynamischen) Betrachtungsweise entspricht dort der Transformation der Lagrange-Funktion in die Hamilton-Funktion mit Hilfe der Legendre-Transformation.
Beispiele
Siehe auch
Literatur
- Richard Bellman: Dynamic Programming. Princeton University Press, 1957.
- Stuart Dreyfus: Richard Bellman on the birth of Dynamic Programming. Band 50, Nr. 1, 2002, S. 48–51 (informs.org [PDF]).
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein: Introduction to Algorithms. 2. Auflage. MIT Press, Cambridge MA 2001, ISBN 0-262-03293-7, S. 323–369 (englisch).
Weblinks
Einzelnachweise
- ↑ Richard Ernest Bellman: The Theory of Dynamic Programming, Rand Paper 550, Santa Monica 1954. Dieses Papier ist der Text einer Rede von Richard Bellman vor der jährlichen Sommertagung der American Mathematical Society in Laramie, Wyoming, am 2. September 1954.
- ↑ Richard Vahrenkamp: Nominal Science without Data: The Cold War Content of Game Theory and Operations Research, in: Real World Economics Review, vol. 88, 2019, pp. 19–50, (http://www.paecon.net/PAEReview/issue88/Vahrenkamp88.pdf). Deutsche Fassung unter Richard Vahrenkamp: Abstraktifizierung – Ein neuer Ansatz zur Evaluation der Wissenschaftsgeschichte von Operations Research in USA und Deutschland, Working Paper in the History of Computing No. 4/2019 (www.vahrenkamp.org/files/Wissenschaftsgeschichte_Operations_Research_Vahrenkamp_WP4_2019.pdf).
- ↑ Schneeweis, Christoph: Dynamische Programmierung, in: Beckmann, Martin, Günter Menges und Reinhard Selten (Hersg.): Handwörterbuch der Mathematischen Wirtschaftswissenschaften, Teilband Unternehmensforschung, Wiesbaden 1979, S. 17–45.
- ↑ Klein, Judy: Cold War, Dynamic Programming, and the Science of Economizing: Bellman Strikes Gold in Policy Space, lecture at First Annual Conference on the History of Recent Economics (HISRECO), University of Paris X -Nanterre, France, 21-23 June 2007.
- ↑ Kurt Mehlhorn, Peter Sanders: Algorithms and Data Structures. The Basic Toolbox. Springer, Berlin / Heidelberg 2008, ISBN 978-3-540-77977-3, S. 243–246, doi:10.1007/978-3-540-77978-0.