Max Plus at Work – Modeling and Analysis of Synchronized Systems: A Course on Max–Plus Algebra and Its Applications: 48 (Princeton Series in Applied Mathematics) - Hardcover

Heidergott, Bernd; Olsder, Geert Jan; Van Der Woude, Jacob

Hardcover

ISBN 10: 0691117632 ISBN 13: 9780691117638

Publisher: Princeton University Press, 2005

Synopsis

Trains pull into a railroad station and must wait for each other before leaving again in order to let passengers change trains. How do mathematicians then calculate a railroad timetable that accurately reflects their comings and goings? One approach is to use max-plus algebra, a framework used to model Discrete Event Systems, which are well suited to describe the ordering and timing of events. This is the first textbook on max-plus algebra, providing a concise and self-contained introduction to the topic.


Applications of max-plus algebra abound in the world around us. Traffic systems, computer communication systems, production lines, and flows in networks are all based on discrete even systems, and thus can be conveniently described and analyzed by means of max-plus algebra.


The book consists of an introduction and thirteen chapters in three parts. Part One explores the introduction of max-plus algebra and of system descriptions based upon it. Part Two deals with a real application, namely the design of timetables for railway networks. Part Three examines various extensions, such as stochastic systems and min-max-plus systems. The text is suitable for last-year undergraduates in mathematics, and each chapter provides exercises, notes, and a reference section.

About this title

About the Author

Bernd Heidergott is Associate Professor of Mathematics and Statistics at Vrije Universiteit, Amsterdam. He is a research fellow of the Tinbergen Institute. Geert Jan Olsder is Professor of Mathematical System Theory and Deputy Vice-Chancellor at Delft University of Technology. Jacob van der Woude is Associate Professor of Mathematical System Theory at Delft University of Technology.

From the Back Cover

"Max Plus at Work is the best English textbook for learning eigenvector eigenvalues and the asymptotic regime of max-plus systems."--J. P. Quadrat, Director of Research, International Research Institute

"This book is very accessible, providing many examples and a clear road map for learning about max-plus algebra."--Bart De Schutter, Delft University of Technology

From the Inside Flap

"Max Plus at Work is the best English textbook for learning eigenvector eigenvalues and the asymptotic regime of max-plus systems."--J. P. Quadrat, Director of Research, International Research Institute

"This book is very accessible, providing many examples and a clear road map for learning about max-plus algebra."--Bart De Schutter, Delft University of Technology

Excerpt. © Reprinted by permission. All rights reserved.

Max Plus at Work

Modeling and Analysis of Synchronized Systems: A Course on Max-Plus Algebra and Its Applications

By Bernd Heidergott, Geert Jan Olsder, Jacob van der Woude

PRINCETON UNIVERSITY PRESS

Copyright © 2006 Princeton University Press
All rights reserved.

ISBN: 978-0-691-11763-8

Contents

Preface, ix, 
Chapter 0. Prolegomenon, 1, 
PART I. MAX-PLUS ALGEBRA, 11, 
Chapter 1. Max-Plus Algebra, 13, 
Chapter 2. Spectral Theory, 28, 
Chapter 3. Periodic Behavior and the Cycle-Time Vector, 47, 
Chapter 4. Asymptotic Qualitative Behavior, 72, 
Chapter 5. Numerical Procedures for Eigenvalues of Irreducible Matrices, 85, 
Chapter 6. A Numerical Procedure for Eigenvalues of Reducible Matrices, 95, 
PART II. TOOLS AND APPLICATIONS, 
Chapter 7. Petri Nets, 115, 
Chapter 8. The Dutch Railway System Captured in a Max-Plus Model, 126, 
Chapter 9. Delays, Stability Measures, and Results for the Whole Network, 140, 
Chapter 10. Capacity Assessment, 153, 
PART Ill. EXTENSIONS, 
Chapter 11. Stochastic Max-Plus Systems, 163, 
Chapter 12. Min-Max-Plus Systems and Beyond, 177, 
Chapter 13. Continuous and Synchronized Flows on Networks, 191, 
Bibliography, 201, 
List of Symbols, 206, 
Index, 209, 

CHAPTER 1

Max-Plus Algebra

In the previous chapter we described max-plus algebra in an informal way. The present chapter contains a more rigorous treatment of max-plus algebra. In Section 1.1 basic concepts are introduced, and algebraic properties of max-plus algebra are studied. Matrices and vectors over max-plus algebra are introduced in Section 1.2, and an important model, called heap of pieces or heap model, which can be described by means of max-plus algebra, is presented in Section 1.3. Finally, the projective space, a mathematical framework most convenient for studying limits, is introduced in Section 1.4.

1.1 BASIC CONCEPTS AND DEFINITIONS

Define [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], and denote by Rmax the set R [intersection] {ε}, where R is the set of real numbers. For elements a, b [member of] Rmax we define operations [direct sum] and [cross product] by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (1.1)

Clearly, max(a, -∞) = max(-∞, a) = a and a + (-∞) = -∞ + a = -∞, for any a [member of] Rmax, so that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (1.2)

for any a [member of] Rmax. The above definitions are illustrated with some numerical examples as follows:

5 [direct sum] 3 = max(5, 3) = 5,

5 [direct sum] ε = max(5, -∞) = 5,

5 [cross product] ε = 5 -∞ = -∞ = ε,

e [direct sum] 3 = max(0, 3) = 3,

5 [cross product] 3 = 5 + 3 = 8.

The set Rmax together with the operations [direct sum] and [cross product] is called max-plus algebra and is denoted by

Rmax = (Rmax, [direct sum], [cross product], ε,e).

As in conventional algebra, we simplify the notation by letting the operation [cross product] have priority over the operation [direct sum]. For example,

5 [cross product] -9 [direct sum] 7 [cross product] 1

has to be understood as

(5 [cross product] -9) [direct sum] (7 [cross product] 1).

Notice that (5 [cross product] -9) [direct sum] (7 [cross product] 1) = 8, whereas 5 [cross product] (-9 [direct sum] 7) [cross product] 1 = 13.

The operations [direct sum] and[cross product] defined in (1.1) have some interesting algebraic properties. For example, for x, y, z [member of] Rmax. it holds that

x [cross product] (y [direct sum] z) = x + max(y, z) = max(x + y,x + z) = (x [cross product] y) [direct sum] (x [cross product] z),

which in words means that [cross product] distributes over [direct sum]. Below we give a list of algebraic properties of max-plus algebra.

• Associativity:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

and

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

• Commutativity:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

• Distributivity of[cross product] over [direct sum]:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

• Existence of a zero element:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

• Existence of a unit element:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

• The zero is absorbing for [cross product]:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

• Idempotency of [direct sum]:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Powers are introduced in max-plus algebra in the natural way using the associative property. We denote the set of natural numbers including zero by N and define for x [member of] Rmax

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (1.3)

for all n [member of] N with n [not equal] 0, and for n = 0 we define [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Observe that x[cross product]n, for any n [member of] N, reads in conventional algebra as

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

For example,

5[cross product]3 = 3 × 5 = 15.

Inspired by this we similarly introduce negative powers of real numbers, as in

8[cross product]-2 = -2 x 8 = -16 = 16[cross product]-1,

for example. In the same vein, max-plus roots can be introduced as

x[cross product]α = α × x,

for α [member of] R. For example,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

and

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Continuing with the algebraic point of view, we show that max-plus algebra is an example of an algebraic structure, called a semiring, to be introduced next.

Definition 1.1A semiring is a nonempty set R endowed with two binary operations [direct sum]R and [cross product]R such that

• [direct sum]R is associative and commutative with zero element εR;

• [cross product]R is associative, distributes over [direct sum]R, and has unit element e R;

• εR is absorbing for [cross product]R.

Such a semiring is denoted by R = (R, [direct sum]R, [cross product]R, εR, eR). If [cross product]R is commutative, then R is called commutative, and if [direct sum]R is idempotent, then it is called idempotent.

Max-plus algebra is an example of a commutative and idempotent semiring. Are there other meaningful semirings? The answer is yes, and a few examples are listed below.

Example 1.1.1

• Identify [direct sum]R with conventional addition, denoted by +, and [cross product]R with conventional multiplication, denoted by x. Then the zero and unit element are εR = 0 and eR = 1, respectively. The object Rst = (R, +, ×, 0, 1) -the subscript st refers to "standard" -is an instance of a semiring over the real numbers. Since conventional multiplication is commutative, Rstis a commutative semiring. Note that Rstfails to be idempotent. However, as is well known, Rstis a ring and even a field with respect to the operations + and ×. See the notes section for some further remarks on semirings and rings.

• Min-plus algebra is defined as Rmin = (Rmin, [direct sum]', [cross product], ε', e), where Rmin = R [union] {+∞}, [cross product]' is the operation defined by a [cross product]' b [??] min(a,b) for all a, b [member of] Rmin, and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Note that Rminis an idempotent, commutative semiring.

• Consider Rmin,max = ([??], [direct sum]', [direct sum], ε' ε), with [??] = R [union] {ε, ε'}, and set ε[direct sum]ε' = ε' [direct sum] ε = ε'. Then Rmin,maxis an idempotent, commutative semiring. In the same vein, Rmax,min = ([??], [direct sum], [direct sum]', ε, ε') is an idempotent, commutative semiring provided that one defines ε [direct sum]' ε' = ε' [direct sum]' ε = ε.

• As a last example of a semiring of a somewhat different nature, let S be a nonempty set. Denote the set of all subsets of S by R; then (R, [union], [intersection], Ø, S), with Ø the empty set, and [union] and [intersection] the set-theoretic union and intersection, respectively, is a commutative, idempotent semiring. The same applies to (R, [union], [intersection], S, Ø).

The above list of examples explains why we choose an algebraic approach. Any statement that is proved for a semiring will immediately hold in any of the above algebras. Apart from the structural insight this provides into the relationship between the different algebras, the algebraic approach also saves a lot of work.

To illustrate this, consider the following problem. Is it possible to define inverse elements (i.e., inverse with respect to the [direct sum]R operation) in an idempotent semiring? For example, consider an idempotent semiring R = (R, [direct sum]R, [cross product]R, εR, eR), with JR. included in R, such as the max-plus or min-plus semiring. For example, is it possible to find a solution of

5 [direct sum]R x = 3? (1.4)

As in conventional algebra, it is tempting to subtract 5 on both sides of the above equation in order to obtain

x = 3 [direct sum]R ( -5)

as a solution. However, is it possible to give meaning to -5 in the above equation? Take, for example, max-plus algebra. Then, equation (1.4) reads

max(5, x) = 3. (1.5)

Obviously, there exists no number that makes equation (1.5) true. On the other hand, in min-plus algebra, equation (1.5) reads

min(5,x) = 3

and has the solution x = 3. Now interchange the numbers 3 and 5 in equation (1.4), yielding 3 [direct sum]Rx = 5. This equation has no solution in min-plus algebra and has the obvious solution x = 5 in max-plus algebra.

Whether an equation has a solution may depend on the algebra. This raises the question whether a particular semiring (i.e., a particular interpretation of the symbols [direct sum]R, [cross product]R, eR, and εR) exists such that all equations of type (1.4) can be solved. The following lemma provides an answer.

Lemma 1.2Let R = (R, [direct sum]R, [cross product]R, εR, eR) be a semiring. Idempotency of [direct sum]R implies that inverse elements with respect to [direct sum]Rdo not exist.

Proof. Suppose that a [not equal] εR had an inverse element with respect to [direct sum]R, say, b. In formula, this is

A [direct sum]R b = εR.

Adding a on both sides of the above equation yields

a [direct sum]R a [direct sum]R b = a [direct sum]R εR.

By idempotency, the left-hand side of the above equation equals a [direct sum]R b, whereas the right-hand side is equal to a. Hence, we have

a [direct sum]R b = a,

which contradicts a [direct sum]R b = εR..

Lemma 1.2 thus gives a negative answer to the above question, because no idempotent semiring exists for which negative numbers can be defined. Observe that this does not contradict the fact that Rst, defined in Example 1.1.1, is a semiring because Rst is not idempotent. The fact that we cannot subtract in an idempotent semiring explains why the methods encountered later, when studying max-plus algebra, will differ significantly from those in conventional algebra.

1.2 VECTORS AND MATRICES

In this section matrices over Rmax will be introduced. The set of n × m matrices with underlying max-plus algebra is denoted by [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. For n [member of] N with n [not equal] 0, define [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. The element of a matrix A [member of] [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] in row i and column j is denoted by aij, for i [member of] [??] and j [member of] [??] Matrix A can then be written

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Occasionally, the element aij will also be denoted as

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (1.6)

The sum of matrices A, B [member of] [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], denoted by A [direct sum] B, is defined by

[A [direct sum B]ij = aij [direct sum] bij

= max (aij, bij), (1.7)

for i [member of] [??] and j [member of] [??]. For example, let

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (1.8)

then [A [direct sum] B]11 = e [direct sum] -1 = max(0, -1) = 0 = e. Likewise, it follows that [A [direct sum] B]12 = ε [direct sum] 11 =max (-∞, 11) = 11, [A [direct sum] B]21 = 3 [direct sum] 1 = max(3, 1) = 3, and [A [direct sum] B]22 = 2 [direct sum] ε = max(2, -∞) = 2. In matrix notation,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Note that for A, B [member of] [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] it holds that A [direct sum] B = B [direct sum] A (see Exercise 4).

For A [member of] [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and α [member of] Rmax, the scalar multiple α [cross product] A is defined by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (1.9)

for i [member of] [??]and j [member of] [??]. For example, let A be defined as in (1.8) and take α = 2; then [2 [cross product] A]11 = 2 [cross product] e = 2 + 0 = 2. Likewise, it follows that [2 [cross product] A]12 = ε, [2 [cross product] A]21 = 5, and [2 [cross product] A]22 = 4, yielding, in matrix notation,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

For matrices A [member of] [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and B [member of] [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], the matrix product A [cross product] B is defined as

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (1.10)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

for i [member of] [??] and k [member of] [??]. This is just like in conventional algebra with + replaced by max and x by +. Notice that A [cross product] B [member of] [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], i.e., has n rows and m columns. For example, let A and B be defined as in (1.8); then the elements of A [cross product] B are given by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

and

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

yielding, in matrix notation,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Notice that the matrix product in general fails to be commutative. Indeed, for the above A and B

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Let E (n, m) denote the n × m matrix with all elements equal to ε, and denote by E(n, m) the n × m matrix defined by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

If n = m, then E(n, n) is called then n × n identity matrix. When their dimensions are clear from the context, ε(n, m) and E(n, m) will also be written as ε and E, respectively. It is easily checked (see exercise 5) that any matrix A [member of] [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] satisfies

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

(Continues...)

Excerpted from Max Plus at Work by Bernd Heidergott, Geert Jan Olsder, Jacob van der Woude. Copyright © 2006 Princeton University Press. Excerpted by permission of PRINCETON UNIVERSITY PRESS.
All rights reserved. No part of this excerpt may be reproduced or reprinted without permission in writing from the publisher.
Excerpts are provided by Dial-A-Book Inc. solely for the personal use of visitors to this web site.

Edition details

• Publisher: Princeton University Press
• Publication date: 2005
• Language: English
• ISBN 10: 0691117632
• ISBN 13: 9780691117638
• Binding: Hardcover
• Number of pages: 224