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 } |
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) |
Das genaue Vorgehen und einige enorme Verbesserungen habe ich in einer Grundpraktikumsarbeit zusammen mit Andreas Richter ausgearbeitet. Die Details können hier nachgelesen werden.