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.09*x1 + 0.21*x2 + 0.841*x3 + 0.31*x4 ≤ 65
0.069*x1 + 0.02*x2 + 0.011*x3 + 0.17*x4 ≤ 20
0.52*x1 + 0.006*x2 + 0.011*x3 + 0.005*x4 ≤ 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.09*x1 + 0.21*x2 + 0.841*x3 + 0.31*x4)) + (20 - (0.069*x1 + 0.02*x2 + 0.011*x3 + 0.17*x4)) + (45 - (0.52*x1 + 0.006*x2 + 0.011*x3 + 0.005*x4)) --> Min
(65 - 0.09*x1 - 0.21*x2 - 0.841*x3 - 0.31*x4) + (20 - 0.069*x1 - 0.02*x2 - 0.011*x3 - 0.17*x4) + (45 - 0.52*x1 - 0.006*x2 - 0.011*x3 - 0.005*x4) --> Min
130 - (0.09*x1 + 0.069*x1 + 0.52*x1) - (0.21*x2+0.02*x2+0.006*x2) - (0.841*x3+0.011*x3+0.011*x3) - (0.31*x4+0.17*x4+0.005*x4) --> Min
130 - (0.679*x1) - (0.236*x2) - (0.863*x3) - (0.485*x4) --> Min
130 - 0.679*x1 - 0.236*x2 - 0.863*x3 - 0.485*x4 --> Min
Daraus mach ich dann für das Kriterium der zu maximierenden Zielfunktion etwas in der Art:
(-1) * (130 - 0.679*x1 - 0.236*x2 - 0.863*x3 - 0.485*x4) --> Max
-130 + 0.679*x1 + 0.236*x2 + 0.863*x3 + 0.485*x4 --> 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