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

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

Hardcover

ISBN 10: 0691117632 ISBN 13: 9780691117638

Verlag: University Press Group, 2005

Inhaltsangabe

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.

Über diesen Titel

Über die Autorin bzw. den Autor

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.

Von der hinteren Coverseite

"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

Aus dem Klappentext

"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

Auszug. © Genehmigter Nachdruck. Alle Rechte vorbehalten.

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...

Details zur Ausgabe

• Verlag: University Press Group
• Erscheinungsdatum: 2005
• Sprache: Englisch
• ISBN 10: 0691117632
• ISBN 13: 9780691117638
• Einband: Gebundene Ausgabe
• Anzahl der Seiten: 226
• Kontakt zum Hersteller: preigu GmbH & Co. KG; mail@preigu.de; ; Lengericher Landstr. 19; Osnabrück; Niedersachsen; 49078; Deutschland