Max-Plus-Algebra

mathematisches Objekt

Eine Max-Plus-Algebra ist ein mathematisches Objekt, das vergleichbar ist mit einer Algebra über den reellen Zahlen, wobei jedoch die Körper-Operationen ersetzt werden: die Addition durch das Bilden des Maximums, die Multiplikation durch die gewöhnliche Addition. Geometrie über der Max-Plus-Algebra wird als tropische Geometrie bezeichnet. Daher wird die Max-Plus-Algebra auch als tropischer Semiring bezeichnet. In der Planungstheorie, etwa bei der Behandlung von Petri-Netzen, erlaubt die Theorie der Max-Plus-Algebren den Einsatz geeigneter Methoden aus der linearen Algebra. Das Optimieren eines Fahrplans kann beispielsweise auf diesem Wege als Eigenwertproblem aufgefasst werden.

Ebenso wie der Begriff Algebra sowohl eine mathematische Struktur als auch ein mathematisches Teilgebiet bezeichnet, versteht man unter Max-Plus-Algebra manchmal auch das mathematische Teilgebiet, das sich mit den besagten Strukturen beschäftigt.

Definition

Bearbeiten

Eine Max-Plus-Algebra ist ein Halbring  , auf dem ein idempotenter kommutativer Halbkörper mit Nullelement   vermöge einer Multiplikation   operiert. (Zum Vergleich: Eine Algebra ist ein Ring, auf dem ein Körper operiert)

Im Einzelnen bedeutet dies, dass die nachfolgend aufgezählten Axiome erfüllt sind, jeweils für alle   und  .

Halbring

Bearbeiten
  1.  
  2.  
  3.  
  4.  
  5.  

Gemäß 1. und 2. ist   kommutative Halbgruppe, gemäß 3. ist   Halbgruppe, 4. und 5. sind die Distributivgesetze.

Idempotenter kommutativer Halbkörper

Bearbeiten
  1.  
  2.  
  3.  
  4.  
  5.  
  6.  
  7.  
  8. Falls  , so gibt es ein   mit  
  9.  
  10.  

Gemäß 1.–5. ist   Halbring, gemäß 6. und 7. sind   und   jeweils neutrale Elemente der Verknüpfungen. Zusammen mit der Existenz multiplikativ inverser Elemente gemäß 8. ist daher   Halbkörper, der gemäß 9. (multiplikativ) kommutativ und gemäß 10. (additiv) idempotent ist.

Operation

Bearbeiten
  1.  
  2.  
  3.  
  4.  
  5.  

Die Operation   soll also in naheliegender Weise verträglich mit den Verknüpfungen auf   bzw.   sein.

Beispiele

Bearbeiten

Im Folgenden werden der besseren Lesbarkeit halber die Indizes an den Verknüpfungen weggelassen, da jeweils aus dem Kontext klar ist, welche der Verknüpfungen gemeint sein muss. Die Umkreisungen der Operatoren dagegen sind erforderlich, um eine Verwechselung mit der gewöhnlichen Addition bzw. Multiplikation zu vermeiden.

Das wichtigste Beispiel für einen idempotenten kommutativen Halbkörper wird mit   bezeichnet und hat als zugrunde liegende Menge   sowie die Verknüpfungen

  •   (speziell  )
  •   (speziell  ).

Das neutrale Element bezüglich   ist dabei  , das bezüglich   ist 0. Diese Verwendung der Operationen Maximum und Addition motiviert auch die Bezeichnung Max-Plus-Algebra. Ein weiterer wichtiger idempotenter kommutativen Halbkörper ist  , er wird zum Teil als Min-Plus-Algebra bezeichnet. Die folgenden Beispiele von Max-Plus-Algebren sind durchweg Max-Plus-Algebren über  :

  •   selbst ist eine Max-Plus-Algebra.
  • Die Menge   aller Abbildungen von einer festen Menge   nach   mit punktweiser Maximumbildung und Addition und Skalaroperation.
  • Auf der Menge   aller Abbildungen   kann man die erforderlichen Operationen wie folgt definieren:
      (punktweise Maximumbildung)
      (so genannte Supremumfaltung)
     
Allerdings ist   unter der Supremumsfaltung nicht abgeschlossen. Durch den Übergang zu geeigneten Teilmengen davon, beispielsweise zur Menge der nach oben beschränkten Abbildungen, erhält man jedoch eine Max-Plus-Algebra. Man beachte, dass diese Struktur sich vom Spezialfall   des vorhergehenden Beispiels unterscheidet.
  • Die Menge   aller  -Matrizen mit Einträgen in  , wobei Addition und Multiplikation von Matrizen nach den üblichen Formeln, in denen jedoch   und   durch   und   ersetzt sind, berechnet werden. Wie die gewöhnliche Matrixmultiplikation ist auch   nicht kommutativ.

Literatur

Bearbeiten
  • Peter Butkovič: Max-linear Systems: Theory and Algorithms. In: Springer Monographs in Mathematics. Springer-Verlag, 2010, doi:10.1007/978-1-84996-299-5.
Bearbeiten