Nebenbedingungen-Restriktionsmatrix und rechte Seite
Matrix-Operationen
Grundlegende Operationen mit Matrizen
Operation
Bedingung
Ergebnis-Dimension
Addition A + B
Gleiche Dimension
m × n
Subtraktion A - B
Gleiche Dimension
m × n
Skalarmultiplikation k·A
Keine
m × n
Multiplikation A·B
Spalten(A) = Zeilen(B)
m × p
Transponierte Aᵀ
Keine
n × m
Inverse A⁻¹
det(A) ≠ 0, quadratisch
n × n
A (m×n) bedeutet: m Zeilen, n Spalten
Häufig gestellte Fragen zum Simplex-Algorithmus-Rechner
Was ist der Simplex-Algorithmus?
Der Simplex-Algorithmus ist ein Verfahren zur Lösung linearer Optimierungsprobleme (LP). Er sucht das Maximum oder Minimum einer linearen Zielfunktion unter linearen Nebenbedingungen. Er bewegt sich entlang der Kanten des zulässigen Bereichs von Eckpunkt zu Eckpunkt.
Was ist ein lineares Optimierungsproblem?
Ein LP besteht aus: einer linearen Zielfunktion (z. B. Z = 3x₁ + 5x₂ maximieren), linearen Nebenbedingungen (Ungleichungen wie 2x₁ + x₂ ≤ 10) und Nichtnegativitätsbedingungen (x₁, x₂ ≥ 0). Alle Beziehungen sind linear.
Warum liegt das Optimum an einem Eckpunkt?
Der zulässige Bereich ist ein konvexes Polyeder. Eine lineare Funktion nimmt auf einem konvexen Polyeder ihr Maximum (und Minimum) immer an einem Eckpunkt an. Der Simplex-Algorithmus nutzt dies, indem er nur Eckpunkte prüft.
Was ist die Standardform eines LP?
Standardform: Maximiere Z = c^T · x unter den Bedingungen Ax ≤ b, x ≥ 0. Durch Einführung von Schlupfvariablen wird daraus: Ax + s = b mit s ≥ 0. Ungleichungen werden zu Gleichungen.
Was sind Schlupfvariablen?
Schlupfvariablen wandeln Ungleichungen in Gleichungen um: x₁ + x₂ ≤ 10 wird zu x₁ + x₂ + s₁ = 10 mit s₁ ≥ 0. Die Schlupfvariable s₁ misst den Abstand zur Nebenbedingungsgrenze (Schlupf = ungenutztes Potenzial).
Kann der Simplex keine Lösung finden?
Ja, in drei Fällen: 1) Unbeschränkt: Die Zielfunktion kann beliebig groß werden (kein Maximum). 2) Unlösbar: Der zulässige Bereich ist leer (widersprüchliche Bedingungen). 3) Mehrdeutig: Mehrere optimale Lösungen auf einer Kante.
Du brauchst eine lineare Zielfunktion, alle Nebenbedingungen, die Richtung der Optimierung und die Vorzeichenbedingungen der Variablen. Jede Nebenbedingung muss vollständig sein, also Koeffizienten, Vergleichszeichen und rechte Seite enthalten.
Warum muss ein Simplex-Problem linear sein?
Der Simplex-Algorithmus nutzt die Geometrie linearer Nebenbedingungen. Der zulässige Bereich besteht aus Geraden, Ebenen oder höheren linearen Flächen. Quadratische Terme, Produkte von Variablen oder nichtlineare Funktionen verletzen diese Voraussetzung und brauchen andere Optimierungsverfahren.
Was bedeutet ein unbeschränktes Ergebnis?
Unbeschränkt bedeutet, dass die Zielfunktion innerhalb der Nebenbedingungen beliebig weiter verbessert werden kann. Dann gibt es kein endliches Maximum oder Minimum. Meist fehlt in solchen Fällen eine begrenzende Nebenbedingung oder eine Vorzeichenbedingung wurde falsch angegeben.