09 Wunschzetteloptimierung

© Friederike Hofmann, MATH+

Autor*innen: Max Klimm, Martin Knaack (TU Berlin)
Projekt: Kombinatorische Netzwerk-Flussmethoden für instationäre Gasflüsse und Gasmarkt-Probleme (CRC/TRR 154, Projekt A07)

Aufgabe

Zu Weihnachten schicken alle Kinder dem Weihnachtsmann ihren Wunschzettel mit einer Liste von Dingen, die sie gerne hätten.

Der Weihnachtsmann hat für jedes Kind einen Geschenkesack vorbereitet, dessen Größe davon abhängt, wie brav das Kind im vergangenen Jahr war. Wenn der Weihnachtsmann den Sack packt, dann arbeitet er die Wunschlisten der Kinder jeweils von oben nach unten ab. Genauer:

• Der Weihnachtsmann versucht zunächst den ersten Gegenstand auf der Liste einzupacken, danach den zweiten, und so weiter bis zum Ende der Liste.
• Immer wenn ein Gegenstand in den Sack passt, kommt er hinein, andernfalls wird er nicht eingepackt und der Weihnachtsmann macht mit den anderen Gegenständen der Liste der Reihe nach weiter.
• Eine Menge von Gegenständen passt genau dann in den Sack, wenn die Summe ihrer Größen kleiner oder gleich der Größe des Sackes ist.

Nasti, Manu, Jona und Uli wünschen sich dieses Jahr die folgenden Gegenstände zu Weihnachten, die bei ihnen jeweils eine gegebene Freude auslösen:

Die Kinder kennen die Größe und die Freude der Gegenstände, wissen aber nicht, wie groß der Sack sein wird, den der Weihnachtsmann für sie auswählt. Natürlich wollen alle vier die gesamte Freude der Geschenke in ihrem Sack maximieren. Sie haben allerdings unterschiedliche Strategien verwendet, um ihren Wunschzettel zu schreiben. Die Wunschzettel der Kinder sehen folgendermaßen aus:

Der Weihnachtsmann hat uns verraten, dass alle Kinder einen Geschenkesack derselben Größe bekommen und dass diese Größe eine positive ganze Zahl ist. Welche der folgenden Aussagen ist korrekt?

Antwortmöglichkeiten:

1. Je größer der Geschenkesack desto größer ist die gesamte Freude von Nastis Geschenken.
2. Die gesamte Freude von Nastis Geschenken ist immer mindestens so groß wie die von Manu.
3. Die gesamte Freude von Nastis Geschenken ist immer mindestens so groß wie die von Uli.
4. Die gesamte Freude von Manus Geschenken ist immer mindestens so groß wie die von Jona.
5. Die gesamte Freude von Manus Geschenken ist immer mindestens so groß wie die von Uli.
6. Die gesamte Freude von Jonas Geschenken ist immer mindestens so groß wie die von Nasti.
7. Die gesamte Freude von Jonas Geschenken ist immer mindestens so groß wie die von Manu.
8. Die gesamte Freude von Ulis Geschenken ist immer mindestens so groß wie die von Nasti.
9. Die gesamte Freude von Ulis Geschenken ist immer mindestens so groß wie die von Jona.
10. Keine der Aussagen 1 bis 9 ist korrekt.

Projektbezug:

Das Projekt beschäftigt sich mit der Kapazitätsauslastung in Wasserstoffnetzwerken. Die Gegenstände entsprechen dann Buchungen im Netzwerk und deren Freude dem wirtschaftlichen Nutzen des jeweiligen Wasserstofftransports. Durch die nicht-lineare Gasphysik und die Komplexität des Wasserstoffnetzes sind die Bedingungen, welche Gegenstände gepackt werden können, wesentlich komplizierter als in dieser Aufgabe. Wie die Gegenstände auch noch dann so gepackt werden können, dass die gesamte Freude maximiert wird, ist Forschungsgegenstand des Projekts.