Mathefrage - Aufteilung Waren in Behälter optimieren

[Jens M. (schuchkleisser)]

Hallo,
wir saßen in einer Männerrunde zusammen und habe so über dies und das 
geplaudert, und dabei kam das Gespräch auf ein Problem zur 
Materialverteilung, für das keiner von uns aus dem Handgelenk eine 
Lösung parat hatte.
Ich hätte auch nur gesagt ich schreib ein Skript das alle Möglichkeiten 
durchtestet und das beste ausspuckt, aber Brute Force ist ja doof.
Kann mir evtl. jemand von euch sagen wie man das am besten berechnet, 
z.B. in Excel oder so?

Das Problem geht so:
- Ich habe eine Kiste, in diese Kiste passen eine bestimmte Anzahl 
Behälter.
- Alle Behälter sind gleich groß, unabhängig des Inhalts. Es gibt also 
keine Probleme beim Mischen innerhalb der Kiste.
- Jeder Behälter enthält eine Anzahl  Teile, die Anzahl hängt vom Teil 
ab (z.B. durch Dichte/Größe).
- Jeder Behälter ist Sortenrein, also sind immer 1 bis x des gleichen 
Teils enthalten.
- Ein Rezept braucht verschiedene Teile in verschiedenen Anzahlen.
- Es dürfen auch unbesetzte Plätze in der Kiste sein (bzw. leere 
Behälter), wenn das Rezept bzw. die Behältergröße ein Teil begrenzt.

Wie finde ich jetzt die optimale Füllung der Kiste heraus, um die 
maximale Anzahl an "Kuchen" nach Rezept bauen zu können?
Es geht hier um die beste Möglichkeit die gegebene Kiste auszunutzen, 
nicht ein bestimmtes Mengenziel zu schaffen!

Beispiel:
Rezept sagt "1x A, 2x B", in die Kiste passen 30 Behälter, die je 10 A 
oder 10 B beinhalten können.
Einfache Lösung: 10 Behälter A und 20 Behälter B ergeben 100 bzw. 200 
Teile, ausreichend für 100 "Kuchen".

Jetzt ist aber die Anzahl der Teile pro Behälter variabel, ebenso das 
Rezept oder die Größe der Kiste.
Wie geht's z.B. bei:
- Kiste schafft z.B. 27 Behälter
- Ein Behälter schafft 80x A oder 115x B oder 34x C
- Ein Rezept erfordert 3x A, 1x B, 1x C

Wie geht man sowas an? Bei zwei Teilen ist das noch im Kopf machbar, 
aber darüber steigts bei mir aus...

Und das ist jetzt bewusst abstrakt, weil es "1 Ei, 100g Zucker und 50g 
Mehl" sein könnten, aber auch "1 Stecker und 14 Kontakte" oder "2 
Schrauben, 2 Muttern, 4 U-Scheiben, 1 Deckel": es gibt kein konkretes 
Problem, nur die allg. Frage nach einem Verfahren zur Bestimmung der 
optimalen Aufteilung.

[A. S. (rava)]

das liest sich für mich wie eine Abänderung des Rucksacksproblems: 
https://de.wikipedia.org/wiki/Rucksackproblem

Mit "Mathe" kommt man da nicht weiter. Es braucht einen Algorithmus.

Wenn du die global beste Lösung haben möchtest, bleibt dir nichts 
anderes übrig, als alle Lösungen aufzulisten (brute force). Kannst du 
diese Liste vielleicht so generieren, dass du frühzeitig aufhören 
kannst?

Wenn du nur eine einigermaßen gute Lösung haben möchtest, kannst du mit 
einer heuristik rangehen.

Ich würde vermutlich mit Graph-Search rangehen, weil man da Optimalität 
und Rechenzeit gut gegeneinander aufwiegen kann. Ein Startpunkt wäre 
hier: https://de.wikipedia.org/wiki/Dijkstra-Algorithmus
allerdings musst du dich noch mit den Varianten auseinandersetzen.

[Jens M. (schuchkleisser)]

A. S. schrieb:
> das liest sich für mich wie eine Abänderung des Rucksacksproblems:

LOL es gibt nix was es nicht gibt... Das isses wohl!

A. S. schrieb:
> Wenn du die global beste Lösung haben möchtest, bleibt dir nichts
> anderes übrig, als alle Lösungen aufzulisten (brute force).

Och.

A. S. schrieb:
> Kannst du
> diese Liste vielleicht so generieren, dass du frühzeitig aufhören
> kannst?

Naja, da es nicht soo viele Kombinationen gibt und viele auch nicht 
sinnvoll sind z.B. durch starkes Ungleichgewicht ist das selbst in Basic 
unter Dos relativ schnell. (Ja, ich hab da mal was in QBasic 
zusammengepfuscht. Aber ob das immer die optimale Lösung liefert, bzw. 
ob das die Lösung des Problems wäre ist ja die Frage...)

[A. S. (rava)]

übrigens: ich bin davon ausgegangen, dass du mehrere Rezepte hast.

Wenn du nur ein Rezept hast, rechnest du, als wäre deine Kiste beliebig 
mit Teilen füllbar. Das wäre Schulniveau. Dann rundest du auf "ganze 
Behälter" ab.

[A. S. (Gast)]

Für 1 Rezept brauchst Du (mindestens) pro Zutat eine Kiste. du kannst 
dann einfach hochzählen.

Du kannst für jede Zutat den fraktionalen Teil einer Kiste bestimmen. 
Und damit binär suchen.

Du kannst auch einen term bestimmen, der aber wenig hilfreich ist, da er 
mit auf- und abrunden arbeitet.

[A. S. (Gast)]

N=[n*fq] + [n*f2] + ... [n*fx]

Mit N=Anzahl Kisten und f = Anteil der Zutat und []= aufrunden und n = 
Anzahl der Kuchen

Bei N=30 und 3 Zutaten ist die Mindestmenge 27/(f1+f2+f3).

Die Maximalmenge entsprechend 30/(f1+f2+f3)

Dazwischen reicht es nummerisch.

[Helmut H. (helmuth)]

A. S. schrieb:
> Es braucht einen Algorithmus.


Ist wesentlich einfacher als das Rucksackproblem, da man die optimale 
Lösung nach max Anzahl Behälter hat:

Man nimmt einen Behälter von jeder Sorte und berechnet die resultierende 
Anzahl Kuchen:

          A     B     C
Kiste     1     1     1
Kuchen   26   115    34

Von der Sorte mit der kleinsten Zahl Kuchen füllt man einen weiteren 
Behälter:

Kiste     2     1     1
Kuchen   53   115    34

Bis 27 Behälter verteilt sind:

Kiste     13    3    11
Kuchen   346  345   374

Man kann also 345 Kuchen backen.

[A. S. (Gast)]

Helmut H. schrieb:
> Von der Sorte mit der kleinsten Zahl Kuchen füllt man einen weiteren
> Behälter:

Die ersten 313 kann man aich mit obiger Formel sparen und ab da 
weiterfüllen.

Uups, bei 27 Kisten und 3 Zutaten kann man mit 27-2=25 rechen.

Also mit 25/(1/26+1/115+1/34)=326 starten

[Jens M. (schuchkleisser)]

Oh, jetzt geht's los!
Danke schonmal für die Ideen!

Also:
Es ging drum, die Kiste (den Rucksack) so zu packen, das die maximale 
Anzahl "Kuchen" rauskommt, egal wie viele das sind.

Als Anwendungsfälle sind uns verschiedene Sachen eingefallen, 
Backmischungen sind da nur ein naheliegendes Beispiel. ;)
Z.B. Kram für's Zeltlager einpacken, Kindergeburtstagsaustattungen, 
Partygetränke, und natürlich auch Bastelzeug, z.B. Bausätze für 
Veranstaltungen, wenn man die z.B. in Sortierkästen räumt.

Von daher wird immer nur ein Rezept angewendet, und es wird wohl nur 
relativ wenige Zutaten geben, ich würde mal "<10" ansetzen; Anzahl der 
Dosen wird auch so 10-50 sein.

Ich muss das mal durchdenken und ausprobieren, aber sieht sehr 
interessant aus!

[A. S. (rava)]

> Wenn du nur ein Rezept hast, rechnest du, als wäre deine Kiste beliebig
> mit Teilen füllbar. Das wäre Schulniveau. Dann rundest du auf "ganze
> Behälter" ab.

also bei deinem Beispiel
> - Kiste schafft z.B. 27 Behälter
> - Ein Behälter schafft 80x A oder 115x B oder 34x C
> - Ein Rezept erfordert 3x A, 1x B, 1x C

27 = 3/80x + 1/115x + 1/34x

bzw.

27 = 0.0756x

damit erhältst du die Anzahl der Kuchen x zu 357,1

Für 357,1 Kuchen brauchst du
* 1071,3 x A (13,4 Behälter)
* 357,1 x B (3,1 Behälter)
* 357,1 x C (10,5 Behälter)

Wenn du also 13 Behälter A, 3xB und 10xC mitnimmst (alle abrunden), 
bekommst du dafür:
aus A: 13 * 80 // 3 = 346 Kuchen
aus B: 3 * 115 // 1 = 345 Kuchen
aus C: 10 * 34 // 1 = 340 Kuchen

C ist also limitierend. Dann also den verbleibenden Platz mit einem 11. 
Behälter C voll machen und 345 Kuchen backen.

[Christoph Z. (christophz)]

Jens M. schrieb:
> z.B. in Excel oder so?

Nur als Ergänzung zu allem richtigen das schon gesagt wurde:

In Excel und LibreOffice Calc gibt es dazu den Solver um solche 
Optimierungsfragen zu lösen. Der kann auch Integer Linear Programming 
(zu dem dein Problem und der Knapsack gehhört):
https://en.wikipedia.org/wiki/Integer_programming

[Thomas (kosmos)]

für mich wäre ganz entscheidend welcher Kuchen wie oft gebacken wird und 
wie die Verteilung der Zutaten ist.

z.B:
Kuchen 1: 40% Zutat A; 20% Zutat B; 10% Zutat C; ....
Kuchen 2: 40% Zutat A; 10% Zutat D;  5% Zutat E; ....

Wenn da Kuchen 2 aber 8 von 10 ausmacht, wird man nicht soviel von der 
Zutat B sondern eher von D vorhalten müssen.

[Yalu X. (yalu) (Moderator)]

Ich habe die Vorgehensweise von von A. S. (rava) mal in Python
umgesetzt:

#!/usr/bin/env python3

from fractions import Fraction
import numpy as np

def solve(task):
  n_containers_per_box, part_info = task
  n_containers_per_cake = np.array([Fraction(*part) for part in part_info])
  n_cakes_theor = n_containers_per_box / np.sum(n_containers_per_cake)
  n_containers_total = np.floor(n_cakes_theor * n_containers_per_cake)
  n_cakes_by_part = n_containers_total / n_containers_per_cake
  delta = n_containers_per_box - np.sum(n_containers_total)
  sorted_indices = n_cakes_by_part.argsort()
  n_containers_total[sorted_indices[:delta]] += 1
  n_cakes_real = np.floor(n_cakes_by_part[sorted_indices[delta]])
  return n_containers_total, n_cakes_real

example = (
  27,          # Anzahl der Behälter in der Kiste
  [            # Für jeden Teiletyp:
    (3,  80),  # Anzahl der Teile im Kuchen, Anzahl der Teile in jedem Behälter
    (1, 115),
    (1,  34),
  ]
)

n_containers_total, n_cakes_real = solve(example)
print('Anzahl Behälter:', n_containers_total)
print('Anzahl Kuchen:  ', n_cakes_real)

Ausgabe:

Anzahl Behälter: [13 3 11]
Anzahl Kuchen:   345

[Joachim B. (jar)]

frage doch diese Dame
https://www.youtube.com/c/MathemaTrick

[Michael M. (Firma: Autotronic) (michael_metzer)]

Zusatzaufgabe:

Jens und Helmut haben ihre leckeren Sahnetorten in ihre jeweiligen 
Rucksäcke gepackt. Sagt Jens zu Helmut: 'Gib mir eine deiner 
Sahnetorten, dann habe ich genauso viele Sahnetorten wie du.' Helmut 
erwidert: 'Ja, aber wenn du mir eine von deinen Sahnetorten gibst, dann 
werde ich doppelt so viele Sahnetorten haben wie du.'

Frage: Wer hat anfangs wie viele Sahnetorten dabei? 🍰

[Yalu X. (yalu) (Moderator)]

Michael M. schrieb:
> Frage: Wer hat anfangs wie viele Sahnetorten dabei? 🍰

Zu leicht :)

[Josef C. (josefc)]

Hier eine Loesung mit https://eclipseclp.org.

Vorsicht Prolog Code.

Funktioniert auch fuer mehrere Rezepte.

% www.mikrocontroller.net/topic/540819
:- lib(ic).
:- lib(branch_and_bound).

first_elem([],[],[]).
first_elem([[A|As]|L], [A|P], [As|Rs]) :- first_elem(L, P, Rs).

listexprs([],[],[]).
listexprs([A|As], [B|Bs], [A*B|Es]) :-
        listexprs(As,Bs,Es).

constraintsR([],_Ms,_Rs,_Ks).
constraintsR([V|Vs],[M|Ms],Rs,Ks) :-
        first_elem(Rs, R1s, Rss), 
        listexprs(R1s,Ks,Lex),
        % V * M #>= K1 * R1 + K2 * R2,
        V * M #>= sum(Lex),
        constraintsR(Vs,Ms,Rss,Ks).

% R Rezepte.
% kisteR(27, [80,115,34],[[3,1,1]], Sol).
% kisteR(27, [80,115,34],[[3,1,1],[1,1,2]], Sol).
kisteR(N, Ms, Rs, Vars -> Ks) :-
        length(Ms,MN),
        length(Vars, MN),
        length(Rs,RN),
        length(Ks,RN),     
        Vars :: 0..N,
        Ks :: 0..1.0Inf,
        sum(Vars) #=< N,
        constraintsR(Vars,Ms,Rs,Ks),
        append(Vars,Ks,Varx),
        Goal #= -sum(Ks),
        bb_min(labeling(Varx), Goal, bb_options{strategy:dichotomic}).

Ausgabe:

kisteR(27,[80,115,34],[[3,1,1]],Sol).
Found a solution with cost 0
... Einige Log Ausgaben ...
Sol = ([13, 3, 11] -> [345])
Yes (0.00s cpu)

Und ein Programm fuer die Torte:

torte(Jens,Helmut) :-
        [Jens,Helmut] :: 0..1000,
        Jens + 1       #=  Helmut - 1,
        (Jens - 1) * 2 #= (Helmut + 1),
        labeling([Jens,Helmut]).

Die Tortenausgabe spar ich mir mal.

[Jens M. (schuchkleisser)]

Thomas O. schrieb:
> Wenn da Kuchen 2 aber 8 von 10 ausmacht, wird man nicht soviel von der
> Zutat B sondern eher von D vorhalten müssen.

Nuja, pro Kiste (bzw. deren Belegung) gibt's nur ein Rezept.
Es gibt mehrere Rezepte, aber jedes wird nue gepackt.
Wir wollen die Kirche ja mal im Dorfe lassen...

Yalu X. schrieb:
> Ich habe die Vorgehensweise von von A. S. (rava) mal in Python
> umgesetzt:

Höhö, das muss ich mal testen! Danke!

Michael M. schrieb:
> Wer hat anfangs wie viele Sahnetorten dabei?

5 bzw. 7
Habs im Kopf ausprobiert...

[Helmut H. (helmuth)]

Übrigens findet man eine Lösung auch mit einem Verfahren zu 
Sitzverteilung nach Wahlen, z. B.
https://staatsrecht.honikel.de/de/sitzzuteilungsrechner.htm

Es sind 27 Sitze zu vergeben, die Anzahl Stimmen ist

 A  100000*3/80  = 3750
 B  100000*1/115 =  870 
 C  100000*1/34  = 2941

Sainte-Laguë/Schepers und Hare-Niemeyer kommen richtig  auf  13 A, 3 B, 
11 C.
D'Hondt bevorzugt bekanntlich die größte Partei und bringt eine 
suboptimale Lösung.

[🕵︎ Joachim L. (Gast)]

Warum nicht erst mal gucken, was es da so an Open Source Lösungen gibt?

https://github.com/search?o=desc&q=Rucksackproblem&s=updated&type=Repositories

Bessere Ergebnisse gibt es für Leute die "Neudeutsch" lesen koennen, 
bzw. wissen wie man Übersetzungs Webseiten benutzt: knapsack problem

https://github.com/search?q=knapsack+problem&type=Repositories

über 3000 Hits!

Oben rechts lässt sich die Sortierung auswählen, sollte man benutzen.

Eine passende Lösung zu finden ist sehr zeitaufwendig, aber ein 
passender Lösungsansatz als Starthilfe für das eigene Programm ist fast 
immer drin. Probiert es mal aus.

Hier z.B. eine Lösung mit 3D-Vizualisierung und fertigem Windows 
Programm sowie Quellcode und Bildern.

https://github.com/JAhimaz/KnapsackProblemSimulation

[Yalu X. (yalu) (Moderator)]

Joachim L. schrieb:
> Warum nicht erst mal gucken, was es da so an Open Source Lösungen gibt?
>
> https://github.com/search?o=desc&q=Rucksackproblem&s=updated&type=Repositories

Das Problem des TE ist weder das Rucksackproblem noch eine
Spezialisierung oder Verallgemeinerung davon.

Mein oben vorgestelltes Python-Progrämmchen löst das TE-Problem in
O(n·log n). Wenn du einen O(n·log n)-Algorithmus für das Rucksackproblem
findest, bist du der Informatik-King.