Quelltext der Seite 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

:<math>\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}</math>
#
<br>
und dem über die Permutation <math>x_{\pi(1)},\ldots x_{\pi(n+m)}</math> davon abgewandelten System
#
:<math>\begin{matrix}
z       & = & f^\pi_0     & + & d^\pi_1\,x_{\pi(1)} & + & \cdots & + &  d^\pi_n\,x_{\pi(n)}
\\[3pt]
x_{\pi(n+1)} & = & b^\pi_1     & + & G^\pi_{11}\,x_{\pi(1)} & + & \cdots & + & G^\pi_{1n}\,x_{\pi(n)}
\\
\vdots  &   & \vdots  &   &  \vdots   &   &        &   &  \vdots
\\
x_{\pi(n+m)} & = & b^\pi_m     & + & G^\pi_{m1}\,x_{\pi(1)} & + & \cdots & + & G^\pi_{mn}\,x_{\pi(n)}
\end{matrix}</math>


Pivotverfahren können sehr verschiedenartig umgesetzt werden,
wobei die Besonderheit der Aufgabe, die Besetzungsdichte des Gleichungssystems und
<!-- andere Faktoren -->
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==

[[Simplex-Verfahren#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
#
:<math>\begin{bmatrix}
              & 0         &~~& \pi(1)    & \cdots & \pi(n)
\\[3pt]
n\!+\!m\!+\!1 & f^B       &  & d^B_1     & \cdots & d^B_n
\\[18pt]
\pi(n+1)      & b^B_1     &  & G^B_{11}  & \cdots & G^B_{1n}
\\
\vdots        & \vdots    &  & \vdots    &        & \vdots
\\
\pi(n+m) & b^B_m          &  & G^B_{m1}  & \cdots & G^B_{mn}
\end{bmatrix}</math>
#
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 <math>\,x_k\ge0\,</math>
auf ein beliebiges Intervall <math>\,p_k\le x_k\le q_k\,</math>
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,
:
:<math>\begin{matrix}
\forall~k\in\{1,\ldots,n+m\}\qquad
-\infty<p_k~\le~ x_k~\le~ q_k<\infty~,
\end{matrix}</math>
:
und definieren die neuen Größen
:
:<math>\begin{matrix}
x'_k ~=~ x_k - p_k, \qquad
x''_k ~=~ q_k - x_k, \qquad
\Delta_k ~=~ q_k - p_k ~\ge~0
\\&.
\end{matrix}</math>
:
Dann gilt <math>\,x'_k + x''_k ~=~ \Delta_k\,</math>&nbsp; und
die Schranken <math>\,p_k\le x_k\le q_k\,</math>&nbsp; sind gleichbedeutend mit den Bedingungen
:
:<math>\begin{matrix}
\forall~k\in\{1,\ldots,n+m\}\qquad
x^B_k\in\{x'_k,\,x''_k\}~,\quad
0\le x^B_k\le\Delta_k
\end{matrix}</math>



Die oberen Schranken in diesen Bedingungen lassen sich auch implizit behandeln, indem wir zweierlei feststellen:
<!-- -->
:*Die Unbekannte&nbsp;<math>x_k\,</math> kann im Gleichungssystem ohne Informationsverlust sowohl durch <math>x'_k\,</math> als auch durch&nbsp;<math>x''_k\,</math> ersetzt werden. Beim Wechsel von einer dieser Hilfsvariablen&nbsp;<math>x^B_k\,</math> auf ihr Gegenstück <math>\,[\Delta_k-x^B_k]\,</math> ändern sich die Koeffizienten der Systemvariablen nur in ihren Vorzeichen.
:*Die Schranken <math>\,{x^B_k\ge0}\,</math> und &nbsp;<math>\,{x^B_k\le\Delta_k}\,</math> können beide gleichzeitig erfüllt sein, aber ''nie gleichzeitig verletzt'' werden. Falls <math>\,{x^B_k\le\Delta_k}\,</math> verletzt werden sollte, ersetzen wir diese Bedingung durch <math>\,[\Delta_k-x^B_k]\ge0\,</math> und wechseln auf die andere Hilfsvariable über.
<!-- -->

Daraus folgt, dass wir dem Gleichungssytem immer
eine dual-zulässige Form
in basisabhängigen Unbekannten&nbsp;<math>\,x^B_k\,</math> geben können,
bei dessen Basislösung
alle Schranken <math>\,{x^B_k\le\Delta_k}\,</math> erfüllt sind:
:
:<math>\begin{matrix}
z              &=& f^B_0  &+& d^B_1\,x^B_{\pi(1)}    &+& \cdots &+&  d^B_n\,x^B_{\pi(n)}
\\[3pt]
x^B_{\pi(n+1)} &=& b^B_1  &+& G^B_{11}\,x^B_{\pi(1)} &+& \cdots &+& G^B_{1n}\,x^B_{\pi(n)}
\\
\vdots         & & \vdots & &  \vdots                & &        & &  \vdots
\\
x^B_{\pi(n+m)} &=& b^B_m  &+& G^B_{m1}\,x^B_{\pi(1)} &+& \cdots &+& G^B_{mn}\,x^B_{\pi(n)}
\\& & & & & & & & &.
\end{matrix}</math>
:
:<math>\begin{matrix}
d^B_1\le0,\ \ldots,\ d^B_n\le0,
\qquad\quad
b^B_1\le\Delta_{\pi(n+1)},\ \ldots,\ b^B_m\le\Delta_{\pi(n+m)}
\\&.
\end{matrix}</math>
:
:<math>\begin{matrix}
x^B_1\ge0,\ \ldots,\ x^B_{n+m}\ge0,\quad z\ge\max
\\&.
\end{matrix}</math>
:
wobei <math>\,x^B_k\in\{x'_k,\,x''_k\}\,</math> mit <math>\,x'_k+x''_k=\Delta_k\,</math> sein muss.
Auf ''welche'' der beiden abgeleiteten Unbekannten sich <math>x^B_k\,</math> bezieht,
muss zusammen mit der Basisinformation&nbsp;<math>B\,</math> 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 <math>x'_{\pi(s)}\,</math> und <math>x''_{\pi(s)}\,</math> gegeneinander aus.

Die Pivotauswahl erfolgt genau so wie bei der symmetrischen Grundform:
#Wähle ein beliebiges <math>\pi(n+r)\,</math>, welches <math>\,b^B_r<0\,</math> erfüllt.&nbsp; Zum Beispiel, suche das ''kleinste'' <math>\pi(n+r)\,</math> mit dieser Eigenschaft.
#Wähle ein beliebiges <math>\pi(s)\,</math>, welches <math>\,(-d^B_s)/G^B_{rs}=\min_j\bigl\{\,(-d^B_j)/G^B_{rj}~|~G^B_{rj}>0\,\bigr\}</math> erfüllt.&nbsp; Zum Beispiel, suche das ''kleinste'' <math>\pi(s)\,</math> mit dieser Eigenschaft.

Das Gleichungssystems wird erst einmal wie bei der symmetrischen Grundform umgewandelt.
''Nach'' der Freilegung von&nbsp;<math>x^B_{\pi(s)}\,</math> und der entsprechenden Koeffizientenberechnung des umgewandelten Gleichungssystems
haben wir diese freigelegte Unbekannte zunächst in&nbsp;<math>x^B_{\pi(n+r)}\,</math> umbenannt.

Die Größen&nbsp;<math>\,b^B_1,\ldots,b^B_m\,</math> haben sich nun verändert.
Für jeder dieser neuen Größen ''außerhalb'' der vorgeschriebenen Schranke <math>\,b^B_i\le\Delta_{\pi(n+i)}\,</math>
tauschen wir die Hilfsvariable&nbsp;<math>x^B_{\pi(n+i)}\,</math> für ihr Gegenstück <math>[\Delta_{\pi(n+i)}-x^B_{\pi(n+i)}]</math> aus,
und wandeln Zeile&nbsp;<math>i\,</math> des Gleichungssystems entsprechend um:
<!-- -->
:<math>\begin{align}
.\\
x^B_{\pi(n+i)}& ~=~ b^B_i + G^B_{i1}\,x^B_{\pi(1)} + \cdots + G^B_{in}\,x^B_{\pi(n)}
\\
&\Longrightarrow~~
[\,\Delta_{\pi(n+i)}-x^B_{\pi(n+i)}\,]
~=~ [\,\Delta_{\pi(n+i)}-b^B_i\,] - G^B_{i1}\,x^B_{\pi(1)} - \cdots - G^B_{in}\,x^B_{\pi(n)}
\end{align}</math>


Ein Pivotverfahren mit beidseitig eingeschränkten Unbekannten verwendet die gleichen Datenstrukturen wie das symmetrische Pivotverfahren,
zum Beispiel, ein Simplextableau mit 2&nbsp;zusätzlichen Zeilen und 2&nbsp;zusätzlichen Spalten,
#
:<math>\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^B_1            & \cdots & d^B_n
\\[18pt]
\Delta_{\pi(n+1)}  & \sigma_{\pi(n+1)}  &\pi(n+1)      & b^B_1     &  & G^B_{11}         & \cdots & G^B_{1n}
\\
\vdots             & \vdots             &\vdots        & \vdots    &  & \vdots           &        & \vdots
\\
\Delta_{\pi(n+m)}  & \sigma_{\pi(n+m)}  &\pi(n+m)      & b^B_m     &  & G^B_{m1}         & \cdots & G^B_{mn}
\end{bmatrix}
\\&.
\end{matrix}</math>
#
wobei <math>\sigma_{\pi(k)}\in\{x',x''\}</math> ist.