© Frauke Jansen, MATH+
Autor*in: Fabian Altekrüger (HU Berlin)
Projekt: Convolutional Proximal Neural Networks for Solving Inverse Problems (EF 3-7)
Aufgabe
Jedes Jahr hat der Weihnachtsmann das gleiche Problem, wenn er und seine Helfer den Transport der Geschenke zu allen Kindern der Welt organisieren… Die Elfen sollen die Geschenke von den Weihnachtsfabriken (F) zu geheimen Lagerhäusern (L) auf allen Kontinenten bringen.
F1: Dieses Jahr wurde ein geheimer Außenposten (F1) im Norden Kanadas genutzt, um 500 Ladungen Geschenke zu produzieren,
F2: da die Hauptfabrik (F2) am Nordpol Produktionsprobleme hatte, so dass dort nur 400 Ladungen Geschenke produziert wurden.
F3: Eine dritte Fabrik (F3) am Südpol produzierte 900 Ladungen Geschenke.
Obwohl die geheimen Lager schon recht gut gefüllt sind, fehlen noch einige Geschenke:
L1: Im Lagerhaus in Nordamerika (L1) fehlen 100 Ladungen.
L2: In Südamerika (L2) fehlen 450 Ladungen.
L3: In Afrika (L3) fehlen 300 Ladungen.
L4: In Australien (L4) fehlen 400 Ladungen.
L5: In Europa (L5) fehlen 200 Ladungen und
L6: in Asien (L6) fehlen noch 350 Ladungen.
Da das Jahr schon anstrengend genug war und der Weihnachtsmann nicht möchte, dass seine Elfen Überstunden machen, suchen sie nach einem optimalen Geschenketransportplan von den Fabriken zu den Lagerhäusern, der die Flugstunden minimiert. Zu diesem Zweck erstellt der Weihnachtsmann eine Tabelle mit den Reisezeiten (in Stunden) von jeder Fabrik zu jedem der Lagerhäuser (siehe Tabelle 1), wobei er berücksichtigt, dass die Fabrik in Kanada (F1) nicht die richtigen Geschenke für die Lagerhäuser in Afrika (L3) und Australien (L4) herstellt:
| L1 | L2 | L3 | L4 | L5 | L6 | |
|---|---|---|---|---|---|---|
| F1 | 2 | 4 | – | – | 5 | 8 |
| F2 | 7 | 8 | 8 | 11 | 3 | 5 |
| F3 | 8 | 6 | 5 | 4 | 9 | 9 |
Tabelle 1: Die jeweilige Flugdauer von den Fabriken (F) zu den Lagerhäusern (L). Zwischen (F1) und (L3) bzw. (L4) finden keine Flüge statt.
Pro Flug kann nur 1 Ladung von einer Fabrik zu einem Lagerhaus transportiert werden. Die leeren Flugzeuge werden von einem Subunternehmer namens WUNDERTRANSPORT zu einem Pauschalsatz zurück zu den Fabriken geflogen, so dass immer genügend Flugzeuge in jeder Fabrik vorhanden sind und die Dauer dieser Rückflüge nicht in die Flugdauer einfließt, die der Weihnachtsmann minimieren möchte.
Diese Aufgabe scheint jedoch etwas zu kompliziert für den armen alten Weihnachtsmann zu sein… Könnt ihr ihm helfen? Wie lang ist die minimale Gesamtflugdauer, die benötigt wird, um alle Geschenke von den Fabriken zu den geheimen Lagerhäusern zu transportieren?
Antwortmöglichkeiten:
- 8080 h
- 8090 h
- 8100 h
- 8110 h
- 8120 h
- 8130 h
- 8140 h
- 8150 h
- 8160 h
- 8170 h
Projektbezug:
Optimaler Transport (OT) ist eine Theorie, die aus der analytischen Beschreibung des Transportproblems hervorgegangen ist, bei dem Objekte (hier Geschenke) von verschiedenen Angebots- (hier die Fabriken) zu verschiedenen Nachfrageorten (hier Lagerhallen) optimal (d. h. kostenminimierend) verteilt werden sollen. In unserem Beispiel sind die Kosten durch die Flugstunden gegeben.
Im Rahmen des Projekts EF 3-7 Convolutional Proximal Neural Networks for Solving Inverse Problems habe ich mich unter anderem mit der 2-ten Wasserstein-Distanz beschäftigt, die einen Spezialfall des OT-Problems darstellt. Wir benutzen die 2-te Wasserstein-Distanz als Regularisierer in inversen Problemen, um empirische Bildverteilungen miteinander zu vergleichen.