Total unimodulare Matrix

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen

Eine total unimodulare Matrix ist eine Matrix mit ganzzahligen Einträgen, bei der noch weitere Ansprüche an die Determinanten aller quadratischen Untermatrizen gestellt sind. Total unimodulare Matrizen spielen in der diskreten Optimierung eine Rolle, da sie unter bestimmten Bedingungen die Ganzzahligkeit der Lösung eines linearen Optimierungsproblems garantieren.

Definition[Bearbeiten | Quelltext bearbeiten]

Sei eine Matrix. Dann heißt total unimodular (manchmal auch absolut unimodular oder vollständig unimodular) genau dann, wenn alle Minoren (Determinanten von quadratischen Untermatrizen) von den Wert oder haben. Insbesondere sind dann alle Einträge (-Untermatrizen) aus .

Alternativ formuliert ist eine total unimodulare Matrix eine (nicht notwendigerweise quadratische) Matrix, bei der alle quadratischen, nichtsingulären Untermatrizen ganzzahlig unimodular sind.

Eigenschaften[Bearbeiten | Quelltext bearbeiten]

  • Die Inzidenzmatrix eines ungerichteten bipartiten Graphen ist total unimodular.
  • Die Inzidenzmatrix eines gerichteten Graphen ist total unimodular.
  • Ist total unimodular, so ist auch die transponierte Matrix total unimodular, denn Determinanten bleiben unter Transposition erhalten.
  • Ihre Bedeutung bekommen total unimodulare Matrizen aufgrund der folgenden Aussage: Ist total unimodular und , so besitzt das Polyeder nur ganzzahlige Ecken. Ist ein lineares Optimierungsproblem unter der Nebenbedingung gegeben, so ist die Optimallösung ganzzahlig. Ist außerdem , so ist auch der Zielfunktionswert ganzzahlig.
  • Die Anzahl an Untermatrizen einer Matrix ist exponentiell in der Anzahl der Zeilen/Spalten der Matrix. Obwohl alle diese Untermatrizen zur Charakterisierung der totalen Unimodularität herangezogen werden, gibt es einen polynomiellen Algorithmus zur Entscheidung, ob eine Matrix total unimodular ist oder nicht.

Beispiel[Bearbeiten | Quelltext bearbeiten]

Betrachte die Matrix

  1. Alle Einträge sind entweder oder und damit auch alle -Untermatrizen
  2. Enthält eine Matrix nur Einträge aus und dabei mindestens eine Null, so ist ihre Determinante auch aus . Insbesondere sind die Determinanten aller -Untermatrizen der obigen Matrix aus .
  3. Mittels der Regel von Sarrus kann man überprüfen, dass auch die Determinanten der vier -Untermatrizen aus sind.

Daher ist die Matrix total unimodular.

Literatur[Bearbeiten | Quelltext bearbeiten]