Benutzer:Heinrich Puschmann/Datenstrukturen für Pivotverfahren

aus Wikipedia, der freien Enzyklopädie
< Benutzer:Heinrich Puschmann
Dies ist die aktuelle Version dieser Seite, zuletzt bearbeitet am 1. Juli 2008 um 14:35 Uhr durch imported>Heinrich Puschmann(215600) (Einleitung).
(Unterschied) ← Nächstältere Version | Aktuelle Version (Unterschied) | Nächstjüngere Version → (Unterschied)

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


und dem über die Permutation davon abgewandelten System


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

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,

und definieren die neuen Größen

Dann gilt   und die Schranken   sind gleichbedeutend mit den Bedingungen


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:

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:

  1. Wähle ein beliebiges , welches erfüllt.  Zum Beispiel, suche das kleinste mit dieser Eigenschaft.
  2. 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:


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,

wobei ist.