Eine Datenstruktur für ein Pivotverfahren speichert auf direkte oder indirekte Art die Information für folgendes Gleichungssystem
![{\displaystyle {\begin{matrix}z&=&f_{0}&+&d_{1}\,x_{1}&+&\cdots &+&d_{n}\,x_{n}\\[3pt]x_{n+1}&=&b_{1}&+&G_{11}\,x_{1}&+&\cdots &+&G_{1n}\,x_{n}\\\vdots &&\vdots &&\vdots &&&&\vdots \\x_{n+m}&=&b_{m}&+&G_{m1}\,x_{1}&+&\cdots &+&G_{mn}\,x_{n}\end{matrix}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e8e68c749befa50b0f8871d9c5bc40d42521c0a4)
und dem über die Permutation
davon abgewandelten System
![{\displaystyle {\begin{matrix}z&=&f_{0}^{\pi }&+&d_{1}^{\pi }\,x_{\pi (1)}&+&\cdots &+&d_{n}^{\pi }\,x_{\pi (n)}\\[3pt]x_{\pi (n+1)}&=&b_{1}^{\pi }&+&G_{11}^{\pi }\,x_{\pi (1)}&+&\cdots &+&G_{1n}^{\pi }\,x_{\pi (n)}\\\vdots &&\vdots &&\vdots &&&&\vdots \\x_{\pi (n+m)}&=&b_{m}^{\pi }&+&G_{m1}^{\pi }\,x_{\pi (1)}&+&\cdots &+&G_{mn}^{\pi }\,x_{\pi (n)}\end{matrix}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/dc5b2ccd0e5c2d963be6fbad0bc7cb2a889f1949)
Pivotverfahren können sehr verschiedenartig umgesetzt werden,
wobei die Besonderheit der Aufgabe, die Besetzungsdichte des Gleichungssystems und
sogar die Darstellung der Koeffizienten
eine Rolle spielen.
Bei jeder Umsetzung liegt ein strukturierter Datensatz vor, der in jedem Schritt des Pivotverfahrens aktualisiert wird.
Anhand der vorliegenden Daten müssen wir dann imstande sein,
die für die Pivotauswahl benötigten Koeffizienten abzulesen oder zu errechnen.
Ob die Verfahren zur Aktualisierung der Datenstruktur und zur Berechnung der Koeffizienten
(zum Beispiel Listenaktualisierung, Lösung linearer Gleichungssysteme, Kreissuche auf einem Graphen)
nun Bestandteil eines Pivotverfahrens sein sollen oder nicht,
ist natürlich eine Ansichtsfrage, die keine kategorische Antwort zulässt.
Für eine getrennte Betrachtung spricht, dass diese zusätzlichen Verfahren auch in anderen Zusammenhängen vollwertig einsetzbar sind.
Simplextableau
Simplextableaus (Simplextafeln) sind die einfachste aller Datenstrukturen für Pivotverfahren,
und wurden erstmalig 1950 von George Dantzig vorgeschlagen.
Im Großteil der älteren Literatur (bis Mitte der achziger Jahre)
wurden Simplextableaus als untrennbarer Bestandteil der Simplexverfahren angesehen.
Sie bestehen im Wesentlichen in:
- einem Array, der sämtliche Koeffizienten des Gleichungssystems enthält
- Zeiger der Unbekannten auf die entsprechenden Spalten und Zeilen des Arrays
![{\displaystyle {\begin{bmatrix}&0&~~&\pi (1)&\cdots &\pi (n)\\[3pt]n\!+\!m\!+\!1&f^{B}&&d_{1}^{B}&\cdots &d_{n}^{B}\\[18pt]\pi (n+1)&b_{1}^{B}&&G_{11}^{B}&\cdots &G_{1n}^{B}\\\vdots &\vdots &&\vdots &&\vdots \\\pi (n+m)&b_{m}^{B}&&G_{m1}^{B}&\cdots &G_{mn}^{B}\end{bmatrix}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5bd2fe2ebbd39a751a34d42de5eaa0e92d080ad8)
Oft werden beim Simplextableau in einigen Spalten, Zeilen oder Blöcken des Arrays
anstelle der Koeffizienten ihre negativen Werte gespeichert.
Beidseitig beschränkte Unbekannte
Die oben angeführte symmetrische Grundform eignet sich hervorragend,
um die Begriffe der Pivotverfahren und deren Dualität zu erläutern;
bei angewandten Aufgaben hingegen ist es oft praktischer,
die Unbekannten
anstelle von
auf ein beliebiges Intervall
zu beschränken.
Die Symmetrie zur dualen Aufgabe freilich
ist bei einer Intervall-orientierten Formulierung
nicht ohne weiteres sichtbar.
Als erstes beobachten wir, dass wir bei vielen Anwendungen
ohne nennenswerte Einschränkung
mit endlichen Schranken arbeiten können,
![{\displaystyle {\begin{matrix}\forall ~k\in \{1,\ldots ,n+m\}\qquad -\infty <p_{k}~\leq ~x_{k}~\leq ~q_{k}<\infty ~,\end{matrix}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/abf091085a010d05def9a1d90acd689dc811d265)
und definieren die neuen Größen
![{\displaystyle {\begin{matrix}x'_{k}~=~x_{k}-p_{k},\qquad x''_{k}~=~q_{k}-x_{k},\qquad \Delta _{k}~=~q_{k}-p_{k}~\geq ~0\\&.\end{matrix}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/99861a3755437cfcc0f08eddfe7f95db1f5c5673)
Dann gilt
und
die Schranken
sind gleichbedeutend mit den Bedingungen
![{\displaystyle {\begin{matrix}\forall ~k\in \{1,\ldots ,n+m\}\qquad x_{k}^{B}\in \{x'_{k},\,x''_{k}\}~,\quad 0\leq x_{k}^{B}\leq \Delta _{k}\end{matrix}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/961073948fbd2aeb0562cdc99407fccac66d258e)
Die oberen Schranken in diesen Bedingungen lassen sich auch implizit behandeln, indem wir zweierlei feststellen:
- Die Unbekannte
kann im Gleichungssystem ohne Informationsverlust sowohl durch
als auch durch
ersetzt werden. Beim Wechsel von einer dieser Hilfsvariablen
auf ihr Gegenstück
ändern sich die Koeffizienten der Systemvariablen nur in ihren Vorzeichen.
- Die Schranken
und
können beide gleichzeitig erfüllt sein, aber nie gleichzeitig verletzt werden. Falls
verletzt werden sollte, ersetzen wir diese Bedingung durch
und wechseln auf die andere Hilfsvariable über.
Daraus folgt, dass wir dem Gleichungssytem immer
eine dual-zulässige Form
in basisabhängigen Unbekannten
geben können,
bei dessen Basislösung
alle Schranken
erfüllt sind:
![{\displaystyle {\begin{matrix}z&=&f_{0}^{B}&+&d_{1}^{B}\,x_{\pi (1)}^{B}&+&\cdots &+&d_{n}^{B}\,x_{\pi (n)}^{B}\\[3pt]x_{\pi (n+1)}^{B}&=&b_{1}^{B}&+&G_{11}^{B}\,x_{\pi (1)}^{B}&+&\cdots &+&G_{1n}^{B}\,x_{\pi (n)}^{B}\\\vdots &&\vdots &&\vdots &&&&\vdots \\x_{\pi (n+m)}^{B}&=&b_{m}^{B}&+&G_{m1}^{B}\,x_{\pi (1)}^{B}&+&\cdots &+&G_{mn}^{B}\,x_{\pi (n)}^{B}\\&&&&&&&&&.\end{matrix}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6f5440a401e26351c8b52c1065f0377427954be4)
![{\displaystyle {\begin{matrix}d_{1}^{B}\leq 0,\ \ldots ,\ d_{n}^{B}\leq 0,\qquad \quad b_{1}^{B}\leq \Delta _{\pi (n+1)},\ \ldots ,\ b_{m}^{B}\leq \Delta _{\pi (n+m)}\\&.\end{matrix}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b4926d163ec074841556b4717b1b7b353588ef09)
![{\displaystyle {\begin{matrix}x_{1}^{B}\geq 0,\ \ldots ,\ x_{n+m}^{B}\geq 0,\quad z\geq \max \\&.\end{matrix}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/28082c64508b7f30be7102030a60f2330c567832)
wobei
mit
sein muss.
Auf welche der beiden abgeleiteten Unbekannten sich
bezieht,
muss zusammen mit der Basisinformation
geführt werden.
Damit die obige Intervall-Form
von Schritt zu Schritt auch beibehalten wird,
wenden wir ein beliebiges duales Simplexverfahren an,
und tauschen gegebenenfalls nach jedem Schritt
im Gleichungssystem
die Unbekannten
und
gegeneinander aus.
Die Pivotauswahl erfolgt genau so wie bei der symmetrischen Grundform:
- Wähle ein beliebiges
, welches
erfüllt. Zum Beispiel, suche das kleinste
mit dieser Eigenschaft.
- Wähle ein beliebiges
, welches
erfüllt. Zum Beispiel, suche das kleinste
mit dieser Eigenschaft.
Das Gleichungssystems wird erst einmal wie bei der symmetrischen Grundform umgewandelt.
Nach der Freilegung von
und der entsprechenden Koeffizientenberechnung des umgewandelten Gleichungssystems
haben wir diese freigelegte Unbekannte zunächst in
umbenannt.
Die Größen
haben sich nun verändert.
Für jeder dieser neuen Größen außerhalb der vorgeschriebenen Schranke
tauschen wir die Hilfsvariable
für ihr Gegenstück
aus,
und wandeln Zeile
des Gleichungssystems entsprechend um:
![{\displaystyle {\begin{aligned}.\\x_{\pi (n+i)}^{B}&~=~b_{i}^{B}+G_{i1}^{B}\,x_{\pi (1)}^{B}+\cdots +G_{in}^{B}\,x_{\pi (n)}^{B}\\&\Longrightarrow ~~[\,\Delta _{\pi (n+i)}-x_{\pi (n+i)}^{B}\,]~=~[\,\Delta _{\pi (n+i)}-b_{i}^{B}\,]-G_{i1}^{B}\,x_{\pi (1)}^{B}-\cdots -G_{in}^{B}\,x_{\pi (n)}^{B}\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/280f767baac4fe720b60ad6c4fc634cb2b9a0e8d)
Ein Pivotverfahren mit beidseitig eingeschränkten Unbekannten verwendet die gleichen Datenstrukturen wie das symmetrische Pivotverfahren,
zum Beispiel, ein Simplextableau mit 2 zusätzlichen Zeilen und 2 zusätzlichen Spalten,
![{\displaystyle {\begin{matrix}{\begin{bmatrix}&&&&&\Delta _{\pi (1)}&\cdots &\Delta _{\pi (n)}\\[6pt]&&&&&\sigma _{\pi (1)}&\cdots &\sigma _{\pi (n)}\\[6pt]&&&0&~~&\pi (1)&\cdots &\pi (n)\\[6pt]&&n\!+\!m\!+\!1&f^{B}&&d_{1}^{B}&\cdots &d_{n}^{B}\\[18pt]\Delta _{\pi (n+1)}&\sigma _{\pi (n+1)}&\pi (n+1)&b_{1}^{B}&&G_{11}^{B}&\cdots &G_{1n}^{B}\\\vdots &\vdots &\vdots &\vdots &&\vdots &&\vdots \\\Delta _{\pi (n+m)}&\sigma _{\pi (n+m)}&\pi (n+m)&b_{m}^{B}&&G_{m1}^{B}&\cdots &G_{mn}^{B}\end{bmatrix}}\\&.\end{matrix}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e75c09173100b344ab13c3091b3a2ef02064cffb)
wobei
ist.