Studien und Aufgaben zur Simulation

1 Einführung

Die Aufgaben der Einführung sind aus dem Gebiet der zeitdiskreten deterministischen Simulation. Die diskrete Zeitvariable wird mit t bezeichnet. Diese Variable zählt die Perioden bzw. Zeitschritte: t = 0, 1, 2, 3, ...

1.1 Populationsdynamik

Größen und Parameter des Wachstumsmodells

N(t)

Bestand der Population zur Zeit t

r

Zuwachsrate (auch: Wachstumsrate)

p

Ernterate

K

Kapazität der Umwelt

Systemgleichung

N (t+1)-N(t) = (r× (1-N/K)-p) × N(t)

Zu untersuchen ist der Zeitverlauf des Wachstums einer Population (Wilson/Bossert, 1973). Die Entwicklungsdynamik wird unabhängig von der Entwicklung anderer Populationen und von der Umwelt angenommen. Das exponentielle Wachstum wird durch die Differenzengleichung N(t+1) - N(t) = r× N(t) regiert (sogenanntes r-Wachstum). Beim begrenzten Wachstum wird die Zuwachsrate r ersetzt durch die bestandsabhängigen Zuwachsrate r(1-N/K), und bei Bewirtschaftung der Population wird die Zuwachsrate durch r(1-N/K)-p ersetzt.

1.1.1 r- und K-Wachstum. Ermitteln Sie den Verlauf der Populationsbestands über einen Zeitraum, innerhalb dessen sich der Gleichgewichtszustand in etwa einstellt. Gehen Sie von einem Anfangsbestand von 100 und einer Zuwachsrate von r = 2% aus. Die Kapazität K der Umwelt wird auf 1000 festgesetzt. Jagd bzw. Ernte findet nicht statt (p=0).

1.1.2 Auf Dauer haltbarer Höchstertrag. Stellen Sie fest, für welche Wert von p sich der auf Dauer haltbare Höchstertrag ergibt.

 

1.2 Modellbildung in der Volkswirtschaft

Aggregierte Größen einer Volkswirtschaft

Y

Sozialprodukt, genauer: Nettosozialprodukt zu Marktpreisen. Rechnet man die Steuern und die Subventionen heraus, erhält man das Volkseinkommen.

C

Privater Konsum

I

Investitionen (genauer: Induzierte Nettoinvestitionen)

G

Staatsausgaben

Parameter

a

Marginale Konsumquote

b

Akzelerator

Systemgleichungen

Y(t) = C(t) + I(t) + G(t)

C(t) = a Y(t-1)

I(t) = b (C(t) - C(t-1))

Der Nobelpreisträger Paul A. Samuelson entwickelte das Multiplikator-Akzelerator-Modell im Rahmen der Untersuchung von Konjunkturschwankungen (Stobbe, 1975, S. 165 ff.; Paulsen, 1970; Neubäumer/Hewel, 1998). Das Modell beschreibt die dynamischen und statischen Beziehungen zwischen den aggregierten Größen einer Volkswirtschaft (nebenstehende Tabelle). Die erste der Gleichungen drückt aus, wie sich das Sozialprodukt zusammensetzt. Sie ist die Grundgleichung des wirtschaftlichen Kreislaufs einer Periode. In den beiden weiteren Gleichungen treten als Parameter die marginale Konsumquote und der Akzelerator auf. Die marginale Konsumquote besagt, in welchem Maß die Haushalte eine Erhöhung des Einkommens für eine Erhöhung der Konsumausgaben verwenden. Die Einkommenserhöhung wirkt mit einer Verzögerung um eine Periode (Robertson-Lag). Dass sich die Nettoinvestitionen (also die Investitionen, die nicht Ersatzinvestitionen sind) nach der Änderung der Konsumgüternachfrage richten, kommt in der dritten Gleichung zum Ausdruck. Der Akzelerator gibt an, in welchem Maß die Konsumänderungen sich auf die Investitionen auswirken. Und so hängt die Konsum- bzw. Nachfrageänderung mit den Nettoinvestitionen zusammen:

1.         Steigt die Nachfrage, sind die Nettoinvestitionen positiv. Der Gerätepark wächst: I >0

2.         Bleibt die Nachfrage gleich, genügen Ersatzinvestitionen: I = 0

3.         Fällt die Nachfrage, unterbleiben Investitionen und I wird - mangels Ersatzinvestitionen - sogar negativ: I < 0

1.2.1 Grundmodell. Erstellen Sie ein Simulationsmodell des Multiplikator-Akzelerator-Modells und führen Sie eine einfache Simulation durch. Gehen Sie von den Festlegungen a  = 0,8, b = 1, G(t) = 20, Y(0) = 0 und C(0) = 0 aus. Die Werte t und Y(t) sollen für t = 0, 1, ..., 20 in einer Tabelle erscheinen.

1.2.2 Parametervariation. Modifizieren Sie das Programm der vorigen Aufgabe, so dass Sie verschiedene Werte für a und ß eingeben können und dass Sie die Kurvenverläufe von Y(t) beliebig weit verfolgen können. Rechnen Sie das Modell für folgende Parameterwerte durch:

1. a = 0,8 und b = 1

2. a = 0,88 und b = 1

3. a = 0,8 und b = 1,1

Zeichnen Sie die Diagramme der Kurvenverläufe und diskutieren Sie das Ergebnis.

1.2.3 Stabilitätsuntersuchung. Ermitteln Sie für die Schwingungen des Volkseinkommens Frequenzen und Dämpfungswerte. Geben Sie weitere Parameterkonstellationen ein. Stellen Sie fest, für welche Parameterwerte keine Stabilität mehr herrscht. (Stabilität heißt, dass sich aus einer beschränkten Eingangsfunktion eine beschränkte Ausgangsfunktion ergibt.)

1.2.4 Optimierung des Volkseinkommens. Versuchen Sie das Minimum des Volkseinkommens im Multiplikator-Akzelerator-Modell zu maximieren. Die Parameter sind a = 0,8 und b = 1. Für Volkseinkommen und Konsum werden die Anfangswerte Y(0) = C(0) = 0 vorgegeben. Ein festes Staatsbudget von 120 ist so auf 6 Perioden aufzuteilen, dass das Minimum des Volkseinkommens in diesen Perioden möglichst groß wird.

 

2 Deterministische Simulation

2.1 Füllstandsregelung

Größen der Füllstandsregelung

x

Wasserstand (Regelgröße)

w

Sollwert des Wasserstands

xw

Regelabweichung

z

Zufluss

y

Abfluss (Stellgröße)

Parameter

a

P-Anteil des Reglers

b

I-Anteil des Reglers

Systemgleichungen

xw = x - w

dx/dt = z - y

Für das Ausregeln kleiner Schwankungen des Flüssigkeitsstands in einem Gefäß mit Zufluss und regelbarem Abfluss hat man das folgende Modell (Schöne, Bd. 1, 1974): Der Flüssigkeitsstand x (Regelgröße) in einem zylindrischen Gefäß soll auf einem konstanten Wert w = 120 cm (Sollwert, Führungsgröße) gehalten werden. Die Regelabweichung ist xw = x - w. Zu- und Abfluss werden gemessen in cm/s und geben die jeweilige Änderung des Flüssigkeitsstandes je Zeiteinheit an. Der Abfluss y ist die Stellgröße. Ihr Wert ist nach unten durch null begrenzt. Der Zufluss ist konstant gleich z = 10 cm/s.

Die letzte der Systemgleichungen beschreibt das Verhalten eines proportional-integralen Reglers (PI-Regler). Die Parameter a und b bestimmen den P- bzw. den I-Anteil.

2.1.1 Zustandsraumdarstellung der Füllstandsregelung. Formulieren Sie die Zustandsraumdarstellung in Normalform. Ermitteln Sie den Gleichgewichtsfall für den konstanten Sollwert w = 120 cm und den konstanten Zufluß z = 10 cm/s. Schreiben Sie ein Simulationsprogramm und berechnen Sie damit den Zeitverlauf von Regel- und Stellgröße für eine Sollwertänderung von 120 cm auf 150 cm. Die Parameter des Reglers sind dabei eingestellt auf die Werte a = 0,1/s und b = 0,1/s2.

2.1.2 Symbolische Methode. Ermitteln Sie durch symbolische Rechnung Frequenz und Dämpfung der Schwingung des Füllstandes.

2.1.3 Parameteroptimierung. Ziel ist die Minimierung der quadratischen Regelabweichung. Das heißt:: das Integral der Funktion xw2(t), integriert von 0 bis ¥, soll möglichst klein werden. Die Optimierung soll für folgende Fälle durchgeführt werden:

Dabei wird vorausgesetzt, daß anfangs der Gleichgewichtszustand herrscht. Die Wertebereiche der Parameter sind gegeben durch 0 £ a £ 0,2/s und 0 £  b £ 0,2/s2. Wie ändern sich die Zeitverläufe, wenn man den I-Anteil des Reglers gleich null setzt? Was passiert, wenn der P-Anteil weggelassen wird?

Lösungshinweis: Führen Sie als weitere Zustandsgröße das fortlaufende Integral v(t) der quadratischen Regelabweichung ein. Diese Größe erfüllt die Differentialgleichung dv(t)/dt = xw2(t) mit der Anfangsbedingung v(0) = 0. Der Wert v(T) am Ende des ausreichend groß gewählten Beobachtungsintervalls [0, T] ist gleich der Zielgröße. Diese ist zu minimieren. Der Vektor der Zustandsgrößen ist nun (x, u, v). Bedenken Sie, dass die Steuergröße nicht negativ werden kann: 0 £ y. Auch der Integralanteil u des Reglers wird festgehalten, wenn er droht unter null zu fallen: du/dt = 0, falls weder xw>0 noch u>0. Führen Sie eine einfache Rastersuche in der a-b-Ebene durch. Teilen Sie dazu die Ebene in beide Richtungen äquidistant auf und ermitteln Sie denjeninge Rasterpunkt mit dem Optimalwert der Zielgröße. Dann halbieren Sie die Intervalle aller Koordinaten und suchen Sie weiter. Das wird fortgesetzt, bis die Feinheit des Rasters eine hinreichend genaue Annäherung an das gesuchte Optimum gewährleistet.

2.1.4 Nichtlineares Ausströmgesetz: Die Aufgabenstellung ist insofern etwas vereinfacht worden, als direkt der Abfluss zur Regelgröße gemacht wurde. Aber eigentlich ist nicht der Abfluss, sondern nur die Ventilöffnung direkt einstellbar. Wegen des Ausströmgesetzes von Torricelli ist der tatsächliche Abfluss proportional zur Ventilöffnung multipliziert mit der Wurzel aus dem Füllstand - letzterer gemessen über dem Abfluss. Wir normieren die Stellgröße so, dass bei einem Füllstand von x0=120 cm der Ausfluss genau gleich der Stellgröße y ist. Wir können also das Torricellische Ausströmgesetz dadurch berücksichtigen, dass wir die Formel dx/dt=z-y ersetzen durch
.

2.2 Schleppkurven

Schleppkurven: die Größen

f(t) = (x(t), y(t))

Führungskurve

s(t) = (u(t), v(t))

Schleppkurve

Parameter

D

Deichsellänge

Systemgleichungen

du/dt = (x-u) ((x-u) dx/dt + (y-v) dy/dt)/D2

dv/dt = (y-v) ((x-u) dx/dt + (y-v) dy/dt)/D2

Ungünstig dimensionierte Verkehrswege - in landwirtschaftlichen Betrieben beispielsweise - führen zu unnötigen Rangiervorgängen und zu erhöhten Risiken. Bereits während der Bauplanung ist der Verkehrsflächenbedarf abzuschätzen. Unter anderem benötigt man den Schleppkurvenverlauf für größere Fahrzeuge und Fahrzeugkombinationen. Der Abstand zwischen Vorder- und Hinterachse eines Fahrzeugs sei gleich D. Der Mittelpunkt der Vorderachse möge sich auf einer Führungskurve f(t) = (x(t), y(t)) bewegen. Dabei sind x und y die Komponenten in kartesischen Koordinaten. Die Schleppkurve s(t) = (u(t), v(t)), das ist die Bewegung des Mittelpunkts der Hinterachse, ist gesucht.

2.2.1 Schleppkurven bei Kreisfahrt. Als Führungskurve wird ein Kreis mit vorgebbarem Radius gewählt. Die Vorderachse startet auf der positiven Halbachse. Die Anfangspositionen des hinteren Achsmittelpunkts sei beliebig vorgebbar. Das Simulationsprogramm soll die zugehörige Schleppkurven ausgeben.

 

2.3 Räuber-Beute-System

Größen des Räuber-Beute-Systems

N1

Bestand der Räuberpopulation

N2

Bestand der Beutepopulation

Parameter

B1

Geburtenrate der Räuberpopulation je Beuteeinheit

D1

Sterberate der Räuberpopulation

B2

Geburtenrate der Beutepopulation

D2

Sterberate der Beutepopulation je Räubereinheit

K

Kapazität der Umwelt für die Beutepopulation

P

Jagdrate: Anteil der gejagten Räuber bezogen auf die Größe der Räuberpopulation je Zeiteinheit

Systemgleichungen

dN1/dt = (B1 N2 - D1 - P) N1

dN2/dt = (B2 (1-N2/K) - D2 N1) N2

Wenn zwei Populationen verschiedener Arten überhaupt Einfluß aufeinander haben, dann kann die Wirkung einer Art auf die andere positiv (+) oder negativ (-) sein; der neutralen Einfluß (0) bliebt hier einmal außer Betracht. Wenn beide Arten aufeinander negativen Einfluß haben (--), spricht man von Konkurrenz, bei wechselseitig positivem Einfluß (++) von Kooperation oder Symbiose. Ist eine Beziehung positiv für die eine und negativ für die andere Population (+- bzw. -+) liegt eine Räuber-Beute-Beziehung oder Parasitismums vor. Wir greifen das Räuber-Beute-System heraus.

Angenommen wird, dass die Geburtenrate der Räuberpopulation proportional zum Bestand der Beute ist. Auf der anderen Seite ist die Sterberate der Beutepopulation von der Anzahl der Räuber abhängig. Das führt zu den bekannten Lotka-Volterra-Gleichungen. Sie ergeben sich aus den Systemgleichungen der Tabelle, wenn man die Jagdrate P gleich null und die Kapazität K der Umwelt gleich unendlich setzt.

2.3.1 Grundmodell. Führen Sie eine Simulation des Räuber-Beute-Systems auf Grundlage der Lotka-Volterra-Gleichungen mit folgenden Parameterwerten durch: B1 = 15/(106 Jahre), D1 = 0,6/Jahr, B2 = 0,6/Jahr, D2 = 300/(106 Jahre). Die Anfangspopulationen seien N1(0) = 2 000 und N2(0) = 100 000. Der Bestand der Populationen ist über wenigsten 10 Jahre zu berechnen. Die Parameter des Modells sind so gewählt worden, daß in etwa die Populationszyklen wiedergegeben werden, wie sie in dem vieldiskutierten System auftreten, das vom Luchs und seiner Hauptbeute, dem Schneehasen, gebildet wird (Wilson, Bossert, 1973).

2.3.2 Symbolische Rechnung. Vorausgesetzt wird P = 0 und K = ¥ . Außerdem seien die Populationsschwankungen relativ klein. Leiten Sie mit der symbolischen Methode die Formel

für die Periodendauer T der Populationsschwankungen her. Diese Formel unterstützt die Validierung des Modells. Zeigen Sie die Übereinstimmung zwischen Simulation, Formel und den empirisch ermittelten Werten.

Lösungshinweise: Im Gleichgewichtsfall bleiben die Populationsgrößen konstant. Daraus folgt dN1/dt = dN2/dt = 0. Also müssen die rechten Seiten der Lotka-Volterra-Gleichungen gleich null sein. Für die Gleichgewichtswerte N1e bzw. N2e gilt N2e = D1/B1 und N1e = B2/D2. Für die Abweichungen der Populationen vom Gleichgewichtswert setzen wir die als relativ klein angenommen Größen n1 (t) und n2(t) ein: N1(t) = N1e + n1(t) und N2(t) = N2e + n2(t). Bei Vernachlässigung kleiner Größen zweiter Ordnung ergibt sich ein System von linearen Differentialgleichungen für die Abweichungen. Es lässt sich mit den üblichen Verfahren lösen.

2.3.3 Jagd mit auf Dauer haltbarem Höchstertrag. Nun erweitern wir das Räuber-Beute-System, indem wir den Jäger hinzunehmen, dessen Ziel die Tiere der Räuberpopulation sind. Außerdem sei die Beutepopulation kapazitätsbeschränkt. Simulieren Sie zunächst die Wirkung der Kapazitätsbeschränkung (P = 0, K = 100 000, alle anderen Parameter bleiben unverändert). Führen Sie dann eine Optimierung der Jagdrate mit dem Ziel ist des "auf Dauer haltbaren Höchstertrags" durch. Zeigen Sie, dass der Optimalwert der Jagdrate bei P = 45% je Jahr liegt.

Lösungshinweis: Die Simulation ergibt, dass sich das System aufgrund der Kapazitätsbeschränkung stabilisiert: Es erreicht von selbst seinen Gleichgewichtspunkt. Dieser ist von der Jagdrate P abhängig. Zur Ermittlung der Jagdrate, die den auf Dauer erreichbaren Höchstertrag liefert, ist das Maximum des Produkts P× N1e(P) zu errechnen.

2.4 Das mathematische Pendel

Größen des mathematischen Pendels

w

Auslenkung des Pendels von der Vertikalen, gemessen im Bogenmaß

v

Winkelgeschwindigkeit

Parameter

g = 9.81 m/s2

Erdbeschleunigung

l

Stablänge

Systemgleichung

d2w(t)/dt2 + (g/l)×sin w(t) = 0

Eine punktförmige Masse ist an einem masselos gedachten Stab der Länge l aufgehängt. Im Aufhängepunkt ist das Pendel reibungfrei gelagert, so dass die Masse eine Kreisbahn beschreiben kann. Die Systemgleichung ist eine Differentialgleichung zweiter Ordnung.

2.4.1 Grundmodell. Führen Sie die Differentialgleichung für die Auslenkung w in eine Zustandsraumdarstellung in Normalform über und Integrieren Sie diese mit dem Verfahren von Heun. Vergleichen Sie zur Verifikation des Modells für den Fall kleiner Auslenkungen das Simulationsergebnis mit dem exakten Ergebnis nach der symbolischen Methode.

Lösungshinweis: Die Ordnung der Differentialgleichung wird durch die Einführung einer weiteren Zustandsvariablen - nämlich der Winkelgeschwindigkeit v - verringert. Dadurch erhält man zwei Differentialgleichungen erster Ordnung, die sich leicht in die Normalform bringen lassen.

 

2.5 Schaltungstechnik: Analog- und Digitalfilter

Die folgenden Aufgaben setzen Grundkenntnisse der Elektotechnik und der mathematischen Systemtheorie voraus. Eine voraussetzungsarme Darstellung des Stoffes (ohne Laplacetransformation und ohne z-Transformation) ist in meinem Skriptum "Simulation - strukturiert und objektorientiert programmiert" zu finden.

2.5.1 Sprungantwort des Serienschwingkreises. Gegeben sei ein Serienschwinkreis mit folgenden Paramterwerten für Induktivität, Kapazität und Widerstand: L = 10-3 W s, C = 25×10-12 s/W und R = 1000 W . Ermitteln sie mittels Zustandsraummethode die Sprungantwort. Führen Sie für den Serienschwingkreis die bilineare Transformation mit der Schrittweite TA = 10ns = 10-8s durch. Zeichnen Sie das Blockschaltbild des Digitalfilters und formen Sie dieses mit Äquivalenztransformationen so um, dass nur noch zwei Speicherbausteine vorkommen. Errechnen Sie auf dieser Grundlage die Sprungantwort.

2.6 Das Quasi-Spezies-Modell

Im Kurs „Umweltsimulation mit Tabellenkalkulation“ wird unter anderem das Quasi-Spezies-Modell von Manfred Eigen behandelt. Dort geht es um die Evolution, also um die Entstehung neuer Muster, und darum, welche Rolle Stabilität und Variabilität dabei spielen. Dort wird die Simulation für extrem kurze Muster (Gene) durchgeführt. Für längere Muster sind Tabellenkalkulationsprogramme nicht geeignet.

2.6.1 Das Quasi-Spezies-Modell für die Evolution  komplexer Strukturen. Es ist ein Programm zu entwickeln, das Einsichten in das Verhalten des Quasi-Spezies-Modells von Eigen erlaubt. Die Evolution komplexer Muster ist zu analysieren.

3 Stochastische Simulation

3.0 Einführung

3.0.1 Buffons Nadel (Papoulis, 1965, S. 185): Eine feine Nadel wird auf ein Blatt Papier geworfen, das mit Linien versehen ist, deren Abstand genau gleich der Nadellänge ist. Die Nadel überschneidet eine der Linien mit der Wahrscheinlichkeit 2/p. Beweisen Sie diese Behauptung und schreiben Sie ein Programm für die näherungsweise Ermittlung der Kreiszahl p mittels stochastischer Simulation.

3.1 Einfache stochastische Simulationsaufgaben

3.1.1 Bäckerei (Sasieni-Yaspan-Friedman, 1971). Eine Bäckerei liefert an eine ihrer Filialen täglich frische Pumpernickel. Die Zahl der täglich gelieferten Laibe ist nicht konstant, sondern hat unten aufgeführte Verteilung.

Laibe je Tag

10

11

12

13

14

15

16

Wahrscheinlichkeit in %

5

10

20

30

20

10

5

Die Zahl der täglichen Pumpernickelkunden ist folgendermaßen verteilt:

Zahl der Kunden

5

6

7

8

9

10

Wahrscheinlichkeit in %

10

15

20

40

10

5

Die Wahrscheinlichkeiten dafür, dass jemand 1, 2 oder 3 Laibe verlangt, sind gleich 40%, 40% und 20%. Schätzen Sie mit Hilfe des simulierten Stichprobenverfahrens die durchschnittliche Zahl der übrigbleibenden Laibe je Tag, sowie die Zahl der durchschnittlich nicht getätigten Verkäufe aus Mangel an Brot. Nehmen Sie an, daß das übrigbleibende Brot am Ende des Tages verschenkt wird.

3.1.2 Halbkreis. In einer zufälligen Art und Weise werden auf einem Kreis n Punkte gewählt und markiert (n ist vorgebbar). Wie groß ist die Wahrscheinlichkeit dafür, dass diese n Punkte auf einem Halbkreis liegen?

3.1.3 Stoffballen. Wie groß ist der Erlös aus einem Ballen mit 10 m Stoff, wenn der Preis je Meter 12.00 DM beträgt und sich die Nachfrage folgendermaßen verteilt? 5% der Kunden wollen 1m Stoff, 30% 1,5m, 50% 2m, 10% 3m, 5% 4m. Sowie ein Kunde mehr verlangt als noch auf dem Ballen ist, wird ein neuer Ballen angefangen und der Rest wird zum Preis von 2.00 DM/Meter verramscht.

Monate bis zum Ersatz

Wahrscheinlichkeit (in Prozent)

6

5

8

10

10

15

12

20

14

20

16

10

18

10

20

5

24

5

3.1.4 Taxiwagen. Ein Taxigeschäft stellt die unten aufgelistete Wahrscheinlichkeitsverteilung für die wirtschaftliche Lebensdauer seiner Taxiwagen fest (Sasieni-Yaspan-Friedman, 1971). Schätzen Sie die Zahl der Ersetzungen, die während zweier Jahre durchgeführt werden müssen, wenn das Taxigeschäft einen Bestand von 20 Wagen besitzt. Geben Sie das Vertrauensintervall an.

Anmerkungen zur Lösung: Für den stationären Fall ist eine Simulation überflüssig: Die gefragte Schätzung läßt sich mit etwas Wahrscheinlichkeitsrechnung machen. Es ist offenbar unerheblich, ob man die erwartete Zahl der Ersetzungen für ein Taxi ermittelt und dann diesen Wert mit 20 multipliziert oder ob man bei der Abschätzung von vornherein mit 20 Taxis rechnet. Wir betrachten also einen Prozess, bei dem jeweils ein Taxi zu erneuern ist. Wir bezeichnen mit pi die Wahrscheinlichkeit dafür, dass das Taxi die Lebensdauer Ti hat. Die mittlere Lebensdauer der Taxiwagen ist gleich t = Si pi Ti = 13,4 Monate. Auf lange Sicht werden im Schnitt 1/t = 0,0746 Fahrzeuge je Monat ersetzt. Bei insgesamt 20 Taxiwagen und einem Zeitraum von 24 Monaten sind also im Schnitt 35,8 Ersetzungen nötig.

Nicht mehr ganz so einfach ist es, die Zahl der Ersetzungen zu ermitteln, wenn der Fuhrpark durch 20 Neuwagen vergrößert wird. Jetzt spielt das Übergangsverhalten eine Rolle. Und genau dieses läßt sich durch die Simulation und Scharmittelwertbildung bequem bestimmen. Der oben errechnete Mittelwert für den Gleichgewichtsfall dient der Validation: Die Scharmittelwerte der späteren Zweijahresperioden müssen sich dem stationären Wert nähern.

3.1.5 Aufzug. Wir betrachten einen Aufzug, der bei Überlastung ein Signal abgibt und stehen bleibt. Die Grenzbelastung beträgt 200 kg. Vor dem Aufzug befindet sich eine längere Warteschlange von Leuten, deren Gewicht normalverteilt ist mit dem Mittelwert 70 kg und der Standardabweichung 10 kg. Die Aufgabe besteht darin, mittels stochastischer Simulation festzustellen, wieviele Personen der Aufzug je Fahrt im Mittel transportiert.

3.1.6 Kugeln. Längs einer Bahn werden Kugeln geworfen. Der Weg, den eine solche Kugel bis zur Ruhe zurücklegt, sei eine normalverteilte Zufallsgröße mit dem Mittelwert 10 m und der Standardabweichung 2 m. Nun werden zwei Kugeln betrachtet. Gesucht ist die Wahrscheinlichkeit p, dass die Kugeln im Abstand von höchstens einem Meter liegenbleiben? Zusammenstöße bleiben unberücksichtigt.

Lösungshinweis: Sei Z eine Zielgröße, die genau dann gleich 1 ist, wenn der Abstand der Kugeln höchstens einen Meter beträgt - ansonsten ist Z gleich 0. Der Erwartungswert von Z ist gleich der gesuchten Wahrscheinlichkeit: E[Z] = 1 p + 0 (1-p) = p. Damit ist das simulierte Stichprobenverfahren zusammen mit der Formel für das Vertrauensintervall anwendbar.

3.1.7 Erstes Ass. Ein Kartenstapel mit 52 Spielkarten, darunter vier Asse, wird gut gemischt. Nun werden der Reihe nach die Karten von oben nach unten aufgedeckt. Wie viele Karten muss man im Mittel aufdecken, bis das erste Ass erscheint (Michalewicz/Michalewicz 2008, S. 180)?

3.2 Lagerhaltungsprobleme

3.2.1 Lagerhaltung. Für ein Lagergut mögen die folgenden Bedingungen gelten (Krüger, 1975, S. 172 ff.):
- der monatliche Bedarf ist normalverteilt mit dem Mittelwert 100 und der Standardabweichung 20
- die Lagerkosten betragen 0.15 DM pro Stück und Monat
- die Bestellkosten belaufen sich auf 20 DM pro Bestellung
- die Fehlmengenkosten betragen 2.50 DM pro Stück
- bei Bestellungen über 2 500 DM gewährt der Lieferant 2% Rabatt
- der Preis des Lagerguts ist 7.50 DM pro Stück
- die Lieferzeit beträgt 1 Monat

Die Lagerhaltungspolitik wird durch die Zeitabstände t der Bestellungen und die Bestellmengen q bestimmt. Bei welcher Lagerhaltungspolitik (t, q) sind die geringsten Gesamtkosten zu erwarten?

3.2.2 Montagerampe (Sasieni-Yaspan-Friedman, 1971). An einer Montagerampe werden pro Tag rund 100 Automobile fertiggestellt. Doch aus vielen Gründen ergeben sich Schwankungen im täglichen Ausstoß. Die Tagesproduktion läßt sich deshalb besser durch eine Wahrscheinlichkeitsverteilung beschreiben (siehe untenstehende Tabelle).

Tagesproduktion

95

96

97

98

99

100

101

102

103

104

105

Wahrscheinlichkeit in %

3

5

7

10

15

20

15

10

7

5

3

Die fertiggestellten Automobile werden jeweils am Schluß des Tages auf einer Fähre an ihren Bestimmungsort transportiert. Der Laderaum der Fähre vermag lediglich 101 Wagen auf einmal zu fassen. Wie groß wird im Durchschnitt die Zahl der Wagen sein, die auf das Verladen warten? Wie groß ist die durchschnittliche Zahl von leeren Frachtplätzen auf der Fähre? Wenden Sie auch hier die Formel für die Vertrauensbereiche an und diskutieren Sie das Ergebnis. Wie kommt man zu "vertrauenswürdigen Vertrauensbereichen"?

 

3.3 Entscheidung bei Risiko

Bezeichnungen

A

Menge der Alternativen a

X

Zufallsvariable oder (allgemeiner) Zufallsvektor X = (X1, X2, ..., Xn)

z(a, X)

Stochastische Zielfunktion in Abhängigkeit von den Alternativen a Î A und dem Zufallsvektor X

a*Î A

Optimale Entscheidung

Optimalitätsbedingung (Maximierung)

Manche Entscheidungsprobleme stellen sich so dar (Bamberg, Coenenberg, 1989): Aus einer endlichen Menge von Alternativen ist eine Wahl zu treffen, so dass eine bestimmte Zielfunktion (Gewinn, Kosten, Risiko) einen möglichst günstigen (also: maximalen oder minimalen) Wert annimmt. Von den üblichen Optimierungsproblemen unterscheiden sich diese Probleme dadurch, dass der Wert der Zielfunktion nicht nur von der gewählten Alternative, sondern darüberhinaus von zufallsbedingten Einflüssen bestimmt wird. Die Entscheidung ist zu treffen, bevor die Realisierung x der Zufallsvariablen bekannt ist. Bekannt ist nur die Verteilungen der Zufallsvariablen. Zur Entscheidungsfindung wird das µ-Kriterium herangezogen: Es wird diejenige Alternative a*ÎA gewählt, für die sich der maximale (minimale) Erwartungswert der Zielgröße ergibt.

3.3.1 Produktionsentscheidung für Dreschmaschinen. Eine Firma produziert kleine Dreschmaschinen. Der Absatz fällt hauptsächlich in die Zeit der Getreideernte. Aus den bisherigen Verkaufsstatistiken geht hervor, dass die Anzahl der je Saison nachgefragten Maschinen im Mittel 100 Stück beträgt und dass die Nachfrage in etwa mit der Standardabweichung 25 schwankt. Zu entscheiden ist über die Zahl der für ein Jahr herzustellenden Maschinen. Die Lagerkosten für jede nicht verkaufte Maschine betragen 345 DM und der entgangene Gewinn für jede nachgefragte und nicht gelieferte Maschine ist 655 DM. Lösen Sie dieses Entscheidungsproblem unter der Voraussetzung, dass die Nachfrage normalverteilt ist. Ermitteln Sie den Erwartungswert des Gewinns je Alternative mit dem simulierten Stichprobenverfahren. Führen Sie die Simulation auch unter der Voraussetzung durch, dass die Nachfrage - bei gleichen Parametern - gleichverteilt ist.

Lösungshinweise: Da es um den Vergleich des Ergebnisses bei verschiedenen Alternativen geht, liegt es nahe, für alle Alternativen gemeinsame Folgen von Zufallszahlen (Common Random Numbers) zu nehmen. Durch diesen Trick reduziert man die Varianz der Abschätzung für die Differenz der Kosten bei verschiedenen Alternativen a1 und a2:

E[z(a1, X)] - E[z(a2, X)] = E[z(a1, X) - z(a2, X)].

Techniken der Varianzreduktion dienen dazu, die Genauigkeit des Ergebnisses bei gleicher Stichprobenzahl zu erhöhen (Bratley, Fox, Schrage 1987, S. 48 ff.). Im Buch von Dinkelbach (1982) ist das analytisch ermittelte exakte Ergebnis für den Fall normalverteilter Nachfrage angegeben: a* = 110.

3.4 Das Paradoxon der Restlebensdauer

3.4.1 Per Anhalter unterwegs. Modellieren Sie den Strom von Autos, der an einem Rasthof vorüberkommt, als Poissonstrom. Irgendwann kommt ein Anhalter. Wie lange muss der Anhalter im Mittel auf das nächste Fahrzeug warten? Wie ist diese Wartezeit verteilt? Wie sieht die Verteilung der Zeitabstands aus, der zwischen dem gerade verpassten und dem kommenden Fahrzeug liegt?

3.5 Lieses Verehrer

„Kommt ein Reitersmann daher durch die grüne Wiese, hat ein Wams von Seide an, neigt sich vor der Liese: Jungfrau so lieblich, Jungfrau so schön, tanzen wir ein wenig? Mag nicht tanzen, danke schön, wart’ auf einen König!“ – das ist die erste Strophe eines Volkslieds. Liese lässt noch mehrere Verehrer abblitzten. Schließlich muss sie sich mit dem Schweinehirten Johann Christoph Stoffel zufrieden geben. Gibt es eine Strategie, nach der Liese den für sie besten Bewerber hätte wählen können? Wenn auch nicht mit Sicherheit, so doch mit der größtmöglichen Wahrscheinlichkeit? (Beck-Bornholdt, Dubben, 2003, S. 237 ff.; Bruss, 2004)

 

3.5.1 Nehmen wir einmal an, dass Liese – zumindest grob – die Zahl n der Bewerber kennt. Diese kommen nacheinander und kehren niemals zurück. Die ersten k Bewerber lässt sie abblitzen, merkt sich aber, wie gut der beste unter ihnen war. Dann entscheidet sie sich im weiteren Verlauf für den ersten, der besser ist als jener. Damit kann sie immer noch bei einem Mittelmäßigen oder gar bei Johann Christoph Stoffel landen. Aber es gibt eine gewisse Wahrscheinlichkeit dafür, dass sie tatsächlich den besten unter den Bewerbern („den König“) auswählt. Bestimmen Sie diese Wahrscheinlichkeit für jedes denkbar k mittels stochastischer Simulation. Geben Sie die bestmögliche Strategie – das optimale k – an. Führen Sie die Simulation für mehrere n durch und ermitteln Sie jeweils den optimalen Wert für den Quotienten k/n. Was stellen Sie fest?

 

3.5.2 Wenn Sie die stochastische Simulationsaufgabe 3.5.1 zu ihrer Zufriedenheit gelöst haben, suchen Sie nach einer analytischen Lösung des Problems. Es wird in der Literatur unter dem Namen Sektretärinnen-Problem behandelt. (Der Chef steht vor demselben Problem wie Liese: Aus einem Strom von Bewerberinnen muss er seine zukünftige Sekretärin auswählen.)

 

3.5.3 Führen Sie die Simulation auch mit anderen (realistischeren) Zielkriterien durch. Es muss ja nicht unbedingt der König sein. Ein Graf wäre ja auch schon ganz nett. Zielkriterien:

(Todd, Miller, 1999)

4 Ereignisorientierte Simulation

4.0 Vorstudie zur objektorientierten Programmierung

4.0.1 Die Schlange - ein Computerspiel. In einem Raster aus m mal n Zellen (Spielfeld) bewegt sich eine Schlange mit wählbarer Geschwindigkeit v (Schwierigkeitsgrad des Spiels). Ihre Bewegung kann mit den Richtungstasten gesteuert werden: Je nach gewählter Richtungstaste wendet sich der Kopf der Schlange nach rechts oder nach links. Mit jedem Zeitschritt rückt der Kopf in die gewählte Richtung um ein Feld weiter, das letzte Feld wird von der Schlange freigegeben. Alle anderen Felder bleiben besetzt. Auf dem Spielfeld ist zu Beginn Futter zufällig verteilt. Trifft die Schlange auf ein Feld mit Futter, wächst sie um eine Zelle. Für diesen Fall besetzt der Kopf das neue Feld, alle anderen Felder bleiben besetzt. Das Spiel ist zu Ende, sobald die Schlange auf ein Feld trifft, das sie selbst belegt - wenn sie sich sozusagen selbst auffrisst -, oder wenn sie mangels Futter nicht mehr weiter wachsen kann. Ziel des Spiels ist, durch geschicktes Manövrieren eine möglichst große Schlange heranzuziehen.

4.1 Beim Friseur

4.1.1 Der Herrenfriseur. Beim Herrenfriseur treffen die Kunden mit einer mittleren Zwischenankunftszeit von 20 Minuten so ein, dass sie einen Poissonstrom bilden. Der Friseur benötigt für die Bedienung eines jeden Kunden genau 15 Minuten. Ermitteln Sie die mittlere Wartezeit mittels Simulation. Erstellen Sie ein Histogramm der Wartezeiten und stellen Sie es mittels Tabellenkalkulationsprogramm dar. Überprüfen Sie Ihre Ergebnisse so gut es geht mittels analytischer Verfahren. Ersetzen Sie die Konstanten durch eingebbare Variablen.

4.1.2 Der Friseursalon. Im Friseursalon sind 1 Herrenfriseur, 2 Damenfriseurinnen und 3 "Alleskönner" beschäftigt. Die Herrenfrisur braucht konstant 15 Minuten, die Damenfrisur ist im Mittel in 30 Minuten fertig und die Bediendauer ist in diesem Falle exponentialverteilt. Die Kunden treffen mit einer mittleren Zwischenankunftszeit a als Poissonstrom ein. Der Frauenanteil beträgt 60%. Ermitteln Sie, welchen Kundenstrom der Salon maximal verkraften kann, also die kürzestmögliche mittlere Zwischenankunftszeit amin. Wie groß sind die mittleren Wartezeiten für die Damen und die Herren, wenn die Auslastung 80 % beträgt. Führen Sie getrennte Warteschlangen für Damen und Herren ein und formulieren Sie eine möglichst gerechte Bedienstrategie. Führen Sie für die hier als fest angenommenen Zahlen Variable ein und führen Sie die Simulationen für verschiedene Werte durch. Überprüfen Sie die Ergebnisse anhand bekannter Sonderfälle.

4.1.3 Modularisierung. Schreiben Sie ein allgemein verwendbares Modul EventSim für die ereignisorientierte Simulation.

4.1.4 Grafische Oberfläche. Programmieren Sie eine grafische Oberfläche zu Eingabe der Parameter und Ausgabe der Simulationsergebnisse. Achten Sie auf strikte Entkopplung des Simulationsmodells vom Ein-Ausgabemodul.

4.2 Platzreservierungssysteme

4.2.1 Platzreservierung, (Page, 1991, S. 42 ff.). Untersuchungsgegenstand ist ein telefonisches Platzreservierungssystem mit n = 5 Bedienplätzen (Schalter) und k = 13 weiteren Telefonleitungen (Warteplätze). Es werden ausschließlich telefonische Platzreservierungen entgegengenommen. Wenn alle Schalter belegt sind, wird der Anrufer, der eine der k Leitungen belegt hat, automatisch aufgefordert zu warten. Freiwerdende Schalter bekommen die Leitung mit der längsten Wartezeit zugeschaltet. Die Wartebereitschaft w der Kunden ist normalverteilt mit dem Mittelwert 4 min und der Standardabweichung 2 min. Falls der Zufallsgenerator eine negative Zeit liefert, wird die Zeit gleich null gesetzt; falls der gelieferte Wert größer als 8 min ist, wird die Zeit auf 8 min gesetzt. Also: niemand wartet länger als 8 min. Dementsprechend ändert sich die Verteilung. Die Zwischenankunftszeit der Anrufe ist exponentialverteilt mit dem Mittelwert a = 20s. Die Bediendauer je Platzreservierung ist ebenfalls exponentialverteilt und hat für die einfache Fahrt den Mittelwert b1 = 1 min und für Hin- und Rückfahrt den Mittelwert b2 = 2 min. Die Wahrscheinlichkeit für den zweiten Fall beträgt p (= 75%). Die Simulation soll sich über eine maximale Simulationszeit von 100h erstrecken.

4.3 Bankschalter

4.3.1 Bankschalter. Diese Aufgabe ist das Standardbeispiel aus dem Buch von Bratley, Fox und Schrage (1987, S. 14 ff.). In einer Bank sind drei Kassierer angestellt. Meistens sind alle drei anwesend. Aber an 15% der Arbeitstage melden sich nur zwei, und an 5% der Tage kommt nur einer zur Arbeit. Die Bank ist von 10 bis 15 Uhr geöffnet. Die Kunden kommen rein zufällig und unabhängig voneinander herein. Die Zwischenankunftszeiten sind exponentialverteilt - allerdings mit unterschiedlichen Ankunftsraten: Von 9.45 Uhr bis 11 Uhr, sowie von 14 bis 15 Uhr kommt im Mittel alle zwei Minuten ein neuer Kunde. Von 11 Uhr bis 14 Uhr betritt etwa jede Minute ein Kunde die Bank. Wer vor 10 Uhr kommt, muß vor der Bank warten bis sie öffnet. Nach 15 Uhr werden noch die Kunden bedient, die bereits in der Bank sind.

Es gibt nur eine Warteschlange für alle drei Schalter. Ein Kunde reiht sich nur dann in die Warteschlange ein, wenn diese nicht zu lang ist, ansonsten gibt er auf und verlässt die Bank. Die Wahrscheinlichkeit pi dafür, dass ein Kunde aufgibt, wenn bereits i Kunden vor ihm da sind, ist gegebem durch

pi = min(max((i-5)/5, 0), 1)

Der erste Kunde der Warteschlange geht jeweils zum nächsten freiwerdenden Kassierer. Die Bedienzeiten sind Erlang-verteilt mit dem Parameter 2 und der mittleren Bedienzeit von 2 Minuten. Zu ermitteln ist der Erwartungswert der Anzahl von Kunden, die an einem Tag bedient werden.

Erläuterungen zur Erlang-Verteilung und zur Simulation inhomogener Poisson-Prozesse (Poissonprozesse mit zeitabhängigem Parameter l ) sind im folgenden Anhang zu finden. 

4.4 Fertigungssysteme

4.4.1 Werkstattfertigung (Page, 1991, S. 71 ff.; Dahl/Dijkstra/Hoare, 1972, S. 216). Das zu simulierende Fertigungssystem besteht aus fünf Maschinengruppen mit jeweils 7, 3, 8, 7 bzw. 3 identischen Maschinen zur Bearbeitung von Werkstücken. Die ankommenden Werkstücke bilden einen Poissonstrom mit einer mittleren Zwischenankunftszeit von 0.1 h. Die Auftragsarten und deren Bearbeitungsfolgen und Maschinenebelegdauern sind in der folgenden Tabelle erfasst.

Auftragsart

Wahrscheinlichkeit

Maschinenfolge

mittlere Bearbeitungsdauern [h]

1

30%

3, 1, 2, 5

0.5, 0.6, 0.85, 0.5

2

50%

4, 1, 3

1.1, 0.8, 0.75

3

20%

2, 5, 1, 4, 3

1.2, 0.25, 0.7, 0.9, 1.0

Wenn ein Auftrag bei einer bestimmten Maschinengruppe eintrifft und alle Maschinen dieser Gruppe sind besetzt, wird er in eine unbegrenzte FIFO-Warteschlange eingereiht. Die Bedienungszeiten werden als Erlang-verteilt mit dem Parameter r angenommen. Führen Sie eine Engpassanalyse für verschiedene Werte von r durch (1, 2, 5, 10). Varieren Sie auch die Zwischenankunftszeit.

4.5 Der Token-Bus

Systembeschreibung: Die Teilnehmer eines Übertragungssystems sind über eine durchgehende Sammelleitung miteinander verbunden. Sendet ein Teilnehmer eine Nachricht über dieses Übertragungssystem, so wird er von allen anderen Teilnehmern verstanden. Alle Teilnehmer sind grundsätzlich gleichberechtigt, zu senden. Ein Zutrittsverfahren (es ist Bestandteil des Übertragungsprotokolls) regelt den Zugang zum Übertragungsmittel, so dass zu jedem Zeitpunkt nur ein Teilnehmer auch tatsächlich sendet. Andernfalls könnten Nachrichten durch Kollisionen verloren gehen. Beim Token-Bus sieht das Zutrittsverfahren so aus: Nach einer - hier nicht näher zu beschreibenden - Anlaufphase besitzt ein Teilnehmer die Sendeberechtigung. Wir sagen: er hat das Staffelholz (Token). Der Teilnehmer sendet, solange er Nachrichten hat oder solange, bis seine Sendeberechtigung erschöpft ist. Dann gibt er das Staffelholz an einen Nachfolger weiter. So geht das Staffelholz zyklisch reihum.

Jeder Teilnehmer ist durch eine oder mehrere Warteschlangen für Nachrichten repräsentiert, die nach Erhalt des Staffelholzes gemäß einer bestimmten Strategie abgearbeitet werden. Bei solchen Bussen interessieren vor allem die Wartezeiten für die einzelnen Nachrichten in den Warteschlangen. Die Wartezeiten sind abhängig vom Datenaufkommen bzw. von der Auslastung des Systems.

Die Wartezeit wird im konkreten Fall für jede einzelne Nachricht festgestellt. Zuweilen reicht es aus, die mittlere Wartezeit w der Nachrichten - eventuell abgestuft nach Prioritätsklassen - zu bestimmen. Außerdem ist interessant, welcher Anteil von Nachrichten eine bestimmte Grenze für die Wartezeit überschreitet. Alle diese Kennzahlen gelten jeweils für ein bestimmtes Datenaufkommen.

4.5.1 Tokenbus-System. Das System hat n = 60 Teilnehmer, die durch je eine (unbegrenzte) Warteschlange repräsentiert sind. Die Warteschlangen werden sämtlich nach dem Silo-(Fifo-)Prinzip abgearbeitet. Die Zwischenankunftszeiten für die Nachrichten sind für jede der Warteschlangen exponentialverteilt. Für jeden der Teilnehmer ist die mittlere Zwischenankunftszeit der Nachrichten gleich a. Die Übertragungsdauer der Nachrichten verteilt sich so: 90% der Nachrichten beanspruchen 100 µs und die restlichen 10% beanspruchen 600 µs. Die mittlere Nachrichtendauer ist folglich gleich b = 150 µs. Die Nachrichtendauern sind unabhängig voneinander. Die Übertragung des Tokens dauert c = 100 µs. Die Grenze für die Sendeberechtigung ist so festgelegt: Jeder Teilnehmer darf nach Erhalt des Staffelholzes höchstens eine Nachricht senden. Welcher Prozentsatz von Nachrichten hat eine Wartezeit von mehr als 100 ms, wenn die mittlere Zwischenankunftszeit a = 18 ms ist? Auf welchen Prozentsatz kommt man für a = 16 ms?

Hinweise zur Validierung des Simulationsmodells: Die kleinste mittlere Zwischenankunftszeit, die vom System verkraftet werden kann, lässt sich folgendermaßen abschätzen: Die größte Token-Umlaufzeit ergibt sich, wenn jede Warteschlange wenigstens ein Element enthält. Für diesen Hochlastfall ist die mittlere Token-Umlaufzeit gleich (b + c) n = 15ms. Das ist der mittlere zeitliche Abstand, in dem jede der Warteschlangen bedient wird. Die Zwischenankunftszeit a darf nicht kleiner als dieser Wert sein. Für den Niedriglastfall ergibt sich die Token-Umlaufzeit zu c× n = 6 ms.

4.6 Rechnernetz mit adaptivem Routing

Gegeben sei ein Rechnernetz mit n Knoten. Die Menge der Knoten des Netzes wird mit N bezeichnet. Die Verbindungen stellen eine Relation R zwischen den Knoten dar: (k, j) Î R genau dann, wenn es eine direkte Verbindung von Knoten k nach Knoten j gibt. Jede Nachricht soll so durch das Netz laufen, dass sie mit möglichst geringer Verzögerung (Delay) am Zielort eintrifft. Die Wegauswahl soll sich automatisch den Lastzuständen im Netz anpassen und im Falle von Ausfällen einzelner Verbindungen den Verkehr so gut es geht aufrechterhalten (adaptives Routing). Das Netz soll also fehlertolerant sein und die Fähigkeit zur angemessenen Leistungsminderung (Graceful Degradation) im Fehlerfall besitzen.

Falls eine direkte Verbindung von k nach j existiert, dann gibt es im Knoten k einen Sendepuffer für all jene Nachrichten, die über diese Verbindung gehen sollen. Der Sendepuffer wird nach dem Fifo-Prinzip (First in first out) verwaltet. Die Anzahl der Nachrichten im Sendepuffer von Knoten k zum Nachbarknoten j wird mit wk(j) bezeichnet.

Jede Nachricht enthält ein Datenfeld mit der Adresse des Zielknotens. Jeder Knoten k besitzt eine Delay-Tabelle, in der zu jedem Zielknoten i und jedem Nachbarknoten j derjenige Zeitbedarf dk(i, j) festgehalten ist, den eine Nachricht bis zur Erreichung ihres Zieles insgesamt braucht, wenn sie als nächstes zum Knoten j gesendet wird - und falls ab Knoten j die jeweils günstigste Verbindung gewählt wird. Falls es zum Knoten j überhaupt keine direkte Verbindung gibt, ist dk(i, j) = ¥ für alle möglichen Zielknoten i.

Die Länge der Nachrichten ist konstant. Die Übertragungsdauer (Sendedauer) für eine Nachricht wird als Zeiteinheit gewählt. Vorausgesetzt, die Zeit vom Sendebeginn bis zum vollständigen Empfang der Nachricht beträgt genau eine Zeiteinheit, dann wäre für die Verzögerung zwischen Nachbarknoten a = 1 zu setzen: Die endliche Ausbreitungsgeschwindigkeit und die Verarbeitungszeiten werden in diesem Fall vernachlässigt. Andernfalls ist die Verzögerung a > 1.

Die Tabelle wird nach folgendem Algorithmus aktualisiert (Kleinrock, II, 1976, S. 424 ff.):

1. Initialisierung: Es wird dk(i, j) = a gesetzt, falls (k, i) Î R und i = j. Für alle anderen Kombinationen (i, j) ist dk(i, j) = ¥ . Es wird a = 4 gewählt.

2. Jeder Knoten übermittelt in regelmäßigen Zeitabständen seine Delay-Tabelle an sämtliche Nachbarknoten. Sobald ein Knoten k eine Tabelle vom Knoten m erhält, aktualisiert er seine Delay-Tabelle nach folgender Vorschrift:

dk(i, m) = a + wk(m) + minjÎ N dm(i, j)

Eine Übermittlung der vollständigen Delay-Tabelle ist offensichtlich unnötig: Es reicht, die Minimalwerte minjÎ N dm(i, j) zu übermitteln.

Der Knoten k sendet Nachrichten mit dem Zielknoten i grundsätzlich über den Knoten j, für den der Ausdruck dk(i, j) minimal wird.

4.6.1 Netz mit Ringstruktur. Das betrachtete Netzwerk ist ein Voll-Duplex-Ring. Die Netzknoten werden durchnumeriert: 0, 1, 2, ..., n-1. Verbindungen bestehen jeweils zwischen Knoten i und Knoten (i+1) mod n und umgekehrt. Falls das Netz aus 3 Knoten besteht, haben wir also folgende Relation: R = [(0, 1), (1, 0), (1, 2), (2, 1), (2, 0), (0, 2)].

Jeder Netzknoten kann gleichzeitig von seinen Nachbarknoten Nachrichten empfangen und an diese senden. Für jede Richtung hat der Knoten einen unerschöpflichen Sendepuffer.

Das Datenaufkommen wird durch die Angaben von
- Quellknoten
- Zielknoten und
- mittlerer Zwischenankunftszeit der Nachrichten für diese Verbindung
vorgegeben. Die Zwischenankunftszeiten werden als exponentialverteilt vorausgesetzt.

Das Simulationsmodell ist so zu gestalten, dass man gegebenenfalls in Einzelschritten von Ereignis zu Ereignis vorangehen kann. An jedem Haltepunkt sind die Füllstände der Sendepuffer sowie die Delay-Tabellen auszugeben. Es soll möglich sein, den Inhalt der Sendepuffer zu inspizieren.

Quellen

Bamberg, G.; Coenenberg, A. G.: Betriebswirtschaftliche Entscheidungslehre. Vahlen, München 1989

Beck-Bornholdt, H.-P.; Dubben, H.-H.: Der Schein der Weisen. Irrtümer und Fehlurteile im täglichen Denken. rororo, Reinbek bei Hamburg 2003 (Abschnitt 21: Chancenungleichheit für alle. S. 237 ff.)

Bratley, P; Fox, B. L.; Schrage, L. E.: A Guide to Simulation. Springer, New York 1987

Bruss, F. T.: Mathematische Unterhaltungen. Strategien der besten Wahl. Spektr. d. Wiss. (2004) 5, 102-104

Dahl, O.-J.; Dijkstra, E. W.; Hoare, C. A. R.: Structured Programming. Academic Press 1972

Dinkelbach, W.: Entscheidungsmodelle. de Gruyter Berlin, New York 1982

Kleinrock, L.: Queuing Systems. Vol. 1: Theory. Wiley-Interscience 1975

Kleinrock, L.: Queuing Systems. Vol. 2: Computer Applications. Wiley-Interscience 1976

Knuth, D.: The Art of Computer Programming. Vol. 1: Fundamental Algorithms. Addison-Wesley, Reading Mass. 1973

Krüger, S.: Simulation. De Gruyter Berlin, New York 1975

Lamprecht, G.: Simula. Einführung in die Programmiersprache. Vieweg, Braunschweig 1988

Michalewicz, Zbigniew und Matthew: Puzzle-based learning. An introduction to critical thinking, mathematics, and problem solving. Melbourne 2008

Neubäumer, R.; Hewel, B. (Hrsg.): Volkswirtschaftslehre. Gabler, Wiesbaden 1998

Neumann, K.: Dynamische Optimierung. BI Mannheim 1969

Page, B.: Diskrete Simulation. Eine Einführung in Modula-2. Springer, Berlin, Heidelberg 1991

Papoulis, A.: Probability, Random Variables, and Stochastic Processes. McGraw-Hill, New York 1965

Paulsen, A.: Allgemeine Volkswirtschaftslehre. Band I. de Gruyter, Berlin 1970

Sasieni, M.; Yaspan, A.; Friedman, L.: Methoden und Probleme der Unternehmensforschung. Physica-Verlag Würzburg, Wien 1965

Schöne, A.: Simulation technischer Systeme. 3 Bände. Hanser-Verlag München, Wien 1974

Stobbe, A.: Gesamtwirtschaftliche Theorie. Springer, Berlin, Heidelberg, New York 1975

Todd, P. M.; Miller, G. F.: From Pride and Prejudice to Persuasion. Satisficing in Mate Search. In "Simple Heuristics that make us smart", S. 287-308, Herausgeber: Gigerenzer, G.;Todd, P. M.; and the ABC Research Group. Erschienen bei Oxford University Press, New York, 1999

Wilson, E. O.; Bossert, W. H.: Einführung in die Populationsbiologie. Springer-Verlag Berlin 1973

Zur Seite Simulation

© Timm Grams, 5. September 2009 (letzte Änderung)