imported>Xario: /* Weblinks */ http://maxplus.org/ maxplus.org entfernt, kann man nicht als excellent bezeichnen. veraltet, ungepflegt, kaum inhalt, viele tote links

2020-05-11T21:31:38Z

Weblinks: http://maxplus.org/ maxplus.org entfernt, kann man nicht als excellent bezeichnen. veraltet, ungepflegt, kaum inhalt, viele tote links

Neue Seite

Eine '''Max-Plus-Algebra''' ist ein [[Mathematik|mathematisches]] Objekt, das vergleichbar ist mit einer [[Algebra über einem Körper|Algebra]] über den [[Reelle Zahl|reellen Zahlen]], wobei jedoch die [[Körper (Algebra)|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-Netz]]en, erlaubt die Theorie der Max-Plus-Algebren den Einsatz geeigneter Methoden aus der [[Lineare Algebra|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 (Algebraische Struktur)|Halbring]] <math>(A,\oplus_A,\otimes_A)</math>, auf dem ein idempotenter kommutativer [[Halbkörper]] mit Nullelement <math>(K,\oplus_K,\otimes_K,\varepsilon,e)</math> vermöge einer Multiplikation <math>\otimes</math> 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 <math>a,b,c\in K</math> und <math> u,v,w\in A</math>.

=== Halbring ===
# <math>u\oplus_A(v\oplus_A w) = (u\oplus_A v)\oplus_A w</math>
# <math>u\oplus_A v = v \oplus_A u</math>
# <math>u\otimes_A(v\otimes_A w) = (u\otimes_A v)\otimes_A w</math>
# <math>u\otimes_A(v\oplus_A w) = (u\otimes_A v)\oplus_A (u\otimes_A w)</math>
# <math>(u\oplus_A v)\otimes_A w = (u\otimes_A w)\oplus_A (v\otimes_A w)</math>
Gemäß 1. und 2. ist <math>(A,\oplus_A)</math> kommutative Halbgruppe, gemäß 3. ist <math>(A,\otimes_A)</math> Halbgruppe, 4. und 5. sind die Distributivgesetze.

=== Idempotenter kommutativer Halbkörper ===
# <math>a\oplus_K(b\oplus_K c) = (a\oplus_K b)\oplus_K c</math>
# <math>a\oplus_K b = b \oplus_K a</math>
# <math>a\otimes_K(b\otimes_K c) = (a\otimes_K b)\otimes_K c</math>
# <math>a\otimes_K(b\oplus_K c) = (a\otimes_K b)\oplus_K (a\otimes_K c)</math>
# <math>(a\oplus_K b)\otimes_K c = (a\otimes_K c)\oplus_K (b\otimes_K c)</math>
# <math>\varepsilon\oplus_K a = a\oplus_K\varepsilon = a</math>
# <math>e\otimes_K a = a\otimes_K e = a</math>
# Falls <math>a\ne\varepsilon</math>, so gibt es ein <math>a'\in K</math> mit <math>a\otimes_K a' = a'\otimes_K a = e</math>
# <math>a\otimes_K b = b \otimes_K a</math>
# <math>a\oplus_K a=a</math>
Gemäß 1.–5. ist <math>(K\oplus_K,\otimes_K)</math> Halbring, gemäß 6. und 7. sind <math>\varepsilon</math> und <math>e</math> jeweils neutrale Elemente der Verknüpfungen. Zusammen mit der Existenz multiplikativ inverser Elemente gemäß 8. ist daher <math>(K,\oplus_K,\otimes_K,\varepsilon,e)</math> Halbkörper, der gemäß 9. (multiplikativ) kommutativ und gemäß 10. (additiv) idempotent ist.

=== Operation ===
# <math>e\otimes v=v</math>
# <math>(a\otimes_K b)\otimes v=a\otimes(b\otimes v)</math>
# <math>a\otimes (v\otimes_A w)=(a\otimes v)\otimes_A w</math>
# <math>(a\oplus_K b)\otimes v=(a\otimes v)\oplus_A (b\otimes v)</math>
# <math>a\otimes (v\oplus_A w)=(a\otimes v)\oplus_A (a\otimes w)</math>
Die Operation <math>\otimes</math> soll also in naheliegender Weise verträglich mit den Verknüpfungen auf <math>A</math> bzw. <math>K</math> 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 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 <math>\R_\max</math> bezeichnet und hat als zugrunde liegende Menge <math>\R\cup\{-\infty\}</math> sowie die Verknüpfungen
* <math>x\oplus y :=\max\{x,y\}</math> (speziell <math>(-\infty)\oplus x=x\oplus(-\infty)=x</math>)
* <math>x\otimes y :=x+y</math> (speziell <math>(-\infty)\otimes x=x\otimes(-\infty)=-\infty</math>).
Das neutrale Element bezüglich <math>\oplus</math> ist dabei <math>-\infty</math>, das bezüglich <math>\otimes</math> ist 0.
Diese Verwendung der Operationen Maximum und Addition motiviert auch die Bezeichnung ''Max-Plus-Algebra''.
Ein weiterer wichtiger idempotenter kommutativen Halbkörper ist <math>\R_\min:=(\R\cup\{+\infty\},\min,+,+\infty,0)</math>, er wird zum Teil als ''Min-Plus-Algebra'' bezeichnet.
Die folgenden Beispiele von Max-Plus-Algebren sind durchweg Max-Plus-Algebren über <math>\R_\max</math>:
* <math>\R_\max</math> selbst ist eine Max-Plus-Algebra.
* Die Menge <math>\R_\max^M</math> aller Abbildungen von einer festen Menge <math>M</math> nach <math>\R_\max</math> mit punktweiser Maximumbildung und Addition und Skalaroperation.
* Auf der Menge <math>\R_\max^\R</math> aller Abbildungen <math>f\colon\R\to\R_\max</math> kann man die erforderlichen Operationen wie folgt definieren:
*:<math>(f\oplus g)(x) = f(x)\oplus g(x) = \max\{f(x),g(x)\}</math> (punktweise Maximumbildung)
*:<math>(f\otimes g)(x) = \sup_{t\in\R}(f(t)+g(x-t))</math> (so genannte Supremumfaltung)
*:<math>(c\otimes f)(x) = c\otimes f(x) = c+f(x)</math>
: Allerdings ist <math>\R_\max^\R</math> 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 <math>M=\R</math> des vorhergehenden Beispiels unterscheidet.
* Die Menge <math>\R_\max^{n\times n}</math> aller <math>n\times n</math>-Matrizen mit Einträgen in <math>\R_\max</math>, wobei Addition und Multiplikation von Matrizen nach den üblichen Formeln, in denen jedoch <math>+</math> und <math>\cdot</math> durch <math>\oplus</math> und <math>\otimes</math> ersetzt sind, berechnet werden. Wie die gewöhnliche [[Matrixmultiplikation]] ist auch <math>\otimes</math> nicht [[Kommutativgesetz|kommutativ]].

== Literatur ==
* {{Literatur
|Autor=Peter Butkovič
|Titel=Max-linear Systems: Theory and Algorithms
|Sammelwerk=Springer Monographs in Mathematics
|Verlag=Springer-Verlag
|Jahr=2010
|DOI=10.1007/978-1-84996-299-5}}

== Weblinks ==
* [http://amadeus.inria.fr/gaubert/maxplus.html amadeus.inria.fr]

[[Kategorie:Algebra]]

Max-Plus-Algebra - Versionsgeschichte

imported>Xario: /* Weblinks */ http://maxplus.org/ maxplus.org entfernt, kann man nicht als excellent bezeichnen. veraltet, ungepflegt, kaum inhalt, viele tote links