Inhaltsverzeichnis
In diesem Abschnitt wird der revidierte Simplexalgorithmus aufgezeigt. Dieser wird angewandt, wenn die Anzahl der Variablen in einem linearen Optimierungsproblem wesentlich größer ist, als die Anzahl der Nebenbedingungen. Es wird im folgenden der revidierte Simplexalgorithmus für ein in kanonischer Form (Maximierungsproblem, kleiner/gleich-Nebenbedingungen, Nichtnegativitätsbedingung, positive Werte der rechten Seite) vorliegendes Problem aufgezeigt.
Gegeben sei das folgende lineare Maximierungsproblem in kanonischer Form:
u.d.N.
Das Problem wird zunächst auf die Normalform gebracht, indem die Schlupfvariablen eingefügt werden:
u.d.N.
Es liegt nun die folgende Form vor:
Methode
max
Vorgehensweise revidierte Simplexmethode
Bevor mit der Berechnung begonnen wird, werden die Koeffizienten in Matrizen geschrieben und die Basis- und Nichtbasisvariablen wie folgt festgelegt:
Es werden ebenfalls die Schlupfvariablen in den Matrizen mitberücksichtigt. In die Zielfunktion gehen diese mit dem Wert null ein, weshalb dort für beide am Ende eine Null steht.
Es wird als nächstes die Matrix
Zu Beginn sind die Basisvariablen die Schlupfvariablen
Die Matrix
Zu Beginn sind die Nichtbasisvariablen die Variablen der Zielfunktion
Merke
Hinweis: Es ist sinnvoll sich die Variablen über die Matrix zu schreiben. Vor allem bei einem späteren Tausch der Variablen kann man sonst schnell den Überblick verlieren.
1. Iteration:
1. Schritt: Auswahl der Pivotspalte.
Bestimmung der Pivotspalte
Es muss also zunächst die Inverse Matrix
Da die Matrix
Es wird nun die Zielfunktionszeile der Inversen
Es wird der kleinste negative Wert ausgewählt, hier:
2. Schritt: Auswahl der Pivotzeile.
Die Pivotzeile wird bestimmt, indem die Inverse
Die Ergebnismatrix wird dann verwendet, um die Pivtozeile zu bestimmen. Es werden die Werte der 2. Spalte durch die zugehörigen Werte der 1. Spalte geteilt. Hierbei dürfen für die 1. Spalte nur Werte größer als Null verwendet werden. Existieren keine Werte größer als Null, so existiert keine optimale Lösung. Es wird der kleinste Quotient ausgewählt:
Die Pivotzeile wird also für
Schritt 3: Neuberechnung der Inversen
Es wird nun in der Ausgangsmatrix
Die Inverse muss nun neu berechnet werden, da sich
2. Iteration
Es kann als nächstes mit der 2. Iteration begonnen werden.
1. Schritt: Auswahl der Pivotspalte.
Bestimmung der Pivotspalte
Es wird der kleinste negative Wert ausgewählt, hier:
2. Schritt: Auswahl der Pivotzeile.
Die Pivotzeile wird bestimmt, indem die Inverse
Die Ergebnismatrix wird dann verwendet, um die Pivotzeile zu bestimmen. Es werden die Werte der 2. Spalte durch die zugehörigen Werte der 1. Spalte geteilt. Hierbei dürfen für die 1. Spalte nur Werte größer als Null verwendet werden. Existieren keine Werte größer als Null, so existiert keine optimale Lösung. Es wird der kleinste Quotient ausgewählt:
Die Pivotzeile wird also für
Schritt 3: Neuberechnung der Inversen
Es wird nun in der Ausgangsmatrix
Die Inverse muss nun neu berechnet werden, da sich
3. Iteration
1. Schritt: Auswahl der Pivotspalte.
Bestimmung der Pivotspalte
Optimale Lösung
Da keine negativen Werte mehr vorhanden sind, liegt die optimale Lösung vor. Diese ergibt sich für die Basisvariablen
Die Werte für die Basisvariablen ergeben sich durch Multiplikation der Inversen
Dabei gilt
Weitere interessante Inhalte zum Thema
-
Beispiel: Revidierter Simplex-Algorithmus
Vielleicht ist für Sie auch das Thema Beispiel: Revidierter Simplex-Algorithmus (Lineare Programmierung) aus unserem Online-Kurs Operations Research 1 interessant.
-
Beispiele: Betragsungleichungen, Bruchungleichungen
Vielleicht ist für Sie auch das Thema Beispiele: Betragsungleichungen, Bruchungleichungen (Grundlagen: Mengenlehre und reelle Zahlen) aus unserem Online-Kurs Analysis und Lineare Algebra interessant.