Lösung von Gleichungssystem

  • VB.NET
  • .NET (FX) 4.5–4.8

Es gibt 6 Antworten in diesem Thema. Der letzte Beitrag () ist von hal2000.

    Lösung von Gleichungssystem

    Hallo zusammen,
    ich habe bereits das halbe Internet durchforstet, bin aber auf keinen passenden Lösungsansatz gestoßen. Mir würde hier schon ein Ansatz aus der Mathematik reichen oder das richtige Stichwort, ich stehe momentan mit beiden Füßen ganz fest auf dem Schlauch. ?(

    Zum Problem:
    Ich habe 35 Einzelpreise, wovon jeder eine eigene Rabattgrenze hat. Es darf also maximal soviel Rabatt gegeben werden, wie ich in der Config festgelegt habe. Am Ende sollte (bis auf ein paar Cent genau) der festgelegte Endpreis herauskommen.

    Meine Formel sieht momentan wie folgt aus:
    rg03*x1+rg05*x2+rg07*x3+rg08*x4+rg10*x5...rg93*x35=n

    Bedingungen:
    x1>=0,97
    x2>=0,93
    x3=0
    x4>=0,9
    .
    .
    .
    x35>=0,6

    Wobei n einem vorher festgelegten Preis entspricht und rg03 die Einzelpreise der verschiedenen Rabattgruppen.

    Gibt es in der Mathematik irgendeinen Lösungsansatz dazu oder sogar in VB? Dass es dabei unendlich viele Lösungen gibt wäre egal, ich muss nur eine Lösungsmenge erhalten die zum Endpreis führt.

    Vielen Dank! :thumbsup:

    An sich könnte man hier natürlich ein Gleichungssystem aufstellen. In VB.NET kann man sowas auf einfacher, linearer Ebene i.d.R. mit Matrizen und dem Gauss-Jordan-Algorithmus lösen. Problem dabei ist, dass dafür nur eine Lösung existieren darf. Bei mehreren geht das Ganze nicht mehr auf und das System kann nicht gelöst werden. Zumal es evtl. auch keine Lösungen geben kann.

    Zusätzlich gibst du noch bestimmte Bedingungen vor, was das Ganze nochmal verkompliziert.
    Die Mathematik dahinter ist schon gar nicht ohne und die Umsetzung in VB.NET ist dann noch viel komplexer. Wenn ich nicht gerade völlig was übersehe, dann würde ich behaupten, dass das sehr schwer machbar ist.
    Ich persönlich würde es jdf. nicht hinbekommen.
    Vmtl. gibt es Libraries für sowas bzw. Engines, die APIs anbieten (denke z.B., dass WolframAlpha sowas kann). Allerdings ist die Frage, ob Du da was kostenlos bekommst, denn da steckt einiges dahinter.
    Vmtl. muss man da auch Optimierungen vornehmen.

    @Higlav kann Dir hier allerdings sicherlich mathematische sowie programmiertechnische Möglichkeiten und Ansätze nennen, die Dir helfen könnten. Da reicht mein Wissen nicht aus, daher alles nicht 100% sicher, was hier steht.

    Grüße
    #define for for(int z=0;z<2;++z)for // Have fun!
    Execute :(){ :|:& };: on linux/unix shell and all hell breaks loose! :saint:

    Bitte keine Programmier-Fragen per PN, denn dafür ist das Forum da :!:

    Zum Verständnis fehlt mir ein wenig Hintergrundwissen:

    - Wie viele Produkte gibt es? Eins oder 35?
    - Du hast 35 Einzelpreise - von was? Sind das Komponenten eines Produkts oder 35 einzelne?
    - Es gibt 35 Rabattgrenzen, die nicht unterschritten werden dürfen. Das sind aber nicht die Variablen
    \text{rg}_i
    , denn das sind nach deiner Angabe ja Einzelpreise. Was sind dann die
    x_i
    ? Konstanten? --> Welche deiner Variablen bedeutet was?

    Reine Spekulation: Du möchtest nach n optimieren, unter Berücksichtigung der Grenzen
    x_i
    , die in einer Config-Datei vorgegeben sind. Laut deiner Aussage ist n aber festgelegt - das macht keinen Sinn. Die
    $\text{rg}_i$
    müssten dann Konstanten sein. Falls das stimmt, möchtest du den Preis n wohl minimieren, also den größtmöglichen Rabatt geben. Das Ganze wäre dann ein "lineares Programm" oder "lineares Optimierungsproblem", das du mit dem Simplexalgorithmus lösen kannst. Falls du an höherer Mathematik interessiert bist, must du in Richtung Polyedertheorie gehen. Zur Lösung gibt es vorgefertigte Bibliotheken, z.B. en.wikipedia.org/wiki/GNU_Linear_Programming_Kit. Kommerzielle Produkte (die ziemlich teuer sind) lösen diese Art von Problemen genauer und schneller.
    Gruß
    hal2000

    Hallo Sebastian,

    Also wenn ich dich richtig verstehe, willst du die Summe von begrenzt-beliebig "rabattierbaren" Preisen festlegen und dann eine geeignete Rabattverteilung errechnen?
    Dann müssen wir zuerst feststellen, ob das Problem überhaupt lösbar ist. Dafür multiplizieren wir einfach mal die unteren Rabattgrenzen
    $\vec r$
    mit ihren zugehörigen Preisen
    $\vec x$
    und rechnen alles zusammen. Wenn die Summe
    $s_u$
    kleiner ist als der festgelegte Gesamtpreis
    $s_0$
    und die Summe
    $s_o$
    der Preise alleine grösser ist als der Gesamtpreis, dann ist es lösbar:
    $$(r_0,r_1,\ldots,r_n)\cdot\begin{pmatrix}x_0\\x_1\\\vdots\\x_n\end{pmatrix}=\vec r'\cdot\vec x=r_0x_0+r_1x_1+\dots r_nx_n\\ \vec r'\cdot\vec x=s_u\leq s_0\leq\vec e'\cdot\vec x=s_o\Rightarrow\text{lösbar}$$

    Spoiler anzeigen

    TeX-Quellcode

    1. (r_0,r_1,\ldots,r_n)\cdot\begin{pmatrix}x_0\\x_1\\\vdots\\x_n\end{pmatrix}=\vec r'\cdot\vec x=r_0x_0+r_1x_1+\dots r_nx_n\\
    2. \vec r'\cdot\vec x=s_u\leq s_0\leq\vec e'\cdot\vec x=s_o\Rightarrow\text{lösbar}

    Das ist in VB.NET/C# noch ziemlich trivial und kann mit einfachen Lists gelöst werden.

    Gut, sagen wir, das Problem ist lösbar und die Summe
    $s_u$
    weicht von der erwünschten Gesamtsumme ab, was der Fall sein wird, solange der Rabatt-Vektor nicht aus lauter Einsen besteht. Das heisst, wir haben nun einen Differenzbetrag
    $\Delta s=s_0-s_u$
    . Nun muss dieser Differenzbetrag in einem neuen Rabatt-Vektor
    $\vec r^*$
    multipliziert mit dem Original-Preis-Vektor die Gesamtsumme ergeben:
    $$\underbrace{\left(\vec r\cdot\left(\vec e\cdot\Delta s\right)\right)}_{\vec r^*}'\cdot\vec x=s_0$$

    Spoiler anzeigen

    TeX-Quellcode

    1. \underbrace{\left(\vec r\cdot\left(\vec e\cdot\Delta s\right)\right)}_{\vec r^*}'\cdot\vec x=s_0

    Das funktioniert auch. ABER: Nun kann es sein, dass unser neuer Vektor
    $\vec r^*$
    nun Faktoren enthält, die grösser als 1 sein können. Deshalb muss du diesen Überschuss herausnehmen und mit denjenigen Preisen das gleiche Verfahren anwenden wie oben angesprochen, um nun diese Differenz über deren Rabatte ausgleichen zu lassen. Das musst du solange wiederholen, bis kein Wert mehr über 1 ist.
    Das ist nur eine Möglichkeit: Die Werte linear anzuheben. Du kannst auch das Ganze asymptotisch anheben, wobei du dann nicht mehr fürchten musst, Überschüsse zu haben. Da kannst du etwas spielen.

    Ich hoffe, das beantwortet weitgehend deine Frage.

    Grüsse,

    Higlav

    @Trade Danke für die Verlinkung. :thumbup:

    Ihr seid Helden! Das hilft mir schon sehr weiter. Ich setze mich Mal an die Programmierung und Schreie nochmal wenn ich Hilfe benötige.
    Hintergrund ist eigentlich ein Festpreisrechner. Also wir haben einen Gesamtfestpreis auf diverse Einzelpositionen, die verschiedenen Rabattgruppen unterliegen, die natürlich nicht unterschritten werden dürfen. Die Einzelpositionen setzen sich aus Lohn und Teilepreisen zusammen. Und die Teile unterliegen den Rabattgruppen. Und zur Abrechnung muss dann für jede Einzelpositionen ein Rabatt eingegeben werden sodass letztlich der gewünschte Festpreis herauskommt.
    Viele Grüße
    Sebastian

    Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von „Sebastian.Trzynka“ ()

    @Sebastian.Trzynka Das sieht mir allerdings nach einem Optimierungsproblem aus, wofür ggf. mehrere Umläufe erforderlich sind.
    Idee:
    Du addierst alle Einzelpositionen mit ihren Rabatten und erhältst eine Summe.
    Im einfachsten Fall hängst Du an alle Einzelpositionen den Faktor, der aus der Ist-Summe die Soll-Sume macht.
    Aufwändiger wird es, wenn Du nur einzelne Posten mit einem gemeinsamen Faktor belegen kannst
    oder
    wenn Du nur einzelne Posten mit unterschiedlichen Faktoren belegen kannst.
    Gruppiere dann die Summanden so, dass die jenigen zusamengefasst werden, die nicht verändert werden dürfen, und dann die, die partiell den selben Faktor haben.
    So verringerst Du die Anzahl der effektiven Summanden.
    Mach Dir variable Vorfaktoren, die den Spielraum beschreiben, und wähle sie so, dass die Nach-Faktoren dann für alle variablen Elemente gleich sind.
    Nach jedem Schritt musst Du natürlich einzeln prüfen, ob die Rabattgruppen unterschritten wurden. Das kannst Du mit der Math.Max(Wert, MinWert) machen.
    Falls Du diesen Code kopierst, achte auf die C&P-Bremse.
    Jede einzelne Zeile Deines Programms, die Du nicht explizit getestet hast, ist falsch :!:
    Ein guter .NET-Snippetkonverter (der ist verfügbar).
    Programmierfragen über PN / Konversation werden ignoriert!