Max-Plus-Algebra

Eine Max-Plus-Agebra 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. 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

Eine Max-Plus-Algebra ist ein Halbring $(A,\oplus_A,\otimes_A)$, auf dem ein idempotenter kommutativer Halbkörper mit Nullelement $(K,\oplus_K,\otimes_K,\varepsilon,e)$ vermöge einer Multiplikation $\otimes$ operiert. (Zum Vergleich: Eine Algebra ist ein Ring, auf dem ein Körper operiert)

Im Einzelnen bedeutet dies, das die nachfolgend aufgezählten Axiome erfüllt sind, jeweils für alle $a,b,c\in K$ und $u,v,w\in A$.

Halbring

1. $u\oplus_A(v\oplus_A w) = (u\oplus_A v)\oplus_A w$
2. $u\oplus_A v = v \oplus_A u$
3. $u\otimes_A(v\otimes_A w) = (u\otimes_A v)\otimes_A w$
4. $u\otimes_A(v\oplus_A w) = (u\otimes_A v)\oplus_A (u\otimes_A w)$
5. $(u\oplus_A v)\otimes_A w = (u\otimes_A w)\oplus_A (v\otimes_A w)$

Gemäß 1. und 2. ist $(A,\oplus_A)$ kommutative Halbgruppe, gemäß 3. ist $(A,\otimes_A)$ Halbgruppe, 4. und 5. sind die Distributivgesetze.

Idempotenter kommutativer Halbkörper

1. $a\oplus_K(b\oplus_K c) = (a\oplus_K b)\oplus_K c$
2. $a\oplus_K b = b \oplus_K a$
3. $a\otimes_K(b\otimes_K c) = (a\otimes_K b)\otimes_K c$
4. $a\otimes_K(b\oplus_K c) = (a\otimes_K b)\oplus_K (a\otimes_K c)$
5. $(a\oplus_K b)\otimes_K c = (a\otimes_K c)\oplus_K (b\otimes_K c)$
6. $\varepsilon\oplus_K a = a\oplus_K\varepsilon = a$
7. $e\otimes_K a = a\otimes_K e = a$
8. Falls $a\ne\varepsilon$, so gibt es ein $a'\in K$ mit $a\otimes_K a' = a'\otimes_K a = e$
9. $a\otimes_K b = b \otimes_K a$
10. $a\oplus_K a=a$

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

Operation

1. $e\otimes v=v$
2. $(a\otimes_K b)\otimes v=a\otimes(b\otimes v)$
3. $a\otimes (v\otimes_A w)=(a\otimes v)\otimes_A w$
4. $(a\oplus_K b)\otimes v=(a\otimes v)\oplus_A (b\otimes v)$
5. $a\otimes (v\oplus_A w)=(a\otimes v)\oplus_A (a\otimes w)$

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

Beispiele

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 de 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 $\R_\max$ bezeichnet und hat als zugrunde liegende Menge $\R\cup\{-\infty\}$ sowie die Verknüpfungen

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

Das neutrale Element bezüglich $\oplus$ ist dabei $-\infty$, das bezüglich $\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 $\R_\min:=(\R\cup\{+\infty\},\min,+,+\infty,0)$. Die folgenden Beispiele von Max-Plus-Algebren sind durchweg Max-Plus-Algebren über $\R_\max$:

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

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

  $(f\otimes g)(x) = \sup_{t\in\R}(f(t)+g(x-t))$ (so genannte Supremumfaltung)

  $(c\otimes f)(x) = c\otimes f(x) = c+f(x)$

Allerdings ist $\R_\max^\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 $M=\R$ des vorhergehenden Beispiels unterscheidet.

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

Literatur

• Peter Butkovič: Max-linear Systems: Theory and Algorithms. In: Springer Monographs in Mathematics. Springer-Verlag, 2010.

Weblinks

• http://maxplus.org
• http://amadeus.inria.fr/gaubert/maxplus.html