Max-Plus-Algebra

A Max Plus Agebra is a mathematical object that is similar to an algebra over the real numbers, but the body can be replaced operations: addition, by forming the maximum, the multiplication by the ordinary addition. In planning theory, as in the treatment of Petri nets, the theory of max-plus algebras allows the use of appropriate methods from linear algebra. Optimizing a roadmap can be considered, for example in this way as an eigenvalue problem.

Just as the term algebra denotes both a mathematical structure as well as a mathematical branch, sometimes you mean by max-plus algebra and the mathematical subspecialty that deals with the said structures.

Definition

A max-plus algebra is a semi- ring on which an idempotent commutative semi body with zero element in virtue of multiplication surgery. (For comparison: An algebra is a ring on which operates a body )

Specifically, this means that the following listed axioms are satisfied, each for all and.

Semiring

According to 1st and 2nd is commutative semigroup, under 3 is semigroup, 4th and 5th are the distributive laws.

Idempotent commutative half body

According to 1st - 5th is half-ring, according to the 6th and 7th are neutral elements and each of the links. Together with the existence of a multiplicative inverse elements, see 8 is therefore half body, in accordance with 9 ( multiplicative) (additive) is commutative and idempotent under 10.

Operation

The operation is to be the shortcuts or so in an obvious meadow tolerated.

Examples

In the following, the indices are omitted on the links, since in each case the context is clear what must be meant of the links for the sake of readability. The orbits de operators, however, are required to avoid confusion with the usual addition and multiplication.

The most important example of an idempotent commutative semi body is referred to and has as its underlying amount and the links

• ( special)
• ( specifically ).

The neutral element with respect to this case, that is with respect to 0, this use of the maximum and addition operations motivated the term max-plus algebra. Another important idempotent commutative semi body. The following examples of max-plus algebras are all max-plus algebras over:

• Itself is a max-plus algebra.
• The set of all mappings from a fixed quantity with pointwise addition and scalar and maximum generation.
• On the set of all mappings you can define the required operations as follows:   ( pointwise maximum generation )   ( so-called Supremumfaltung )

• The set of matrices with entries in, said addition and multiplication of matrices according to the normal formula, in which, however, are by and replaced, can be calculated. As the ordinary matrix multiplication is not commutative.