Modellbildung und Simulation

Als Einstieg in die Modellbildung (Simulation wird hier noch praktisch keine Rolle spielen) betrachten wir strategische Spiele. Vor einer formalen Definition sehen wir uns zunächst zwei berühmte Beispiele an: Diese beiden Beispiele lassen schon erkennen, was die Spieltheorie vom Standpunkt einer Einführung in die Modellbildung attraktiv macht: Einerseits sind die Probleme noch so übersichtlich, dass sie schnell erklärt sind und gewonnene Aussagen leicht überprüft werden können, andererseits scheinen Abstraktion und Formalisierung schon lohnend zu sein: Woran liegt es denn, dass bei den beiden Problemen die Entscheidungsfindung ganz unterschiedlich abläuft? Sicher nicht an der Einkleidung in unterschiedliche Geschichten. Die sollten wir schnell zugunsten einer formalen (mathematischen) Notation aufgeben, um dann das auf die wesentlichen Elemente reduzierte Problem zu verstehen. Nur dann haben wir die Möglichkeit, mit vernünftigem Aufwand zu analysieren, was für Fälle eigentlich überhaupt auftreten können, und was jeweils vernünftiges Handeln ist. Die Aussagen darüber sind (solange sie sich auf das Modell beziehen) von mathematischer Exaktheit und lassen keinen Raum für den Zweifel, der einem meistens bleibt, wenn man solche Aufgaben durch Knobeln zu lösen versucht.

Das in diesem Kapitel verwendete mathematische Instrumentarium ist größtenteils elementar, nur im Rahmen der gemischten Strategien im Abschn. 3.6 werden einige grundlegende Dinge aus der Stochastik verwendet (Erwartungswert diskreter Zufallsvariablen, Unabhängigkeit; vgl. Abschn. 2.​3.​2).

In diesem Kapitel wird es um Situationen gehen, in denen es verschiedene Möglichkeiten gibt, die in eine Rangfolge gebracht werden sollen – etwa Parteien bei einer Wahl, Sänger bei einem Schlagerwettbewerb oder Varianten der Verkehrsführung in einer Stadt.

Zu diesen Möglichkeiten gibt es Ansichten von Individuen (bei der Wahl wären das die Wähler, beim Schlagerwettbewerb etwa das Publikum und bei der Verkehrsführung vielleicht alle Verkehrsteilnehmer, vielleicht aber auch die Mitglieder des Gemeinderates). Aus diesen Ansichten – die sich in der Regel widersprechen werden – soll eine gemeinsame Rangfolge festgelegt werden, es gibt also ein Wahlgesetz oder eine andere Festlegung eines Verfahrens, das aus allen möglichen Rangfolgen eine auswählt.

In der Regel werden nicht alle mit dieser Auswahl einverstanden sein, und die Unzufriedenen könnten nun argumentieren, dass das Verfahren „ungerecht“ sei, sie werden vielleicht Beispiele konstruieren, in denen das Verfahren „eklatant unsinnig“ sei, und es stellt sich die Frage nach der Bewertung verschiedener Entscheidungsverfahren.

Dazu müssen zunächst die Präferenzen der Individuen modelliert werden, anschließend das Entscheidungsverfahren selbst. In diesem Modell werden wir einige Beispiele für Entscheidungsverfahren betrachten und insbesondere Situationen, bei denen es zu unerwünschten Ergebnissen kommt. Dass solche auftreten, wird sich als nahezu unvermeidlich herausstellen – es lässt sich nämlich beweisen, dass schon mit den hier formulierten Anforderungen kein Verfahren alle Bedingungen erfüllt, sobald mehr als zwei Möglichkeiten zur Wahl stehen.

Auch dieses Kapitel kommt mit elementaren mathematischen Dingen aus – Relationen und ihre Eigenschaften (vgl. Abschn. 2.​1) werden eine wichtige Rolle spielen, die wesentlichen Definitionen hierzu werden in diesem Kapitel behandelt, sodass keine speziellen Vorkenntnisse notwendig sind.

Die – möglichst optimale – Zuordnung von Ressourcen (Zeit, Personal, Werkzeuge, etc.) zu Aufgaben, die erledigt werden müssen, ist ein herausforderndes und ökonomisch bedeutendes Gebiet der Entscheidungsfindung. Beispiele sind etwa die Planung eines Projektes, der Produktionsablauf in einer Fabrik, Stundenpläne in einer Schule oder die Versorgung von Mietwagenkunden mit Autos.

In diesem Abschnitt geht es spezieller um die Modellierung von Aufgaben, wie sie bei der Planung eines Projektes oder der Produktion in einer Fabrik auftreten, und um Abhängigkeiten zwischen diesen Aufgaben: So kann etwa die Reihenfolge, in der die Aufgaben zu behandeln sind, teilweise vorgegeben sein, oder gewisse Aufgaben können nicht gleichzeitig bearbeitet werden, weil die dafür notwendigen Ressourcen nur einmal zur Verfügung stehen. (Die Probleme, die sich bei den Stundenplänen oder bei der Autovermietung einstellen, sind in der Regel von ganz anderer Natur, sodass dort völlig andere Techniken zum Einsatz kommen.)

Zweck solcher Modelle ist in der Regel die Optimierung: Aus allen möglichen Reihenfolgen soll eine ausgewählt werden, die unter einem vorgegebenen Qualitätsmaß optimal ist – ein optimaler Zeitplan ist zu erstellen.

Das erschließt interessante neue Anwendungsfelder, etwa in der Finanzmathematik – als Beispiel werden wir in diesem Kapitel ein einfaches Modell für Aktienkurse herleiten, das Black-Scholes-Modell . Diese Überlegungen sollen den Teil „Spielen – entscheiden – planen“ abschließen und illustrieren, wie mathematische Modelle plötzlich in ganz anderem Zusammenhang wieder auftauchen können. Andererseits sind oft auch ganz verschiedene Herangehensweisen für ähnliche Problemstellungen möglich – das in diesem Kapitel vorgestellte Modell für die Entwicklung einer Kapitalanlage hat z. B. einen engen Bezug zu den Modellen für die Populationsdynamik in Kap. 10, die ein völlig anderes Instrumentarium verwenden werden.

Dieses Kapitel ist insofern nicht unabhängig von den anderen zu verwenden, als dass es auf Kap. 5 aufsetzt, insbesondere werden die Überlegungen aus Abschn. 5.​2 fortgeführt. Naturgemäß spielt in diesem Kapitel das Instrumentarium der Stochastik (vgl. Abschn. 2.​3) eine große Rolle – wir werden es mit diskreten Verteilungen (Bernoulli-Verteilung, Binomialverteilung), mit der Normalverteilung als kontinuierlicher Verteilung (und ihren Quantilen) und dem Übergang zwischen beiden Welten (Stichwort Asymptotik, Abschn. 2.​3.​4) zu tun haben.

Straßenverkehr geht uns alle an, jeder ist davon betroffen. Unsere Wünsche und Vorstellungen bezüglich des Straßenverkehrs sind jedoch in der Regel etwas widersprüchlich: Einerseits wollen wir möglichst viel davon. Wir wollen mobil sein und so schnell und angenehm wie möglich von der Wohnung zur Uni oder Arbeit, vom Heimatort zum Ferienziel oder vom Einkaufen zur Freizeitbeschäftigung gelangen. Wir wünschen uns dazu gut ausgebaute Straßen und Parkplätze oder häufig fahrenden Personennahverkehr. Andererseits wollen wir möglichst wenig davon. Straßenverkehr soll uns nicht belästigen. Wir möchten nicht im Berufsverkehr oder in den kilometerlangen Mammutstaus zu Ferienbeginn und -ende stehen, wünschen uns, von Lärm- und Abgasemissionen unbehelligt zu bleiben, und bevorzugen Grünstreifen anstelle von Straßenasphalt.

Gerade der Wunsch nach freier Fahrt ist häufig genug mehr Utopie als Realität. Es gibt zwar alleine ca. 230.782 km überörtliche Straßen in Deutschland (nur Bundesautobahnen, Bundesstraßen, Landesstraßen und Kreisstraßen) und damit viel Platz für jeden. Andererseits werden diese von über 51.735.000 in Deutschland zugelassenen Kraftfahrzeugen bevölkert mit einer Gesamtfahrleistung von etwa 705 Mrd. km pro Jahr (Stand 2011, [57, 12]). Besucher und Durchreisende aus anderen Ländern sind dabei noch gar nicht berücksichtigt. Zusätzlich konzentriert sich diese hohe Zahl an Fahrzeugen gerne an zentralen Stellen und verteilt sich nicht gleichmäßig über das Straßennetz. Überbelastungen der Verkehrswege und damit Staus bis hin zum Verkehrskollaps sind vorprogrammiert. Doch diese sind nicht nur nervig, sondern auch kostspielig und sollten schon alleine aus finanziellen Gründen vermieden werden: Die Kosten, die jährlich in der Europäischen Union durch Staus verursacht werden, werden auf etwa 1 % des BIPs [18] geschätzt, d. h. 2011 rund € 126 Mrd..

Einfach viele neue Straßen zu bauen scheitert an Kosten (Konstruktion und Instandhaltung), Platz und Zeitaufwand und ist nur begrenzt möglich. Die Verkehrsinfrastruktur bedeckt bereits etwa 5 % der deutschen Landesfläche, davon etwa 90 % Straßen, Wege und Plätze [56]. Vor allem die vorhandenen Ressourcen müssen daher besser ausgenutzt werden. Eine optimale Regelung des Verkehrs über Verkehrsleitsysteme ist ein Beispiel. Doch wie funktioniert Verkehr? Wie können wir herausfinden, wie wir eingreifen und die Verkehrssituation proaktiv oder reaktiv verbessern können?

Zuerst müssen wir verstehen, wie sich beispielsweise Staus oder Stop-and-go-Wellen bilden, und herausfinden, in welchem Zusammenhang Verkehrsgrößen stehen und welche Auswirkungen es hat, wenn wir an einer bestimmten Stelle in den Straßenverkehr eingreifen. Erst dann können wir dieses Wissen nutzen, um Staus vorhersagen, Neubauten planen, die Auswirkung von Straßensperrungen und Baustellen prognostizieren und zu Verbesserungen beitragen zu können.

In diesem Kapitel wollen wir daher Straßenverkehr modellieren. Wir werden ein grundlegendes Modell aufgrund physikalischer Überlegungen herleiten und beispielhaft aufzeigen, wie Verfeinerungen der zunächst sehr einfachen Modellwelt zu einer realistischeren Abbildung der Realität führen können. Die Dynamik einzelner Verkehrsteilnehmer ist für uns dabei eher uninteressant, wichtiger ist die kollektive Gesamtdynamik des Verkehrs. Wir sprechen daher von makroskopischer Verkehrssimulation und betrachten insbesondere mittlere Größen für die Verkehrsdichte ϱ, den Fluss f und die Geschwindigkeit v. Die Verkehrsdichte in Fzg/km beschreibt dabei, wie „dicht“ Fahrzeuge auf der Straße stehen, der Fluss in Fzg/h, wie viele Fahrzeuge pro Zeit an einem Kontrollpunkt vorbeifahren.

Wollen wir die Möglichkeit haben, große Verkehrsnetze wie das europäische Autobahnnetz zu simulieren, so sollten wir darauf achten, keine unnötigen Größen zu berechnen. Besonders in den Anfangszeiten der Verkehrssimulation waren die Modellierung und Betrachtung einzelner Teilnehmer schon alleine vom Rechenaufwand her ausgeschlossen; mittlerweile kann Straßenverkehr auch mikroskopisch aufgelöst und simuliert werden, was Gegenstand von Kap. 8 ist. Wir werden im Folgenden die makroskopische Verkehrssimulation näher betrachten, die es uns ermöglichen wird, das gewonnene Verkehrsmodell theoretisch zu untersuchen und analytische Ergebnisse zu gewinnen.

An benötigtem Instrumentarium aus Kap. 2 werden neben grundlegenden Begriffen der Analysis (Abschn. 2.​2.​2) insbesondere einige Teile aus Abschn. 2.​4 zur Numerik (Stabilität, Diskretisierung, Finite Differenzen, partielle Differentialgleichungen) benötigt.

Wie in Kap. 7 wollen wir erneut Straßenverkehr modellieren und simulieren. Natürlich haben wir wieder das Ziel, Straßenverkehr besser zu verstehen, und unser Modell soll möglichst gut Verkehrsphänomene erklären und realen Verkehr simulieren können. Das Modell soll es uns ermöglichen, Anforderungen an den Verkehr zu optimieren (regelnd einzugreifen) und Veränderungen (zum Beispiel Baumaßnahmen) zu planen – ohne alle denkbaren Varianten in der Realität ausprobieren zu müssen. Dass die verschiedenen Anforderungen zum Teil miteinander konkurrieren, versteht sich dabei fast von selbst. „Freie Fahrt bei leeren Straßen“ aus Sicht des Verkehrsteilnehmers verträgt sich beispielsweise nicht mit dem Ziel des Verkehrsplaners, möglichst vielen Fahrzeugen pro Zeit ohne Stau die Benutzung eines Autobahnabschnitts zu ermöglichen.

Im Gegensatz zur makroskopischen Simulation sind wir jetzt jedoch nicht nur am Durchschnitt wichtiger Verkehrsgrößen für einen Straßenabschnitt wie der Geschwindigkeit v in km/h, des Flusses f in Fzg/h oder der Dichte ϱ in Fzg/km interessiert; zur Bestimmung des Flusses messen wir an einem Kontrollpunkt die Anzahl der vorbeifahrenden Fahrzeuge pro Zeit, für die Dichte zählen wir die Fahrzeuge pro Strecke in einem Kontrollabschnitt. Bei der mikroskopischen Simulation wollen wir den Verkehr bis auf den einzelnen Verkehrsteilnehmer „mikroskopisch“ genau auflösen um das individuelle Verhalten betrachten zu können. Aus Sicht des einzelnen Fahrers ist das beispielsweise für die Routenplanung wichtig. Diese sollte möglichst dynamisch und abhängig von der aktuellen Verkehrssituation sein und auch individuelle Eigenschaften wie z. B. die Maximalgeschwindigkeit des eigenen Fahrzeugs berücksichtigen.

Wer viel unterwegs ist kann sich leicht vorstellen, dass die Eigenschaften des Verkehrs zum Teil sehr stark vom Individuum oder von einzelnen Klassen von Fahrzeugtypen abhängen können. Auf einer unübersichtlichen Landstraße kann ein einzelner Traktor oder LKW eine lange Fahrzeugkolonne erzwingen, da es für andere Verkehrsteilnehmer keine Überholmöglichkeit gibt – im betrachteten makroskopischen Modell war stets die Überholmöglichkeit implizit gegeben. Für die Verkehrsplanung auf einer Autobahn interessiert es, welche Auswirkungen ein Überholverbot für einen Teil der Verkehrsteilnehmer, zum Beispiel nur für LKWs, auf den Gesamtverkehr hat. Zudem zeigen LKWs und PKWs ein deutlich unterschiedliches Verhalten auf der Straße. Das sind alles Gründe, den Verkehr mikroskopisch zu betrachten.

Haben wir zudem das Ziel, ein Straßennetz (beispielsweise in einer größeren Stadt) sehr präzise aufzulösen und darzustellen, dann wird eine makroskopische Simulation basierend auf Wellenausbreitungsmodellen wie in Kap. 7 sehr rechenaufwändig. Zur Prognose von Staus muss es möglich sein, schneller als in Echtzeit zu simulieren, da die Ergebnisse sonst schon während der Berechnung veralten. Zumindest historisch betrachtet stieß die makroskopische Simulation hierbei an ihre Grenzen. Eine einfachere Modellierung musste gesucht werden.

In diesem Kapitel wollen wir ein Modell vorstellen, das auf stochastischen zellulären Automaten basiert. Dieses Modell ist in seiner Grundform zwar sehr einfach, es modelliert und erklärt jedoch verschiedene Verkehrsphänomene und ist, in verbesserten Versionen, erfolgreich im Einsatz, zum Beispiel zur Stauprognose in Deutschland oder zur Simulation des gesamten Individualverkehrs der Schweiz. Das benötigte Instrumentarium ist (außer dem Begriff des Graphen aus Abschn. 2.​1) elementar, und es sind keine Vorkenntnisse nötig.

Für eine dritte Variante, Verkehr zu simulieren, wollen wir Verkehr mit speziellen Charakteristiken betrachten, wie er insbesondere in Rechensystemen zu beobachten ist.

Stellen wir uns hierzu einen Rechnerraum an einer Hochschule mit vielen Rechnern vor. Die Rechner sind alle vernetzt, und die Benutzer haben über das Netzwerk die Möglichkeit, an einem zentralen Drucker zu drucken. Es gibt zunehmend Beschwerden, dass es zu lange dauert, bis ein Druckauftrag fertiggestellt ist. Sie haben die Aufgabe, einen neuen Drucker zu kaufen, um das Problem zu lösen. Doch wie schnell und leistungsstark muss der neue Drucker sein, damit seine Kapazität reicht? Ein industrieller Hochleistungsdrucker, wie er für „Zeitung on demand“ eingesetzt wird, wäre viel zu teuer, leistungsstark und überdimensioniert. Zudem müssen Sie den Kaufpreis rechtfertigen! Und liegt es überhaupt am Drucker? Wenn nur über einen zentralen Rechner gedruckt werden darf, dann könnte der Engpass auch am Netzwerk liegen. Auf gut Glück einfach einen neuen Drucker kaufen?

Oder betrachten wir ein Telekommunikationsunternehmen. Das Unternehmen hat kräftig Kundenzuwachs bekommen. Muss es nun sein Leitungsnetz ausbauen? Benötigt es neue Verteilerstationen, dickere Leitungen oder zusätzliche Mobilfunkmasten? Und wenn, wo? An welcher Stelle stößt das Netz zuerst an seine Kapazitätsgrenze, wo ist der sprichwörtliche Flaschenhals?

Auch in Systemen, die nichts mit Datenverkehr zu tun haben, müssen solche oder ähnliche Fragestellungen untersucht und beantwortet werden – ob bei der klassischen Postfiliale mit mehreren Schaltern und einer oder mehreren Schlangen, der Mautstation an einem kostenpflichtigen Autobahnabschnitt oder der Prozessplanung in einer Fabrik oder Firma: Wo ist der kritischste Punkt im System? Wie lange müssen Menschen, Fahrzeuge oder Aufträge warten, bis sie an der Reihe sind? Wie viele warten normalerweise gleichzeitig?

Aus Sicht des Besitzers oder Betreibers, also des Administrators, Filialleiters oder Mautunternehmers, sind dies – mal wieder – Teilfragen eines größeren Optimierungsproblems: Wie maximiere ich den Nutzen für gegebene Kosten? Der Nutzen kann dabei natürlich vielfältig sein: etwa höhere Einnahmen durch den Wegfall eines Schalters an der Mautstation oder alternativ durch stärkeres Verkehrsaufkommen wegen kürzerer Wartezeiten bei der Öffnung weiterer Schalter; die Zufriedenheit und eventuell daraus resultierende Bindung von Kunden und vieles mehr. Die einzelnen Optimierungsziele können durchaus im gegenseitigen Konflikt stehen: Beispielsweise sollten in einer Postfiliale idealerweise sowohl die durchschnittliche Wartezeit der Kunden als auch die zu erwartende Untätigkeit des Personals minimiert werden.

Um diese Fragestellungen beantworten zu können, müssen wir den Auftragsverkehr durch die Systeme modellieren und simulieren – wie schon bei der makroskopischen und mikroskopischen Verkehrssimulation in den Kap. 7 und 8. Aufträge sind hier Druckjobs, Telefongespräche, Kunden oder Fahrzeuge. Es stellt sich natürlich die Frage, wieso wir nicht einfach auf die bereits vorgestellten makro- und mikroskopischen Modellierungs- und Simulationstechniken zurückgreifen.

Betrachten wir, welche Aspekte wir aus beiden Welten übernehmen wollen, so stellen wir fest, dass ein alternativer Ansatz sinnvoll ist. Wie bei der makroskopischen Verkehrssimulation interessieren wir uns bei den genannten Szenarien zwar eher für Durchschnittswerte (wenn auch beispielsweise abhängig von der Tageszeit) als für den einzelnen Auftrag; wir wollen jedoch wie bei der mikroskopischen Simulation einzelne Aufträge auflösen – allerdings nicht genauso detailliert: Aus der Sicht eines Druckers ist die Lebensgeschichte eines Druckauftrags nebensächlich. Wichtig ist, wann er ankommt und wie lange es dauert, ihn zu bearbeiten. Wir interessieren uns weniger für das exakte Verhalten der Aufträge zwischen zwei Punkten (räumliche Entwicklung des Straßenverkehrs und genaue Darstellung von Überholvorgängen auf einer langen Straße, Weg zur Post), sondern vielmehr für das Verhalten an bestimmten Punkten (Kreuzung mit Ampel oder Mautstation, Postamt). Zudem können wir nicht davon ausgehen, dass sich beispielsweise Druckaufträge wellenförmig fortbewegen oder meist in Rudeln am Drucker eintreffen.

Die Ereignisse, die einen Auftragseingang auslösen, können für eine Modellierung viel zu vielfältig sein. Mit eingeschränkter, partieller Sicht sind sie unvorhersagbar und können nicht zugeordnet oder angegeben werden. Man muss sich nur überlegen, welche Gründe einen dazu veranlassen können, dass man den Druckknopf betätigt oder ein Telefongespräch führt.

Beides, die eigene partielle Sicht auf die Auftragsverursachung und das Interesse an erwarteten, durchschnittlichen Größen, spricht für ein stochastisches Instrumentarium. Wir wollen daher die stochastische Simulation von Verkehr mit Warteschlangenmodellen näher betrachten. Für einfache Fälle werden sich die Modelle noch analytisch behandeln und gesuchte Größen berechnen lassen. Für komplexere Systeme werden wir simulieren müssen. Da uns nur die Ereignisse selbst interessieren und nicht die dazwischen liegenden Zeitspannen, werden wir dazu die Zeit nach Ereignissen diskretisieren und diskret und ereignisbasiert simulieren. Vom Instrumentarium in Kap. 2 wird dafür im Wesentlichen der Abschn. 2.​3 zu Stochastik und Statistik benötigt.

Die Entwicklung der Population einer oder mehrerer Tier- oder Pflanzenarten ist ein überschaubares Beispiel, um die Dynamik eines Systems zu studieren. Der Zustandsraum besteht hier aus der Anzahl von Individuen der jeweiligen Art – der Begriff „Raum“ ist daher etwas irreführend, da gerade keine räumliche Auflösung des betrachteten Gebietes vorgenommen wird, sondern angenommen wird, dass die Zuwachs- bzw. Abnahmeraten, mit denen sich die Populationsgrößen verändern, nur von der Größe der Populationen abhängen.

Naheliegend wäre, diesen Zustandsraum durch natürliche Zahlen bzw. (im Fall mehrerer Arten) durch Tupel natürlicher Zahlen zu beschreiben, da es sich um die Anzahlen von Individuen handelt. Ein derartiges Modell, bei dem dann Zu- und Abnahme durch einen stochastischen Prozess modelliert werden, wird am Ende dieses Kapitels diskutiert. Diese Modelle werden aber schnell relativ komplex; Modelle, die wesentlich einfacher zu handhaben sind, erhält man, indem man das Wachstum mittels (gewöhnlicher) Differentialgleichungen beschreibt. Das bedingt aber, dass die Populationsgrößen durch (nichtnegative) reelle Zahlen beschrieben werden. Im Fall sehr kleiner Populationen ist das problematisch – eine Population von 2,5 Pinguinen ist nicht sehr sinnvoll – aber im Fall großer Populationen ist dieses Modell gerechtfertigt. In diesem Fall können wir auch davon ausgehen, dass die Gesamtwachstumsrate als Summe vieler unabhängiger Einzelereignisse deterministisch modelliert werden kann, da sich zufällige Schwankungen über eine große Population gemittelt aufheben.

Die kontinuierlichen Modelle werden auf (gewöhnliche) Differentialgleichungen führen, also das Instrumentarium aus der Analysis (Abschn. 2.​2.​2) verwenden, insbesondere aber die Überlegungen aus dem ersten Teil von Abschn. 2.​4.​5 (lineare Differentialgleichungen mit konstanten Koeffizienten, Differentialgleichungssysteme, Konvergenzverhalten, Richtungsfelder und Trajektorien) weiterführen. Für das diskrete Modell werden hingegen Methoden aus der Stochastik (diskrete Verteilungen, bedingte Wahrscheinlichkeiten) herangezogen werden (Abschn. 2.​3).

Das Ziel der Regelungstechnik ist, ein dynamisches System von außen so zu beeinflussen, dass es sich auf eine gewünschte Weise verhält. Dabei wird das Verhalten ständig durch einen Vergleich von Soll- und Ist-Werten des Systems überwacht, und bei Abweichung wird das System mit dem Ziel beeinflusst, diese Abweichung zu minimieren. Aufgrund von dieser Rückkopplung spricht man vom geschlossenen Regelkreis. Findet keine Rückkopplung statt, findet die Einflussnahme also ohne Wissen über den tatsächlichen Zustand des Systems statt, spricht man nicht von Regelung, sondern von Steuerung.

Im täglichen Leben handelt der Mensch sehr häufig selbst als Regler, z. B. unter der Dusche beim Einstellen der Wassertemperatur. Der Soll-Zustand ist eine angenehme Wassertemperatur, der Ist-Zustand weicht leider viel zu häufig stark davon ab. Wir verändern solange die Stellung des Wasserhahns, bis die Abweichung vom Sollwert für unsere Bedürfnisse gering genug ist. Auch in der Natur kommen Regelungen vor. In unserem Körper gibt es eine Vielzahl an Regelkreisen, die Größen wie z. B. die Körpertemperatur oder den Blutdruck auf bestimmten Werten halten.

Ihren hauptsächlichen Einsatz findet die Regelungstechnik heutzutage bei technischen Systemen. Bekannte Anwendungsgebiete sind z. B. Klimaanlagen oder Fahrsicherheitssysteme wie ABS und ESP. Aber auch bei nichttechnischen Systemen findet die Regelungstechnik Anwendung, z. B. in der Ökonomie oder bei der Analyse biologischer Regelungen. In jedem Fall gehört zur Regelungstechnik immer auch die Modellierung des zu regelnden Systems. Wir gehen in Abschn. 11.2 exemplarisch auf eine solche Modellierung anhand eines mechanisches Systems ein.

Es gibt viele verschiedene Ansätze, ein gegebenes Regelungsziel zu erreichen. Bei Methoden aus dem Bereich der „klassischen Regelungstechnik“, auf die wir in Abschn. 11.1.4 kurz eingehen, wird ein Regler so entworfen, dass der geschlossene Regelkreis bestimmte, mathematisch definierbare, Eigenschaften aufweist. Ein Vorteil dieser Vorgehensweise ist, dass man die Reaktion des Regelkreises auf bestimmte Eingaben gut vorausberechnen kann und so verschiedenste Gütekriterien durch einen entsprechenden Entwurf des Reglers erfüllt werden können.

Als Grundlagen für das Verständnis dieses Kapitels werden aus dem Instrumentarium Abschn. 2.​1 und die Abschnitte zur Analysis und zur Numerik gewöhnlicher Differentialgleichungen benötigt. Darüber hinaus ist ein rudimentäres physikalisches Grundwissen hilfreich.

Bei der Erwähnung des Begriffs Chaostheorie denken viele vielleicht zunächst an faszinierende Bilder von Fraktalen, wie z. B. das „Apfelmännchen“. Diese Bilder zeigen aber nur einen Teilbereich dessen, worum es bei der Chaostheorie geht. Sie beschäftigt sich im Wesentlichen mit der Untersuchung nichtlinearer dynamischer Systeme, also von Systemen, deren Dynamik z. B. durch nichtlineare Differentialgleichungen beschrieben wird. Nahezu jedes in der Realität vorkommende System zeigt nichtlineares Verhalten, daher beschäftigen sich Menschen aus den verschiedensten Bereichen der Wissenschaft mit solchen Systemen. Ein prominentes Beispiel ist natürlich das Wetter, das sich auch mit noch so viel Rechenleistung niemals beliebig lange vorhersagen lässt, da eben hin und wieder in China ein Sack Reis umfällt. Oftmals lässt sich bei den untersuchten Systemen in manchen Situationen scheinbar regelloses, so genanntes chaotisches Verhalten beobachten.

Was hat nun Chaos mit Modellbildung und Simulation zu tun? Zunächst geht es darum, chaotisches Verhalten zu verstehen, in solchem Verhalten Strukturen zu entdecken – die klassische Aufgabe der Chaostheorie. Systeme mit chaotischem Verhalten zu modellieren und zu simulieren – trotz der Unzugänglichkeit – ist für viele wissenschafliche Gebiete von Bedeutung. In der Finanzmathematik versucht man, aus chaotischem Verhalten Rückschlüsse auf die Entwicklung von Geldmärkten zu ziehen; in der Neurologie wird die Chaostheorie dazu verwendet, epileptische Anfälle vorherzusagen. Der Grund, weshalb sich die Chaostheorie als eigenständiges Forschungsgebiet etabliert hat, ist, dass sich solch seltsam anmutendes Verhalten bei den verschiedensten Anwendungen findet und sich dabei häufig ähnliche Strukturen entdecken lassen. Bei der Untersuchung nichtlinearer Systeme ist man fast zwangsläufig auf Computersimulationen angewiesen, da sich nur die wenigsten nichtlinearen Gleichungen analytisch lösen lassen.

Sowohl bei diskreten (z. B. diskrete Abbildungen) als auch bei kontinuierlichen (z. B. Differentialgleichungen) Systemen tritt Chaos auf. Die wesentlichen Merkmale des Chaos wie Bifurkationen und seltsame Attraktoren werden wir aufgrund der besseren Anschaulichkeit anhand einfacher diskreter Abbildungen erklären. Aber auch bei kontinuierlichen Systemen lassen sich die gleichen Effekte beobachten. Wir werden daher im letzten Teil des Kapitels ein mechanisches System – ein angetriebenes Pendel – zunächst kurz modellieren und dann mit Hilfe von Simulationsergebnissen das chaotische Verhalten des Systems betrachten. Zum leichteren Verständnis dieses Kapitels sind die Abschnitte zur Analysis und zur Numerik gewöhnlicher Differentialgleichungen aus Kap. 2 hilfreich.

Die Molekulardynamik beschäftigt sich mit der Simulation von Stoffen auf molekularer bzw. atomarer Ebene. Das bedeutet, dass zumindest jedes Molekül, wenn nicht sogar jedes einzelne Atom, im Simulationsgebiet getrennt betrachtet wird. Damit ist sofort klar, dass die in Frage kommenden Gebiete sehr klein sein müssen. Ein Mol eines Stoffes enthält ca. 6 ⋅ 10²³ Partikel. Bei einem idealen Gas entspricht ein Mol 22,4 Litern, bei Feststoffen ist das Volumen dieser Stoffmenge natürlich noch sehr viel geringer. Da außerdem für die Simulation nennenswerter Zeiträume sehr viele Simulationszeitschritte berechnet werden müssen, ist an die Simulation großer Gebiete gar nicht zu denken. So wird man wohl niemals (zumindest nicht zu einer Zeit, die die Autoren dieses Buches erleben werden) einen Windkanal komplett auf molekularer Ebene simulieren – und das wäre wohl auch, wenn es technisch möglich wäre, ein Overkill. Dennoch gibt es eine Menge Anwendungsfelder, in denen eine molekulare Betrachtung auch mit den gegebenen Einschränkungen sinnvoll, ja notwendig ist. Sie ist beispielsweise in biologischen oder medizinischen Anwendungen nötig, um die Funktion von Proteinen oder anderen Makromolekülen zu untersuchen, oder auch in der Nanotechnik. Auch in Feldern, wo normalerweise Simulationen auf kontinuierlicher Ebene eingesetzt werden, also beispielsweise Strömungssimulationen, kann manchmal eine Molekulardynamiksimulation sinnvoll sein. Denn auch dort treten Phänomene auf, die auf der kontinuierlichen Ebene nicht aufgelöst werden können, beispielsweise das genaue Verhalten an der Grenze zwischen zwei unterschiedlichen Stoffen. Des Weiteren gewinnt die Molekulardynamik auch in den Materialwissenschaften und der Verfahrenstechnik zunehmend an Bedeutung. Bei Letzterer steht das Wechselspiel zwischen verschiedenen Aggregatszuständen, also z. B. Verdunstung, Verdampfung und Destillationsvorgänge, im Vordergrund. Aus den vielen verschiedenen Anwendungebereichen ist dies das Gebiet, auf das wir uns in diesem Kapitel konzentrieren werden. Ein wichtiges Merkmal dabei ist, dass üblicherweise zwar – im Vergleich etwa zu Proteinen – sehr kleine Moleküle betrachtet werden, davon aber jede Menge.

Wir werden, ausgehend von den physikalischen Gesetzmäßigkeiten, Modelle für die Interaktion von Atomen herleiten. Diese Modelle überführen wir in eine Differentialgleichung, die wir für die Simulation diskretisieren. Vorwissen aus den Gebieten Analysis und Numerik gewöhnlicher Differentialgleichungen (siehe Kap. 2) ist dazu hilfreich. Im Anschluss an die Diskretisierung beschäftigen wir uns mit dem Aufbau eines Simulationsgebiets und den dafür nötigen Parametern und Randbedingungen. Zuletzt gehen wir auf Methoden zur effizienten Implementierung und zur Parallelisierung, d. h. zur Verteilung des Rechenaufwands auf viele Prozessoren, ein.

Für die molekulardynamischen Simulationen aus Kap. 13 wurden zur Beschreibung der Teilchenbahnen gewöhnliche Differentialgleichungen (ODE) verwendet. Diese hängen nur von einer unabhängigen Variablen ab, in diesem Fall der Zeit. Es gibt aber auch eine sehr große Bandbreite an physikalischen Problemstellungen, bei denen eine Modellierung mit Hilfe partieller Differentialgleichungen (PDE) irgendwo im Bereich zwischen naheliegend, angemessen und erforderlich ist. Ein Beispiel hierfür stellt die Strukturmechanik dar, wo unter anderem die Verformung von Bauteilen unter dem Einfluss von Kräften betrachtet wird. Derartige Untersuchungen sind in ganz unterschiedlichen Szenarien relevant – vom Bau von Brücken bis hin zur Konstruktion mikroelektromechanischer Sensoren und Aktuatoren (MEMS). Ein weiteres wichtiges Beispiel ist die Strömungsmechanik, mit der wir uns im nächsten Kapitel noch beschäftigen werden. Aus Sicht der Simulation sind solche Probleme, die sich mit PDE modellieren lassen, auch deshalb interessant und herausfordernd, weil für ihre effiziente numerische Lösung in der Regel modernste Methoden und Rechner unerlässlich sind.

Doch der Reihe nach: Eine relativ einfach herzuleitende Problemstellung wird durch die Wärmeleitungsgleichung beschrieben, die in diesem Kapitel prototypisch als Beispiel für ein auf Ausgleichsprozessen beruhendes Phänomen betrachtet werden soll. In der Thermodynamik, aber auch in vielen anderen Anwendungsbereichen ist es wichtig, Aussagen über die Ausbreitung von Wärme treffen zu können. Häufig geht es darum, Wärme entweder möglichst schnell abzuführen (z. B. bei Klimaanlagen und Kühlgeräten) oder sie möglichst schnell und verlustfrei zuzuführen (z. B. bei Herdplatten). In anderen Anwendungen kann es auch wichtig sein, die Verteilung der Wärme in einem Körper zu untersuchen, um Stellen zu erkennen, an denen beispielsweise eine Überhitzung droht.

Im Folgenden wird zunächst kurz in die physikalischen Grundlagen der Wärmeleitung eingeführt. Da die Komplexität der späteren Simulation sehr entscheidend von der Anzahl an unabhängigen Variablen, in diesem Fall der alleinigen Betrachtung der Temperatur also von der Anzahl der im Modell berücksichtigten Dimensionen (Raum und Zeit) abhängt, wird auch die Wahl der Dimensionalität betrachtet. Abschließend beschäftigen wir uns natürlich mit der Simulation der (stationären) Wärmeleitungsgleichung. Dazu gehören zum einen die Diskretisierung und zum anderen die Lösung des sich ergebenden linearen Gleichungssystems.

Aus dem Instrumentarium in Kap. 2 werden dazu neben der Analysis weite Teile des Abschnitts zur Numerik benötigt. Natürlich ist die Betrachtung hier wieder relativ knapp gehalten. Ausführlicher sowohl bei der physikalischen Beschreibung als auch bei der Diskretisierung ist [61].

Strömungen zählen von jeher zu den am meisten modellierten und (numerisch) simulierten Phänomenen. Dabei treten sie in völlig verschiedenen Zusammenhängen und Disziplinen auf. Astrophysik, Plasmaphysik, Geophysik, Klimaforschung und Wettervorhersage, Verfahrenstechnik und Aerodynamik sowie Medizin – überall werden Strömungen studiert, wenngleich auch ganz unterschiedlicher Materialien bzw. Fluide. Wie wir im Kap. 7 über makroskopische Verkehrssimulation gesehen haben, werden Strömungsvorgänge auch als Denkmodell für Anwendungen hergenommen, bei denen kein Stoff im üblichen Sinn fließt. Strömungen sind zudem ein Paradebeispiel sehr rechenintensiver Simulationen – insbesondere, wenn Turbulenz im Spiel ist – und somit sehr oft ein Fall für Hochleistungsrechnen (High Performance Computing (HPC)) und Hochleistungsrechner. Und so darf natürlich auch in diesem Buch ein Kapitel zur numerischen Strömungsmechanik (Computational Fluid Dynamics (CFD)) nicht fehlen. Simulationsseitig haben wir es also wieder mit einem numerischen Simulationsansatz zu tun, modellseitig meistens mit einem PDE-basierten Modell. Dementsprechend benötigen wir nun vom Instrumentarium aus Kap. 2 vor allem die Abschnitte zur Analysis und zur Numerik.

Aus der Vielzahl relevanter Szenarien greifen wir im Folgenden den Fall viskoser, d. h. reibungsbehafteter, laminarer Strömungen inkompressibler Fluide heraus. Die Begrifflichkeiten werden im nächsten Abschnitt eingeführt und besprochen, als Faustregel für dieses Kapitel denke man eher an Honig als an Luft. Der Einfachheit halber bewegen wir uns zudem in einer zweidimensionalen Geometrie. Als Anwendungsbeispiel soll die Umströmung eines Hindernisses dienen. Für eine weiterführende Diskussion der Thematik sei auf die Bücher „Numerische Simulation in der Strömungsmechanik“ von Michael Griebel, Thomas Dornseifer und Tilman Neunhoeffer [28] und „Numerische Strömungsmechanik“ von Joel H. Ferziger und Milovan Peric [19] verwiesen.

In diesem Kapitel wenden wir uns einer ur-informatischen Anwendung von Modellierung und Simulation zu – und befassen uns doch zugleich mit Physik im Rechner. Schließlich ist eines der großen Ziele der Computergraphik der Photorealismus, also die Erzeugung möglichst realistisch anmutender Computerbilder. An vielen Stellen begegnen wir dabei Modellen – bei der Beschreibung von Objekten und Effekten – sowie Simulationen – bei deren effizienter graphischer Darstellung. Als Beispiele seien genannt die Darstellung natürlicher Objekte (Berge, Bäume etc.) mittels Fraktalen oder Grammatikmodellen, die Darstellung natürlicher Effekte (Feuer, Nebel, Rauch, Faltenwurf von Stoffen etc.) mittels Partikelsystemen, die Abbildung biomechanischer Vorgänge (Dinosaurierbäuche und sonstige „Schwabbelmassen“) oder allgemein die Beschreibung von Animation. Von zentraler Bedeutung für die Computergraphik sind ferner Techniken zur globalen Beleuchtung. Mit ihr wollen wir uns im Folgenden befassen. Die Darstellung folgt dabei [13]. Vom Instrumentarium aus Kap. 2 werden insbesondere die Abschnitte zur Analysis und Numerik benötigt.

In der Computergraphik studierte man früh lokale Beleuchtungsmodelle, um die Lichtverhältnisse an einem bestimmten Punkt einer Szene beschreiben zu können, und unterschied dabei ambientes Licht, punktförmige Lichtquellen mit diffuser Reflexion und punktförmige Lichtquellen mit spiegelnder Reflexion. Für die Erzeugung photorealistischer Bilder ist aber auch die Modellierung der globalen Beleuchtung, also der Licht-Wechselwirkungen aller Objekte der Szene miteinander, wichtig.

Der erste Ansatz, das so genannte Ray-Tracing , geht auf Whitted und Appel zurück [4, 62]. Es kann spiegelnde Reflexion perfekt wiedergeben, diffuse Beleuchtung bzw. ambientes Licht dagegen überhaupt nicht. Die resultierenden Bilder wirken synthetisch und fast zu perfekt. Gewissermaßen das Gegenstück, das Radiosity-Verfahren , wurde von Goral et al. vorgestellt [26] und gibt diffuse Beleuchtung perfekt wieder. Spiegelnde Reflexionen sind allerdings nicht möglich. Die resultierenden Bilder wirken natürlicher, aber noch nicht realistisch – es fehlen eben Spiegelungs- und Glanzeffekte. In der Folge wurden zahlreiche Ansätze zur Kombination von Ray-Tracing und Radiosity entwickelt, ausgehend von der einfachen Hintereinanderschaltung bis hin zu komplizierteren Verfahren. Trotzdem bleiben Probleme bei der Wiedergabe indirekter spiegelnder Beleuchtungen (etwa über einen Spiegel), so genannte Caustics . Weitere Entwicklungsstufen waren Path-Tracing [37] und Light oder Backward Ray-Tracing [5]. Beide sind prinzipiell in der Lage, das globale Beleuchtungsproblem zu lösen, haben jedoch Probleme hinsichtlich Aufwand bzw. Einschränkungen bei der Geometriebeschreibung. Eine signifikante Verbesserung stellt Monte Carlo Ray-Tracing mit Photon Maps dar [36], das auch Caustics in befriedigender Qualität effizient wiedergeben kann.