Was haben Plätzchenausstechen oder Lastwagenbeladen mit Mathematik zu tun? Zwei völlig verschiedene Aufgaben, die zudem auf den ersten Blick eher praktische Tätigkeiten sind, ähneln sich doch in einem Punkt. Beide wollen auf einem vorgegebenen Platzangebot (der ausgerollte Plätzchenteig oder die Ladefläche eines LKWs) möglichst viele Objekte (Plätzchen oder Pakete) unterbringen, dabei möglichst wenig Platz verschwenden, oder im Fall vom LKW vielleicht gewisse Waren bevorzugen um einen hohen Gewinn zu erziehlen (vielleicht auch beim Plätzchen ausstechen, wenn man Engelfiguren den Weihnachtsmännern vorzieht :) ).

Und schon sind wir bei der Mathematik angelang. Man kann das Beladen eines LKWs systematisch machen, insbesondere wenn die Pakete unterschiedliche Größen haben, um den LKW so voll wie möglich zu machen. Das Plätzchenbeispiel verdeutlicht die Problematik: man möchte unterschiedliche Formen so drehen und verschieben, dass viele Plätzchen herauskommen. Und intuitiv macht man das meist auch schon sehr gut. Für das Plätzchenbacken ist es aber höchtens in sehr großen Bäckereien interessant wirklich zu berechnen, was die optimale Anordnung der Formen ist.

Ich möchte hier einen Spezialfall vorstellen, mit dem man aber schon sehr brauchbare Ergebnisse erziehlen kann. Die erste Einschränkung ist, dass wir nur ein 2-dimensionales Reckteck befüllen. Alle Pakete sind auch Rechtecke und von jeder Packetgröße haben wir unbeschränkt viele zur Verfügung (auch, wenn wir vielleicht nur sehr wenige in das Reckeck packen werden). In vielen Produktionsstätten werden nur eine gewisse Anzahl verschiedener Produkte gefertig (am laufenden Band - also gibt es "beliebig" viele davon) und diese werden meist in rechteckige Kartons verpackt, also ist unsere Einschränkung oft auch akzeptabel. Die zu lösende Aufgabe wird als zwei-dimensionales Zuschnittproblem bezeichnet, in speziellen beschäftige ich mich hier mit dem Guillotine-Zuschnittproblem.

Guillotine-Zuschnitt

Das Mittelalterliche Tötungsinstrument diente vornehmlich dazu einen Menschen in zwei Teile zu zerschneiden. Der Begriff der Guillotine wurde hier übernommen, um das prinzipielle Vorgehen zu veranschaulichen: Unser Ausgangsrechteck wir mit einem geraden Schnitt, senkrecht zu einer Kante, in zwei Teile geteilt. Die entstehenden Rechtecke können danach genauso wieder zerteilt werden. Dieses Vorgehen wiederholen wir solange, bis die gewünschten Teile aus der Platte zugeschnitten wurden.
Es sind hier zwei Zuschnitte abgebildet. Auf dem linken Bild ist ein Guillotine-Zuschnitt zu sehen, das rechte ist nicht nach diesem Prinzip erstellt wurden.

Jedes Teil das zugeschnitten werden soll, hat eine Breite w und eine Höhe h, Zusätzlich wird jedem Teil ein Wert zugeordnet (z.B. Preis, Größe, oder Präferenz). Es soll nun die Summe der Werte der Teile, die zugeschnitten wurden, maximiert werden. Um dies zu erreichen, wird eine Rekursionsvorschrift, nach dem Prinzip der dynamischen Optimierung, definiert. Dazu sei die Funktion

v(h,w):=maxi {ci: hi<=h, wi<=w }

die angibt, welcher maximale Wert durch Platzieren eines Typenteils in einem Rechteck hxw erreicht werdem kann. Die damit zu definierende Rekursionsvorschrift lautet

V(h,w):=max( max{V(h,x)+V(h,w-x) | x∈N, x<=w/2}, max{V(y,w)+V(h-y,w) | y∈N, y<=h/2}, v(h,w), 0)

Dabei ist V(h,w) der Wert eines Rechtecks hxw, der durch ein optimales Schnittmuster entsteht. Ist unsere Grundplatte in der Größe HxW, dann erhalten wir einen optimalen Zuschnitt und den zugehörigen Zuschnitt-Wert durch Berechnung von V(H,W).

Das genaue Vorgehen und einige enorme Verbesserungen habe ich in einer Grundpraktikumsarbeit zusammen mit Andreas Richter ausgearbeitet. Die Details können hier nachgelesen werden.