Laden...

Lineare Gleichungen mit n-Variablen lösen lassen

Erstellt von OXO vor einem Jahr Letzter Beitrag vor einem Jahr 657 Views
O
OXO Themenstarter:in
86 Beiträge seit 2020
vor einem Jahr
Lineare Gleichungen mit n-Variablen lösen lassen

Hallo,

ich möchte ein Programm schreiben, das Lösungen für bis zu 10 Gleichungen finden kann (prinzipiell auch denkbar, es auch auf n zu erweitern => das macht aber eher weniger Sinn von der Laufzeit her).

Die Gleichungen sind im Grunde über Constraints definiert:

  • Es gibt eine Auswahl 1 ... Auswahl n
  • Jede Auswahl 1 .. Auswahl n hat einen Datenvektor mit 3 Konstanten, mit denen Werte x1 .. xn multipliziert werden
  • Spaltensumme A ≤ erlaubtes Maximum Spalte A
  • Spaltensumme B ≤ erlaubtes Maximum Spalte B
  • Spaltensumme C ≤ erlaubtes Maximum Spalte C
  • Ein Fehler-Wert ist definiert als Abstand der jeweiligen Spaltensumme zum erlaubten Maximum der Spalte: (Max_A - Summe_Spalte_A) + (Max_B - Summe_Spalte_B) + (Max_C - Summe_Spalte_C)
  • Aufgabe: Finde x1 .. xn, so dass der Fehler-Wert möglichst gering ist

Als Beipiel die Datenvektoren für eine Ausahl:

  • Auswahl 1 = (0.01 0.04 0.332)
  • Auswahl 2 = (0.21 0.5 0.12)
  • ...
  • Auswahl n = (0.71 0.24 0.332)
  • Die Werte aus Spalte A, B und C ergeben sich immer durch Multiplikation des Datenvektors mit dem zu findenden x1 ... xn

Dann ergiben sich Constraints etwa in der Form:

  • Constraint 1: Spaltensumme A ≤ Max_A

  • Constraint 2: Spaltensumme B ≤ Max_B

  • Constraint 3: Spaltensumme C ≤ Max_C

  • x1 .. xn sind ganzzahlig

  • x1 muss zwischen .. und .. sein (diese Mindest und Höchstwerte muss man vorgeben und sind ≥0)

  • x2 muss zwischen .. und .. sein (diese Mindest und Höchstwerte muss man vorgeben und sind ≥0)

  • x3 muss zwischen .. und .. sein (diese Mindest und Höchstwerte muss man vorgeben und sind ≥0)

  • Fehlerwert: (Max_A - (0.01x1 + 0.04x2 + ... + 0.332xn)) + (Max_B - (0.21x1 + 0.6x2 + ... + 0.12xn)) + (Max_C - (0.71x1 + 0.24x2 + ... + 0.332*xn))

  • Finde x1 ... xn, so dass der Fehlerwert möglichst minimal wird (sofern es eine Lösung gibt!)

Wie könnte man denn möglichst performant so ein System über einen C#-Algorithmus lösen lassen?

G
154 Beiträge seit 2015
vor einem Jahr

Lineare Optimierung unter Zwangsbedingungen -> Simplex Verfahren.
Habe jetzt keine konkrete Implementierung parat, aber das gibt es bestimmt schon zu Hauf.

O
OXO Themenstarter:in
86 Beiträge seit 2020
vor einem Jahr

Danke für den Hinweis mit dem Simplex-Algorithmus!

Ich habe das mal mit folgender Implementierung versucht, aber noch etwas Probleme, wie ich meine Constraints richtig machen muss:
https://gist.github.com/trevordixon/9702052

Meine Coeffizienten für x1 ... x4 sind folgende:
Auswahl 1: 0.09 0.069 0.52
Auswahl 2: 0.21 0.02 0.006
Auswahl 3: 0.841 0.011 0.011
Auswahl 4: 0.31 0.17 0.005

Die Constraints für Spalte A, B und C sind folgende:
0.09x1 + 0.21x2 + 0.841x3 + 0.31x4 ≤ 65
0.069x1 + 0.02x2 + 0.011x3 + 0.17x4 ≤ 20
0.52x1 + 0.006x2 + 0.011x3 + 0.005x4 ≤ 45

Die Constraints für x1 ... x4:
x1 ≥ 60 --> Als ≤ Constraint formuliert: -x1 ≤ -60
x1 ≤ 120
x2 ≥ 0 --> Als ≤ Constraint formuliert: -x2 ≤ 0
x2 ≤ 150
x3 ≥ 1 --> Als ≤ Constraint formuliert: -x3 ≤ -1
x3 ≤ 100
x4 ≥ 0 --> Als ≤ Constraint formuliert: -x4 ≤ 0
x4 ≤ 100

Der Fehlerwert bzw. meine Zielfunktion ist eigentlich eine Minimierungsfunktion, muss aber beim Simplex-Algorithmus wohl dann in eine **Maximierungsfunktion **umgebaut werden.

Zunächst die Zielfunktion als Minimierungsfunktion umgeformt:
(65 - (0.09x1 + 0.21x2 + 0.841x3 + 0.31x4)) + (20 - (0.069x1 + 0.02x2 + 0.011x3 + 0.17x4)) + (45 - (0.52x1 + 0.006x2 + 0.011x3 + 0.005x4)) --> Min
(65 - 0.09x1 - 0.21x2 - 0.841x3 - 0.31x4) + (20 - 0.069x1 - 0.02x2 - 0.011x3 - 0.17x4) + (45 - 0.52x1 - 0.006x2 - 0.011x3 - 0.005x4) --> Min
130 - (0.09x1 + 0.069x1 + 0.52x1) - (0.21x2+0.02x2+0.006x2) - (0.841x3+0.011x3+0.011x3) - (0.31x4+0.17x4+0.005x4) --> Min
130 - (0.679x1) - (0.236x2) - (0.863x3) - (0.485x4) --> Min
130 - 0.679x1 - 0.236x2 - 0.863x3 - 0.485x4 --> Min

Daraus mach ich dann für das Kriterium der zu maximierenden Zielfunktion etwas in der Art:
(-1) * (130 - 0.679x1 - 0.236x2 - 0.863x3 - 0.485x4) --> Max
-130 + 0.679x1 + 0.236x2 + 0.863x3 + 0.485x4 --> Max

In dem C#-Algorithmus aus dem Link steht folgendes:


// We are asked to maximize revenue where
//   Revenue = 45*numChairs + 80*numTables
//   Subject to constraints:
//     5*numChairs + 20*numTables <= 400 wood units
//     10*numChairs + 15*numTables <= 450 labor hours
//     numChairs + numTables <= 35 as per Soviet rules
//   Implicit: numChairs >= 0 && numTables >= 0
var s = new Simplex(
    new double[] { 45, 80 }, // revenue for each product
    new double[,] { // constraint coefficients
        { 5, 20 },
        { 10, 15 },
        { 1, 1 },
    },
    new double[] { 400, 450, 35 } // limits
);
// Solution: (maximum: 2100, production: [20, 15], remaining numbers: [0, 25, 0])

Also hätten wir im ersten Array doch irgendwie die Koeffizienten meiner Zielfunktion. Nur, wie mache ich das da mit den "-130"?


var simplexSolver = new Simplex(
                new[] { 0.679, 0.236, 0.863, 0.485 },          // Revenue
                new[,] {
                    // X1 >= 60 and <= 120 Constraints
                    {-1, 0.0, 0.0, 0.0},
                    { 1, 0.0, 0.0, 0.0},
                    
                    // X2 >= 0 and <= 150
                    {0.0, -1, 0.0, 0.0},
                    {0.0,  1, 0.0, 0.0},

                    // X3 >= 1 and <= 100
                    {0.0, 0.0, -1, 0.0},
                    {0.0, 0.0,  1, 0.0},

                    // X4 >= 0 and <= 100
                    {0.0, 0.0, 0.0, -1},
                    {0.0, 0.0, 0.0,  1},

                    // Constraint for Revenue Function as "="-Function
                    // therefore we have to create <= and >= Constraints for it
                    //{-0.679, -0.236, -0.863, -0.4850},
                    //{0.679, 0.236, 0.863, 0.4850},
                },
                new double[] { -60, 120,   0, 150,   -1, 100,   0, 100 }                             // Limits

So kommen aber leider nur Quatsch-Werte raus und ich verstehe aktuell nicht, wo ich schrauben kann, damit das Ergebnis richtig wird.
Eine Lösung hab ich mal über Excel errechnet und da komme ich auf folgende ganzzahliche Ergebnis-Werte:

x1: 84
x2: 144
x3: 8
x4: 66
Fehlerwert bzw. meine Minimierte Zielfunktion: 0.66
Spaltensummen mit den x1 .. x4: A: 64,988 B: 19,984 C: 44,962