lehrkraefte:blc:informatik:glf4-23:fluege-ueberbuchen [https://fginfo.ksbg.ch Fachgruppe Informatik der KSBG]

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
~~NOTOC~~

eventuell nützlich: Liste (mit Links zu Erklärungen) aller Excel-Funktionen auf [[https://support.microsoft.com/en-us/office/excel-functions-alphabetical-b3944572-255d-4efb-bb96-c6d90033e188|englisch]] bzw. [[https://support.microsoft.com/de-de/office/excel-funktionen-alphabetisch-b3944572-255d-4efb-bb96-c6d90033e188|deutsch]].

====== Überbuchen von Flügen ======

Fluggesellschaften überbuchen Ihre Flüge, d.h. Sie verkaufen möglicherweise mehr Sitzplätze als überhaupt vorhanden. Der Grund ist, dass Flugpassagiere mit einer gewissen Wahrscheinlichkeit aus irgendwelchen Gründen gar nicht zum Flug erscheinen. Sollten trotzdem zu viele Leute erscheinen, werden Freiwillige gesucht (oft auch mit Entschädigungen) die dann auf andere Flüge umbuchen.

==== Annahmen ====
  * Ein Flugpassagier erscheint nicht zum Flug mit Wahrscheinlichkeit $p=0.05$.
  * Wir betrachten ein Flugzeug mit $n=300$ Plätzen.
==== Fragestellung ====
  * Wie viele Tickets sollen verkauft werden, damit mit 99%-iger Wahrscheinlichkeit alle erscheinenden Passagiere auch einen Sitzplatz haben?

===== Vorbereitung und Layout der Arbeitsmappe =====
  * Die Simulation eines Flugs wird in einer Spalte stattfinden (die dann kopiert werden kann).
  * Die grün markierten Zellen enthalten die Parameter und sind entsprechend benannt, damit diese in den Formeln verwendet werden können.

{{:lehrkraefte:blc:informatik:glf4-20:simulation:pasted:20210416-100419.png}}


===== Markieren mit Tastenkombinationen =====
In vielen Programmen kann mit der Shift-Taste und einer Bewegung Inhalt markiert werden.
  * Z.B. mit <key>Shift</key>+<key>➜</key> Wird nach rechts markiert.
  * Mit <key>PgUp</key> und <key>PgDown</key> können grosse Sprünge gemacht werden.
  * Mit <key>Home</key>wird an den Anfang gesprungen, mit <key>End</key> wird ans Ende gesprungen.
  * Mit <key>Shift</key>+<key>Ctrl</key>+Pfeiltaste wird ans Ende des Inhalts gesprungen, was sehr praktisch ist.

===== Simulation eines Flugs =====
  * Ob ein Passagier rechtzeitig am Gate erscheint (1) oder nicht (0) kann mit folgender Formel ermittelt werden: ''=IF(RAND()<pshow,1,0)''. Sie müssen diese allerdings noch auf Deutsch übersetzen.
  * Diese Formel wird ca. 350 mal nach unten kopiert (für 350 potentielle Passagiere).
  * Die Anzahl tatsächlich erscheinender Passagiere ist die Summe der ersten ''tickets'' Zellen. Die Summe über einen variablen Bereich kann mit der Formel ''=SUM(OFFSET(C8,0,0,tickets,1))'' berechnet werden. Wieder Übersetzung auf Deutsch nötig. Dokumentieren Sie die Parameter der ''OFFSET''-Funktion.
  * Die Zelle OK soll 1 sein, wenn der alle erscheinenden Passagiere befördert werden können, sonst 0 (wenn Passagiere abgewiesen werden müssen).
  * Lassen die die Arbeitsmappe mehrmals durch Drücken der F9-Taste neu berechnen, "spielen" Sie mit den Parametern.


===== Simulation mehrerer Flüge =====
  * Kopieren Sie die 3. Spalte "einige Male" (zwischen 50 und 100) nach rechts.
  * Berechnen Sie dann den Durchschnitt der 6. Zeile (d.h. wie viel mal sämtliche erscheinende Passagiere befördert werden konnten).
  * Drücken Sie wieder mehrmals die F9-Taste, um die Arbeitsmappe neu zu berechnen. Versuchen Sie damit zu erraten, bei wievielen verkauften Tickets das Ziel von 99% Flügen ohne Abweisung möglich ist.

{{:lehrkraefte:blc:informatik:glf4-20:simulation:pasted:20210416-102056.png}}



===== Probleme mit der Simulation / mathematischer Ansatz =====
  * Die Simulation ist recht ungenau, man müsste eher 1000 oder gar mehr Spalten haben, um halbwegs aussagekräftige Resultate zu erhalten.
  * Die Anzahl erscheinender Passagiere folgt einer **Binomialverteilung** mit den Parametern $n$ (tickets) und $p=0.95$ (pshow).
  * Es ist möglich, solche Verteilungen mit Excel zu analysieren: Man verwendet dazu die Funktionen ''BINOM.DIST'' und ''BINOM.INV'' (bzw. deren deutsche Übersetzungen).
===== Mathematische Lösung mit ''BINOM.DIST'' =====

<hidden Ausklappbox, eventuell hilfreich zum systematischen Lernen der Befehle ''BINOM.DIST'' und ''BINOM.INV''>
Das folgende Spreadsheet/die folgende Tabelle selbst erstellen:

Die Befehle für die Zellen in den drei Tabellen sehen beispielsweise so aus:
  * Zelle E9: ''=IF(E$6<nowiki><=</nowiki>$A9, BINOM.DIST(E$6, $A9, p_erfolg, 0), 0)''
  * Zelle E29: ''=IF(E$6<nowiki><=</nowiki>$A29, BINOM.DIST(E$6, $A29, p_erfolg, 1), 0)''
  * gelbe Zelle I52: ''=IF(I$6<nowiki><=</nowiki>$A36, BINOM.INV($A52, p_erfolg, I$42), 0)''

(Der Befehl ''BINOM.INV'' wird erst im nächsten Abschnitt benötigt.)

{{:lehrkraefte:blc:informatik:glf4-20:simulation:pasted:binom-dist-und-binom-inv-lernen.png}}
</hidden>


  * Die Wahrscheinlichkeit, dass eine binomialverteilte Zufallsvariable einen bestimmten Wert überschreitet kann in Excel berechnet werden: ''=BINOM.DIST(plaetze,tickets,pshow,1)''
  * Anstatt der Zelle ''tickets'' erzeugen Sie eine Spalte mit Werten von 300 bis 330.
  * In der Spalte daneben, berechnen Sie die Wahrscheinlichkeiten, dass der Flug überbucht ist.
  * Plotten Sie am Schluss die Wahrscheinlichkeiten, dass kein Passagier abgewiesen werden muss.

{{:lehrkraefte:blc:informatik:glf4-20:simulation:pasted:20210416-104722.png}}

===== Mathematische Lösung mit ''BINOM.INV'' (Experte) =====

Der Funktionsaufruf ''=BINOM.INV(320, pshow, 0.99)'' liefert die kleinste Zahl $x$, so dass bei ''320'' verkauften Tickets die Wahrscheinlichkeit, dass höchstens $x$ Passagiere erscheinen, grösser-gleich ''0.99'' ist. Als Ergebnis liefert Excel ''312''. Dies bedeutet, dass die Wahrscheinlichkeit, dass höchstens 312 Passagiere erscheinen, mindestens 0.99 ist; hingegen ist die Wahrscheinlichkeit, dass höchstens 311 Passagiere erscheinen, echt kleiner als 0.99 ist. Mit anderen Worten: Bei 320 verkauften Tickets sollte das Flugzeug 312 Plätze haben, damit mit mindestens 99%-iger Wahrscheinlichkeit alle erscheinenden Passagiere einen Platz bekommen. "Offizielle" Erklärung:
  * ''BINOM.INV'' "Returns the smallest value for which the cumulative binomial distribution is greater than or equal to a criterion value." Referenz: https://help.libreoffice.org/7.3/en-US/text/scalc/01/04060181.html?&DbPAR=SHARED&System=UNIX
<!--  * <del>Es ist möglich, solche Zufallszahlen in Excel zu generieren: ''=BINOM.INV(tickets,pshow,RAND())''  (Übersetzung auf Deutsch nötig).</del>
  * <del>Berechnen Sie in der ersten Spalte einige Tausend dieser Zufallswerte und berechnen Sie dann die Wahrscheinlichkeit, dass keine Passagiere abgewiesen werden müssen.</del>
-->

Im Screenshot ist die markierte Box diejenige, die zeigt, dass man maximal 307 Tickets verkaufen sollte.

{{:lehrkraefte:blc:informatik:glf4-20:simulation:pasted:binom-inv-kumulativ.png}}


===== Gewinnmaximierende Lösung (Experte) =====
  * Wir nehmen grosszügig an, dass sich die Kosten, einen Passagier abzuweisen, das 10-fache eines Ticket-Preises betragen (darin ist z.B. neben der Entschädigung und dem Aufwand für die Umbuchung auch der Reputationsverlust eingerechnet).
  * Wie weit kann dann ein Flugzeug mit 300 Plätzen überbucht werden, um die Einnahmen zu maximieren (in Tickets gerechnet).
  * Dazu müssen wir ausrechnen, wie viele Passagiere im Durchschnitt abgewiesen werden, bei einer gegebenen Anzahl verkaufter Tickets.
    * Sei $X = \text{Bin}(t,p)$ eine binomialverteilte Zufallsvariable ($t=$ Anzahl der Experimente, hier der verkauften Tickets; $p=$ Wahrscheinlichkeit (dass ein Passagier kommt)). Sei $m$ die Anzahl verfügbarer Plätze. <!--, $t$ die Anzahl verkaufter Tickets.-->
    * Die Zufallsvariable $Y$ entspricht der Anzahl abgewiesener Personen und ist $0$, wenn $X\leq m$ gilt, und sonst $X-m$.
    * $P(Y=0) = P(X\leq m)$ und $P(Y=k) = P(X=k+m)$ für alle $k\geq 1$.
    * Damit ist der Erwartungswert (also die erwartete Anzahl abgewiesener Passagiere) $$E(Y) = \sum_{k=1}^{t-m} 10 \cdot k \cdot P(Y=k) =  \sum_{k=1}^{t-m} 10 \cdot k \cdot P(X=m+k)$$ (um die erwarteten Kosten zu erhalten, muss man diese Zahl mit 10 multiplizieren).
  * Für alle Werte von $t$ (tickets) und alle Werte von $k$ (zu viel erscheinende Passagiere) berechnen Sie $k \cdot P(X=m+k)$ und summieren Sie über $k$, um den Erwartungswert zu erhalten.
  * Berechnen Sie dann die Einnahmen (in Anzahl Tickets) und bestimmen Sie die optimale Anzahl.
  * Verändern Sie dann die Kosten einen Abweisung und betrachten Sie die Wahrscheinlichkeit einer Abweisung beim Optimum. Fällt Ihnen ein Zusammenhang auf? Können Sie diesen erklären?
  * Link zur [[https://fginfo.ksbg.ch/~ivo/videos/informatik/excel/tabellenkalkulation-simulation-ueberbuchung-expert.mp4|Videoanleitung]] und auch auf [[https://web.microsoftstream.com/video/a9073adf-b197-4ecf-b53a-c01474098779|Stream]].