Man, man, man,

ein spannende Problem. Ich brauche ein bischen Zeit, aber ich glaube, es wird mich eh nicht loslassen.

Ich habe schon ein Starter:

Aus deiner Anfangsaufstellung, wo alle Plätze P nach Weglänge W aufsteigend und Artikel A nach Menge M absteigend sortiert sind, bilden die minimale Gesamtweg G, wenn sie ein zu eins in dieser Reihenfolge zugeordnet wären. Also Platz P1 (Weg W1, kurzeste)  zu Artikel A1 (Menge M1, grösste)  , P2 (W2) zu A2 (M2), usw. Beweis, siehe unten. Man kann annehmen, das je weiter man sich davon entfern, desto grösser wird der Gesamtweg G. Beweise habe ich an der Stelle nicht.

Nun gibt es leider die Bedingungen, die passen müssen. Stufe 1 ist noch gemütlich:

wenn in der Reihe P1-A1 zu P8-A8 das Artikel 4 so hoch ist, dass es nur entweder in P1 oder P8 passt -der Grund warum 1 bis 8 eine "Reihe" bildet- gilt es, 2 Variante zu rechnen und sie miteinander vergleichen:

A4 in P1, also nach vorn (v): Gv = W1 * M4 + Summe [1:3] ( W(i+1) * Mi ) + Summe [5:8] ( Wi * Mi )

=> die Artikel 1 bis 3 Rücken nach hinten: W2 * M1 + W3 * M2 + W4 * M3, Artikel 5 bis 8 unverändert.

A4 in P8, nach hinten (h): Gh = W8 * M4 + Summe [1:3]( Wi * Mi ) + Summe [4:7] (Wi * M(i+1) )

=> die Artikel 1 bis 3 unverändert, die  Artikel 5 bis 8 rücken nach vorn: W4 * M5 + W5 * M6 + W6 * M7 + W7 * M8.

Das kleinste von Gv und Gh ist die Lösung. Aber...

Erstens: wenn innerhalb der 7 andere Artikel sind bestimmt auch Hohen-Bedingungen nicht erfüllt, gleiche Problem. Es bildet sich ein Baum (binär. ich gehe nicht davon aus, es eine grosse Tiefe haben wird: 2^6 = 64...)

Zweitens: wenn in Platz 11 auch eine Artikel mit gleiche Höhe wie 4 und der nächste passende Platz 15 ist, dann haben wir 2 Artikel und 3 Plätze, also 3 Kombinationen (weil ich davon ausgehe, siehe erste Teil, dass es weder A4 in P15 noch A11 in P1 sinnvoll ist. Es wäre "weiter entfernt" der optimale Lösung)

So weit bin ich gerade. Ich denke es ist schon genug Stoff, um ein paar Simulation laufen zu lassen. Aber nicht mehr heute. Bleibt dran, es kommt noch was.

Beweis Wi * Mi + Wj * Mj kleiner als Wi * Mj + Wj * Mi :

Alle Wege und Menge sind positiv.

Wi * Mi = Wi * Mi + Wi * Mj - Wi * Mj = Wi * Mj + Wi * ( Mi - Mj )

genauso: Wj * Mj = Wj * Mi + Wj * ( Mj - Mi )

zusammen: Wi * Mi + Wj * Mj = Wi * Mj + Wj * Mi + Wi * ( Mi - Mj ) + Wj * ( Mj - Mi ) = ( Wi * Mj + Wj * Mi ) + [( Wi - Wj ) * ( Mi - Mj)]

Durch die Sortierung, wenn i < j , dann ist Wi kürzer als Wj, daher Wi - Wj negativ, Mi grösser als Mj, daher der Produkt von beiden (eckige Klammer) auf alle Fälle negativ. Wenn i > j, umgedreht, aber auch negativ. Daher muss man aus Wi * Mj + Wj * Mi etwas abziehen (negatif) um auf Wi * Mi + Wj * Mj zu kommen. Daher ist Wi * Mi + Wj * Mj auf alle Fälle kleiner als Wi * Mj + Wj * Mi.

Da diese Ergebnis zwischen 1 und 2, 2 zu 3, aber 1 zu 3, usw gilt, dann ist die Startreihenfolge das Minima ultima.

Gute Nacht

Yal