Algorithmus: Optimale Kombination von verschiedenen Längen

[bernerbaer]

ich habs nicht näher angeschaut aber vielleicht ist ja das etwas:
delphiforfun

[Aphton]

edit: ..

[Panthrax]

Mathematische Sicht: Man kann es als ein lineares Gleichungssystem ausdrücken und dann mit dem Simplex-Verfahren lösen. Allerdings: Die Gleichungen, welche die Kombinationen der Einzelstücke zur Ziellänge ausdrücken, müssen selbst algorithmisch gefunden werden; und, das Simplex-Verfahren ist wahrscheinlich nicht mal eben implementiert.

Mir ist kein Lösungsweg eingefallen ohne einen Zwischenschritt mit einem anderen Algorithmus (hier das Finden der Kombinationen).

Praktische Sicht: Der Computer ist fleißig, einfaches Durchprobieren tut's vielleicht auch? Das ist aber vielleicht auch nicht mehr im Sinne des Erfinders?

Wie gesagt, eine gezielt-algorithmisch-mathematische Lösung ist nicht so einfach -- wegen der Mathematik und der Implementierung. Das soll aber nicht entmutigen! Es bleibt noch eine (vielleicht nur hypothetische) Frage: Ich nehme auch an, dass die Zahl verfügbarer Längenstücke begrenzt ist, oder werden die erst zugeschnitten?

[Horst_]

Hallo,

Zitat von bernerbaer:

ich habs nicht näher angeschaut aber vielleicht ist ja das etwas:
delphiforfun

Das sieht ja gut aus, ist leider die Umkehrung des Problems.
Ich habe nur 1 m Stücke und brauche 4 von 68 cm,... 7 von 17 cm ...
Wie bekommt man da die Unschärfe von 100 +- 2 cm rein.
Vielleicht mit integer Rechnung und der Angabe der möglichen Länge und mit Kosten pro cm = konstant
Treppe.txt sieht so aus:
5 verschiedene Ausgangslängen
6 verschiedene Ziellängen

Code:

5 6 2
PARTS
   Length   # Required
    67.00   4
    57.00   4
    41.00   4
    32.00   4
    25.00   4
    17.00   7

STOCK
   Length   Cost
   102.00    102.00
   101.00    101.00
   100.00    100.00
    99.00    099.00
    98.00    098.00

Mit dem Ergebnis:

Code:

 --- Optimal Integer Solutuion ---
Pattern(1)  Stock length:     99,00  Needed: 4
   Order length:  67,00  Number cut from each stock piece:     1
   Order length:  32,00  Number cut from each stock piece:     1
   Unused from each stock piece 0,00
Pattern(2)  Stock length:     98,00  Needed: 4
   Order length:  57,00  Number cut from each stock piece:     1
   Order length:  41,00  Number cut from each stock piece:     1
   Unused from each stock piece 0,00
Pattern(3)  Stock length:     99,00  Needed: 0
   Order length:  41,00  Number cut from each stock piece:     2
   Order length:  17,00  Number cut from each stock piece:     1
   Unused from each stock piece 0,00
Pattern(4)  Stock length:     98,00  Needed: 0
   Order length:  32,00  Number cut from each stock piece:     2
   Order length:  17,00  Number cut from each stock piece:     2
   Unused from each stock piece 0,00
Pattern(5)  Stock length:    100,00  Needed: 1
   Order length:  25,00  Number cut from each stock piece:     4
   Unused from each stock piece 0,00

Das sieht doch nicht schlecht aus.

Gruß Horst

[bernerbaer]

Zitat von Horst_:

... Das sieht ja gut aus, ist leider die Umkehrung des Problems.

Ich habe mir das Programm mal ganz kurz angeschaut und verstehe nicht weshalb es eine Umkehrung deines Problems sein sollte. So wie ich es verstehe, erfüllt es doch _fast_ genau deine Anforderungen, Du hast Blöcke mit einer Seitenlänge von 100cm und willst aus diesen Blöcken möglichst optimal die bestellten Längen herausschneiden, und genau das macht das Programm.

• Du hast Blöcke mit 100cm Länge (= Längeneintrag bei "Available stock size")
• Du hast bestellt Stücke zu x, y, z, ... cm Länge (Eintrag bei "Ordered Size" -> Size)
• Du hast die erforderliche Anzahl der bestellten Stücke [Eintrag bei "Ordered sizes" unter "Nbr required"

Das Programm gibt dir nun aus, wieviele Blöcke du benötigst und zeigt dir die Aufteilung der Blöcke an.

Zitat von Horst_:

... Wie bekommt man da die Unschärfe von 100 +- 2 cm rein.

Was meinst du genau mit Unschärfe? Ist damit der Schnittverlust gemeint?

Ich habe mir den Source des Programmes nicht angeschaut, aber wenn Du den dahinterliegenden Algorithmus findest und verstehst, sollte es "relativ" einfach sein für jeden Schnitt einen Schnittverlust hinzuzufügen. Alternativ, kannst du ja allenfalls eine Sicherheitsmarge bei der Blocklänge eingeben, also zb Statt 100 cm für die Blocklänge zb 98cm.

Oder ist damit die unterschiedliche Breite der einzelnen Blöcke gemeint?

Dann erfüllt, so wie ich es sehe, das Programm deine Anforderungen bereits, du kannst in der Liste der verfügbaren Blöcke unterschiedliche Blöcke mit unterschiedlichen Längen erfassen.

[Klaus01]

Zitat von bernerbaer:

Zitat von Horst_:

... Das sieht ja gut aus, ist leider die Umkehrung des Problems.

Ich habe mir das Programm mal ganz kurz angeschaut und verstehe nicht weshalb es eine Umkehrung deines Problems sein sollte. So wie ich es verstehe, erfüllt es doch _fast_ genau deine Anforderungen, Du hast Blöcke mit einer Seitenlänge von 100cm und willst aus diesen Blöcken möglichst optimal die bestellten Längen herausschneiden, und genau das macht das Programm.

• Du hast Blöcke mit 100cm Länge (= Längeneintrag bei "Available stock size")
• Du hast bestellt Stücke zu x, y, z, ... cm Länge (Eintrag bei "Ordered Size" -> Size)
• Du hast die erforderliche Anzahl der bestellten Stücke [Eintrag bei "Ordered sizes" unter "Nbr required"

Nein,

das Problem ist so:

Zitat:

Situation: Ich habe eine Menge verschiedener Längen (von 16cm bis 68cm, Werte können mehrfach auftreten).

Problem: Ich möchte die einzelnen Längen so kombinieren, das ich möglichst viele 100cm Längen bekomme (± 2cm). Es dürfen 2 bis 4 Elemente aus der Grundmenge verwendet werden.

Er will aus mehreren kleinen Stücken möglichst viele 100cm Stücke optimal zusammensetzen.

Grüße
Klaus

[Horst_]

Hallo,

ich habe es vielleicht unglücklich formuliert.

Aber in der Textdatei Treppe.txt kann Jonelmeier nun einfach alle seine kleinen Stücke eingeben absteigend sortiert unter parts eingeben und muss die zweite Zahl in der ersten Zeile anpassen auf die Anzahl der verschiedenen Stücke.
Dann müßte es funktionieren.

Gruß Horst