Laden...

Wie kann ich im C# Werte berechnen, so wie Excel das auch macht?

Erstellt von OXO vor 3 Jahren Letzter Beitrag vor 3 Jahren 952 Views
O
OXO Themenstarter:in
86 Beiträge seit 2020
vor 3 Jahren
Wie kann ich im C# Werte berechnen, so wie Excel das auch macht?

Hallo,

ich habe mir in Excel ein kleine Tabelle gemacht, die mit Hilfe des Excel-Solvers optimale Mengen errechnet.

Dazu habe ich ein Schema, wie im angehängten Screenshot.

In Spalte A sind Artikel hinterlegt, die man auswählen kann. Zu jedem Artikel sind kleinere Werte W1 - W3 auf 100g hinterlegt (Spalten B - D). In den Spalten E und F kann man angeben, in welchem Bereich sich die Mengen bewegen müssen

In Zeile 12 gibt es ein Summenprodukt mit der Menge aus Spalte G. In Zeile 13 wird als Beschränkung angegeben, wie hoch dieses Summenprodukt maximal sein darf. Der Solver errechnet dann die optimalen Mengen in der Spalte G, um diese Summenprodukte möglichst hoch zu machen, damit die Werte der Zeile 13 möglichst optimal erreicht werden. Hierzu hat der Solver Beschränkungen, so dass die Werte über die Formel =(B13-B12)+(C13-C12)+(D13-D12) möglichst klein werden. Nennen wir das mal die Abweichung oder den Fehler, der dann möglichst klein sein soll.

Meine Frage: wie kann ich diese Berechnung mit C#-Bordmitteln machen? Das Problem ist, dass ich das Ganze später auf meinem Handy laufen lassen möchte, bei dem ich keinen Excel-Solver zur Verfügung habe und möglichst auch keine externe Bibliothek einbinden möchte. Wie erreiche ich denn die Berechnung dieser möglichst optimalen Mengen so?

6.911 Beiträge seit 2009
vor 3 Jahren

Hallo OXO,

ganz verstanden hab ich nicht was du optimieren willst, aber ich denke es ist Suche nach "Knappsack" bzw. Suche nach "Rucksack".

mfG Gü

Stellt fachliche Fragen bitte im Forum, damit von den Antworten alle profitieren. Daher beantworte ich solche Fragen nicht per PM.

"Alle sagten, das geht nicht! Dann kam einer, der wusste das nicht - und hat's gemacht!"

309 Beiträge seit 2020
vor 3 Jahren

Bzgl. Optimierung / Annäherung an Null kenne ich das Newtonverfahren. Vielleicht hilft das hier auch.

O
OXO Themenstarter:in
86 Beiträge seit 2020
vor 3 Jahren

Eigentlich geht es darum, die Mengen in Spalte G errechnen.
Das sind natürlich am Ende optimierte Mengen, so dass die Werte der Zeile 12 möglichst nahe an die gesetzten Werte der Zeile 13 ran kommen.

Die Spalten werden dabei jeweils mit der zu errechnenden Menge aus Spalte G multipliziert.

Als Beispiel ergibt sich in B12 das Ergebnis wie folgt:

B4G4 + B5G5 + B6G6 + B7G7 + ... + B10*G10

G12 errechnet sich wie folgt:
(B13-B12) + (C13-C12) + (D13-D12)

Bedeutet also, das ist die Abweichung vom "Optimum" und diese sollte möglicht gering werden und nahe 0 sein.

Die Spalten E und F (Mindest- und Höchstmenge) sind einfach nur die Grenzen zwischen denen sich die optimale Menge der zu errechnenden Spalte G bewegen darf.

F
10.010 Beiträge seit 2004
vor 3 Jahren

Du weisst also wie es sich berechnet, wo ist dann jetzt das Problem das Du nicht gelöst bekommst?

O
OXO Themenstarter:in
86 Beiträge seit 2020
vor 3 Jahren

Denke, an dem, wie man es effizient bzw. am besten aufbaut.

Die Artikelmenge, also die Zeilen ab Zeile 4 sind von der Anzahl her variabel. Es kann 1, 2, ... Artikel geben, die zu berücksichtigen sind.

Für jede Zeile bzw. für jeden Artikel müsste ich alle Werte zwischen der Mindestmenge und Höchstmenge "durchprobieren". Also sozusagen gibt es doch dann für jeden Artikel eine weitere Schachtelung, also eine innere Schleife.

Also irgendwie ergibt das ja für jeden Artikel bzw. für jede Mindest- und Höchstmenge eine weitere geschachtelte Schleife, die von der Mindest- bis zur Höchstmenge laufen kann. Praktisch für jeden weiteren Artikel einen "Berechnungspfad".

Das verwirrt mich gerade, wie man sowas effizient angehen und gestalten könnte.

F
10.010 Beiträge seit 2004
vor 3 Jahren

Hast Du denn schon mal ausprobiert wie schnell es ist, wenn du es einfach mal so implementierst?
Wahrscheinlich ist die Berechnung schneller, als Du denkst und du musst nichts optimieren.

Nur dran denken, du arbeitest dann mit den Werten, und nicht mit irgendwelchen UI Controls.

O
OXO Themenstarter:in
86 Beiträge seit 2020
vor 3 Jahren

Mittlerweile ist die Geschwindigkeit ein nebensächliches Problem.

Ich hab keine vorgegebene Anzahl an Artikeln, sondern es können theoretisch beliebig viele sein.
Hab mir im Voraus mal Matrizen (Arrays) aufgebaut, die erst einmal alle Multplikationen von der angegebenen Mindestmenge, bis zur angegebenen Höchstmenge mit den angegebenen Grundwerten pro Spalte machen, also etwa so

Artikel 1:
Mindestmenge: 1
Höchstmenge 30
Grundwerte: 0.22 ; 0.83 ; 0.42

Dann würde für diesen Input eine Matrix mit den berechneten Werten entstehen. Die letzte Spalte enthält dann die Menge selbst, mit der die Berechnung gemacht wurde.

1x0.22 1x0.83 1x0.42 1
2x0.22 2x0.83 2x0.42 2
..
30x0.22 30x0.83 30x0.42 31

Artikel 2:
Mindestmenge: 100
Höchstmenge 500
Grundwerte: 0.12 ; 0.53 ; 0.31

100x0.12 100x0.53 100x0.31 100
101x0.12 101x0.53 101x0.31 101
..
100x0.12 100x0.53 100x0.31 500

Das Ganze für n Artikel dann mit n Arrays dieser Form.

Im Anschluß muss ich ja irgendwie versuchen alle Kombinationsmöglichkeiten zu bilden, um die Spalten-Summen und den Fehler-Wert (Abweichung) zu berechnen.

Die maximalen Spalten-Summen sind ja vorgegeben. Nachdem für eine Mengen-Konfigurtion die Spalten-Summen errechnet wurden, kann dann der Fehler-Wert, sprich die Abweichung zur vorgegebenen maximal erlaubten Spalten-Summe berechnet werden.

Eine Mengen-Konfiguration wäre dann am Ende z.B.
Artikel 1: Menge 10
Artikel 2: Menge 7
..
Artikel n: Menge 100

Mit diesen Mengen würde man ja für jede der 3 Spalten pro Artikel eine Zeile bekommen und kann sich dann die Spalten-Summe errechnen und sehen, ob diese möglichst optimal erreicht wird. Ob diese möglichst optimal erreicht wird, erkennt man am Fehler-Wert, der sagt, wie arg die Spalten-Summen von den Vorgaben abweichen. Dieser muss dann also möglichst klein sein.

Hat man erst einmal alle Kombinationsmöglichkeiten erstellt, kann man den Wert mit dem kleinsten Fehlerwert nehmen und hat damit die Vorgaben möglichst optimal ausgereizt.

Also vom Algorithmus her, nehme Zeile 1..n der Matrix 1 (Artikel 1), kombiniere diese mit Zeile 1..n der Matrix 2 (Artikel 2) kombiniere diese mit Zeile 1..n der Matrix n (Artikel n), berechne die jeweilige Spalten-Summen und den Fehler-Wert mit der Abweichung zu den vorgegebenen maximal erlaubten Spalten-Summen.

Ich hab die Berechnung aller Kombinationen mal mit Rekursion gemacht, da ich ja bei beliebiger Anzahl Artikel fast nicht anders ran komme, oder? Bei jedem Absteigen hab ich mir die nächste Instanz in eine Art Decorator eingepackt, um unten dann optimal die Spalten-Summen für diese Konfiguration errechnen zu können. Auf dem Weg hab ich mir auch noch eingesammelt, mit welcher Mengen-Konfiguration über die verschiedenen Artikel ich es gerade zu tun habe.

Am Ende hätte ich damit eine riesen Matrix mit allen Mengen-Konfigurationen und dem Error-Value dazu. Der kleinste Error-Value ist dann die optimalste Mengen-Konfiguration.

Man kann sich leicht vorstellen, dass das erstens schon dauern kann das alles zu berechnen, wenn man schon mit 4 - 5 Artikel arbeitet. Zweitens hab ich das Problem, dass mir jetzt der Speicher übergelaufen ist, weil das mit den ganzen Werten doch über die 2 GB raus ging. Vermutlich auch ein Stück wegen der Rekursion, wobei ich mir nicht sicher bin, wie arg die da überhaupt rein spielt, oder ob das nicht nur der Speicher der Ziel-Matrix ist.

Im Grunde bräuchte ich ja auch nicht alle diese Kombinationen vorrätig halten und berechnen, aber wie bestimme ich sonst die Spalten-Summen einer bestimmten Konfiguration aus n Artikeln?

Hab Ihr da ein paar Ideen , wie ich das algorithmisch anders machen könnte, oder vermeiden könnte, dass mir auf diese Weise der Speicher volläuft?

16.807 Beiträge seit 2008
vor 3 Jahren

da man ja algorithmisch keine n for-Schleifen fest vorgeben kann.

Dafür gibts Stack<T>

Trotdem kann man sich leicht vorstellen, dass das erstens schon dauern kann wenn man schon 4 - 5 Artikel nimmt.

Also ich ehrlich gesagt nicht.
Das sollte eigentlich nicht lange dauern dürfen.

Rucksackproblem Berechnungen sind eigentlich vergleichweise effizient.

oder vermeiden könnte, dass mir auf diese Weise der Speicher volläuft?

Dafür gibt es kein pauschales Vorgehen.

Das 2 GB Limit existiert nur für einzelne Objekte; nicht für den Prozess (das wurde vor ~10 Jahren entfernt).
Bei solchen Berechnungen bietet sich oft das Laden in den Speicher an; und wenn das geworfen wird dann ist das heutzutage meist ein Code Design Issue.