---

Hallo Experten,

Ich kämpfe im Moment wieder an einem Problem in Zusammenhang mit den Pressen. Für Stanzaufträge brauche ich Coilmaterial. Je nach Größe des Auftrags mal mehr mal weniger. Die benötigte Menge V soll aus den Lagerbeständen C1 bis Cn befriedigt werden. Cx ist ein Coil im Lager mit einem beliebigen Gewicht. Beispiel: C1 = 3000 kg, C2 = 4250 kg usw.
Für einen Auftrag mit V = 2856 kg nehme ich natürlich C1 und verbrauche ihn komplett (Rücklieferung ins Lager ist zu teuer). Bei V = 3555 muss ich natürlich C2 nehmen. So weit kann das jeder verstehen.
Das Problem beginnt aber mit mehr als 3 Coils im Lager und gleichzeitig V > als der dickste (schwerste)Coil:

C1 = 3000
C2 = 4250
C3 = 3870
C4 = 5530

Dann kann man folgende Ungleichung aufstellen:
5530 < V > 6870 => C1 + C3
6870 < V > 7250 => C1 + C2
7250 < V > 8120 => C2 + C3
8120 < V > 8550 => C1 + C4
8550 < V > 9400 => C3 + C4
usw . Bei V > 9780 benötige ich 3 Coils.

Ich finde das ist ähnlich dem Problem einen beliebigen Geld-Betrag mit möglichst wenigen Münzen zu zahlen....
Hat schon jemand so ein Problem gelöst? Ich habe leichte Probleme, das in eine Programmiersprache zu fassen.
Ausgangspunkt ist eine unsortierte Tabelle mit Coils einer Güte. Je Coil ein Coilgewicht. Die benötigte Menge V ist bekannt. Als Ergebnis soll in der Tabelle hinter den reservierten Coils ein Kennzeichen stehen. Beste Lösung ist: mit möglichst wenigen Coils die Menge zu reservieren, die am dichtesten bei V liegt.

Wohl gemerkt: Nicht für alle Aufträge optimiert, sondern nur eine Menge. Mir ist auch klar, dass die Auswahl der Coils immer geringer wird und die Auwahl dann immer gröber.

Wer Fragen hat, der frage.

------------------
Gruß
Samson

Eine Antwort auf diesen Beitrag verfassen (mit Zitat/Zitat des Beitrags) IP

---

Hier noch einige Ergänzungen, nachdem ich die Beispieldaten etwas genauer analysiert habe.

Der Fall wird komplizeirter, wenn die Coilgewichte dichter beieinander liegen und die Ungleichungen nicht so eindeutig sind, wie im Beispiel:

C1 = 4125
C2 = 3920
C3 = 4000
C4 = 3888
C5 = 3920
usw.
Eine solche Verteilung ist realistischer. Ich hoffe die Verschärfung des Problems wird deutlich und ich habe euch damit nicht verschreckt. 

------------------
Gruß
Samson

Eine Antwort auf diesen Beitrag verfassen (mit Zitat/Zitat des Beitrags) IP

---

Hallo Samson,

dieses Problem wurde in der Komplexitätstheorie als sogenanntes Knapsack (Rücksack-) Problem untersucht. Es ist nachweislich schwer zu lösen, wenn die Anzahl der Cx sehr groß wird.
Das Problem solltest Du genauer formulieren: Gegeben sind C1,...,Cx,..., Cn und V. Gesucht ist die minimale Anzahl der Cx, deren Summe der Gewichte größer als V ist.
Für kleine Anzahlen von Cx kann die Aufgabe algorithmisch durch eine vollständige Aufzählung aller denkbaren Auswahlen von Cx gelöst werden. Beispielsweise für 5 Cx müssen dann 2^5 - 1 = 31 verschiedene Auswahlen untersucht werden, ob die summe größer als V ist.

------------------
PM

www.math4fun.de

Eine Antwort auf diesen Beitrag verfassen (mit Zitat/Zitat des Beitrags) IP

---

Vielen Dank für deine Antwort.

Ich hatte schon so etwas befürchtet. Ich gehe davon aus, dass ich i.d.R. nicht mehr als 5 Cx für ein V benötige. Der Aufwand scheint dann gerechtfertigt. Ich teste also zunächst, ob ich mit einem Cx auskomme. Dann mit 2 usw. Je nachdem muss ich dann mehrere Kombinationen bilden und die Beste bewerten und dann reservieren.

------------------
Gruß
Samson

Eine Antwort auf diesen Beitrag verfassen (mit Zitat/Zitat des Beitrags) IP