Warteschlangentheorie

Transcript

Warteschlangentheorie FT 2014 Übung 1 Dr. Andreas Löpker Aufgabe 1: Eine Zufallsvariable X mit Werten in der Menge N = {1, 2, . . .} besitzt die Wahrscheinlichkeitsfunktion f (n) = P (X = n) = 2−n , n ∈ N. (a) Berechnen Sie P (X = 2), P (X < 2) und P (X > 2). (b) Berechnen Sie E(3−X ). Aufgabe 2: In einer Warteschlange sei T1 die Ankunftszeit des ersten Kunden. Die Verteilungsfunktion von T1 sei   ; x<2 0 F (x) = P (T1 ≤ x) = 91 (x − 2)2 ; x ∈ [2, 5)  1 ; x≥5 (a) Zeichnen Sie F (x). Ist F wirklich eine Verteilungsfunktion? (b) Berechnen Sie die zugehörige Dichte f (x). (c) Berechnen Sie P (X ≤ 3). (d) Berechnen Sie P (X ∈ (3, 4]). (e) Wie groß ist der Erwartungswert von X? (f) Berechnen Sie die Varianz von X. Aufgabe 3: X besitze eine Binomialverteilung mit n = 10 und p = 0.1. Berechnen Sie P (X ≤ 3). Aufgabe 4? : X sei eine Zufallsvariable, die nur die beiden Werte a und b annimmt. Es gelte P (X = a) = p, P (X = b) = 1 − p. Zeigen Sie, dass die Varianz von X niemals größer als
a−b 2 2 ist. Warteschlangentheorie Übung 2 FT 2014 Dr. Andreas Löpker Aufgabe 5: In einer Warteschlange seien die Zwischenankunftszeiten A1 , A2 , . . . exponentiell verteilt mit Parameter λ = 2 min−1 . (a) Wie lange dauert eine Zwischenankunftszeit im Mittel? (b) Wie groß ist die Wahrscheinlichkeit, dass der erste Kunde erst nach mehr als drei Minuten erscheint? (c) Angenommen der erste Kunde erreicht die Warteschlange vor Ende der zweiten Minute. Wie groß ist die Wahrscheinlichkeit dass er erst nach der ersten Minute erschien? (d) Mit welcher Wahrscheinlichkeit kommt der sechste Kunde vor der zweiten Minute an? Aufgabe 6: Es sei N (t) ein Poisson-Prozess der den Ankunftsprozess einer Warteschlange beschreibt. Die Ankunftsrate betrage 10 Kunden pro Stunde. (a) Wie groß ist die Wahrscheinlichkeit, dass in 5 Minuten mehr als ein Kunde erscheint? (b) Sie schließen die Wette ab, dass in den ersten 12 Minuten kein Kunde ankommt. Ihr Wetteinsatz ist ein Euro. Die Wettquote beträgt q, d.h. wenn sie Recht behalten, erhalten Sie q Euro. Berechnen Sie q (in Abhängigkeit von x) so, dass sie im Mittel x Euro gewinnen bzw. verlieren. Bei welchem q machen Sie im Mittel weder Gewinn noch Verlust? Aufgabe 7: Es sei Y eine geometrisch Verteilte Zufallsvariable vom Typ II (siehe Vorlesung). Berechnen Sie für ein beliebiges m ∈ {0, 1, 2, 3, . . .} die Wahrscheinlichkeit, dass X ≥ m ist. Warteschlangentheorie Übung 3 FT 2014 Dr. Andreas Löpker Aufgabe 8: In einer Warteschlange mit einer Bedienstation, kommen die ersten 7 Kunden zu den Zeiten 2, 6, 7, 10, 17, 18 und 25 Minuten an. Ihre Bedienzeiten betragen jeweils 9, 4, 1, 2, 3, 3 und 2 Minuten. Zeichnen Sie den Verlauf des Prozesses Xt , der die Anzahl der Kunden im System beschreibt, für 0 ≤ t ≤ 28. Tragen Sie die die Leer- und Besetztzeiten, die Ankunftszeitpunkte und Abgangszeitpunkte ein. Aufgabe 9: In einer M/M/1-Wartschlange beträgt die mittlere Zwischenankunftszeit 7 Minuten. Die Bearbeitungszeit dauert im Mittel 5 Minuten. (a) Wie viele Kunden sind im Mittel nach 10 Minuten angekommen? (b) Nach 10 Minuten ist das Wartesystem bereits seit 3 Minuten leer. Wie groß ist die Wahrscheinlichkeit, dass das System noch weitere 3 Minuten leer bleibt. (c) Nach 20 Minuten ist ein Kunde in Bearbeitung. Wie groß ist die Wahrscheinlichkeit, dass dieser Kunde noch mindestens 8 Minuten im System verbleibt? (d) Berechnen Sie die Verkehrsintensität. (e) Wie groß ist die Wahrscheinlichkeit im System mehr als m Kunden vorzufinden? (f) Mit welcher Wahrscheinlichkeit muss ein ankommender Kunde nicht warten? Aufgabe 10: Eine M/M/1-Warteschlange erreichen im Schnitt stündlich 10 Kunden. Die durchschnittliche Bearbeitungszeit eines Kunden ist 5 Minuten. Angenommen, die Warteschlange befinde sich im stationären Zustand. (a) Wie groß ist die Auslastung. (b) Wie groß ist die Wahrscheinlichkeit im System exakt 3 Kunden anzutreffen? Wie groß ist die Wahrscheinlichkeit, dass sich mehr als 3 Kunden im System befinden? (c) Wie groß ist die erwartete Kundenzahl im System? (d) Um wie viel Prozent erhöht sich die erwartete Kundenzahl, wenn die Ankunftsrate um 1% steigt? Warteschlangentheorie FT 2014 Übung 4 Dr. Andreas Löpker Aufgabe 11: An einem Schalter werden Konzertkarten verkauft. Es kommt im Mittel ein Kunde pro Minute an. Die Zwischenankunftszeiten und die Bedienzeiten seien exponentiell verteilt. Für den Verkauf einer Karte werden im Mittel 50 Sekunden benötigt. Eine Karte kostet regulär 15 Euro. (a) Wie viele Kunden sind im Mittel im System? Wie groß ist die Wahrscheinlichkeit, dass mehr als 10 Kunden im System sind? (b) Wie lange warten die Kunden durchschnittlich in der Schlange? (c) Ein Ticketverkäufer bietet folgenden Deal an. Kunden zahlen für die Konzertkarte 20 Euro, wenn sie weniger als 10 Minuten in der Warteschlange warten. Ansonsten ist die Karte schon für 2 Euro zu haben. Lohnt sich das für die Kunden? (d) Ein Kunde erreicht den Schalter und findet 6 Kunden in der Warteschlange, sowie einen Kunden am Schalter vor. Er hat nur 5 Minuten Zeit. Wie groß ist die Wahrscheinlichkeit, dass er noch eine Karte bekommt und rchtzeitig das System verlässt? Aufgabe 12: Eine Markovkette Xn mit drei Zuständen 1, 2 und 3 besitze die folgende Übergangsmatrix.   0 0.5 0.5 P =  0.5 0.5 0  1 0 0 (a) Zeichnen Sie ein Übergangsdiagramm. (b) Berechnen Sie P (X1 = 2|X0 = 1) und P (X3 = 1|X0 = 3) Aufgabe 13: Ein Markovkette in stetiger Zeit besitzt  −3 2.4 Q =  1 −2 0.4 3.6 folgende Intensitätsmatrix:  0.6 1 −4 (a) Bestimmen Sie λ und P . (b) Wie viele Lösungen besitzt das lineare Gleichungssystem Q · x = 0? Warteschlangentheorie FT 2014 Übung 5 Dr. Andreas Löpker Aufgabe 14: An einem Flughafen warten Taxis mit vier Sitzplätzen auf Gäste. Ein Taxi wartet jeweils solange, bis alle Plätze belegt sind und fährt dann sofort los. Das nächste Taxi rückt unmittelbar nach. Der Ankunftsprozess der Kunden sei ein Poissonprozess, es kommen im Mittel 6 Kunden in einer Stunde an. Es sei Kt die Zahl der wartenden Kunden. (a) Beschreiben Sie Kt als Markovkette in stetiger Zeit mit vier Zuständen {0, 1, 2, 3}. Zeichnen Sie ein Übergangsdiagramm. (b) Geben Sie die Intensitätsmatrix an. (c) Die stationäre Verteilung π erfüllt die Gleichungen π0 + . . . + π3 = 1 und πQ = 0. Lösen Sie die Gleichung. Aufgabe 15: Gegeben Sei eine Warteschlange mit einer Bedienstation, exponentiellen Ankünften und exponentiellen Bedienzeiten mit einer mittleren Dauer von 2 Minuten. Die Ankunftsrate λ(k) sei von der Zahl der Kunden k im System abhängig (Kunden werden durch eine lange Warteschlange abgeschreckt), es gelte: λ(k) = 5 min−1 1+k Es sei wie üblich Xt die Anzahl der Kunden im System. (a) Geben Sie ein Übergangsdiagramm für den Geburts- und Todesprozess Xt an. (b) Ist der Prozess rekurrent und ergodisch? (c) Wie lautet die stationäre Verteilung? ∞ X k x x /k! = e Hinweis: k=0 Aufgabe 16: Folgende Übergangsdiagramme gehören zu drei Geburts- und Todesprozessen. Stellen Sie fest, unter welchen Bedingungen eine Grenzverteilung existiert und bestimmen Sie diese. Warteschlangentheorie Übung 6 FT 2014 Dr. Andreas Löpker Aufgabe 17: In einer Telefonzelle dauern die Gespräche im Mittel 160 Sekunden. Es kommt im Mittel jede Minute ein Kunde an, der telefonieren möchte. Ist die Zelle besetzt, so gehen die Kunden weiter zur nächsten Telefonzelle. Wie groß ist die Wahrscheinlichkeit eine besetzte Zelle vorzufinden? Aufgabe 18: Pro Tag erreichen durchschnittlich 6 Touristen einen Urlaubsort. Sie bleiben im Mittel 5 Tage (die Aufenthaltszeit sei exponentiell verteilt). Wie groß ist die Wahrscheinlichkeit, in dem Ort exakt 25 Touristen anzutreffen. Aufgabe 19: Berechnen Sie für die M/M/1/K-Warteschlange den Grenzwert für K → ∞ der Wahrscheinlichkeit zurückgewiesen zu werden. Unterscheiden Sie die Fälle % < 1, % = 1 und % > 1. Aufgabe 20: Eine Arztpraxis möchte einen Warterraum einrichten. Sie rechnet mit einem Patientenaufkommen von 9 Patienten pro Stunde. Eine Konsultation dauert im Mittel 6 Minuten. Wie viele Patienten muss das Wartezimmer aufnehmen können, wenn die Wahrscheinlichkeit ein volles Wartezimmer anzutreffen weniger als 5 Prozent betragen soll? Aufgabe 21: In einer M/M/1/2 Warteschlange mit Ankunftsrate 1 min−1 soll die Wahrscheinlichkeit einer Zurückweisung 10 Prozent betragen. Wie schnell muss die Bedienstation arbeiten? Warteschlangentheorie Übung 7 FT 2014 Dr. Andreas Löpker Aufgabe 22: An einem Würstchenstand gibt es 3 Mitarbeiter. Die Zubereitung und der Verkauf eines Würstchens dauert im durchschnittlich 45 Sekunden. Im Mittel besuchen 200 Kunden pro Stunde den Stand. (a) Wie groß ist die Wahrscheinlichkeit, dass alle drei Mitarbeiter nichts zu tun haben? (b) Wie groß ist die Wahrscheinlichkeit, dass ein Kunde nicht warten muss? (c) Wie lange muss man im Mittel warten? Aufgabe 23: An einer Autowaschstation gibt es 8 Plätze an denen Autos vom Benutzer gewaschen werden können. Im Durchschnitt dauert so ein Vorgang 10 Minuten. Stündlich erreichen im Mittel 30 Autos die Anlage. Sie warten gegebenenfalls auf einem Parkplatz vor der Station bis ein Platz in der Station frei wird. (a) Wie groß ist die Wahrscheinlichkeit nicht warten zu müssen ? (b) Wie viele Kunden findet man im System durchschnittlich vor? (c) Wie lange muß man durchschnittlich warten? Aufgabe 24: In einer Maschine werden Schokoladen verpackt. Dabei können bis zu drei Tafeln gleichzeitig verpackt werden. Die Verpackung einer Tafel dauert im Mittel 2 Sekunden, pro Minute kommen im Mittel 60 Tafeln auf einem Transportband an. Ist die Maschine komplett ausgelastet, so müssen die ankommenden Tafeln zur nächsten Maschine (die hier nicht betrachtet wird) weitergeleitet werden. (a) Wie viel Prozent der Tafeln werden an dieser Maschine bedient? (b) Wie viele Tafeln sind im Mittel in der Maschine in Bearbeitung? Warteschlangentheorie Übung 8 FT 2014 Dr. Andreas Löpker Aufgabe 25: Ein Wartezimmer bei einem Arzt hat 4 Warteplätze. Pro Tag (10h) besuchen im Durchschnitt 60 Patienten den Arzt. Jeder von Ihnen bleibt im Mittel 12 Minuten. Wir groß ist die Wahrscheinlichkeit, dass ein Patient ein volles Wartezimmer antrifft. Aufgabe 26: Auf einer Party befinden 20 Raucher, von denen jeder einmal in 120 Minuten auf den Balkon geht um eine Zigarette zu rauchen (Verweilzeit im Durchschnitt 2 Minuten). Leider können nur maximal zwei Personen gleichzeitig den kleinen Balkon betreten. Mit welcher Wahrscheinlichkeit werden Partygäste am Rauchen gehindert, weil sie einen vollen Balkon vorfinden? Aufgabe 27: In einer Fabrik stehen 10 Maschinen, die im Durchschnitt in einer Woche sechsmal ausfallen. Ein Team von 3 Mitarbeitern ist für die Reparatur zuständig. Diese dauert im Mittel einen Tag. Wie groß ist die Wahrscheinlichkeit, dass eine ausfallende Maschine nicht sofort repariert werden kann? Aufgabe 28: An einer Leuchtreklame gibt es 20 Lichter, die jeweils für eine exponentielle Zeitspanne (Mittelwert 2 Sekunden) leuchten und dann für eine exponentielle Zeitspanne (Mittelwert 1 Sekunde) aus sind. Die Leuchtreklame wird fotografiert. Wie groß ist die Wahrscheinlichkeit, dass auf dem Foto genau die Hälfte der Lichter leuchten?   0 1 0 Aufgabe 29: Gegeben Sei die Matrix P = 0.5 0 0.5. 0.5 0 0   1 0 0 (a) Berechnen Sie die Matrix (I − P )T . Dabei ist I = 0 1 0 die Einheitsmatrix. 0 0 1   0 (b) Lösen Sie das lineare Gleichungssystem (I − P )T x = λ. 0 Aufgabe 30: (?) An einer M/M/1-Warteschlange kommen im Mittel 20 Kunden pro Stunde an. Das System befinde sich im Gleichgewicht. Wie groß ist die Wahrscheinlichkeit, dass nach t Zeiteinheiten die Zahl der bereits vollständig bedienten Kunden kleiner ist, als die Zahl der Kunden die zu dem Zeitpunkt im System sind? Warteschlangentheorie Übung 9 FT 2014 Dr. Andreas Löpker Aufgabe 31: Eine M/M/1-Warteschlange befinde sich im stationären Zustand. Es sei λ = 4 h−1 , µ = 5 h−1 . Wie lange dauert es im Mittel bis der erste Kunde das System verlässt? Aufgabe 32: Gegeben sei folgendes Netzwerk von M/M -Warteschlangen: (a) Berechnen Sie die Grenzverteilung des obigen Netzwerks. (b) Bestimmen Sie die Wahrscheinlichkeit zwei, einen und keinen Kunden in den Warteschlangen 1, 2 und 3 vorzufinden. (c) Mit welcher Wahrscheinlichkeit befinden sich in den drei Wartesystemen gleich viele Kunden? Aufgabe 33: Gegeben sei folgendes Tandem-Warteschlangensystem mit Rücklauf. (a) Bestimmen Sie die Grenzverteilung. (b) Es sei p = 1/2, λ = 2 und µ1 = µ2 = 6. Wie groß ist die Wahrscheinlichkeit dass sich in der ersten Warteschlange nicht weniger Kunden befinden, als in de zweiten? Warteschlangentheorie Übung 10 FT 2014 Dr. Andreas Löpker Aufgabe 34: Im folgenden Netzwerk befinden sich drei Wartesysteme mit insgesamt drei Kunden. Bestimmen Sie die Grenzverteilung. Berechnen Sie die Wahrscheinlichkeit in jeder Station genau einen Kunden anzutreffen. Aufgabe 35: Zwei Kunden halten sich in folgendem Netzwerk auf. Bestimmen Sie die gemeinsame Grenzverteilung für die Kundenzahl in den 4 Wartesystemen. Aufgabe 36: Gegeben sei folgendes System mit drei Servern und drei Warteschlangen. Die Bedienzeiten seien 3h,1h und 4h. Im System befinden sich 5 Kunden. Bestimmen Sie die gemeinsame Grenzverteilung der Kundenzahlen.