Simplexalgorithmus - Versionsgeschichte

Flbkwikiadmin am 6. Februar 2026 um 09:05 Uhr

2026-02-06T09:05:13Z

Flbkwikiadmin am 6. Februar 2026 um 08:58 Uhr

2026-02-06T08:58:20Z

← Nächstältere Version		Version vom 6. Februar 2026, 10:58 Uhr
Zeile 1:		Zeile 1:
	~~= Simplexalgorithmus =~~

	== Definition ==		== Definition ==

Flbkwikiadmin am 6. Februar 2026 um 08:58 Uhr

2026-02-06T08:58:14Z

Änderungen zeigen

Flbkwikiadmin am 6. Februar 2026 um 08:23 Uhr

2026-02-06T08:23:29Z

← Nächstältere Version		Version vom 6. Februar 2026, 10:23 Uhr
Zeile 1:		Zeile 1:
	== Definition ==		== Definition ==
	Der '''Simplexalgorithmus''' ~~(oder das Simplex-Verfahren)~~ ist ein ~~iteratives~~ numerisches Verfahren zur Lösung ~~von [[Lineares Optimierungsproblem\|linearen Optimierungsproblemen]]~~. Er ~~wird~~ insbesondere ~~dann eingesetzt, wenn mehr als zwei Entscheidungsvariablen vorliegen und eine grafische Lösung nicht mehr möglich ist~~.		Der '''Simplexalgorithmus''' ist ein numerisches Verfahren zur Lösung '''linearer Optimierungsprobleme''' mit mehreren Variablen.
			Er eignet sich insbesondere für Probleme im '''ℝ³ oder höher'''.

	== ~~Vorgehensweise~~ ==		== Voraussetzungen ==
			* Lineares Standard-Maximumproblem
			* Nebenbedingungen als Gleichungen
			* Alle Variablen ≥ 0

	==~~= 1. Aufstellen der Normalform (~~Schlupfvariablen~~) =~~==		== Schlupfvariablen ==
	~~Um die~~ Ungleichungen ~~des Bedingungssystems in Gleichungen zu überführen,~~ werden '''Schlupfvariablen''' ~~(\(s_1, s_2, ...\)) eingeführt. Diese Variablen füllen die Differenz zwischen der verbrauchten Ressource und der [[Kapazitätsgrenze]] auf.~~		Ungleichungen werden durch '''Schlupfvariablen''' in Gleichungen überführt:
	* Beispiel: ~~Aus \(2x_1~~ + ~~x_2~~ \le ~~100~~\~~) wird~~ \~~(2x_1~~ + ~~x_2~~ + ~~s_1 = 100\).~~		:<math>a_1x + a_2y \le b \;\Rightarrow\; a_1x + a_2y + s = b</math>
	* Wenn \(s_1 = ~~0\), liegt ein '''Engpass''' vor (die Kapazität ist voll ausgeschöpft).~~

	==~~= 2. Das~~ Simplex-Tableau ===		== Simplex-Tableau ==
	~~Die Gleichungen werden~~ in ~~einem speziellen Schema, dem '''Simplex-Tableau''', angeordnet. Die Zielfunktion wird dabei so umgeformt, dass alle Variablen auf einer Seite stehen (meist \~~(~~z - c_1x_1 - c_2x_2 ..~~. ~~= 0\)~~).		Das Optimierungsproblem wird in Tabellenform dargestellt (vgl. [[Matrix]]).

	~~{\| class~~=~~"wikitable" style~~=~~"text~~-~~align~~:~~center;"~~		=== Begriffe ===
	~~! Basis !! \(x_1\) !! \(x_2\) !! \(s_1\) !! \(s_2\) !! r.S. !! Q~~		* '''Pivot-Spalte''': Variable mit größtem Zielfunktionskoeffizienten
	\|-		* '''Pivot-Zeile''': Engpass (Minimumquotient)
	~~\| \~~(~~s_1\~~) ~~\|\| 2 \|\| 1 \|\| 1 \|\| 0 \|\| 100 \|\| 50~~		* '''Pivot-Element''': Schnittpunkt von Pivot-Zeile und Pivot-Spalte
	\|-		* '''Engpass''': begrenzende Nebenbedingung
	~~\| \(s_2\) \|\| 1 \|\| 2 \|\| 0 \|\| 1 \|\| 80 \|\| 40~~
	\|-
	~~\| style="background~~:~~#eee;" \| \(z\) \|\|~~ -~~40 \|\|~~ -~~50 \|\| 0 \|\| 0 \|\| 0 \|\|~~
	\|}

	==~~= 3. Iterationsschritte =~~==		== Algorithmus ==
	* '''Pivot-~~Spalte''': Die Spalte mit dem negativsten Wert in der Zielfunktionszeile (Indikatorzeile). Sie zeigt den größten relativen Zuwachs.~~		1. Aufstellen des Simplex-Tableaus
	* '''Pivot-Zeile''': Die Zeile mit dem kleinsten positiven Quotienten \(Q\) aus der rechten Seite (r.~~S.) und dem Wert~~ der Pivot-Spalte. ~~Sie markiert den ersten eintretenden Engpass.~~		2. Bestimmung der Pivot-Spalte
	* '''Pivot-Element''': Das Schnittpunkt-Element von Pivot-Spalte und Pivot-Zeile.		3. Bestimmung der Pivot-Zeile
			4. Pivotisierung
			5. Abbruch, wenn keine Verbesserung möglich ist

	Mithilfe des [[Gaußsches Eliminationsverfahren\|Gaußschen Eliminationsverfahrens]] wird das Pivot-Element auf 1 und alle anderen Werte in der Pivot-Spalte auf 0 transformiert. Dieser Prozess wird wiederholt, bis keine negativen Werte mehr in der Zielfunktionszeile stehen.		== Beispiel ==
			Maximiere:
			:<math>Z = 3x + 2y</math>

	== ~~Ökonomische Interpretation~~ ==		unter:
	~~Das Endtableau gibt die optimale Produktionsmenge sowie den maximalen Erfolg~~ (~~Deckungsbeitrag) an~~. ~~Schlupfvariablen im Endtableau, die ungleich Null sind, zeigen nicht genutzte Kapazitäten in den jeweiligen Abteilungen an~~.		:<math>
			\begin{aligned}
			x + y &\le 4\\
			2x + y &\le 5\\
			x,y &\ge 0
			\end{aligned}
			</math>

			Nach Einführung der Schlupfvariablen entsteht ein Simplex-Tableau, aus dem iterativ die optimale Lösung abgelesen wird.

			== Hilfsmittel ==
			* CAS
			* Tabellenkalkulation (z. B. Excel)

			== Zusammenhang ==
			* Grafische Lösung: [[Eckpunktberechnungsmethode]]
			* Lineare Gleichungssysteme: [[Gaußsches Eliminationsverfahren]]

	[[Kategorie:Lineare_Optimierung]]		[[Kategorie:Lineare_Optimierung]]
	[[Kategorie:AHR_WuV_Mathe_GK]]		[[Kategorie:AHR_WuV_Mathe_GK]]

Flbkwikiadmin: Die Seite wurde neu angelegt: „== Definition == Der '''Simplexalgorithmus''' (oder das Simplex-Verfahren) ist ein iteratives numerisches Verfahren zur Lösung von linearen Optimierungsproblemen. Er wird insbesondere dann eingesetzt, wenn mehr als zwei Entscheidungsvariablen vorliegen und eine grafische Lösung nicht mehr möglich ist. == Vorgehensweise == === 1. Aufstellen der Normalform (Schlupfvariablen) === Um die Ungleichungen des Bedingungssystem…“

2026-02-06T08:02:11Z

Die Seite wurde neu angelegt: „== Definition == Der '''Simplexalgorithmus''' (oder das Simplex-Verfahren) ist ein iteratives numerisches Verfahren zur Lösung von linearen Optimierungsproblemen. Er wird insbesondere dann eingesetzt, wenn mehr als zwei Entscheidungsvariablen vorliegen und eine grafische Lösung nicht mehr möglich ist. == Vorgehensweise == === 1. Aufstellen der Normalform (Schlupfvariablen) === Um die Ungleichungen des Bedingungssystem…“

Neue Seite

== Definition ==
Der '''Simplexalgorithmus''' (oder das Simplex-Verfahren) ist ein iteratives numerisches Verfahren zur Lösung von [[Lineares Optimierungsproblem|linearen Optimierungsproblemen]]. Er wird insbesondere dann eingesetzt, wenn mehr als zwei Entscheidungsvariablen vorliegen und eine grafische Lösung nicht mehr möglich ist.

== Vorgehensweise ==

=== 1. Aufstellen der Normalform (Schlupfvariablen) ===
Um die Ungleichungen des Bedingungssystems in Gleichungen zu überführen, werden '''Schlupfvariablen''' (\(s_1, s_2, ...\)) eingeführt. Diese Variablen füllen die Differenz zwischen der verbrauchten Ressource und der [[Kapazitätsgrenze]] auf.
* Beispiel: Aus \(2x_1 + x_2 \le 100\) wird \(2x_1 + x_2 + s_1 = 100\).
* Wenn \(s_1 = 0\), liegt ein '''Engpass''' vor (die Kapazität ist voll ausgeschöpft).

=== 2. Das Simplex-Tableau ===
Die Gleichungen werden in einem speziellen Schema, dem '''Simplex-Tableau''', angeordnet. Die Zielfunktion wird dabei so umgeformt, dass alle Variablen auf einer Seite stehen (meist \(z - c_1x_1 - c_2x_2 ... = 0\)).

{| class="wikitable" style="text-align:center;"
! Basis !! \(x_1\) !! \(x_2\) !! \(s_1\) !! \(s_2\) !! r.S. !! Q
|-
| \(s_1\) || 2 || 1 || 1 || 0 || 100 || 50
|-
| \(s_2\) || 1 || 2 || 0 || 1 || 80 || 40
|-
| style="background:#eee;" | \(z\) || -40 || -50 || 0 || 0 || 0 ||
|}

=== 3. Iterationsschritte ===
* '''Pivot-Spalte''': Die Spalte mit dem negativsten Wert in der Zielfunktionszeile (Indikatorzeile). Sie zeigt den größten relativen Zuwachs.
* '''Pivot-Zeile''': Die Zeile mit dem kleinsten positiven Quotienten \(Q\) aus der rechten Seite (r.S.) und dem Wert der Pivot-Spalte. Sie markiert den ersten eintretenden Engpass.
* '''Pivot-Element''': Das Schnittpunkt-Element von Pivot-Spalte und Pivot-Zeile.

Mithilfe des [[Gaußsches Eliminationsverfahren|Gaußschen Eliminationsverfahrens]] wird das Pivot-Element auf 1 und alle anderen Werte in der Pivot-Spalte auf 0 transformiert. Dieser Prozess wird wiederholt, bis keine negativen Werte mehr in der Zielfunktionszeile stehen.

== Ökonomische Interpretation ==
Das Endtableau gibt die optimale Produktionsmenge sowie den maximalen Erfolg (Deckungsbeitrag) an. Schlupfvariablen im Endtableau, die ungleich Null sind, zeigen nicht genutzte Kapazitäten in den jeweiligen Abteilungen an.

[[Kategorie:Lineare_Optimierung]]
[[Kategorie:AHR_WuV_Mathe_GK]]