SVOR logo  SATW logo

Optimierungswettbewerb 2010

Am Wettbewerb dürfen Studenten der Gymnasien der Schweiz teilnehmen

 

Beschreibung des Wettbewerbs

deutsche Version (pdf), deutsche Version (docx)

 

Plakat

deutsche Version (pdf), deutsche Version (pptx)

 

Download

  • Das Problem
  • Zum Einsenden der Lösungen

    •  

     

    Einleitung

     

    Die Suche nach einem optimalen Versendungsplan in einem Netzwerk ist wegen der grossen Anzahl von möglichen Lösungen ein komplexes Problem. Es ist tatsächlich einfach, eine zulässige Lösung für ein solches Problem zu finden. Es erweist sich aber als sehr schwierig, die Optimalität einer Lösung zu beweisen.

     

    Das Problem der Versendung von Paketen in einem Netzwerk von Freunden in Facebook ist ein Beispiel für jene Probleme, die von der Operationsforschung (operations research) behandelt werden. Für solche Probleme ist es nur für kleine Netze möglich, die Optimalität einer Lösung per Aufzählung aller möglichen Lösungen zu beweisen. Die Operationsforschung bietet Methoden an, die die optimale Lösung finden, jedoch ohne dass jede mögliche Lösung ausgewertet wird.

     

    Die Operationsforschung ist eine Wissenschaft, die sich auf halbem Wege zwischen Informatik und Mathematik befindet. Sie stellt Entscheidungshilfe-Methoden bereit, um Optimierungsprobleme zu lösen, wie zum Beispiel die Bestimmung eines Versandplans mit minimalen Versandkosten.

     

    Um Operationsforschung bei den zukünftigen Universitätsstudenten bekannt zu machen, organisiert der Schweizerische Verband für Operations Research (SVOR) dieses Jahr einen Wettbewerb, der sich mit den sozialen Netzen in Facebook beschäftigt.

     

    Formulierung des Wettbewerbs

     

    Michel und Emma sind auf Facebook Freunde. Bald ist Emmas Geburtstag, und Michel möchte zu dieser Gelegenheit ein Fest organisieren. Michel benutzt Facebook um die 16 Freunden zu identifizieren, die er und Emma in verschiedenen Ländern gemeinsam haben. Dank eines Programms, das die Beziehungen zwischen den gemeinsamen Freunden anzeigt (es kann auf der Website http://danielmclaren.net/node/77 gefunden werden), erhält Michel den Graph aus Abbildung 1. Dieser ermöglicht ihm eine einfache Visualisierung davon, wer mit wem (auf Facebook) befreundet ist.

     

    Die Herausforderung für Michel ist, originelle Geschenke für Emma zu finden. Michel ist zur Zeit in Südafrika, um die Fußballweltmeisterschaft zu verfolgen. Er findet auf einem lokalen Markt eine Sammlung afrikanischer Masken, welche Emma mit Leidenschaft sammelt.

    Abbildung 1: Graph der Beziehungen zwischen Michels und Emmas gemeinsamen Freunden. Zwei Personen kennen sich, wenn sie mit einem Stich verbunden sind.

     

    Das Geschenk ist also gefunden! Damit das Geschenk ein grosser Erfolg wird, soll jeder Gast mit seiner eigenen Maske zum Fest kommen, um sie Emma zu schenken.

    Der Transport der Masken erweist sich leider als sehr kompliziert. Es ist unmöglich, alle Masken im Flugzeug mitzunehmen. Michel entscheidet also, die Geschenke per Post zu schicken.

    Wegen einer Verpackungssteuer würden jedoch 16 individuelle Versände zu teuer sein, und das Risiko, eine der Masken zu verlieren wäre zu gross. Michel beschliesst also, ein einziges Paket mit allen 16 Masken an einen seiner Freunde zu schicken. Dieser wird dann die Verantwortung haben, den anderen Gästen die Masken zukommen zu lassen.

    Die Gäste kennen sich aber nicht alle, wie es der Graph illustriert. Michel muss also die Versände so organisieren, dass Masken nur zwischen Personen, die sich kennen versendet werden (siehe das Beispiel weiter unten).

    Natürlich kostet der Versandplan ein Vermögen, wenn er nicht richtig organisiert ist! Michel hat es also mit einem Optimierungsproblem zu tun: Er muss entscheiden, an wen das Paket mit den 16 Masken für Emma zu schicken ist, und dazu auch noch dieser Person erklären, wie die Masken an die anderen Gäste weiter-zu-leiten sind, damit die gesamten Versandkosten so klein wie möglich werden.

    Jeder der Freunde wohnt in einer von drei Tarifzonen von der Post: dir graue Zone (G), die gelbe Zone (J) und die mauve Zone (M). Die Versandkosten sind danach angegeben:

     

     

    Michel muss also entscheiden, zu wem er die 16 Masken schickt, und wie diese Person die Masken weiter versenden soll, damit jeder Gast mit einer Maske zum Fest kommt und damit die Versendungskosten minimal werden.

    Ausdrücklich muss Michel die folgenden Bedingungen beachten:

    1.      Das Packet, das er aus Südafrika sendet, muss alle 16 Masken enthalten, und kann nur zu ein einzige Person versendet werden;

    2.      eine Versendung zwischen zwei Gästen kann nur dann stattfinden, wenn die zwei Personen auf Facebook Freunde sind, das heisst, wenn sie in Abbildung 1 verbunden sind;

    3.      es spielt keine Rolle, welcher Gast mit welcher Maske kommt;

    4.      eine Maske kann mehrfach weitergesendet werden;

    5.      eine Person kann ein Paket mit mehreren Masken an eine andere Person schicken;

    6.      die Versandkosten eines Pakets sind entsprechend der Zonen des Versenders, des Empfängers und der Anzahl Masken zu berechnen (zum Beispiel kostet eine Paket mit 3 Masken von Zone „J“ zu Zone „M“ 6 €);

    7.      die gesamten Versandkosten sind die Summe der Versandkosten für alle Personen die mindestens ein Paket versenden.

    Hauptfrage: An wem muss Michel das Paket mit den 16 Masken schicken, und wie müssen dann die Masken weiter versendet werden, damit die gesamten Versandkosten minimal sind? Was sind die Kosten dieser Lösung?

    Zusatzfrage: Wie viele Tore werden während der gesamten Fussballweltmeisterschaft in Südafrika erzielt? Achtung, Tore, die beim Elfmeterschiessen erzielt werden, werden nicht gezählt!

     

    Beispiel

    Der folgende Versendungsplan ermöglicht den 16 gemeinsamen Freunden von Michel und Emma, eine Maske zu erhalten. Die gesamten Versandkosten betragen 145€. Gibt es ein Versendungsplan, der geringere Gesamtkosten als 145€ hat? Ja… dann finden Sie ihn!

     

    Versender

    Gruppe

    Empfänger

    Gruppe

    Anzahl Masken

    Kosten

    Michel

     

    Moshe

    G

    16

    32 €

    Moshe

    G

    Eric

    M

    3

    9 €

    Moshe

    G

    Maya

    G

    12

    36 €

    Maya

    G

    Carolina

    J

    9

    27 €

    Maya

    G

    Charisma

    J

    1

    3 €

    Maya

    G

    Matteo

    M

    1

    3 €

    Carolina

    J

    Gautier

    G

    3

    9 €

    Carolina

    J

    Benjamin

    M

    3

    6 €

    Carolina

    J

    Javier

    M

    2

    4 €

    Eric

    M

    Mogens

    M

    2

    2 €

    Gautier

    G

    Antonio

    M

    1

    3 €

    Gautier

    G

    Jelena

    J

    1

    3 €

    Benjamin

    M

    Jacques

    G

    1

    3 €

    Benjamin

    M

    Fafa

    J

    1

    2 €

    Javier

    M

    Veronica

    J

    1

    2 €

    Mogens

    M

    Sebastian

    M

    1

    1 €

     

     

     

     

     

     

     

     

     

     

    Gesamte Versandkosten

    145 €

     

     

     

     

     

    Organisation des Wettbewerbs

    Die vollständige Beschreibung der Wettbewerbsregeln ist im Internet unter www.svor.ch zu finden.

     

    Ihre Lösung (Hauptfrage) und die Antwort auf die Zusatzfrage senden sie Bitte mittels der Datei Loesung_Wettbewerb_SVOR_2010.xls per Email an info@svor.ch. Diese Excel-Datei ist auf der Website der SVOR zu finden. Bitte geben Sie auch Ihre persönlichen Daten an, und eine kurze Beschreibung der Methode, die angewendet wurde.

    Die Teilnahmefrist endet am Sonntag, dem 6. Juni 2010.

     

    Reglement

    Der Wettbewerb ist für Schüler(inn)en von Schweizer Gymnasien reserviert.

    Die SVOR ermutigt die Schüler(inn)en, ein Modell oder ein Computerprogramm zu implementieren, um die beste Lösung der Hauptfrage zu finden. Eine „manuelle“ Lösung ist jedoch auch erlaubt.

    Nur fristgerechte Antworten werden berücksichtigt.

    Die SVOR wird die 5 zulässigen Lösungen prämieren, welche die kleinsten gesamten Versandkosten haben (Hauptfrage). Falls zwei Antworten dieselben gesamten Versandkosten haben, wird der Gewinner auf der Basis der Zusatzfrage bestimmt. Falls dies nicht ausreicht, wird der Gewinner per Los bestimmt.

     

    Preise

    Der Wettbewerb sieht fünf Preise von insgesamt 2'000 CHF vor.

    1. Preis:              600 CHF

    2. Preis:             500 CHF

    3. Preis:             400 CHF

    4. Preis:             300 CHF

    5. Preis:             200 CHF

    Die SVOR wird den Gewinnern im Laufe des Juli 2010 Bescheid geben.