Max-Plus-Algebra

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 w​ie der Begriff Algebra sowohl e​ine mathematische Struktur a​ls auch e​in mathematisches Teilgebiet bezeichnet, versteht m​an unter Max-Plus-Algebra manchmal a​uch das mathematische Teilgebiet, d​as sich m​it den besagten Strukturen beschäftigt.

Definition

Eine Max-Plus-Algebra ist ein Halbring ${\displaystyle (A,\oplus _{A},\otimes _{A})}$, auf dem ein idempotenter kommutativer Halbkörper mit Nullelement ${\displaystyle (K,\oplus _{K},\otimes _{K},\varepsilon ,e)}$ vermöge einer Multiplikation ${\displaystyle \otimes }$ 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 ${\displaystyle a,b,c\in K}$ und ${\displaystyle u,v,w\in A}$.

Halbring

1. ${\displaystyle u\oplus _{A}(v\oplus _{A}w)=(u\oplus _{A}v)\oplus _{A}w}$
2. ${\displaystyle u\oplus _{A}v=v\oplus _{A}u}$
3. ${\displaystyle u\otimes _{A}(v\otimes _{A}w)=(u\otimes _{A}v)\otimes _{A}w}$
4. ${\displaystyle u\otimes _{A}(v\oplus _{A}w)=(u\otimes _{A}v)\oplus _{A}(u\otimes _{A}w)}$
5. ${\displaystyle (u\oplus _{A}v)\otimes _{A}w=(u\otimes _{A}w)\oplus _{A}(v\otimes _{A}w)}$

Gemäß 1. und 2. ist ${\displaystyle (A,\oplus _{A})}$ kommutative Halbgruppe, gemäß 3. ist ${\displaystyle (A,\otimes _{A})}$ Halbgruppe, 4. und 5. sind die Distributivgesetze.

Idempotenter kommutativer Halbkörper

1. ${\displaystyle a\oplus _{K}(b\oplus _{K}c)=(a\oplus _{K}b)\oplus _{K}c}$
2. ${\displaystyle a\oplus _{K}b=b\oplus _{K}a}$
3. ${\displaystyle a\otimes _{K}(b\otimes _{K}c)=(a\otimes _{K}b)\otimes _{K}c}$
4. ${\displaystyle a\otimes _{K}(b\oplus _{K}c)=(a\otimes _{K}b)\oplus _{K}(a\otimes _{K}c)}$
5. ${\displaystyle (a\oplus _{K}b)\otimes _{K}c=(a\otimes _{K}c)\oplus _{K}(b\otimes _{K}c)}$
6. ${\displaystyle \varepsilon \oplus _{K}a=a\oplus _{K}\varepsilon =a}$
7. ${\displaystyle e\otimes _{K}a=a\otimes _{K}e=a}$
8. Falls ${\displaystyle a\neq \varepsilon }$, so gibt es ein ${\displaystyle a'\in K}$ mit ${\displaystyle a\otimes _{K}a'=a'\otimes _{K}a=e}$
9. ${\displaystyle a\otimes _{K}b=b\otimes _{K}a}$
10. ${\displaystyle a\oplus _{K}a=a}$

Gemäß 1.–5. ist ${\displaystyle (K\oplus _{K},\otimes _{K})}$ Halbring, gemäß 6. und 7. sind ${\displaystyle \varepsilon }$ und ${\displaystyle e}$ jeweils neutrale Elemente der Verknüpfungen. Zusammen mit der Existenz multiplikativ inverser Elemente gemäß 8. ist daher ${\displaystyle (K,\oplus _{K},\otimes _{K},\varepsilon ,e)}$ Halbkörper, der gemäß 9. (multiplikativ) kommutativ und gemäß 10. (additiv) idempotent ist.

Operation

1. ${\displaystyle e\otimes v=v}$
2. ${\displaystyle (a\otimes _{K}b)\otimes v=a\otimes (b\otimes v)}$
3. ${\displaystyle a\otimes (v\otimes _{A}w)=(a\otimes v)\otimes _{A}w}$
4. ${\displaystyle (a\oplus _{K}b)\otimes v=(a\otimes v)\oplus _{A}(b\otimes v)}$
5. ${\displaystyle a\otimes (v\oplus _{A}w)=(a\otimes v)\oplus _{A}(a\otimes w)}$

Die Operation ${\displaystyle \otimes }$ soll also in naheliegender Weise verträglich mit den Verknüpfungen auf ${\displaystyle A}$ bzw. ${\displaystyle K}$ sein.

Beispiele

Im Folgenden werden d​er besseren Lesbarkeit halber d​ie Indizes a​n den Verknüpfungen weggelassen, d​a jeweils a​us dem Kontext k​lar ist, welche d​er Verknüpfungen gemeint s​ein muss. Die Umkreisungen d​er Operatoren dagegen s​ind erforderlich, u​m eine Verwechselung m​it der gewöhnlichen Addition bzw. Multiplikation z​u vermeiden.

Das wichtigste Beispiel für einen idempotenten kommutativen Halbkörper wird mit ${\displaystyle \mathbb {R} _{\max }}$ bezeichnet und hat als zugrunde liegende Menge ${\displaystyle \mathbb {R} \cup \{-\infty \}}$ sowie die Verknüpfungen

• ${\displaystyle x\oplus y:=\max\{x,y\}}$ (speziell ${\displaystyle (-\infty )\oplus x=x\oplus (-\infty )=x}$)
• ${\displaystyle x\otimes y:=x+y}$ (speziell ${\displaystyle (-\infty )\otimes x=x\otimes (-\infty )=-\infty }$).

Das neutrale Element bezüglich ${\displaystyle \oplus }$ ist dabei ${\displaystyle -\infty }$, das bezüglich ${\displaystyle \otimes }$ ist 0. Diese Verwendung der Operationen Maximum und Addition motiviert auch die Bezeichnung Max-Plus-Algebra. Ein weiterer wichtiger idempotenter kommutativen Halbkörper ist ${\displaystyle \mathbb {R} _{\min }:=(\mathbb {R} \cup \{+\infty \},\min ,+,+\infty ,0)}$, er wird zum Teil als Min-Plus-Algebra bezeichnet. Die folgenden Beispiele von Max-Plus-Algebren sind durchweg Max-Plus-Algebren über ${\displaystyle \mathbb {R} _{\max }}$:

• ${\displaystyle \mathbb {R} _{\max }}$ selbst ist eine Max-Plus-Algebra.
• Die Menge ${\displaystyle \mathbb {R} _{\max }^{M}}$ aller Abbildungen von einer festen Menge ${\displaystyle M}$ nach ${\displaystyle \mathbb {R} _{\max }}$ mit punktweiser Maximumbildung und Addition und Skalaroperation.
• Auf der Menge ${\displaystyle \mathbb {R} _{\max }^{\mathbb {R} }}$ aller Abbildungen ${\displaystyle f\colon \mathbb {R} \to \mathbb {R} _{\max }}$ kann man die erforderlichen Operationen wie folgt definieren:

  ${\displaystyle (f\oplus g)(x)=f(x)\oplus g(x)=\max\{f(x),g(x)\}}$ (punktweise Maximumbildung)

  ${\displaystyle (f\otimes g)(x)=\sup _{t\in \mathbb {R} }(f(t)+g(x-t))}$ (so genannte Supremumfaltung)

  ${\displaystyle (c\otimes f)(x)=c\otimes f(x)=c+f(x)}$

Allerdings ist ${\displaystyle \mathbb {R} _{\max }^{\mathbb {R} }}$ 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 ${\displaystyle M=\mathbb {R} }$ des vorhergehenden Beispiels unterscheidet.

• Die Menge ${\displaystyle \mathbb {R} _{\max }^{n\times n}}$ aller ${\displaystyle n\times n}$-Matrizen mit Einträgen in ${\displaystyle \mathbb {R} _{\max }}$, wobei Addition und Multiplikation von Matrizen nach den üblichen Formeln, in denen jedoch ${\displaystyle +}$ und ${\displaystyle \cdot }$ durch ${\displaystyle \oplus }$ und ${\displaystyle \otimes }$ ersetzt sind, berechnet werden. Wie die gewöhnliche Matrixmultiplikation ist auch ${\displaystyle \otimes }$ nicht kommutativ.

Literatur

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

Weblinks

• amadeus.inria.fr