Mathe: geringsten Rest ermitteln

[Thomas]

Hallo,

ich habe ein Problem bei dem ich nicht weiterkomme.
Hab wirklich schon alles versucht, denn ich hätte es sehr gerne selber gelöst. Hab ein halbes Buch voller Formelgeschmiere erstellt ;-)

es geht um folgendes:
Ich habe zum Beispiel 3 Rohre in der Rohfassung.

Rohr 1: Länge 2000 cm
Rohr 2: Länge 4600 cm
Rohr 3: Länge 8000 cm

Es können auch 4 oder 5 Rohre sein. Oder auch nochmehr ;-)
Für das Beispiel nehme ich jetzt eben 3.

Jetzt soll ein Stück in der Länge 1500 cm (als Beispiel eine glatte zahl) aus diesen Roh-Fassungen geschnitten werden.
Und zwar 9 mal. (Beispiel)

Wie kann ich jetzt errechnen wie/wo in welcher kombination es den geringsten Rest (Abfall) gibt?

wenn ich jetzt:
2000 / 1500 = 1,33
4600 / 1500 = 3,06
8000 / 1500 = 5,33

rechne, weiß ich ja schon wie oft ich etwas aus welcher rohfassung rausbekomme.

aber ich kann jetzt 1x2000 + 1x4600 + 1x8000, oder 2 x 8000, oder usw...

wie kann ich das errechnen was den geringsten Rest ergibt?

Ich hoffe ihr versteht meine Frage und könnt mir weiterhelfen.
Ich komm einfach nicht weiter.

Vielen Dank schon mal.

Gruß
Thomas

P.S.: Wenn was unklar ist, einfach nochmal nachfragen.

[Micha]

Hallo Thomas,

reicht hierfür nicht die modulare Operation?

Diese funktioniert wie folgt:

7/3 = 2.3333

von 2.5 nimmst Du den Ganzzahligen Teil, alos 2 und multiplizierst diesen mit dem Teiler

2*3=6

der Rest ist nun die Differnez aus beiden

7-6=1

Bei Deinem Beispiel:

4600 / 1500 = 3,06
1500*3 = 4500
4600-4500 = 100

Es bleiben 100mm übrig.

Mit freundlichem Gruß
Micha

[Micha]

... ich sollte die Vorschau etwas intensiver nutzen. *hinterdieohrenschreib*

[Thomas]

Bei Deinem Beispiel:

4600 / 1500 = 3,06
1500*3 = 4500
4600-4500 = 100

Es bleiben 100mm übrig.

ja soweit war ich auch schon ;-)
also bei Anzahl 9 wären das 100 (für 3 Stücke)*3 dann hätte ich meine 9 STück mit einem Rest von 300.

Ich könnte ja aber auch:
8000 / 1500 = 5,33
1500*5 = 7500
8000-7500 = 500

dann hab ich erst 5 Teile also fehlen noch 4.
4600 / 1500 = 3,06
1500*3 = 4500
4600-4500 = 100

dann fehlt noch 1 Stück, 8 habe ich jetzt mit einem Gesamtrest von 600

2000 / 1500 = 1,33
1500*1 = 1000
2000-1500 = 500

jetzt hab ich alle 9 mit einem Gesamtrest von 1100.

Klar in diesem Fall natürlich jetzt nicht das optimale.
Dann lieber 3x die Rohfassung 4600 wo ich einen Gesamtrest von 900 habe.

Aber es kann ja durchaus vorkommen das eine bestimmte Kombination einen geringeren Rest ergibt als wenn ich jetzt nur mit einer Art Rohfassung arbeite.

Mein Problem ist eben genau das irgendwie in eine Funktion zu packen die das berechnet!

Mit freundlichem Gruß
Micha

Vielen Dank für deine Antwort.

Gruß

[Thomas]

Dann lieber 3x die Rohfassung 4600 wo ich einen Gesamtrest von 900 habe.

natürlich 300 nicht 900!

[Tom]

Hello Thomas,

Das versetzt mich glatt ins Jahr 1993 zurück...
Verschnittoptimierung für einen Rolladenbauer.

Wie kann ich jetzt errechnen wie/wo in welcher kombination es den geringsten Rest (Abfall) gibt?

Gar nicht. Die Aufgabenstellung ist unvollständig.
Ohen weitere Angaben müsste alles das als Verschnitt angenommen werden, das kürzer als die einzige von Dir verlangte Nutzlänge ist. Das ist weder praxisgerecht noch eine sinnvolle Aufgabe. Da kannst Du einfach drauf los schneiden ;-)

Du musst also die Rahmenbedingungen noch nennen. Welche Längen werden in welcher Häufigkeit abgefordert. Nur das ergibt eine Basis für eine sinnvolle Berechnung.

Beipiel: Wenn sonst die Länge 85cm sehr häufig verlangt wird, Du aus einem 6m langen Stück nun aber im Momnent 1,20m Längen schneiden sollst, wann hörst Du dann auf?

Der einfache Taschenrechner würde sagen, was solls denn? Das geht doch auf. Mach 5 Stück draus und es bleibt kein Rest. Leider spielt da die Säge nicht mit. Die möchte jedes Mal noch 4mm Schnittbreite fressen. Da würden dann also am letzten Stück 1,6cm fehlen, den "Gradschnitt" an beiden Enden der Stange jetzt mal außer Acht gelassen). 118,4cm würden aber gerade noch 1 Stück à 85cm ergeben. Rest wäre dann 33,4 cm. Das ist wohl auch in der Praxis dann Abfall, denn Fenster dieser Breite (ca. 23cm) sind extrem selten :-)

Wenn Du nun nur 2 Stücke à 120cm + Sägeschnitt = 240,8cm und 4 Stücke à 0,854m schneidest, beleiben 17,6 cam Rest. Das ist für die Praxis zwar immer noch nicht optimal, aber schon besser, als 33,4cm Abfall.

Siehst Du die Denkweise?

Schau also nach, ob beid er Aufgabe nicht 'was fehlt.

Harzliche Grüße vom Berg
http://bergpost.annerschbarrich.de

Tom

[Thomas]

Ohen weitere Angaben müsste alles das als Verschnitt angenommen werden, das kürzer als die einzige von Dir verlangte Nutzlänge ist. Das ist weder praxisgerecht noch eine sinnvolle Aufgabe. Da kannst Du einfach drauf los schneiden ;-)

das versteh ich nicht ganz. Wenn ich weiß bei welcher Rohfassung wieviel verschnittmenge entsteht und alle Rohfassungen mit Ihren Verschnittmengen vergleich, kann ich doch das mit dem geringsten verschnitt errechnen, oder beachte ich hier irgendwas nicht?

Welche Längen werden in welcher Häufigkeit abgefordert.

Zur Häufigkeit kann ich leider nichts sagen. Da gibt es keine feste Regel.

Leider spielt da die Säge nicht mit. Die möchte jedes Mal noch 4mm Schnittbreite fressen. Da würden dann also am letzten Stück 1,6cm fehlen, den "Gradschnitt" an beiden Enden der Stange jetzt mal außer Acht gelassen).

Daran hatte ich noch gar nicht gedacht. Aber ok, dass kann ja einfach mit einberechnet werden.
Jedenfalls schon mal danke für den Tip, dass hätte ich jetzt gar nicht berücksichtigt.

Siehst Du die Denkweise?

ich glaub nicht so ganz, oder doch? ;-)

Tom

Danke für die Antwort.

[Stahli]

Hi,

Ohen weitere Angaben müsste alles das als Verschnitt angenommen werden, das kürzer als die einzige von Dir verlangte Nutzlänge ist. Das ist weder praxisgerecht noch eine sinnvolle Aufgabe. Da kannst Du einfach drauf los schneiden ;-)

das versteh ich nicht ganz. Wenn ich weiß bei welcher Rohfassung wieviel verschnittmenge entsteht und alle Rohfassungen mit Ihren Verschnittmengen vergleich, kann ich doch das mit dem geringsten verschnitt errechnen, oder beachte ich hier irgendwas nicht?

Egal wie du schneidest gilt: Nimmst du alle Schnittreste und legst sie am Ende aneinander kommst du immer auf die gleiche Länge (lässt man mal die Schnittbreite außer acht). Als Schnittreste sehe ich jetzt alle Teile an, die übrig bleiben, wenn du deine 9 Zuschnitte fertig hast.

Du musst also noch spezifizieren, wie die Schnittreste am Besten auszusehen haben.

Gruß,
Felix

[Tom]

Hello Felix,

Egal wie du schneidest gilt: Nimmst du alle Schnittreste und legst sie am Ende aneinander kommst du immer auf die gleiche Länge (lässt man mal die Schnittbreite außer acht). Als Schnittreste sehe ich jetzt alle Teile an, die übrig bleiben, wenn du deine 9 Zuschnitte fertig hast.

Du musst also noch spezifizieren, wie die Schnittreste am Besten auszusehen haben.

Gut erklärt, finde ich. Hätte ich auch drauf kommen können ;-)

Jedenfalls fehlt die Definition für "Abfall".
Die ist offen.

Es nicht bekannt, ob er noch weitere Stücke dieser Länge benötigt, was hier aber auch egal wäre, ob er noch andere Längen benötigt usw.

Harzliche Grüße vom Berg
http://bergpost.annerschbarrich.de

Tom

[Thomas]

Egal wie du schneidest gilt: Nimmst du alle Schnittreste und legst sie am Ende aneinander kommst du immer auf die gleiche Länge (lässt man mal die Schnittbreite außer acht). Als Schnittreste sehe ich jetzt alle Teile an, die übrig bleiben, wenn du deine 9 Zuschnitte fertig hast.

Das ist doch nicht richtig oder?

wenn ich jetzt folgende Stangen habe:
3000
4000
7000

ich brauch ein 2000 Stück 3 mal!

dann hab ich diese Möglichkeiten:
3000 Stange zwei 2000 Stücke -> Rest: 1000
Ich brauch das Stück 3 mal also 3 3000 STangen, -> also ein REst von 3000(3 mal 1000 Reststange)

4000 Stange - ein 2000 Stück -> Rest: 0
nochmal eine 4000 weil ein 2000 Stück noch fehlt -> also ein Rest von 2000 (1 mal 2000 Reststange)

usw... das ist doch immer unterschiedlich

ich kann ja auch kombinieren:

4000 Stange zwei 2000 Stücke daraus -> Rest: 0
dann 3000 Stange ein 2000 Stück daraus -> Rest: 1000

also schon noch ein stück besser

Und dieses ganze Verfahren würde ich eben gerne in ein Funktion packen.

Habe ich einen Denkfehler?

Danke, gruß.

[Thomas]

3000 Stange zwei 2000 Stücke -> Rest: 1000

ein 2000 Stück nicht 2

4000 Stange - ein 2000 Stück -> Rest: 0

2 2000 Stücke nicht 1

sorry ;-)

[Sven Rautenberg]

Moin!

Egal wie du schneidest gilt: Nimmst du alle Schnittreste und legst sie am Ende aneinander kommst du immer auf die gleiche Länge (lässt man mal die Schnittbreite außer acht). Als Schnittreste sehe ich jetzt alle Teile an, die übrig bleiben, wenn du deine 9 Zuschnitte fertig hast.

Das ist doch nicht richtig oder?

Wenn du sagst, dass du drei Rohre vorliegen HAST, aus denen du was schneiden kannst, dann stimmts doch.

wenn ich jetzt folgende Stangen habe:
3000
4000
7000

ich brauch ein 2000 Stück 3 mal!

Dann brauchst du die 4000-Stange komplett auf, und von der 7000er schneidest du 2000 ab und behälst 5000 übrig.

Dann nimmst du deine drei 2000er-Stangen weg, und alles, was übrig bleibt, ist "Müll": Die 3000er-Stange, und der 5000er-Stangenrest. Summe: 8000 laufende Längeneinheiten.

Das war aber auch arithmetisch so zu erwarten: 3000 + 4000 + 7000 - (3*2000) = 8000.

Es ist halt die Frage, welcher Rest "besser" ist, ein 1000er von der 3000er, oder ein 5000er von der 7000er. Mit dem 5000er kann man sicherlich noch mehr unterschiedlich lange Stücke schneiden, als mit der 1000er, man wäre also vielleicht später nochmal flexibler. Aber es gibt in der Aufgabenstellung keine Aussicht auf das, was später nochmal kommen wird, also kann man nicht beurteilen, welche Lösung günstiger ist.

Wenn beispielsweise recht selten, aber konstant, eine Stangenlänge von 5001 (oder länger) benötigt wird, ist es extrem ungünstig, die 7000er-Stange zu benutzen.

Dieses Szenario setzt aber voraus, dass du im Prinzip unendlich viele Stangen benutzen könntest, und auch unendlich viele Stücke unterschiedlicher Länge zu schneiden hast - nicht sofort auf einmal, sondern immer mal wieder.

In diesem Licht betrachtet würdest du vermutlich feststellen, dass du sehr häufig 2000er-Stücke benötigst, und deine drei Stücke daher aus zwei 4000er-Stangen herstellen, weil das Reststück von 2000 später mit Sicherheit noch benötigt wird, nur eben jetzt nicht.

Wenn du hingegen vor der Entscheidung stehst, im Laden aus dem Sortiment von 3000/4000/7000 Material zu kaufen für EXAKT drei Stangen zu 2000, dann ist die Wahl auch klar: Kauf das, wo am wenigsten Rest bleibt, also 3000 + 4000.

Ich möchte abschließend anmerken, dass deine Problemstellung sich vielleicht auf den ersten Blick recht einfach gibt, aber tatsächlich mit zu den schwierigsten Problemen gehört, die man sich so vorstellen kann - und es gibt, wie du vielleicht schon an meinen Ausführungen siehst, nicht "DIE" Lösung, sondern allenfalls den Versuch, eine gefundene Lösung im Hinblick auf verschiedene Faktoren zu optimieren, die sich möglicherweise auch gegenseitig ausschließen.

Siehe Rucksackproblem.

- Sven Rautenberg

[Thomas]

Wenn du hingegen vor der Entscheidung stehst, im Laden aus dem Sortiment von 3000/4000/7000 Material zu kaufen für EXAKT drei Stangen zu 2000, dann ist die Wahl auch klar: Kauf das, wo am wenigsten Rest bleibt, also 3000 + 4000.

Dieses Verfahren würde mir für den Anfang erst einmal reichen.
Nur wie gehe ich da mit der Berechnung vor?

Das andere ist dann wieder ein paar Stufen weiter und ich glaub nicht das ich da momentan in den Grünen Bereich komm.

Ich möchte abschließend anmerken, dass deine Problemstellung sich vielleicht auf den ersten Blick recht einfach gibt, aber tatsächlich mit zu den schwierigsten Problemen gehört, die man sich so vorstellen kann

Das habe ich mittlerweile auch schon überraschend feststellen müssen.

• Sven Rautenberg

Danke schön.
Gruß

[Sven Rautenberg]

Moin!

Wenn du hingegen vor der Entscheidung stehst, im Laden aus dem Sortiment von 3000/4000/7000 Material zu kaufen für EXAKT drei Stangen zu 2000, dann ist die Wahl auch klar: Kauf das, wo am wenigsten Rest bleibt, also 3000 + 4000.

Dieses Verfahren würde mir für den Anfang erst einmal reichen.
Nur wie gehe ich da mit der Berechnung vor?

Du kannst es nicht einfach so berechnen, du mußt iterativ vorgehen. Der Link zum Rucksackproblem in Wikipedia sollte dich da eigentlich weiterbringen.

- Sven Rautenberg

[Stahli]

Ah, ich bin nicht davon ausgegangen dass du quasi eine unbegrenzte Anzahl von 3000er, 4000er und 8000er Stangen zur Verfügung hast. Ich fand das Problem intressant und hab mal ein kleines Script geschrieben.

Link zum Script

Hier der relevante Teil des Scripts.

  
 echo "<p>Es sollen $count Stücke der Länge $laenge aus den Rohstücken ".implode(', ',$roh).' geschnitten werden.</p>';  
 $min_rest=-1;  
 while($kombi[$roh_count-1]<=$count){  
  //Neue Kombination berechnen  
  $kombi[0]++;  
  for($j=0;$j<$roh_count-1;$j++)  
   if($kombi[$j]>$count){  
    $kombi[$j+1]++;  
    $kombi[$j]=0;  
   }  
  //Überprüfen, ob diese Kombination die gewünschte Anzahl an fertigen Stangen ergibt  
  $anzahl=0;  
  foreach($kombi as $par_anzahl)  
   $anzahl+=$par_anzahl;  
  if($anzahl!=$count)  
   continue;  
  //Rest dieser Kombination berechnen  
  $rest=0;  
  for($i=0;$i<$roh_count;$i++){  
   $a=ceil($kombi[$i]/floor($roh[$i]/$laenge));//Soviele Rohstücke dieser Länge brauche ich  
   $rest+=$a*$roh[$i] - $kombi[$i]*$laenge;  
  }  
  //Wenn neuer Minimalwert erreicht -> merken  
  if(($rest<$min_rest)||($min_rest<0)){  
   $min_kombi=$kombi;  
   $min_rest=$rest;  
  }  
 }  

Das Script ist sicher noch verbesserungswürdig (vor allem die Ermittlung der verschiedenen Kombinationen ist ziemlich unperformant), aber es erfüllt ersteinmal seinen Zweck.

Ich gehe hierbei davon aus, dass eine unbegrenzte Anzahl von Rohstücken vorhanden ist. "Abfall" ist das, was nach dem Sägen von den benutzten Rohstücken übrigbleibt. Der Abfall am Ende aneinander gelegt soll minimal sein.

Die Länge der verfügbaren Rohstücke trägst du einfach zeilenweise in das Textfeld ein.

Gruß,
Felix

[Tom]

Hello Felix

Es sollen 5 Stücke der Länge 200 aus den Rohstücken 1000, 950 geschnitten werden.

Benutze

* 1 mal 1000er Stange(n).
    * 0 mal 950er Stange(n).

Dabei entsteht ein Rest von 0.

Das ist z.B. ein geliefertes Ergebnis.
Irgendwie hat sich Dein Appparat da verrechnet und die Codierung hat er auch nicht mitgeteilt, wie es aussieht.

Harzliche Grüße vom Berg
http://bergpost.annerschbarrich.de

Tom

[Stahli]

Hi Tom,

Es sollen 5 Stücke der Länge 200 aus den Rohstücken 1000, 950 geschnitten werden.

Benutze

* 1 mal 1000er Stange(n).
    * 0 mal 950er Stange(n).

Dabei entsteht ein Rest von 0.

Das ist z.B. ein geliefertes Ergebnis.
Irgendwie hat sich Dein Appparat da verrechnet

Ist doch richtig.. Ich möchte 5 Stücke der Länge 200 haben. Da nehm ich mir ein 1000er Rohstück und zersäge es in 5 Teile. Dann hab ich 5 Teile der Länge 200 und keinen Rest.

und die Codierung hat er auch nicht mitgeteilt, wie es aussieht.

Oh hab ich übersehen. Danke.

Gruß,
Felix

[Thomas]

Es sollen 5 Stücke der Länge 200 aus den Rohstücken 1000, 950 geschnitten werden.

* 1 mal 1000er Stange(n).
    * 0 mal 950er Stange(n).

Dabei entsteht ein Rest von 0.

Irgendwie hat sich Dein Appparat da verrechnet

Wieso das ist doch richtig.
Meinst du das es keinen Rest gibt oder wo siehst du einen Fehler?

Das es keinen Rest gibt ist richtig.
Denn die Stange 950 wird für diese Durchführung gar nicht angefasst, nur wenn es notwendig gewesen wäre

gruß

[Tom]

Hello,

Es sollen 5 Stücke der Länge 200 aus den Rohstücken 1000, 950 geschnitten werden.

* 1 mal 1000er Stange(n).
    * 0 mal 950er Stange(n).

Dabei entsteht ein Rest von 0.

Irgendwie hat sich Dein Appparat da verrechnet

Wieso das ist doch richtig.
Meinst du das es keinen Rest gibt oder wo siehst du einen Fehler?

Die Glühlampe ging bei mir eben auch erst an, als ich noch einen zweiten Versuch geamcht habe...
Ich hatte die Anweisung einfach falsch verstanden.

Harzliche Grüße vom Berg
http://bergpost.annerschbarrich.de

Tom

[Kai345]

Grütze .. äh ... Grüße!

Irgendwie hat sich Dein Appparat da verrechnet ...

Es sollen 4 Stücke der Länge 2000 aus den Rohstücken 2050, 8000, 6762 geschnitten werden.

Benutze
0 mal 2050er Stange(n).
1 mal 8000er Stange(n).
0 mal 6762er Stange(n).

Dabei entsteht ein Rest von 0.

Soweit verstehe ich es. Aber nun ändere ich die Schnittlänge auf 2001 und erhalte:

Es sollen 4 Stücke der Länge 2001 aus den Rohstücken 2050, 8000, 6762 geschnitten werden.

Benutze
2 mal 2050er Stange(n).
0 mal 8000er Stange(n).
0 mal 6762er Stange(n).

Dabei entsteht ein Rest von 196.

4 Stücke á 2001 aus 2 Stangen á 2050 .. du bist ein Genie. Sämtliche Materialeinkäufer werden dich wegen drastisch gesunkener Materialvorhaltung geradezu verehren ;)

Cü
Kai

[Stahli]

Hi,

Soweit verstehe ich es. Aber nun ändere ich die Schnittlänge auf 2001 und erhalte:

Ups, ja das war ein Schusslichkeitsfehler bei der Ausgabe. Der Fehler dürfte jetzt aber behoben sein. Der vorher gepostete Code und der Link stimmen immernoch, aber ich erweitere mal den gezeigten Code um ein paar Zeilen, damit er verständlicher wird.

  
 echo "<p>Es sollen $count Stücke der Länge $laenge aus den Rohstücken ".implode(', ',$roh).' geschnitten werden.</p>';  
 $roh_count=count($roh);  
 $min_rest=-1;  
 while($kombi[$roh_count-1]<=$count){  
  //Neue Kombination berechnen  
  $kombi[0]++;  
  for($j=0;$j<$roh_count-1;$j++)  
   if($kombi[$j]>$count){  
    $kombi[$j+1]++;  
    $kombi[$j]=0;  
   }  
  //Überprüfen, ob diese Kombination die gewünschte Anzahl an fertigen Stangen ergibt  
  $anzahl=0;  
  foreach($kombi as $par_anzahl)  
   $anzahl+=$par_anzahl;  
  if($anzahl!=$count)//Wenn nicht -> neue Kombination  
   continue;  
  //Rest dieser Kombination berechnen  
  $rest=0;  
  for($i=0;$i<$roh_count;$i++){  
   $a=ceil($kombi[$i]/floor($roh[$i]/$laenge));//Soviele Rohstücke dieser Länge brauche ich  
   $rest+=$a*$roh[$i] - $kombi[$i]*$laenge;  
  }  
  //Wenn neuer Minimalwert erreicht -> merken  
  if(($rest<$min_rest)||($min_rest<0)){  
   $min_kombi=$kombi;  
   $min_rest=$rest;  
  }  
 }  
  
 //Ausgabe  
 echo "<p>Benutze</p>  
 <ul>";  
 for($i=0;$i<$roh_count;$i++){  
  $a=ceil($min_kombi[$i]/floor($roh[$i]/$laenge));//Soviele Rohstücke dieser Länge brauche ich  
  echo "<li>$a mal ".$roh[$i]."er Stange(n).</li>\n";  
 }  
 echo "</ul>\n<p>Dabei entsteht ein Rest von $min_rest.</p>\n";  

4 Stücke á 2001 aus 2 Stangen á 2050 .. du bist ein Genie. Sämtliche Materialeinkäufer werden dich wegen drastisch gesunkener Materialvorhaltung geradezu verehren ;)

Die alte Version lässt sich garantiert besser verkaufen, da hast du Recht. :)

Gruß,
Felix

[Thomas]

Das Script ist sicher noch verbesserungswürdig (vor allem die Ermittlung der verschiedenen Kombinationen ist ziemlich unperformant), aber es erfüllt ersteinmal seinen Zweck.

Jetzt muss ich mir mal in Ruhe anschauen wie du die verschiedenen Kombinationen ermittelt hast. Noch blicke ich da nicht ganz durch ;-)

Mal schauen ob ich aus deinem Script schlau werde.

Auf jedenfall vielen Dank für dein Mühe.
Das hilft mir sicher einen großen Schritt weiter.

Gruß,
Felix

Gruß