Benutzer:Heinrich Puschmann/Datenstrukturen für Pivotverfahren

Eine Datenstruktur für ein Pivotverfahren speichert auf direkte oder indirekte Art die Information für folgendes Gleichungssystem

${\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}}$

und dem über die Permutation $x_{\pi (1)},\ldots x_{\pi (n+m)}$ davon abgewandelten System

${\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}}$

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

${\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}}$

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 $\,x_{k}\geq 0\,$ auf ein beliebiges Intervall $\,p_{k}\leq x_{k}\leq q_{k}\,$ 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,

${\begin{matrix}\forall ~k\in \{1,\ldots ,n+m\}\qquad -\infty <p_{k}~\leq ~x_{k}~\leq ~q_{k}<\infty ~,\end{matrix}}$

und definieren die neuen Größen

${\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}}$

Dann gilt $\,x'_{k}+x''_{k}~=~\Delta _{k}\,$  und die Schranken $\,p_{k}\leq x_{k}\leq q_{k}\,$  sind gleichbedeutend mit den Bedingungen

${\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}}$

Die oberen Schranken in diesen Bedingungen lassen sich auch implizit behandeln, indem wir zweierlei feststellen:

• Die Unbekannte $x_{k}\,$ kann im Gleichungssystem ohne Informationsverlust sowohl durch $x'_{k}\,$ als auch durch $x''_{k}\,$ ersetzt werden. Beim Wechsel von einer dieser Hilfsvariablen $x_{k}^{B}\,$ auf ihr Gegenstück $\,[\Delta _{k}-x_{k}^{B}]\,$ ändern sich die Koeffizienten der Systemvariablen nur in ihren Vorzeichen.
• Die Schranken $\,{x_{k}^{B}\geq 0}\,$ und  $\,{x_{k}^{B}\leq \Delta _{k}}\,$ können beide gleichzeitig erfüllt sein, aber nie gleichzeitig verletzt werden. Falls $\,{x_{k}^{B}\leq \Delta _{k}}\,$ verletzt werden sollte, ersetzen wir diese Bedingung durch $\,[\Delta _{k}-x_{k}^{B}]\geq 0\,$ und wechseln auf die andere Hilfsvariable über.

Daraus folgt, dass wir dem Gleichungssytem immer eine dual-zulässige Form in basisabhängigen Unbekannten $\,x_{k}^{B}\,$ geben können, bei dessen Basislösung alle Schranken $\,{x_{k}^{B}\leq \Delta _{k}}\,$ erfüllt sind:

${\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}}$

${\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}}$

${\begin{matrix}x_{1}^{B}\geq 0,\ \ldots ,\ x_{n+m}^{B}\geq 0,\quad z\geq \max \\&.\end{matrix}}$

wobei $\,x_{k}^{B}\in \{x'_{k},\,x''_{k}\}\,$ mit $\,x'_{k}+x''_{k}=\Delta _{k}\,$ sein muss. Auf welche der beiden abgeleiteten Unbekannten sich $x_{k}^{B}\,$ bezieht, muss zusammen mit der Basisinformation $B\,$ 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 $x'_{\pi (s)}\,$ und $x''_{\pi (s)}\,$ gegeneinander aus.

Die Pivotauswahl erfolgt genau so wie bei der symmetrischen Grundform:

1. Wähle ein beliebiges $\pi (n+r)\,$, welches $\,b_{r}^{B}<0\,$ erfüllt.  Zum Beispiel, suche das kleinste $\pi (n+r)\,$ mit dieser Eigenschaft.
2. Wähle ein beliebiges $\pi (s)\,$, welches $\,(-d_{s}^{B})/G_{rs}^{B}=\min _{j}{\bigl \{}\,(-d_{j}^{B})/G_{rj}^{B}~|~G_{rj}^{B}>0\,{\bigr \}}$ erfüllt.  Zum Beispiel, suche das kleinste $\pi (s)\,$ mit dieser Eigenschaft.

Das Gleichungssystems wird erst einmal wie bei der symmetrischen Grundform umgewandelt. Nach der Freilegung von $x_{\pi (s)}^{B}\,$ und der entsprechenden Koeffizientenberechnung des umgewandelten Gleichungssystems haben wir diese freigelegte Unbekannte zunächst in $x_{\pi (n+r)}^{B}\,$ umbenannt.

Die Größen $\,b_{1}^{B},\ldots ,b_{m}^{B}\,$ haben sich nun verändert. Für jeder dieser neuen Größen außerhalb der vorgeschriebenen Schranke $\,b_{i}^{B}\leq \Delta _{\pi (n+i)}\,$ tauschen wir die Hilfsvariable $x_{\pi (n+i)}^{B}\,$ für ihr Gegenstück $[\Delta _{\pi (n+i)}-x_{\pi (n+i)}^{B}]$ aus, und wandeln Zeile $i\,$ des Gleichungssystems entsprechend um:

${\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}}$

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,

${\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}}$

wobei $\sigma _{\pi (k)}\in \{x',x''\}$ ist.