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:
Als Beipiel die Datenvektoren für eine Ausahl:
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?
Lineare Optimierung unter Zwangsbedingungen -> Simplex Verfahren.
Habe jetzt keine konkrete Implementierung parat, aber das gibt es bestimmt schon zu Hauf.
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