Weihnachtsmann rot

Aufgabe vom 10. Dezember

Chaos in der Plätzchenfabrik

Autoren: Miriam Schlöter, Leon Sering

Aufgabe:

Wie konnte das passieren? Jetzt haben sich nicht nur die Mathematiker-Helfer-Elfin Alvina und ihr Vertreter Melvin BEIDE krank gemeldet, sondern auch die Rentiere der Rudolphs Heiligabend Logistik (RHL) drohen mal wieder damit, ihre Arbeit niederzulegen. Rudolph und der Weihnachtsmann könnten sich glatt die Kerzen vom Weihnachtsbaum reißen. Immerhin ist die erste Verhandlungsrunde mit der Vereinten Rentier Gewerkschaft (VeR.ti) halbwegs gut verlaufen. Die Plätzchenfabrik versinkt derweil im Chaos: Tausende von Helfer-Elfen, die eigentlich die fertigen Plätzchen von der Plätzchenfabrik zum Schlittenstartplatz bringen sollten, schreien durcheinander, laufen im Kreis und bewerfen sich mit Kekskrümeln und Mehl.

„Es reicht“, ruft der Weihnachtsmann und schlägt so heftig auf den Tisch, dass Rudolph vor Schreck seinen Spekulatius fallen lässt, den er gerade in seinen Morgen-Kakao tunken wollte. „Du sorgst dafür, dass die Rentiere wieder den ganzen Tag Plätzchen ausliefern und ich sorge dafür, dass so viele Plätzchen wie möglich zum Schlittenstartplatz transportiert werden!“

Ein Telefonat später:

Rudolph: Die Rentiergewerkschaftsversammlung stimmt heute um 17 Uhr über meinen Vorschlag ab. Wenn sie ihn annehmen, wird die letzte Lieferung um 23 Uhr abgeholt. Wenn der Vorschlag allerdings abgelehnt wird, werden die Rentiere keine weiteren Lieferungen beginnen. In diesem Fall können wenigstens alle Plätzchen, die bis 17 Uhr beim Schlittenstartplatz sind, ausgeliefert werden, alle Plätzchen, die nach 17 Uhr ankommen, werden allerdings nicht mehr ausgeliefert.

Weihnachtsmann: Ich habe keine Ahnung, wie Alvina und Melvin diesen chaotischen Haufen von Helfer-Elfen in den Griff bekommen haben! Wenigstens habe ich in deren Büro das Wegenetz zwischen der Plätzchenfabrik und dem Schlittenstartplatz gefunden. Das sieht eigentlich nicht so kompliziert aus, aber so richtig verstehe ich es trotzdem nicht...

PIC

Rudolph: Schau Weihnachtsmann, das ist eigentlich ganz einfach: Hier links kommen die Helfer-Elfen aus der Plätzchenfabrik und sollen ihre Plätzchen hier rechts zum Schlittenstartplatz befördern. Das Wegenetz besteht aus einzelnen Wegabschnitten. Es gibt kurze Wegabschnitte der Länge 2, d.h. die Helfer-Elfen brauchen 2 Stunden um diesen Wegabschnitt zu durchqueren, und längere Wegabschnitte der Länge 3. Weiterhin ist zu erkennen, dass es insgesamt drei verschiedene Wege gibt, die von der Plätzchenfabrik zum Schlittenstartplatz führen, denn alle Streckenabschnitte sind Einbahnstraßen von links nach rechts.

In unserer Plätzchenfabrik arbeiten Tausende von Helfer-Elfen, die im Vergleich zu den Wegen in der Fabrik sehr klein sind. Man muss sich die Helfer-Elfen, die sich durch das Wegenetz bewegen, deswegen eher wie eine Flüssigkeit vorstellen, die durch ein Netz aus Rohren fließt. Dabei werden die Elfen in Elfeneinheiten gemessen (eine Elfeneinheit besteht aus sehr vielen Elfen), wobei die Elfen die Plätzchenfabrik mit einer Rate von zwei Elfeneinheiten pro Stunde verlassen.

Unmittelbar am Anfang jedes Wegabschnitts gibt es einen Checkpoint (c), an dem überprüft wird, ob alle Plätzchenlieferungen noch vollständig sind. Der Überprüfungsprozess nimmt keine Zeit in Anspruch. Allerdings ist die Kapazität der Checkpoints begrenzt und es kann nur maximal eine Rate von einer Elfeneinheit pro Stunde kontrolliert werden. Man kann sich die Checkpoints also als eine Engstelle im Wegenetz vorstellen, an dem sich die Elfen aufstauen können.

Für den Fall, dass die Helfer-Elfen in einer höheren Rate an einem Checkpoint ankommen, als dieser überprüfen kann, gibt es einen extra Wartebereich neben der Strecke, in dem sich die Elfen anstellen. Die Warteschlange funktioniert dabei so, wie eine Flüssigkeit durch eine Engstelle fließt. Sind beispielsweise zwei Elfeneinheiten in der Warteschlange, müssen die Elfen ganz hinten genau zwei Stunden warten, bis sie den Checkpoint passieren können (siehe Abbildung 1).

Wichtig ist, dass wir uns jetzt möglichst schnell für eine Strategie entscheiden, denn dann können die Helfer-Elfen um 8 Uhr anfangen zu arbeiten. Damit so viele Plätzchen wie möglich ausgeliefert werden können, egal wie sich die Rentiere entscheiden, sollte unsere Strategie die Eigenschaft haben, dass bis 17 Uhr und bis 23 Uhr so viele Elfeneinheiten wie möglich am Schlittenstartplatz ankommen. Es kommen bis 17 Uhr (bzw. 23 Uhr) so viele Elfeneinheiten wie möglich an, wenn es keine Strategie gibt, in der bis 17 Uhr (bzw. 23 Uhr) mehr Elfeneinheiten am Schlittenstartplatz ankommen.


PIC

Abbildung 1: Die Funktionsweise eines Checkpoints, wenn eine Rate von zwei Elfeneinheiten pro Stunde den Checkpoint passieren wollen. Die Situation ist ein kontinuierlicher Prozess und wird in der Abbildung im Stundentakt angezeigt.

Weihnachtsmann: So ist das also... Dann ist es doch ganz einfach! Damit die Zahl der ausgelieferten Plätzchen maximal ist, egal wie die Abstimmung von Ver.Ti ausgeht, sollten wir alle Helfer-Elfen mit einer Rate von einer Elfeneinheit pro Stunde auf dem kürzesten Weg über die Brücke zum Schlittenstartplatz schicken.

Auch Knecht Ruprecht, der sich eben noch eine Eierschlacht mit den Helfer-Elfen geliefert hat, mischt sich grinsend ein:

Knecht Ruprecht: Ach, Weihnachtsmann! Das ist eine sehr schlechte Idee! Wenn alle Elfen nur den oberen Weg an den Zuckerbergen vorbei und den unteren Weg entlang des Weihnachtsbaumtestgeländes benutzen und das mit einer Rate von einer Elfeneinheit pro Stunde, dann können wir zu jedem Zeitpunkt viel mehr Elfeneinheiten losschicken, als bei deinem Plan. Das muss besser sein!

Der Weihnachtsmann beginnt verzweifelt sich Haarbüschel aus dem Bart zu reißen. Nur Rudolph bewahrt einen klaren Kopf. Nach einiger Zeit kommt ihm eine Idee.

Rudolph: Eure Ideen sind beide nicht gut, denn bei beiden Plänen bleiben Wege völlig ungenutzt! Ich weiß aber, wie wir die Helfer-Elfen durch das Wegenetz schicken können, sodass, egal wie die Verhandlungen mit den Rentieren ausgehen, immer so viele Plätzchen wie möglich von den Rentieren ausgeliefert werden. In meiner optimalen Strategie ist sogar um 15 Uhr schon eine komplette Elfeneinheit beim Startplatz.

Rudolph erklärt seinen Plan dem Weihnachtsmann, der erleichtert ruft: „So ist es gut. Es ist völlig egal, wie die Vereinte Rentier Gewerkschaft entscheidet, mehr Plätzchen können wir nicht transportieren lassen. Weihnachten ist gerettet!“

Über ein Megafon versuchen Rudolph und der Weihnachtsmann den Helfer-Elfen ihren Plan zu vermitteln. Doch diese maulen nur und wollen sich nicht darauf einlassen. Die Helfer-Elfen finden den Plan aus irgendeinem Grund ungerecht und dem Weihnachtsmann und Rudolph fehlt die Autorität, sich durchzusetzen. Am Ende verliert der Weihnachtsmann die Geduld und ruft völlig resigniert: „Okay dann machen wir es eben anders. Ihr dürft selber entscheiden, welchen Weg ihr nehmen wollt. Wer seine Plätzchen bei den Rentieren abgeliefert hat, darf nach Hause gehen!“

Auf diesen Arbeitsplan lassen sich die Elfen ein. Natürlich möchte nun jeder von ihnen so schnell wie möglich Feierabend haben und jeder Elf entscheidet sich, sobald er die Plätzchenfabrik verlässt, für den Weg, der ihn aktuell am schnellsten zum Schlittenstartplatz führt. Beim Verlassen der Plätzchenfabrik wissen die Helfer-Elfen dabei ganz genau, wie sie schnellstmöglich zum Schlittenstartplatz kommen, da sie auf einem Monitor am Ausgang der Fabrik beobachten können, wie viele Elfeneinheiten sich im Netzwerk befinden und wie sich die Warteschlangen vor den Checkpoints entwickeln werden.

Punkt 8 Uhr kommen die ersten Elfen aus der Fabrik und machen sich auf den Weg. Der Weihnachtsmann ist sich nicht sicher, ob das eine gute Idee von ihm war, denn bis kurz vor 10 Uhr wollen immer noch alle Elfen auf dem direkten Weg über die Brücke zum Schlittenstartplatz. Der erste Checkpoint auf der Strecke ist völlig überfordert und die anderen Wege blieben bisher völlig ungenutzt. Er überlegt schon, ob er die Elfen nicht irgendwie bestechen kann, damit sie sich doch noch gleichmäßiger auf die Wege verteilen, aber just in dem Moment, die Uhr schlägt gerade 10, gibt es die ersten Abweichler. Nun macht sich die Hälfte der Elfen plötzlich auf den Weg entlang des Weihnachtsbaumtestgeländes, während die andere Hälfte sich weiter stur in die Warteschlange des ersten Checkpoints einreiht.

Welche der folgenden Aussagen ist falsch?

Die Aufgabe als PDF runterladen

Antwortmöglichkeiten:

  1. Der Plan von Knecht Ruprecht führt zu einem optimalen Ergebnis, falls die Rentiere bis 23 Uhr abfliegen.

  2. In dem Arbeitsplan der Elfen sind die Wartezeiten vor den Checkpoints nie länger als zwei Stunden.

  3. In Rudolphs optimaler Strategie gibt es Elfen, die später beim Schlittenstartplatz ankommen als andere Elfen, obwohl sie früher losgehen müssen.

  4. Wenn die Rentiere um 17 Uhr zum letzten Mal starten, ist der Arbeitsplan, den die Elfen befolgen, genauso gut, wie die Strategie vom Weihnachtsmann; d.h. es kommen genauso viele Plätzchen an.

  5. In der Strategie vom Weihnachtsmann erreichen bis 23 Uhr 5 Elfeneinheiten weniger den Schlittenstartplatz als in Rudolphs optimaler Strategie.

  6. In dem Arbeitsplan der Elfen entscheiden sich manche Elfen, den oberen Weg zu benutzen.

  7. Die Strategie vom Weihnachtsmann ist optimal, wenn die Rentiere um 17 Uhr ihre letzte Lieferung starten.

  8. Im Arbeitsplan der Elfen kommen die Elfen, die früher aus der Plätzchenfabrik kommen, auch früher am Startplatz an.

  9. In Rudolphs optimaler Strategie würden mindestens 1,5-mal so viele Elfeneinheiten bis 23 Uhr am Startplatz ankommen, wie in dem Arbeitsplan, den die Elfen befolgen.

  10. In Rudolphs optimaler Strategie und dem Arbeitsplan der Elfen werden die Elfen in einem bestimmten Zeitintervall wie in Knecht Ruprechts Strategie geschickt.

Sie müssen sich einloggen um die Aufgaben abgeben zu können.