▷ Simplex-Verfahren » Definition, Erklärung & Beispiele + Übungsfragen

Das Simplex Verfahren gehört zu den Optimierungsmethoden im Operations Research zur Findung einer optimalen Lösung von linearen Optimierungsproblemen.

Dieses Kapitel zeigt dir, was man unter dem Simplex Verfahren versteht, warum es wichtig ist und wie es angewendet wird. Außerdem stellen wir dir passende Übungsaufgaben bereit, mit denen du dich auf deine nächste Prüfung vorbereiten kannst.

Synonym: Simplex Algorithmus

Inhalt dieser Lektion

Warum ist das Simplex Verfahren wichtig?

Die Optimierung der innerbetrieblichen Prozesse ist Grundlage für den wirtschaftlichen Erfolg eines Unternehmens. Das Simplex Verfahren stellt eine Möglichkeit dar, mit der Prozesse und Probleme optimal gelöst werden können, d.h. die bestmögliche Lösung gefunden werden kann. Angewendet werden kann das Simplex Verfahren beispielsweise in den Bereichen:

Produktionsplanung
Kostenoptimierung
Gewinnmaximierung
Personaleinsatzplanung
Planung von Marketing- und Verkaufsfördermaßnahmen
uvm.

Überall dort, wo unter verschiedenen Bedingungen eine optimale Lösung gefunden werden muss, kann das Simplex Verfahren genutzt werden, sofern das zu lösende Problem in lineare Gleichungen übertragen werden kann. In der betrieblichen Praxis werden hierfür spezielle Software-Programme genutzt, um die benötigte Zeit zu reduzieren.

Was versteht man unter dem Simplex Verfahren?

Das Simplex Verfahren ist eine mathematische Methode zur Lösung linearer Optimierungsprobleme bzw. zur Feststellung der Nichtexistenz einer optimalen Lösung. Die optimale Lösung ist der Schnittpunkt zweier Nebenbedingungen, welcher innerhalb der zulässigen Lösungsmenge liegt.

Schritt für Schritt wird dabei der Wert der Zielfunktion verbessert, bis es keine bessere Lösung mehr gibt. Dies ist dann die optimale Lösung der Zielfunktion und somit die optimale Lösung des gegebenen Optimierungsproblems.

Zur Anwendung des Simplex Verfahrens benötigt man folgende Elemente:

Die Zielfunktion, welche optimiert werden soll
Die gegebenen Nebenbedingungen, welche die Einschränkungen des Lösungsraumes darstellen
Die Nichtnegativitätsbedingung der Variablen

Die unterschiedlichen Varianten des Simplex Verfahrens

Das Simplex Verfahren kann je nach zu lösendem Problem in unterschiedlichen Varianten genutzt werden:

Primale Simplex: Beispiel

Die “Computernerd AG” stellt sowohl Laptops (x₁) als auch Tablets (x₂) her. Gesucht wird das optimale Produktionsprogramm, mit dem der Deckungsbeitrag (z) maximiert werden kann (Zielfunktion).

Mit Produkt A kann das Unternehmen einen Deckungsbeitrag von 600 € pro Stück erzielen, mit Produkt B einen Deckungsbeitrag von 1.000 €. Für die Produktion werden die Maschinen 1, 2 und 3 benötigt.

Diese haben folgende monatliche Kapazität:

Maschine 1 = 340 Stunden
Maschine 2 = 300 Stunden
Maschine 3 = 360 Stunden

Die Fertigung eines Laptops benötigt jeweils 2 Stunden an Maschine 1 und 2. Für ein Tablet werden 4 Stunden an Maschine 1, 2 Stunden an Maschine 2 und 6 Stunden an Maschine 3 benötigt.

Ausgangsbedingungen aufstellen

Es ergeben sich also folgende Bedingungen zur Lösung des Optimierungsproblems:

Zielfunktion (ZF):

$max~z = 600x_1 + 1.000x_2$

Nebenbedingungen:

$2x_1 + 4x_2 \leq = 340$

$2x_1 + 2x_2 \leq = 300$

$0x_1 + 6x_2 \leq = 360$

Bedingungen in Gleichungen überführen

Um das Simplex Verfahren anwenden zu können, müssen die aufgestellten Bedingungen in Gleichungen überführt werden. Hierzu werden Schlupfvariablen eingesetzt, die in diesem Fall die nicht genutzte Kapazität der einzelnen Maschinen darstellen.

$z = 0 + 600x_1 + 1.000x_2$

$y_a = 340 - 2x_1 - 4x_2$

$y_b = 300 - 2x_1 - 2x_2$

$y_c = 360 - 0x_1 - 6x_2$

Diese aufgestellten Gleichungen werden nun in das Simplex Tableau eingetragen, wobei b die aktuelle Basislösung darstellt, x₁ und x₂ die Nichtbasisvariablen und y_i die Basisvariablen. 600 und 1000 sind in diesem Fall die Zielfunktionskoeffizienten c_i.

	x₁	x₂	rechte Seite
-z	600	1000	0
y_a	2	4	340 = b
y_b	2	2	300 = b
y_c	0	6	360 = b

Zulässige Ausgangslösung bestimmen

Da für den Simplex Algorithmus die Nichtnegativitätsbedingung gilt, kann in dieser Phase der Einfachheit halber für die Nichtbasisvariablen (x₁ und x₂) der Wert Null angenommen werden, um eine der zulässigen Lösungen für die Basisvariablen zu erhalten. So ergibt sich:

y_a = 340
y_b = 300
y_c = 360

Die Basisvariablen ergeben nun die Basis B, von denen die Einheitsmatrix die Basismatrix A_B darstellt. Die entsprechende Basislösung ist A^-1_B b = b für den Fall, dass x₁ und x₂ gleich Null sind, also keine Produkte produziert werden.

Ausgangslösung verbessern

Da jedoch das optimale Produktionsprogramm bestimmt werden soll, können wir uns nicht mit der gefunden Lösung für den Nichtproduktionsfall zufrieden geben und müssen nach einer besseren Lösung suchen.

Zuerst wird dazu eine Pivotzeile und -spalte ausgesucht. Hierzu wird eine der Basisvariablen gegen eine unabhängige Variable ausgetauscht. Das Ziel ist die Verbesserung des Zielfunktionswerts, weshalb dazu Nichtbasisvariablen mit positivem Zielfunktionskoeffizienten in Frage kommen.

Anschließend wird diese Variable so weit erhöht, bis einer oder auch mehrere der Basisvariablen null ergeben. Somit kann eine der Basisvariablen gegen die Nichtbasisvariable ausgetauscht werden.

x₁ als Nichtbasisvariable hat den zugehörigen Zielfunktionskoeffizienten 600. Durch eine Erhöhung kann die Zielfunktion vergrößert werden. Daher kann Sie als basis-eintretende Pivotvariable in Frage kommen.

Bei der Erhöhung gelten in unserem Beispiel folgende Bedingungen:

$0 \leq y_a = 340 - 2x_1$

$0 \leq y_b = 300 - 2x_1$

oder auch:

$x_1 \leq min \{\frac{340}{2},\frac{300}{2}\} = 150$

So erhält man die erste Basisvariable, welche auf null stößt, mit dem Quotienten 300/1, welcher y_b ist. Tauscht man diese also gegen x₁ aus, so ergibt sich der Zielfunktionswert:

$z = 600 * (\frac{300}{2})=90.000$

Da x₂ mit 1.000 ebenfalls einen positiven Zielfunktionskoeffizienten hat, kommt auch diese als eintretende Nichtbasisvariable in Betracht. Demnach führen wir auch für x₂ die eben gemachten Schritte durch und erhalten:

$x_2 \leq min \{ \frac{340}{2},\frac{300}{2},\frac{360}{6} \} = 60$

Der gefunden minimale Quotient 360/6 ist y_c, wodurch sich für den Zielfunktionswert ergibt:

$z = 1000 * (\frac{360}{6}) = 60.000$

Um die Zielfunktion zu maximieren, nutzen wir also den ersten Fall und legen die Nichtbasisvariable x₁ anstelle der Basisvariablen y_b frei.

Austauschschritt durchführen

In diesem Schritt ersetzen wir die Basisvariable y_b nach unserem vorherigen Ergebnis durch x₁:

$y_b = 300 - 2x_1 - 2x_2$

$x_1 = 150 - \frac{y_b}{2} - x_2$

Anschließend wird in den übrigen Gleichungen x₁ entsprechend ersetzt:

$z = 0 + 600*(150-\frac{y_b}{2}-x_2) +1.000x_2$

$y_a = 340 - 2*(150-\frac{y_b}{2} - x_2) - 2x_2$

$y_c = 360 - 0 * (150 - \frac{y_b}{2} - x_2) - 6x_2$

Im Simplex Tableau übernimmt nun x₁ die Zeile von y_b und y_b die Spalte von x₁, sodass das neue Simplex Tableau nun folgendermaßen aussieht:

	y_b	x₂	rechte Seite
-z	-300	400	-90.000
y_a	-1	4	40 = b
x₁	-1/2	-1	300 = b
y_c	0	6	360 = b

Daraus ergibt sich das folgende neue Gleichungssystem:

$z = 90.000 - 300y_b + 400x_2$

$y_a = 40 - y_b - 4x_2$

$x_1 = 150 - \frac{y_b}{2} - x_2$

$y_c = 360 - 0y_b - 6x_2$

Für die “Computernerd AG” bedeutet das:

Sie produziert 150 Laptops und keine Tablets.
Der zu erzielende Deckungsbeitrag liegt bei 90.000 €.
Maschine 1 wird dabei nur 300 Stunden im Monat genutzt und hat eine Leerlaufzeit von 40 Stunden.
Die Kapazität von Maschine 2 wird vollständig ausgenutzt.
Da für die Produktion der Laptops die Maschine 3 nicht benötigt wird, liegt ihre Leerlaufzeit bei den vollen 360 Stunden ihrer Kapazität.

Simplexschritte wiederholen

Das entstandene Simplex Tableau enthält noch immer einen positiven Zielkoeffizienten. Demnach muss noch eine bessere Lösung existieren. Da nur noch x₂ einen positiven Zielkoeffizienten enthält, kommt auch nur noch diese als eintretende Nichtbasisvariable als Pivotelement in Frage. Wie oben beschrieben wird nun auch für x₂ die Basisvariable gesucht. So ergibt sich:

$x_2 \leq min \{ \frac{40}{4} , \frac{150}{1} , \frac{360}{6} \} = 10$

Als einzige Basisvariable für einen Pivot kommt also y_a in Frage. Daher wird diese Basisvariable durch x₂ ausgetauscht. Es ergibt sich nach Durchführung der oben genannten Umrechnungen also folgendes neues Gleichungssystem:

$z = 94.000 - 700y_b - 400y_a$

$x_2 = 10 - y_b -y_a$

$x_1 = 140 - 1,5y_b - y_a$

$y_c = 300 + 6y_b - 6y_a$

Das neue Simplex Tableau sieht folgendermaßen aus:

	y_b	y_a	rechte Seite
-z	-700	-400	-94.000
x₂	-1	-1	10 = b
x₁	-1,5	-1	140 = b
y_c	6	-6	300 = b

Dualer Simplex

Der Duale Simplex wird verwendet, wenn in der rechten Seite des Simplex Tableaus negative Werte vorhanden sind und man die Zielfunktion maximieren möchte. Im Grunde ist das Verfahren dem primalen Simplex ähnlich, da auch hier in der Normalform eine Einheitsmatrix unter Verwendung von Schlupfvariablen gebildet werden muss.

Das Vorgehen beim dualen Simplex wird anhand des folgenden Beispiels deutlich:

$min~Z = x_1 + x_2$

Nebenbedingungen:

$x_1 - 2x_2 \geq 1$

$x_1 + 2x_2 \geq 4$

$x_1 + x_2 \geq -2$

Weiterhin gilt die Nichtnegativitätsbedingung, also:

$x_1, x_2 \geq 0$

Zuerst muss das zu lösende Problem in ein Maximierungsproblem umgewandelt werden, welches mit Kleiner-Gleich-Nebenbedingungen beschrieben wird.
Hierzu wird die Zielfunktion mit (-1) multipliziert:

$-x_1 -x_2 = max~Z$

Die Nebenbedingungen sind als Größer-Gleich-Nebenbedingungen gegeben. Damit wir Kleiner-Gleich-Nebenbedingungen erhalten, müssen diese ebenfalls mit (-1) multipliziert werden.

$- x_1 + 2x_2 \geq -1$

$- x_1 - 2x_2 \geq -4$

$-x_1 -x_2 \geq 2$

Da auf der rechten Seite negative Werte vorhanden sind, kann der primale Simplex nicht genutzt werden. Daher kommt der duale Simplex zur Anwendung. Dazu werden zunächst die Schlupfvariablen y_i eingeführt, um das Problem in die Normalform zu übertragen.

$max~Z = -x_1 -x_2$

$-x_1 + 2x_2 +y_1 = -1$

$-x_1 - 2x_x + y_2 = -4$

$-x_1 -x_2 + y_3 = 2$

$x_1 , x_2 \geq 0$

Das Simplex-Tableau sieht demnach folgendermaßen aus:

	x₁	x₂	b_i
-z	1	1	0
y₁	-1	2	-1
y₂	-1	-2	-4
y₃	-1	1	2

Wie beim primalen Simplex auch, wird zuerst die Pivotzeile ausgesucht. Der kleinste negative Wert ist hier -4, weshalb y₂ die Pivotzeile darstellt.

Anschließend wird die Pivotspalte gewählt. Hierbei werden die negativen Werte der Pivotzeile berücksichtigt und der jeweilige Quotient gebildet:

$\frac{1}{-1} = -1$

$\frac{1}{-2} = -\frac{1}{2}$

Der maximale Quotient ist also -¹/₂. Er wird gewählt, wonach die Pivotspalte die zweite Spalte ist. Das Pivotelement findet sich am Schnittpunkt von Pivotspalte und Pivotzeile und ist -2:

	x₁	x₂	b_i
-z	1	1	0
y₁	-1	2	-1
y₂	-1	-2	-4
y₃	-1	1	2

Entsprechend dem primalen Simplex wird nun der erste Austauschschritt vollzogen und das neue Simplex-Tableau aufgestellt:

	x₁	y₂	b_i
-z	¹/₂	¹/₂	-2
y₁	-2	1	-5
y₂	¹/₂	-¹/₂	2
y₃	-¹/₂	-¹/₂	4

Da noch ein weiterer negativer Eintrag auf der rechten Seite vorhanden ist, wird ein weiterer Schritt des dualen Simplex durchgeführt. Analog zum vorherigen Vorgehen werden zunächst Pivotspalte- und zeile ausgewählt, um das Pivotelement zu erhalten:

	x₁	y₂	b_i
-z	¹/₂	¹/₂	-2
y₁	-2	1	-5
x₂	¹/₂	-¹/₂	2
y₃	-¹/₂	-¹/₂	4

Durch die Anwendung der Austauschschritte erhalten wir nun das neue Simplex-Tableau:

	y₁	y₂	b_i
-z	¹/₄	³/₄	-¹³/₄
x₁	-¹/₂	-¹/₂	⁵/₂
x₂	¹/₄	-¹/₄	³/₄
y₃	-¹/₄	-³/₄	²¹/₄

Da keine negativen Werte mehr auf der rechten Seite zu finden sind, ist die optimale Lösung gefunden:

$x_1 = \frac{5}{2}$

$x_2 = \frac{3}{4}$

$y_3 = \frac{21}{4}$

Big-M-Methode

Die Big-M-Methode ist eine weitere Variante des Simplex Verfahrens. Mit ihr kann eine optimale Lösung gefunden werden, ohne eine Einheitsmatrix mit Schlupfvariablen bilden zu müssen.

Allerdings funktioniert das nur, wenn:

die Werte der rechten Seite nicht negativ sind
das Gleichungssystem in Normalform vorhanden ist
die Zielfunktion maximiert werden soll

Beispiel zur Big-M-Methode

$Max~Z = -2_x1 - 2x_2 - 6x_3$

Nebenbedingungen:

$-2x_1 + 2x_2 \leq 20$

$2x_1 - 2x_3 \geq 24$

$2x_1 - 2x_2 - 2x_3 \leq 16$

$4x_1 - 2x_2 + 2x_3 \geq 4$

Unter Einbringung zusätzlicher Schlupfvariablen kann dieses Gleichungssystem in die Normalform gebracht werden:

$-2x_1 + 2x_2 + x_4 = 20$

$2x_1 - 2x_3 - x_5 = 24$

$2x_1 - 2x_2 -2x_3 + x_6 = 16$

$4x_1 - 2x_2 + 2x_3 - x_7 = 4$

Die Zeilen, welche negative Schlupfvariablen enthalten, werden nun durch die künstlichen Variablen y_i ergänzt. In der Zielfunktion werden diese künstlichen Variablen mit einer möglichste hohen Zahl M (Big M) multipliziert.

$-2x_1 + 2x_2 + x_4 = 20$

$2x_1 - 2x_3 - x_5 + y_1 = 24$

$2x_1 - 2x_2 - 2x_3 + x_6 = 16$

$4x_1 - 2x_2 + 2x_3 - x_7 + y_2 = 4$

$Max~Z = -2x_1 -2x_2 - 6x_3 - My_1 - My_2$

Anschließend werden die Nebenbedingungen entsprechend nach y₁ und y₂ umgestellt:

$y_1 = 24 - 2x_1 + 2x_3 + x_5$

$y_2 = 4 -4x_1 + 2x_2 + x_7$

Diese werden nun in die Zielfunktion eingesetzt:

$Max~Z = -2x_1 - 2x_2 -6x_3 M(24-2x_1+2x_3+x_5)-M(4-4x_1+2x_2-2x_3+x_7)$

Die nun erhaltene Zielfunktion wird soweit vereinfacht, bis der F-Teil und der M-Teil ablesbar ist. Damit erhalten wir:

$Max~Z = -2x_1 -2x_2 -6x_3+6Mx_1-2Mx_2-Mx_5-Mx_7-28M.$

Der erste Teil der Big-M-Methode ist damit abgeschlossen. Anschließend wird das Gleichungssystem in das Simplex-Tableau übertragen, welches dann folgendermaßen aussieht:

	x₁	x₂	x₃	x₄	x₅	x₆	x₇	y₁	y₂	b_i
x₄	-2	2		1	0	0	0			20
y₁	2		-2		-1	0	0	1		24
x₆	2	-2	-2	0	0	1	0			16
y₂	4	-2	2	0	0	0	-1		1	4
F	2	2	6	0	0	0	0	0		0
M	-6M	-2M	0	0	M	0	M	0	0	-28M

Die Auswahl der Pivotspalte ergibt sich aus dem kleinsten Wert der M-Zeile. In diesem Fall also -6M. Zur Wahl der Pivotzeile berechnest du den Quotienten aus bi und den Eintragungen in der vorher gewählten Pivotspalte.

Es ergibt sich also:

	x₁	x₂	x₃	x₄	x₅	x₆	x₇	y₁	y₂	b_i	Quotient
x₄	-2	2		1	0	0	0			20
y₁	2		-2		-1	0	0	1		24	12
x₆	2	-2	-2	0	0	1	0			16	8
y₂	4	-2	2	0	0	0	-1		1	4	1
F	2	2	6	0	0	0	0	0		0
M	-6M	-2M	0	0	M	0	M	0	0	-28M

Der kleinste Quotient ist die 1. Das Pivotelement ist damit die 4:

	x₁	x₂	x₃	x₄	x₅	x₆	x₇	y₁	y₂	b_i	Quotient
x₄	-2	2		1	0	0	0			20
y₁	2		-2		-1	0	0	1		24	12
x₆	2	-2	-2	0	0	1	0			16	8
y₂	4	-2	2	0	0	0	-1		1	4	1
F	2	2	6	0	0	0	0	0		0
M	-6M	-2M	0	0	M	0	M	0	0	-28M

Anschließend werden dem Tableau neue Zeilen hinzugefügt, um die Big-M-Methode anwenden zu können. Dazu wird die Nichtbasivariable aus der vorher definierten Pivotspalte als neue Basivariable gegen die künstliche Variable y₂ ausgetauscht. In der Pivotspalte wird damit ein Einheitsvektor geschaffen, unter der Einbeziehung der F- und der M-Zeile.

Daraus ergibt sich folgende Iteration:

	x₁	x₂	x₃	x₄	x₅	x₆	x₇	y₁	y₂	b_i	Quotient
x₄	-2	2		1	0	0	0			20
y₁	2		-2		-1	0	0	1		24	12
x₆	2	-2	-2	0	0	1	0			16	8
y₂	4	-2	2	0	0	0	-1		1	4	1
F	2	2	6	0	0	0	0	0		0
M	-6M	-2M	0	0	M	0	M	0	0	-28M

x₄	0	1	1	1	0	0	-¹/₂			22	22
y₁	0	1	-3		-1	0	¹/₂			22	22
x₆	0	-1	-3	0	0	1	¹/₂			14
y₂	1	-¹/₂	¹/₂	0	0	0	-¹/₄			1
F	0	3	5	0	0	0	¹/₂	0		-2
M	0	-M	3M	0	0	0	-^M/₂	0		-22M

Da y₂ durch x₁ ersetzt wurde, wird auch diese Spalte direkt eliminiert. Um die optimale Lösung mit der Big-M-Methode zu erhalten, werden die vorhergehenden Schritte solange angewendet, bis keine künstlichen Variablen mehr enthalten sind. In diesem Falle ist noch y₁ vorhanden.

Durch einen weiteren Iterationsschritt zur Entfernung dieser künstlichen Variablen erhältst du folgendes Tableau:

	x₁	x₂	x₃	x₄	x₅	x₆	x₇	y₁	y₂	b_i	Quotient
x₄	0	1	1	1	0	0	-¹/₂			22	22
y₁	0	1	-3		-1	0	¹/₂			22	22
x₆	0	-1	-3	0	0	1	¹/₂			14
x₁	1	-¹/₂	¹/₂	0	0	0	-¹/₄			1
F	0	3	5	0	0	0	¹/₂	0		-2
M	0	-M	3M	0	M	0	-^M/₂	0		-22M

x₄	0	0	4	1	1	0	-1			0
x₂	0	1	0		-1	-1	0			22
x₆	0	0	-6	0	-1	1	1			36
x₁	2	0	-2	0	-1	0	0			12
F	0	0	8	0	2	1	0			-68
M	0	0	0	0	0	0	0			0

Da keine negativen Einträge mehr in der F-Zeile zu finden sind, ist die optimale Lösung gefunden:

$x^* = (12,22,0)$

$F^* = 68$

Ist noch keine optimale Lösung nach Anwendung der Big-M-Methode gefunden, so kann die Berechnung einfach mit dem primalen Simplex Verfahren fortgesetzt werden.

Vorteile und Nachteile des Simplex Verfahrens

Vorteile

Verschiedenste Optimierungsprobleme können gelöst werden.
Mit dem primalen und dualen Simplex und der Big-M-Methode stehen verschiedene Lösungsmöglichkeiten für unterschiedliche Voraussetzungen zur Verfügung.

Nachteile

Die händisch angewandte Lösung von Optimierungsproblemen in der betrieblichen Praxis erfordert einen hohen Zeitaufwand, weshalb spezielle Software-Programme nötig sind.

Simplex-Verfahren

Warum ist das Simplex Verfahren wichtig?

Was versteht man unter dem Simplex Verfahren?