Benutzer:Heinrich Puschmann/Simplexkreis

(Achtung: Eine Matrix darf in Wikipedia maximal 10 Spalten haben)

Die folgenden Beispiele lassen sich direkt in algebraischer Notation lösen. Um Rundungsfehler zu vermeiden, arbeiten wir mit Bruchzahlen und wählen einen gemeinsamen Nenner für das gesamte Gleichungssystem:

Der primale Simplexalgorithmus kann kreiseln. Hierzu ein einfaches Beispiel:

${\begin{matrix}z&=&(&~0&+~3x_{1}&+~4x_{2}&-~2x_{3}&-~9x_{4}&)~/~1\\[2pt]x_{5}&=&(&~0&+~3x_{1}&+~7x_{2}&-~2x_{3}&-~7x_{4}&)~/~1\\[2pt]x_{6}&=&(&~0&-~~x_{1}&-~2x_{2}&+~~x_{3}&+~3x_{4}&)~/~1\end{matrix}}$

Die zulässigen Pivots sind $(x_{6},\,x_{1})$ und $(x_{6},\,x_{2})$; wir legen $\,x_{2}\,$ an Stelle von $\,x_{6}\,$ frei und erhalten:

${\begin{matrix}z&=&(&~0&+~2x_{1}&-~4x_{6}&~~~~~~&-~6x_{4}&)~/~2\\[2pt]x_{5}&=&(&~0&-~~x_{1}&-~7x_{6}&+~3x_{3}&+~7x_{4}&)~/~2\\[2pt]x_{2}&=&(&~0&-~~x_{1}&-~~x_{6}&+~~x_{3}&+~3x_{4}&)~/~2\end{matrix}}$

Die zulässigen Pivots sind $(x_{5},\,x_{1})$ und $(x_{2},\,x_{1})$; wir legen $\,x_{1}\,$ an Stelle von $\,x_{5}\,$ frei und erhalten:

${\begin{matrix}z&=&(&~0&-~2x_{5}&-~9x_{6}&+~3x_{3}&+~4x_{4}&)~/~1\\[2pt]x_{1}&=&(&~0&-~2x_{5}&-~7x_{6}&+~3x_{3}&+~7x_{4}&)~/~1\\[2pt]x_{2}&=&(&~0&+~~x_{5}&+~3x_{6}&-~~x_{3}&-~2x_{4}&)~/~1\end{matrix}}$

Aber dieses Gleichungssystem ist -abgesehen von der Benennung der Veränderlichen- identisch mit dem Startsystem. Die Zahleneinträge des Systems wiederholen sich alle 2 Schritte, und nach insgesamt 12 Schritten wiederholt sich das Startsystem genau, einschließlich der Variablenbenennung.