ich möchte ein lineares Optimierungsproblem mittels (Dualem)Simplex-Algorithmus lösen, habe aber gerade noch Schwierigkeiten, wie ich die Zielfunktion für diesen Algorithmus eingeben muss und welche Kriterien ich letztlich brauche
Aufgabe:
Ich habe 4 Konfigurationen, die alle ihren gewissen Anteil an 3 Töpfen haben. Die Töpfe selber haben eine maximal erlaubte Füllmenge. Die Spaltensumme der Töpfe muss somit immer ≤ Topf-Maximum sein.
Topf 1: 65
Topf 2: 20
Topf 3: 45
Die Mengen x₁, .., x₄ sind auch immer in gewissen Grenzen
60 ≥ x₁ ≤ 120
0 ≥ x₂ ≤ 150
1 ≥ x₃ ≤ 100
0 ≥ x₄ ≤ 100
Die zu minimierende Zielfunktion ist mehr oder weniger eine Fehler-Funktion, die sich aus dem Abstand zum optimalen Spalten-Maximum über alle 3 Spalten (Töpfe) ergibt.
Also so in der Art:
f(x₁, .., x₄) = (65 - 0,09x₁ - 0,21x₂ - 0,841x₃ - 0,31x₄) + (20 - 0,069x₁ - 0,02x₂ - 0,011x₃ - 0,17x₄) + (45 - 0,52x₁ - 0,006x₂ - 0,011x₃ - 0,005x₄) → min
Zusammengefasst auf:
f(x₁, .., x₄) = 130 - 0,679x₁ - 0,236x₂ - 0,863x₃ - 0,485x₄ → min
Problem/Ansatz:
Mein Problem kurz gesagt ist, wie behandle ich diese Konstante "130" im Ausgangs-Tableau für (Dual)Simplex-Verfahren? Das ist ja das Gesamt-Maximum über alle Töpfe und von der müssen ja die Spalten-Summen abgezogen werden. In jedem Fall möchte ich diese Funktion minimieren, damit der Fehler möglichst gering wird. Für die x₁, .., x₄ sollen unter den Kriterien die optimalen Werte (ganzzahlig) gefunden werden.
Ich habe folgende Nebenbedingungen formuliert:
0,09x₁ + 0,21x₂ + 0,841x₃ + 0,31x₄ ≤ 65
0,069x₁ + 0,02x₂ + 0,011x₃ + 0,17x₄ ≤ 20
0,52x₁ + 0,006x₂ + 0,011x₃ + 0,005x₄ ≤ 45
1x₁ + 0x₂ + 0x₃ + 0x₄ ≥ 60
1x₁ + 0x₂ + 0x₃ + 0x₄ ≤ 120
0x₁ + 1x₂ + 0x₃ + 0x₄ ≥ 0
0x₁ + 1x₂ + 0x₃ + 0x₄ ≤ 150
0x₁ + 0x₂ + 1x₃ + 0x₄ ≥ 1
0x₁ + 0x₂ + 1x₃ + 0x₄ ≤ 100
0x₁ + 0x₂ + 0x₃ + 1x₄ ≥ 0
0x₁ + 0x₂ + 0x₃ + 1x₄ ≤ 100
⇒ Die ≥ als ≤ formuliert durch Multiplikation mit (-1)?
0,09x₁ + 0,21x₂ + 0,841x₃ + 0,31x₄ ≤ 65
0,069x₁ + 0,02x₂ + 0,011x₃ + 0,17x₄ ≤ 20
0,52x₁ + 0,006x₂ + 0,011x₃ + 0,005x₄ ≤ 45
-1x₁ + 0x₂ + 0x₃ + 0x₄ ≤ -60
1x₁ + 0x₂ + 0x₃ + 0x₄ ≤ 120
0x₁ -1x₂ + 0x₃ + 0x₄ ≤ 0
0x₁ + 1x₂ + 0x₃ + 0x₄ ≤ 150
0x₁ + 0x₂ - 1x₃ + 0x₄ ≤ -1
0x₁ + 0x₂ + 1x₃ + 0x₄ ≤ 100
0x₁ + 0x₂ + 0x₃ - 1x₄ ≤ 0
0x₁ + 0x₂ + 0x₃ + 1x₄ ≤ 100
⇒ Einführen von Schlupf-Variablen pro ≤ Nebenbedingung
0,09x₁ + 0,21x₂ + 0,841x₃ + 0,31x₄ + s1 = 65
0,069x₁ + 0,02x₂ + 0,011x₃ + 0,17x₄ + s2 = 20
0,52x₁ + 0,006x₂ + 0,011x₃ + 0,005x₄ + s3 = 45
-1x₁ + 0x₂ + 0x₃ + 0x₄ + s4 = -60
1x₁ + 0x₂ + 0x₃ + 0x₄ +s5 = 120
0x₁ -1x₂ + 0x₃ + 0x₄ + s6 = 0
0x₁ + 1x₂ + 0x₃ + 0x₄ + s7 = 150
0x₁ + 0x₂ - 1x₃ + 0x₄ + s8 = -1
0x₁ + 0x₂ + 1x₃ + 0x₄ +s9 = 100
0x₁ + 0x₂ + 0x₃ - 1x₄ + s10 = 0
0x₁ + 0x₂ + 0x₃ + 1x₄ + s11 = 100
⇒ Anfangs-Tableau
0,09 0,21 0,841 0,31 1 0 0 0 0 0 0 0 0 0 0 65
0,069 0,02 0,011 0,17 0 1 0 0 0 0 0 0 0 0 0 20
0,52 0,006 0,011 0,005 0 0 1 0 0 0 0 0 0 0 0 45
-1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 -60
1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 120
0 -1 0 0 0 0 0 0 0 1 0 0 0 0 0 0
0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 150
0 0 -1 0 0 0 0 0 0 0 0 1 0 0 0 -1
0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 100
0 0 0 -1 0 0 0 0 0 0 0 0 0 1 0 0
0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 100
Fragen:
Ist dieses Anfangs-Tableau schon einmal soweit richtig, oder habe ich da noch einen Fehler in meinen Ausführungen?
Als letzte Zeile müsste ich ja noch die zu minimierende Ziel-Funktion schreiben, die aber als Maximierungs-Funktion.
f(x₁, .., x₄) = -130 + 0,679x₁ + 0,236x₂ + 0,863x₃ + 0,485x₄ → max
Wie müsste das denn richtig aufgebaut werden und was mache ich mit diesen -130 in der Ziel-Funktion?
