Die Homepage wurde aktualisiert. Jetzt aufrufen.
Hinweis nicht mehr anzeigen.

Mathematik im Advent: Plätzchen backen für Perfektionisten

Von

Weihnachtsplätzchen als Herausforderung: Wie muss man die Ausstechformen auf dem Teig platzieren, damit möglichst viele Kekse herauskommen? Fraunhofer-Forscher haben das Problem mit einer Software gelöst, die sonst den Zuschnitt von Röcken und Hosen optimiert.

SCAI

Wir Menschen sind faul. Wenn wir eine Sache erledigen müssen, dann versuchen wir das möglichst effizient zu tun. Statt zweimal nacheinander zu Kollegen drei Etagen tiefer zu laufen, verbindet man die Wege lieber miteinander. Das spart Zeit und Energie, und schließlich gibt es auch noch anderes zu tun.

Zur Meisterschaft in Sachen Effizienz bringen es Mathematiker. Sie haben verschiedene Instrumentarien entwickelt, um alle möglichen Dinge zu optimieren. Egal ob es um kurze Umsteigezeiten beim U-Bahnfahren geht oder um das Packen eines Kofferraums - sie finden auch für knifflige Aufgaben eine gute Lösung.

Ein ganz typisches Optimierungsproblem beschäftigt kurz vor Weihnachten viele Hobbybäcker: Wie muss man die Plätzchen aus dem ausgerollten Teig ausstechen, damit möglichst wenige Zwischenräume übrigbleiben? Oder anders gefragt: Wie nutzt man den Teig optimal, wenn beispielsweise vier verschiedene Kekse in gleicher Menge gebacken werden sollen?

Die Aufgabe hat es in sich: Mit welcher Ausstechform beginnt man? Passen mehr Weihnachtsmänner nebeneinander, wenn sie abwechselnd aufrecht und auf dem Kopf stehen? Oder sollten zwischen den Weihnachtsmännern besser kleine Sterne platziert werden? Die Zahl der denkbaren Varianten ist riesig.

Das Weihnachtsplätzchenproblem mag belanglos erscheinen. Wer beim Ausstechen viel Teig verschwendet, muss den Restteig ja nur öfter ausrollen. In der Textilbranche ist die optimale Ausnutzung von Flächen hingegen bares Geld wert. Bei edlen Stoffen kann das Material bis zu 70 Prozent der Gesamtkosten ausmachen. Hersteller achten daher auf jedes Prozent und versuchen, die Schnittbilder etwa von Hosen oder Röcken optimal auf den Stoffbahnen zu verteilen.

Durchschütteln, bis es passt

Dafür nutzen sehr viele Hersteller eine Software, die Forscher am Fraunhofer-Institut für Algorithmen und Wissenschaftliches Rechnen (SCAI) in St. Augustin entwickelt haben. Autonester heißt das Paket, das auch in CAD-Systeme integriert werden kann. Die Anwender geben vor, wie viele Stücke welcher Form und Größe sie aus einer Stoffbahn schneiden möchten. Und die Software findet eine Verteilung der Stücke, bei der kaum Verschnitt auftritt.

Fotostrecke

11  Bilder
Plätzchen oder Jeans: Flächen optimal nutzen
Das Programm kann sogar Streifen- und Karomuster berücksichtigen. Schließlich darf das Muster der Arme bei einem Hemd nicht anders orientiert sein als beim Rest des Hemdes. Im Vergleich dazu wirkt das Plätzchenausstechen geradezu einfach, denn hier dürfen die Formen nach Belieben gedreht werden.

Wie aber findet die Software die optimale Verteilung der Formen? Letztlich probiert sie einfach nur aus, und zwar Zehntausende Male. "Das ist ein bisschen wie beim Füllen eines Bonbonglases", sagt Fraunhofer-Forscher Ralf Heckmann. "Anfangs schüttelt man stärker, damit größere Löcher schnell mit Bonbons aufgefüllt werden." Später schüttle man dann nur noch ein bisschen.

Das Video zeigt im Zeitraffer, wie die verschiedenen Schnittformen auf der Stoffbahn sich nach und nach zurechtruckeln. Zu Beginn sind die Formen zufällig verteilt und liegen teils sogar übereinander. In den folgenden, tausenden Schritten werden Formen gedreht, miteinander vertauscht oder an andere Stellen positioniert.

Verschieben, vergleichen, verwerfen

Nach jedem Schritt bewertet das Programm Autonester, ob sich die Ausnutzung der Fläche verbessert hat oder nicht. So werden manche Aktionen auch wieder verworfen. Anfangs sind auch Verschlechterungen zulässig. Je nach genutztem Algorithmus dürfen sich die Formen sogar leicht überschneiden. Nähert sich die Optimierung ihrem Ende, ist das natürlich nicht mehr erlaubt.

Bei der Optimierung kombiniert Autonester verschiedene Verfahren wie Simuliertes Abkühlen und Sintflutalgorithmus (siehe Kasten links oben). Systematisches, tausendfaches Probieren allein reicht jedoch nicht aus. Bei Formen, deren Größe sich stark unterscheidet, schaut die Software auch immer wieder nach größeren Lücken, in die man die kleineren Formen platzieren könnte.

Die Suche nach einer guten Lösung erledigt ein moderner PC binnen Minuten. Die Berechnung einer effizienten Verteilung von 40 Plätzchenformen auf einem herkömmlichen Backblech hat beispielsweise zehn Minuten gedauert. Das Ergebnis - siehe Fotostrecke - kann sich sehen lassen: Der Teig wird zu 80 Prozent ausgenutzt. Und auf die Verteilung wäre man als Hobbybäcker wohl kaum von selbst gekommen.

Oft wird die Optimierung auch mehrmals nacheinander gestartet - immer mit etwas anderen Startbedingungen. Dabei können auch Ergebnisse herauskommen, die sich minimal unterscheiden. Denn Autonester findet nicht zwingend die bestmögliche Verteilung.

"Das Nesting-Problem ist NP-schwer", erklärt Ralf Heckmann. Mit zunehmender Zahl der zu verteilenden Stücke steige der Rechenaufwand deshalb enorm. Die gefundene Lösung kommt dem Optimum jedoch in der Regel sehr nahe, versichert der Forscher.

Diesen Artikel...
Forum - Diskutieren Sie über diesen Artikel
insgesamt 78 Beiträge
Alle Kommentare öffnen
    Seite 1    
1. oooo
inci 19.12.2010
Zitat von sysopWeihnachtsplätzchen als Herausforderung: Wie muss man die Ausstechformen auf dem Teig platzieren, damit möglichst viele Kekse herauskommen? Fraunhofer-Forscher haben das Problem mit einer Software gelöst, die sonst den Zuschnitt von Röcken und Hosen optimiert. http://www.spiegel.de/wissenschaft/mensch/0,1518,733067,00.html
die wissenschaftler hätten einfach mal ihre oma fragen sollen. die hätte ihnen gesagt, daß man die reste nicht wegwirft, sondern einfach wieder zusamenknetet, erneut ausrollt und so lange weitermacht, bis der ganz teig "ausgestochen" wurde. nicht ausstechfähige kleine reste werden mit der hand zu einem "probekeks" geformt.
2. Erst lesen
Auswahlaxiom, 19.12.2010
Zitat von incidie wissenschaftler hätten einfach mal ihre oma fragen sollen. die hätte ihnen gesagt, daß man die reste nicht wegwirft, sondern einfach wieder zusamenknetet, erneut ausrollt und so lange weitermacht, bis der ganz teig "ausgestochen" wurde. nicht ausstechfähige kleine reste werden mit der hand zu einem "probekeks" geformt.
Der inci hätte einfach mal den Artikel lesen sollen, denn genau das steht drin: Dort ist aber auch zu lesen: War aber irgendwie klar, dass die Wissenschaftsfeinde gleich wieder mit dem üblichen Bashing kommen, dass Mathematik, Physik und Co. weltfremde und praxisferne Dinge sind. Daher mein Tip: Erst lesen, dann verstehen, dann posten.
3. Effizienz
Gegengleich 19.12.2010
Zitat von incidie wissenschaftler hätten einfach mal ihre oma fragen sollen. die hätte ihnen gesagt, daß man die reste nicht wegwirft, sondern einfach wieder zusamenknetet, erneut ausrollt und so lange weitermacht, bis der ganz teig "ausgestochen" wurde. nicht ausstechfähige kleine reste werden mit der hand zu einem "probekeks" geformt.
So ist es. Mit der Oma. Und der Bäcker würde sagen: Hier wird's nicht effizienter, denn bis ich die Formen genau wie berechnet platziert habe, habe ich die Restteige schon 3x ausgerollt. Einzig und allein der Hersteller von Ausstecher-Verbund-Matten o.ä. könnte hier Vorteile heraus ziehen. Die dringendste Frage überhaupt ist jedoch Folgende: Braucht man wirklich dafür, daß man Textilzuschnittsoftware auf Plätzchenausstecher überträgt, *allen Ernstes* Fraunhofer-Institute.
4. Plätzchen backen privat!
yettiz 19.12.2010
Zitat von sysopWeihnachtsplätzchen als Herausforderung: Wie muss man die Ausstechformen auf dem Teig platzieren, damit möglichst viele Kekse herauskommen? Fraunhofer-Forscher haben das Problem mit einer Software gelöst, die sonst den Zuschnitt von Röcken und Hosen optimiert. http://www.spiegel.de/wissenschaft/mensch/0,1518,733067,00.html
Aber es besteht weiterhin ein Problem mit den Keksen auf dem Blech zu platzieren, diese dürfen dann nicht zu nah an einander liegen, da sie sonst zusammen backen können. Ausserdem ist der Zeitaufwand mit der Berechnung bei privaten Haushalten größer als den Rest neu zu verkneten und auszurollen. In Großproduktionsstätten könnte man dieses Verfahren anwenden, aber besteht dann ein weiteres Problem mit den Ausstechformen, da diese auf Endlos eingestellt sind. Aber nett gemeint ist es trotzdem.
5. Die berühmte Oma
Auswahlaxiom, 19.12.2010
Zitat von GegengleichSo ist es. Mit der Oma. Und der Bäcker würde sagen: Hier wird's nicht effizienter, denn bis ich die Formen genau wie berechnet platziert habe, habe ich die Restteige schon 3x ausgerollt. Einzig und allein der Hersteller von Ausstecher-Verbund-Matten o.ä. könnte hier Vorteile heraus ziehen. Die dringendste Frage überhaupt ist jedoch Folgende: Braucht man wirklich dafür, daß man Textilzuschnittsoftware auf Plätzchenausstecher überträgt, *allen Ernstes* Fraunhofer-Institute.
Einfache Antwort: Weil Ihre Oma das nicht kann. Komplizierte Antwort: Weil es genau andersherum ist. Der Autor des Artikels hat das Plätzchenausstechen als Beispiel gewählt, um Wissenschaftsleugnern wie Ihnen eine Brücke zu bauen. Er konnte nicht ahnen, dass selbst diese Anschauung von Ihnen zu viel verlangt. Schnittmuster anzufertigen, die möglichst wenig Reste hinterlassen, ist ein enorm schwieriges Optimierungsproblem. Wenn Ihre Oma das besser kann, sollte man ihr vielleicht die Fields-Medaille verleihen.
Alle Kommentare öffnen
    Seite 1    

© SPIEGEL ONLINE 2010
Alle Rechte vorbehalten
Vervielfältigung nur mit Genehmigung der SPIEGELnet GmbH



Methoden zur Optimierung
Simulierte Abkühlung (Simulated Annealing)
Vorbild hierfür ist eine sich abkühlende Schmelze. Zu Beginn können sich die Atome (Hosenstücke, Ausstechformen) noch relativ frei bewegen - also wandern oder Plätze tauschen. Mit sinkender Temperatur nimmt ihre Bewegungsfreiheit ab. Verschlechterungen der Flächennutzung werden nur mit einer gewissen Wahrscheinlichkeit akzeptiert, die beim Abkühlen abnimmt. Ganz zum Schluss ist die Schmelze erstarrt. Je langsamer man abkühlt, umso größer sind die Chancen, eine effiziente Verteilung zu finden.



Sintflut Algorithmus
Die Analogie dafür ist ein Wanderer, der vor der steigenden Sintflut immer höher in die Berge flüchtet. Anfangs steigt das Wasser rasch, am Ende nur noch langsam. Im Fall des Stoffs oder des Plätzchenteiges bedeutet eine steigende Flut eine abnehmende Fläche. Hinter dem Erklimmen von Bergen steckt nichts anderes als das Drehen, Verschieben oder Vertauschen von Flächen. Steigt dabei die Flächenausnutzung, ist man ein Stück weg vom Wasser nach oben gestiegen.
Schwellenakzeptanz (Threshold Accepting)
Die Schwellenakzeptanz gleicht der Simulierten Abkühlung. Allerdings akzeptiert der Algorithmus stets auch Verschlechterungen der Flächennutzung, solange diese unterhalb des Schwellenwertes liegen. Im Laufe der Berechnung sinkt der Schwellenwert allerdings immer weiter.


Fotostrecke
Verräterische IMEI: Analyse der Seriennummern von Handys
Können Sie Ihr Glück fassen?
Glück oder Pech, Schicksal oder Zufall - das Leben ist nicht berechenbar. Oder doch? Mit minimalen Mathe- und Denkkniffen kann jeder Chancen und Risiken berechnen. Testen Sie Ihr Zahlengefühl im Mathe-Quiz.

Fotostrecke
Packproblem: Scheiben möglichst dicht anordnen

Der kompakte Nachrichtenüberblick am Morgen: aktuell und meinungsstark. Jeden Morgen (werktags) um 6 Uhr. Bestellen Sie direkt hier: