Besser als Mathe: Moderne angewandte Mathematik aus dem MATHEON zum Mitmachen 3834807338, 9783834807335 [PDF]

Zitiervorschau

Katja Biermann | Martin Grötschel | Brigitte Lutz-Westphal (Hrsg.) Besser als Mathe

Katja Biermann | Martin Grötschel | Brigitte Lutz-Westphal (Hrsg.)

Besser als Mathe Moderne angewandte Mathematik aus dem MATHEON zum Mitmachen Mit Illustrationen von Sonja Rörig POPULÄR

Bibliografische Information der Deutschen Nationalbibliothek Die Deutsche Nationalbibliothek verzeichnet diese Publikation in der Deutschen Nationalbibliografie; detaillierte bibliografische Daten sind im Internet über abrufbar. Katja Biermann Technische Universität Berlin Institut für Mathematik Straße des 17. Juni 135 10623 Berlin E-Mail: [email protected] Professor Dr. Dr. h.c. mult. Martin Grötschel Konrad-Zuse-Zentrum für Informationstechnik Berlin (ZIB) Takustraße 7 14195 Berlin E-Mail: [email protected] Professor Dr. Brigitte Lutz-Westphal Freie Universität Berlin Institut für Mathematik Königin-Luise-Str. 24-26 14195 Berlin E-Mail: [email protected] 1. Auflage 2010 Alle Rechte vorbehalten © Vieweg+Teubner |GWV Fachverlage GmbH, Wiesbaden 2010 Lektorat: Ulrike Schmickler-Hirzebruch | Nastassja Vanselow Vieweg+Teubner ist Teil der Fachverlagsgruppe Springer Science+Business Media. www.viewegteubner.de Das Werk einschließlich aller seiner Teile ist urheberrechtlich geschützt. Jede Verwertung außerhalb der engen Grenzen des Urheberrechtsgesetzes ist ohne Zustimmung des Verlags unzulässig und strafbar. Das gilt insbesondere für Vervielfältigungen, Übersetzungen, Mikroverfilmungen und die Einspeicherung und Verarbeitung in elektronischen Systemen. Die Wiedergabe von Gebrauchsnamen, Handelsnamen, Warenbezeichnungen usw. in diesem Werk berechtigt auch ohne besondere Kennzeichnung nicht zu der Annahme, dass solche Namen im Sinne der Warenzeichen- und Markenschutz-Gesetzgebung als frei zu betrachten wären und daher von jedermann benutzt werden dürften. Layout und Satz: Christoph Eyrich, Berlin Umschlaggestaltung: KünkelLopka Medienentwicklung, Heidelberg Druck und buchbinderische Verarbeitung: MercedesDruck, Berlin Gedruckt auf säurefreiem und chlorfrei gebleichtem Papier. Printed in Germany ISBN 978-3-8348-0733-5

Vorwort

Liebe Leserin, lieber Leser, Mathematik ist überall, sie ist jedoch meistens unsichtbar. Dieses Buch will die Augen öffnen für „den mathematischen Blick auf die Welt“. Ausgehend von praktischen Fragestellungen nehmen wir Sie mit auf eine Entdeckungsreise zu mathematischen Herausforderungen. Diese sind als Aufgaben formuliert, die für jeden verständlich sind. Die Aufgaben stammen aus den sehr erfolgreichen mathematischen Adventskalendern (www.mathekalender.de), die das DFGForschungszentrum Matheon „Mathematik für Schlüsseltechnologien“ in Berlin seit 2004 jährlich für die Klassenstufen 9–13 und viele andere Mathematikinteressierte veranstaltet. Hierbei wird im Dezember täglich eine Aufgabe freigeschaltet, die einen Aspekt der aktuellen Forschung des Matheon zugänglich macht. Dieser Wettbewerb hatte in den letzten Jahren jeweils fast 10 000 Teilnehmerinnen und Teilnehmer, die mit großem Vergnügen jeden Abend neue Aufgaben lösten. Der erstaunliche Erfolg des Mathekalenders bei Jung und Alt war der Anlass, die besten Aufgaben neu zu formulieren, mit ausführlichen Erklärungen zu dem jeweiligen Praxisbezug zu versehen und in diesem Buch zu veröffentlichen. Besser als Mathe. „Besser als Mathe“ war die Fragebogenantwort eines Schülers der 8. Klasse nach einer Unterrichtseinheit zur Optimierung von Telefonnetzen.1 Diese positive Überraschung über eine Art von Mathematik, die etwas mit der Lebenswelt und dem Alltagsgeschehen zu tun hat, wollen wir mit diesem Buch weitertragen.

1. Unterrichtsversuch im Wildermuth-Gymnasium Tübingen, 2002, im Rahmen des von der Volkswagenstiftung geförderten Matheon-Projekts „Diskrete Mathematik für die Schule“ (Leitung und Durchführung: Martin Grötschel und Brigitte Lutz-Westphal)

v

Vorwort

Wir möchten es ermöglichen, in Unterricht, Studium oder Freizeit häufiger einen Blick auf aktuelle Forschungsfragen und Anwendungen der Mathematik zu werfen und dazu anregen, dies auch zu tun. Das Besondere an dieser Aufgabensammlung ist, dass alle Aufgaben direkt aus der forschenden Tätigkeit der Autorinnen und Autoren entstanden sind. Sie spiegeln somit unmittelbar wieder, womit sich mathematische Forschung derzeit beschäftigt. Sie zeigen einen authentischen Ausschnitt aus der aktuellen angewandten Mathematik. Diese Aufgaben machen auch deutlich, dass in der Mathematik keinesfalls bereits alles erforscht ist. Mathematik ist ein sehr lebendiges Forschungsfeld. Daran können Sie in diesem Buch teilhaben! Für wen ist das Buch? Dieses Buch soll neugierig machen auf angewandte Mathematik. Es soll zeigen, wo sich Mathematik in unserem Leben verbirgt, und es soll diese Mathematik erfahrbar machen. Daher richtet sich das Buch an eine breite Leserschaft, angefangen von Jugendlichen ab der 9. Klasse über interessierte Erwachsene bis hin zu Lehrenden an Sekundarstufen, Hochschulen und Universitäten. Dieses Buch nutzen. Man kann das Buch auf zweierlei Weise nutzen: Als Herausforderung zum selbstständigen Lösen der Aufgaben oder als Lesebuch zur angewandten Mathematik, je nachdem, ob man sich selbst auf die Suche nach eigenen Lösungsansätzen macht, oder ob man die Lösungen als Lehrstücke und Anregungen für die Anwendung von Mathematik liest. Wie in den Adventskalendern üblich, gibt es für jede Aufgabe verschiedene Antwortmöglichkeiten zur Auswahl. Dort verbergen sich häufig schon Hinweise auf einen Lösungsansatz. Alle Aufgaben sind als Problemlösungsaufgaben konzipiert, deren Bearbeitung vielfältige mathematische Kompetenzen fördert und gleichzeitig Anwendungskenntnisse vermittelt. Das Buch ist in sieben Kapitel gegliedert, die sich jeweils mit einem Thema aus der Lebenswelt beschäftigen. Das letzte Kapitel ist ein „Bonuskapitel“ mit Aufgaben, die einen sehr kurzen Auf-

vi

Vorwort

gabentext haben. Wir haben die Aufgaben bezüglich ihres Anwendungskontextes gruppiert. In jedem Kapitel erschließen sich dadurch vielfältige mathematische Sichtweisen und Methoden. Unterschiedlichste mathematische Fachgebiete kommen bei den Lösungen zum Tragen. Damit eignet sich diese Aufgabensammlung auch für projektartigen Unterricht in den Sekundarstufen. Beispielsweise kann das Kapitel „Mathematik im menschlichen Körper“ für ein fächerübergreifendes Projekt mit dem Biologieunterricht genutzt werden. Dank. Die Entstehung dieses Buches ist das Ergebnis einer Zusammenarbeit Vieler. Erhard Zorn hatte die Idee zum mathematischen Adventskalender. Zusammen mit Sabina Jeschke und Christine von Renesse hat er die Urform dieses Wettbewerbs für Ingenieurstudenten der TU Berlin entwickelt. Aus dieser ist dann der jetzige Adventskalender hervorgegangen. Ihnen gebührt ein besonderer Dank. Wir danken all jenen, die an den Adventskalendern und an diesem Buch mitgewirkt haben. Es sind dies so viele Personen aus den Trägerinstitutionen des DFG-Forschungszentrums Matheon (Freie Universität Berlin, Humboldt-Universität zu Berlin, Technische Universität Berlin, Weierstraß-Institut Berlin und Zuse-Institut Berlin), dass wir sie hier nicht alle nennen können. Wir möchten jedoch den Einsatz der an das Matheon abgeordneten Lehrerinnen und Lehrer besonders erwähnen, die Jahr für Jahr die redaktionelle Arbeit des Adventskalenderteams unterstützen. Berlin, im Oktober 2009

Katja Biermann Martin Grötschel Brigitte Lutz-Westphal

vii

Inhalt

Vorwort

v

Mathematik ganz freizeitlich Musik einpacken 3 Andreas Loos Zum Glück gibt es Garantie! Volker Mehrmann

9

Molekülbillard 17 Martin Weiser Stein–Schere–Papier 23 Boris Springborn

Mathematik in Bewegung Katz und Maus 29 Peter Deuflhard und Anton Schiela Zugfahrt nach Berlin 41 Christian Liebchen Zuschauer beim Berlin-Marathon 53 Stefan Hougardy, Stefan Kirchner und Mariano Zelke Die gelben Engel von Noehtam Jörg Rambau

ix

59

Mathematik komplett technologisch Wie viel Kapazität hat ein Mobilfunknetz? 77 Andreas Eisenblätter und Hans-Florian Geerdes Wie Rechner rechnen 87 René Lamour und Caren Tischendorf Wann geht der Laser an? 93 Mark Lichtner und Lutz Recke

Mathematik ganz zufällig Der Forsch-Frosch Fred Volker Kaibel

101

Keller oder Dach zuerst? Nicole Megow

111

Viele Tests – viele Fehler? Karsten Tabelow

117

Karamell und Schokolade optimal Andreas Eichhorn

121

Mathematik in Produktion und Logistik Roboter und Zuckerstangen Heike Siebert Die Welt des Herrn Kuhn Daniela Kern

131

141

Arvin, Berit und die Lastwagen 151 Falk Ebert und Anita Liebenau

x

Lagenwechsel minimieren – oder das Bohren von Löchern in Leiterplatten 161 Martin Grötschel, Thorsten Koch und Nam D˜ ung Hoàng

Mathematik gegen Bankrott Die Paketversicherung von MathPost Peggy Daume

175

Ein Kredit für Weihnachtsbaumkugeln Sina Tutsch

183

Optionsbewertung 187 John Schoenmakers

Mathematik im menschlichen Körper Das morgendliche Brückenritual Oliver Sander

195

Die Schokoladen-Diät 205 Matthias Ehrhardt Von Bakterien und Antibiotika 213 Alexander Bockmayr und Abdelhalim Larhlimi Das DNA-Puzzle 219 Stefan Kirchner Die kalte Zunge 227 Sören Bartels und Rüdiger Müller

xi

Mathematik auf die Schnelle Knoten 239 John M. Sullivan Dachkunst 243 Ulrich Reitebuch und Christian Schulz 102009 ? 249 Serhiy Yanchuk und Leonhard Lücken

Stichwortverzeichnis

253

Die Autorinnen und Autoren

xii

257

Mathematik ganz freizeitlich

Musik einpacken Andreas Loos

Wer schon einmal Nudeln selbst gemacht hat, der weiß: Frische Pasta kann ganz schön pappen. Das ist ein Problem für die Nudelindustrie, denn es ist nicht leicht, mit unregelmäßigen und klebrigen Nudel-Klumpen 500-Gramm-Beutel genau zu füllen. Einige Hersteller verwenden daher „Teilmengenwaagen“. Die besitzen bis zu hundert kleine Waagschalen, die über ein Förderband mit jeweils ungefähr 50 Gramm Nudel-Klumpen befüllt werden. Dann kommt Mathematik ins Spiel: Ein Computer wählt die zehn Waagschalen aus, deren Inhalt zusammen die 500 Gramm genau erreicht, und leert sie in einen Beutel aus. Mathematiker nennen das Problem, das der Computer dabei am laufenden Band löst, ein Subset-Sum-Problem („Summe aus Teilmengen“). Die Aufgabe besteht im Kern darin, in einer gegebenen Menge von Zahlen diejenigen Zahlen herauszusuchen, die aufsummiert genau eine gegebene Zahl ergeben. Mal ein Beispiel: Nehmen wir an, die gegebene Menge M enthält alle Primzahlen zwischen 1 und 100, also M := {1 < i < 100 | i ist prim.} Welche Untermenge bildet genau die Summe 100? Es gibt mehrere Lösungen; eine Möglichkeit wäre zum Beispiel 97 + 3 = 100. Doch wir können auch Wünsche äußern – zum Beispiel kann es manchmal praktisch sein, dass so viele Summanden wie möglich in der Summe vorkommen. Die (beweisbar) beste Lösung ist dann: 2 + 3 + 5 + 7 + 11 + 13 + 17 + 19 + 23 = 100. Mathematiker sortieren die Subset-Sum-Probleme in eine allgemeinere Klasse von Problemen ein, die sie Knapsack-Probleme getauft haben. Das Wort kommt aus dem Mittelalter; Knappen waren damals sozusagen Ritter in Ausbildung. Wenn sie etwas transpor-

3

Mathematik ganz freizeitlich

Abbildung 1. Nicht nur Nudeln werden mit „Subset-Sum“-Waagen gewogen, sondern auch zum Beispiel Salzstangen (Bild: Ishida Europe).

tieren mussten, dann packten sie es in ihren Knappsack, eine Art Rucksack. Und das Knapsack-Problem – ein „p“ ging in den Jahrhunderten verloren – hat tatsächlich mit Rucksäcken zu tun: Es besteht darin, einen Rucksack bestmöglich zu packen. Man kann sich vorstellen, der Knappe soll eine ganze Reihe von Dosen, Schachteln und Kistchen transportieren. Jeder Gegenstand wiegt etwas und hat einen bestimmten Wert. Doch der Knappe kann natürlich nur ein bestimmtes Gesamtgewicht schleppen – den Rest muss er zum Beispiel in eine Pferdetasche stecken und dem Pferd überlassen. Hier ist der Unterschied zum Subset-Sum-Problem: Beim Knapsack-Problem kommt es nicht darauf an, genau das Zielgewicht zu treffen.

4

Musik einpacken

Was packt der Knappe am Besten in den Knappsack? Klar, die wertvollsten Dinge. Doch es kann klug sein, einen großen, wertvollen Gegenstand dem Pferd zu überlassen, um den Platz im Knappsack mit kleinen – für sich genommen nicht so wertvollen – Gegenständen besser ausfüllen zu können. Unter Umständen steckt dann am Ende in der Summe mehr Wert im Knappsack. Knapsack-Probleme sind einfach zu formulieren, aber in der Regel schwierig zu lösen. Mehrere dicke Bücher wurden allein in den letzten 15 Jahren über das Knapsack-Problem und seine Varianten geschrieben. Denn obwohl der Nudel-Computer die Lösung des Subset-Sum-Problems an der Nudelwaage innerhalb weniger Millisekunden ausrechnet, sind Knapsack-Probleme im Allgemeinen schwer zu knacken. Genauer: Sie gehören zu einer Problemklasse, die Mathematiker N P nennen. Zur Lösung solcher Probleme sind derzeit nur Algorithmen bekannt, die zwar bei kleinen Beispielen noch ganz gut funktionieren; bei großen Problemen aber explodiert die Rechenzeit. Ein Knapsack-Problem zum Selberknacken ist das folgende: Man hat auf einen MP3-Player eine Anzahl Songs kopiert, und nur noch 39,2 Megabyte Platz. Die in Tabelle 1 aufgeführten Lieblingslieder liegen noch auf dem Rechner: Auf jeden Fall will man von jedem Lied eine Version auf dem Player haben; wenn zwei Fassungen existieren, dann bevorzugen wir aber die besondere. Wie viele Lieder in besonderer Version kann man unter diesen Umständen höchstens auf den Player kopieren?

Antwortmöglichkeiten

1. 2. 3. 4. 5.

keinen 1 Song 2 Songs 3 Songs 4 Songs

6. 7. 8. 9. 10.

5

5 Songs 6 Songs 7 Songs 8 Songs 9 Songs

Mathematik ganz freizeitlich Tabelle 1. Lieblingslieder

s1 s1 s2 s2 s3 s3 s4 s5 s5 s6 s6 s7 s7 s8 s8 s9 s10  s10 s11  s11

Jingle Bells (standard version) Jingle Bells (80’s Disco remix) Rudolph the reindeer (standard version) Rudolph the reindeer (trance version) Oh du fröhliche (standard version) Oh du fröhliche (techno version) Vom Himmel hoch (standard version) In dulci jubilo (standard version) In dulci jubilo (Latino-Salsa Remix) Oh Tannenbaum (standard version) Oh Tannenbaum (mit 12 Minuten Gitarrensolo) Stille Nacht (standard version) Stille Nacht (gesungen vom Chor der Engel) Morgen, Kinder, wird’s was geben (standard version) Morgen, Kinder, wird’s was geben (unplugged version) Little drummer boy (standard version) Süßer die Glocken (standard version) Süßer die Glocken (House remix) Es kommt ein Schiff geladen (standard version) Es kommt ein Schiff geladen (phunky-phunky)

6

3,1 MByte 5,3 MByte 3,1 MByte 7,3 MByte 2,3 MByte 3,4 MByte 3 MByte 3 MByte 6 MByte 3 MByte 8 MByte 2,5 MByte 8,6 MByte 2,5 MByte 8,7 MByte 6 MByte 2,1 MByte 5,5 MByte 1,1 MByte 5,3 MByte

Musik einpacken

Lösung (Richtige Lösung: Antwort 4) Sei c = 39, 2 MByte die Restkapazität des mp3-Players. Wir legen fest: s4 := 3 und s9 := 6. (Um die Sache nicht noch komplizierter zu machen, tun wir ganz einfach so, als ob die beiden Songs s4 und s9 besondere Versionen hätten, die genauso lang wie die normalen Versionen sind, und bedenken das dann bei der Lösung.) Eine kurze Rechnung zeigt: 11

11

i =1

i =1

∑ si = 31,7 MByte < c = 39,2 MByte < ∑ si = 67,1 MByte.

Daher bekommen wir auf jeden Fall alle Standardversionen unter, alle besonderen Versionen (plus die zwei Lieder, die nur in Standardversion existieren) aber nicht. Welche Standardversionen kann man also durch besondere Versionen ersetzen? Hier wendet man einen Trick an: Man kann aus den Angaben, ob ein Gegenstand in den Knapsack gepackt wird oder nicht, einen 0/1-Vektor basteln – wenn xi = 1 ist, dann wird der i-te Gegenstand eingepackt, bei xi = 0 nicht. Wenn man mit G nun das zulässige Höchstgewicht, gi die Einzelgewichte, wi die Werte der Gegenstände sind und n deren Anzahl bezeichnet, dann kann man das Problem auch so beschreiben: n

Maximiere

∑ xi wi unter Berücksichtigung von

i =1

n

∑ xi gi ≤ G, wobei xi ∈ {0, 1}.

i =1

Soll heißen: Wir maximieren den Wert, wobei die Summe über die Gewichte der mitgenommenen Gegenstände G nicht überschreiten darf. Die xi kann man sich wie Schalter vorstellen, die den jeweiligen Gegenstand ein- oder ausschalten. Geometrisch beschreiben diese Formeln einen Körper in einem n-dimensionalen Raum, das

7

Mathematik ganz freizeitlich

sogenannte 0-1-Knapsack-Polytop. Die Lösungen des Problems, also die möglichen Vektoren x, sind die Ecken dieses Körpers. Genau das machen wir nun auch beim Musikpacken. Wir erzeugen einen Vektor δ mit Einträgen δi := si − si : δ = (2,2; 4,2; 1,1; 0; 3; 5; 6,1; 6,2; 0; 3,4; 4,2). Damit ist folgendes Knapsack-Problem zu lösen (der Wert der Gegenstände beträgt wi = 1 für alle i): 11

Maximiere

∑ xi unter Berücksichtigung von

i =1 11

∑ δi xi ≤ 39,2 − 31,7 MByte = 7,5 MByte,

i =1

wobei xi ∈ {0, 1}.

In der Praxis weicht man – besonders bei großen Problemfällen – auf Näherungslösungen aus. Oft reicht ein Greedy-Algorithmus („greedy“ heißt „gierig“). Man berechnet für jeden Gegenstand den Gewinn pro Gewichtseinheit und verpackt anschließend erst den Gegenstand mit dem größten Quotienten, dann den mit dem zweigrößten Quotienten und so weiter – bis der Knapsack voll ist. Theoretisch kann man aber stets auch exakte Lösungen bestimmen, zum Beispiel mit einem Algorithmus, der auf Dynamischer Programmierung basiert. In unserem Fall liefert der Greedy-Algorithmus die Lösung: Man sortiert die δi aufsteigend nach Größe und wählt die ersten k Songs, bis der verfügbare Speicherplatz aufgebraucht ist. Das ergibt folgenden Lösungsvektor: x = (1; 0; 1; 1; 1; 0; 0; 0; 1; 0; 0). Das bedeutet: Wir tauschen Song Nummer 1, 3, 4, 5 und 9. (Genau genommen darf man dem Greedy-Algorithmus nicht trauen, doch man sieht zum Beispiel beim Durchprobieren, dass es keine Lösung mit mehr Songs gibt.) Da es für i = 4 und i = 9 keine besonderen Fassungen gibt, kann man also drei Standard-Songs gegen besondere Songs austauschen.

8

Zum Glück gibt es Garantie! Volker Mehrmann

Die numerische Lösung von Gleichungssystemen ist eine zentrale Aufgabe bei der Untersuchung fast jeden wissenschaftlichen Problems. Die Beschreibung physikalischer, chemischer oder biologischer Prozesse erfolgt im Wesentlichen immer durch Systeme von Gleichungen. Diese können aus Differentialgleichungen oder auch algebraischen Gleichungen bestehen. Lösungsverfahren dieser Systeme führen jedoch meist auf das Lösen von sehr großen linearen Gleichungssystemen. Daher ist es notwendig Methoden zu entwickeln um diese linearen Gleichungssysteme effizient zu lösen. Im Mathematikunterricht in der Schule werden üblicherweise zwei Gleichungen mit zwei Unbekannten (oder auch gelegentlich drei Gleichungen mit drei Unbekannten) gelöst, wie beispielsweise 2x + 2y = 2, 3x − 3y = 0. Solche Gleichungssysteme kann man meist mit Papier und Bleistift einfach und exakt lösen. In der industriellen und wissenschaftlichen Praxis sind jedoch heute Systeme mit 10 Millionen Gleichungen und Unbekannten keine Seltenheit mehr. Diese kann man natürlich nicht mehr mit der Hand lösen und verwendet daher numerische Algorithmen (Berechnungsvorschriften) auf Computern. Bei der Lösung mit Hilfe von Rechnern gibt es allerdings das Problem, dass ein Rechner immer nur mit endlich vielen Dezimalstellen rechnen kann, das sind zum Beispiel 8, 16 oder 32 Stellen, je nach verwendeter Rechnerarchitektur bei PCs oder 13 Stellen bei vielen Taschenrechnern. Das bedeutet, dass die Ergebnisse und Ausgangszahlen auf diese Stellenzahl gerundet werden müssen und so mit Fehlern behaftet sein können. Bei einem Weiterrechnen können

9

Mathematik ganz freizeitlich

sich diese vielen kleinen Fehler zu sehr großen Fehlern aufsummieren. Daher stellt sich dann die Frage ob die berechneten Ergebnisse überhaupt einigermaßen korrekt sind. Wenn dieser Effekt, dass sich Fehler aufschaukeln, bei einer numerischen Methode auftritt, so nennt man die Methode numerisch instabil, ansonsten stabil. Es ist also eine wichtige Aufgabe der Mathematik numerisch stabile Algorithmen zur Lösung realer Praxisprobleme zu entwickeln. Dazu kommt in der Praxis noch ein weiteres Problem: Die Lösung des Gleichungssystems kann sehr empfindlich von kleinen Änderungen in den Ausgangsdaten abhängen. Das bedeutet auch wenn man mit sehr vielen Stellen rechnet, kann das Ergebnis vollkommen falsch werden. Probleme, bei deren Berechnung auf dem Rechner selbst bei der Verwendung von numerisch stabilen Algorithmen viele oder alle Stellen verloren gehen, nennt man schlecht konditioniert. Um den Ergebnissen trauen zu können ist es ist daher auch wichtig, solche schlecht konditionierten Probleme zu erkennen, und, wenn möglich, etwas gegen die schlechte Kondition zu tun. Man entwickelt sogenannte auf das Problem angepasste Präkonditionierer. Dies ist eine weitere wichtige Aufgabe der Numerischen Mathematik. Ein sehr einfaches Beispiel, das die genannte Problematik verdeutlicht, ist das Gleichungssystem 888 445 x + 887 112 y = 1, 887 112 x + 885 781 y = 0. Die exakte Lösung ist x = 885 781,

y = −887 112.

Das Standardverfahren, das auch häufig in der Praxis verwendet wird, liefert (mit 16 Stellen Genauigkeit gerechnet) x = 885 803,836,

y = −887 134,8704,

d. h. es stimmen für x also gerade mal 3 Stellen. Zum Warmwerden könnt ihr das Ergebnis einmal mit dem Taschenrechner berechnen.

10

Zum Glück gibt es Garantie

Auch in der folgenden Aufgabe geht es darum, zu überprüfen, ob das gegebene Problem schlecht konditioniert ist. Ein Warenhaus ordert regelmäßig elektronisches Spielzeug bei einer Herstellungsfirma. Da dieses oft fehlerhaft ist, können die Waren zurückgegeben werden. Am 1. März bestellt das Warenhaus 4 Playstations, 1048 Gameboyspiele und 11 040 000 Tamagotchis. Die Kosten belaufen sich auf 44 274 140 Euro. Am 2. März gibt das Warenhaus 2 Playstations, 504 Gameboyspiele und 5 350 000 Tamagotchis wegen Defekt zurück und erhält eine Rückzahlung von 21 455 010 Euro. Am 3. März bestellt das Warenhaus 503 neue Gameboyspiele und 504 000 Tamagotchis. Die Rechnung beträgt 2 067 809 Euro. Um die Rechnung zu prüfen und kalkulieren zu können, will der Einkäufer die Preise der einzelnen Waren (mit dem GaußschenEliminationsverfahren) berechnen. a. Was kostet eine Playstation (P), ein Gameboyspiel (G) und ein Tamagotchi (T) (in vollen Euro)? b. Leider ist der Taschenrechner des Einkäufers defekt, so dass er die Rechnung im Kopf überschlagen muss. Er kann es nur im Kopf ausrechnen, wenn er die Zahlen und Ergebnisse rundet. Dabei geht er wie folgt vor: ◦ Er stellt alle Zahlen in der Form 0, xyz · 10 j mit j ∈ Z = {. . . − 4, −3, −2, −1, 0, 1, 2, 3, 4 . . . } dar. ◦ Er rundet dann auf die zweite Nachkommastelle nach den üblichen Rundungsregeln. Er betrachtet dazu nur die dritte Nachkommastelle. (Im mathematischen heißt dies, man rundet auf zwei gültige Stellen.) Beispiele: 13 445 = 0,13445 · 105 ≈ 0,13 · 105 = 13 000 0,00555 = 0,555 · 10−2 ≈ 0,56 · 10−2 = 0,0056.

11

Mathematik ganz freizeitlich

Was erhält der Einkäufer bei dieser Rechnung als Kosten für eine Playstation, ein Gameboyspiel und ein Tamagotchi (in vollen Euro)?

Antwortmöglichkeiten (1) (2) (3) (4) (5) (6) (7) (8) (9) (10)

a. b. a. b. a. b. a. b. a. b. a. b. a. b. a. b. a. b. a. b.

P = 9.993.144 Euro, G = 4236 Euro und T = 0 Euro P = −19.786.667 Euro, G = −7734 Euro und T = 12 Euro P = 1549 Euro, G = 103 Euro und T = 4 Euro P = 9.083.333 Euro, G = 2700 Euro und T = 1 Euro P = 1179 Euro, G = 97 Euro und T = 4 Euro P = 15.050.000 Euro, G = −5800 Euro und T = -10 Euro P = −24 Euro, G = 102 Euro und T = 4 Euro P = 1 =179 Euro, G = 97 Euro und T = 4 Euro P = 1179 Euro, G = 97 Euro und T = 4 Euro P = 9.083.333 Euro, G = 2667 Euro und T = 0 Euro P = 1549 Euro, G = 103 Euro und T = 4 Euro P = 1549 Euro, G = 103 Euro und T = 4 Euro P = −24 Euro, G = 102 Euro und T = 4 Euro P = −20.004.590 Euro, G = 8909 Euro und T = 12 Euro P = 9993 Euro, G = 4 236 Euro und T = 0 Euro P = −24 Euro, G = 102 Euros und T = 4 Euro P = 1549 Euro, G = 103 Euro und T = 4 Euro P = −15.050.000 Euro, G = −5800 Euro und T = 10 Euro P = 9.993.144 Euro, G = 4236 Euro und T = 0 Euro P = 19.786.667 Euro, G = 7734 Euro und T = 12 Euro

12

Zum Glück gibt es Garantie

Lösung (Richtige Lösung: Antwort 9) (a) Die Einkäufe des ersten Tages können wie folgt geschrieben werden: 4 · P + 1 048 · G + 11 040 000 · T = 44 274 140 Von Tag 2 und 3 so:

−2 · P − 504 · G − 5 350 000 = −21 455 010 0 · P + 503 · G + 504 000 · T = 2 067 809 Gesamt gesehen gibt dies folgendes Gleichungssystem 4 · P + 1 048 · G + 11 040 000 · T = 44 274 140

−2 · P − 504 · G − 5 350 000 · T = −21 455 010 0 · P + 503 · G + 504 000 · T = 2 067 809 und kann als erweitere Koeffizientenmatrix geschrieben werden: 4 1 048 11 040 000 −2 −504 −5 350 000 0 503 504 000

44 274 140 −21 455 010 2 067 809

Mittels des Gaußschen Eliminationsverfahren formen wir wie folgt um: 1. Die erste Zeile multipliziert mit 12 auf die zweite Zeile addieren: 4 0 0

1 048 20 503

11 040 000 170 000 504 000

44 274 140 682 060 2 067 809

2. Die zweite Zeile multipliziert mit 503 20 von der dritten Zeile abziehen: 44 274 140 4 1 048 11 040 000 682 060 0 20 170 000 0 0 −3 771 500 −15 086 000

13

Mathematik ganz freizeitlich

Jetzt haben wir schon Dreiecksform und können die Warenpreise ausrechnen. Aus der letzten Zeile berechnen wir: T=

−15 086 000 =4 −3 771 500

Eingesetzt in die zweite Gleichung erhalten wir: G=

682 060 − (170 000 · 4) = 103 20

G und T eingesetzt in die erste Gleichung ergibt: P=

44 274 140 − (11 040 000 · 4 + 1 048 · 103) = 1 549 4

Somit kostet eine Playstation 1 549 Euro, 103 Euro kostet ein Gameboyspiel und 4 Euro ein Tamagotchi. (b) Unsere erweiterte Koeffizientenmatrix heißt jetzt: 4 1 000 11 000 000 −2 −500 −5 400 000 0 500 500 000

44 000 000 −21 000 000 2 100 000

Mittels des Gaußschen Eliminationsverfahren formen wir wie folgt um: 1. Die erste Zeile multipliziert mit 12 auf die zweite Zeile addieren: 4 0 0

1 000 0 500

11 000 000 100 000 500 000

44 000 000 1 000 000 2 100 000

2. Mit Vertauschung von Zeile 2 und 3 haben wir schon Dreiecksform: 4 1 000 11 000 000 44 000 000 2 100 000 0 500 500 000 0 0 100 000 1 000 000

14

Zum Glück gibt es Garantie

Aus der letzten Zeile berechnen wir: T=

1 000 000 = 10 100 000

Aus der zweiten Gleichung können wir berechnen: G=

2 100 000 − 500 000 · 10 = −5800 500

Und noch in die erste Gleichung eingesetzt erhalten wir: P=

44 000 000 − (11 000 000 · 10 + 1 000 · −5800 = −15 050 000 4

Mittels des Gaußschen Eliminationsverfahrens erhalten wir die folgende Lösung: Der Einkäufer bekommt 15 050 000 Euro, wenn er eine Playstation kauft, 5 800 Euro, wenn er ein Gameboyspiel kauft und er zahlt 10 Euro, wenn er ein Tamagotchi kauft. Das einfache Runden auf zwei gültige Stellen führt also zu vollkommen falschen Resultaten. Dieses Problem ist offenbar schlecht konditioniert.

15

Molekülbillard Martin Weiser

Die Entwicklung moderner Medikamente (siehe Abbildung 1) zielt auf das Design von hochspezifischen Wirkstoffen, um Nebenwirkungen so weit wie möglich auszuschließen. Da biochemische Reaktionen, z. B. die Blockade eines Rezeptors durch ein Wirkstoffmolekül, zumeist nach dem Schlüssel-Schloss-Prinzip funktionieren, ist die Gestalt von Molekülen entscheidend für die Wirksamkeit. Biochemische Tests oder gar klinische Studien sind aufwändig und teuer, daher werden zunehmend mathematische Simulationsverfahren zur Berechnung der Gestalt von Molekülen verwendet. Moleküle, insbesondere große Biomoleküle wie Proteine, mit hunderten oder tausenden von Atomen, sind keine starren Gebilde. Die einzelnen Atome in einem Molekül verhalten sich im wesentlichen wie Massepunkte in der Newtonschen Mechanik (Kraft ist Masse mal Beschleunigung: F = m · a), wobei zwischen je zwei Atomen entfernungsabhängige anziehende oder abstoßende Kräfte wirken. Insbesondere stoßen die Atome sich gegenseitig ab, wenn sie einander zu nahe kommen – ganz ähnlich wie Billardkugeln. Zwischen ihren Bindungspartnern schwingen die Atome schnell hin und her, wobei die Schwingungsperiode bei wenigen Femtosekunden (10−15 s) liegt. Viel langsamer, im Bereich von Millisekunden, führt die ständige atomare Bewegung aber auch zum Drehen oder Umklappen von ganzen Molekülteilen, was sich deutlich auf die Gestalt des Moleküls auswirken kann. Die verschiedenen Formen, die ein Molekül auf diese Weise annehmen kann, werden Konformationen genannt (siehe Abbildung 2) Für den Entwurf von neuen Medikamenten ist es wichtig, berechnen zu können, in welcher Konformation die gewünschte Reaktion abläuft und wie wahrscheinlich es ist, dass das Wirkstoffmolekül diese Konformation überhaupt einnimmt.

17

Mathematik ganz freizeitlich

Abbildung 1. Amprenavir, ein antiretrovirales organisches Molekül, das für die HIV-Therapie eingesetzt wird (Visualisierung: D. Baum, ZIB).

Der Einfluss der schnellen Atombewegung auf die langsame Formänderung des Moleküls ist komplex und nichtlinear, so dass die Molekülbewegung mit großem Rechenaufwand numerisch simuliert werden muss. Jedoch ist das Problem schlecht konditioniert. Das bedeutet, dass schon kleinste Änderungen der Anfangsbedingungen (Position und Geschwindigkeit der Atome) nach kurzer Zeit (wenige Picosekunden, 10−12 s) zu drastischen Abweichungen in der Gestalt des Moleküls führen. Dies ist der aus der Chaostheorie bekannte Schmetterlingseffekt. Dass trotz dieser Schwierigkeit die numerische Simulation einen wichtigen Beitrag zum Wirkstoffentwurf und zum Verständnis der molekularen Prozesse leisten kann, liegt daran, dass man an der speziellen Form eines einzelnen Moleküls zu einem bestimmten Zeitpunkt gar nicht interessiert ist. Wichtig sind stattdessen die Übergangswahrscheinlichkeiten zwischen verschiedenen Konformationen, sowie die Wahrscheinlichkeit des Vorliegens der einzelnen Konformationen. Die Berechnung dieser Größen ist gut konditioniert, hängt also nur sehr wenig von den Anfangsbedingungen ab, weil über eine große Menge von Molekülen in den verschiedensten

18

Molekülbillard

Abbildung 2. Zwei verschiedene Konformationen eines SARS-Inhibitors (Visualisierung: D. Baum, ZIB)

Zuständen und damit auch über viele verschiedene Anfangswerte gemittelt wird. Die extreme Abhängigkeit der konkreten Form des Moleküls von den Anfangsbedingungen lässt sich einfach durch ein Gedankenexperiment verstehen. Wir stellen uns einen idealen Billardtisch vor: Exakt runde Kugeln rollen reibungsfrei und absolut geradlinig auf diesem Tisch (was natürlich in der Wirklichkeit nie so sein kann). Auf der Diagonale des Tisches verteilen wir gleichmäßig drei Kugeln, so dass deren Mittelpunkte Abstände von 50 cm haben. Mit einem gut gezielten Stoß auf die erste Kugel möchten wir alle Kugeln der Reihe nach anstoßen, so dass die dritte Kugel schließlich in die 1 m von ihrem Mittelpunkt entfernte Ecktasche rollt. (Dafür muss man gar nicht wissen, wie groß der Tisch ist. Auf Standardtische passen die Kugeln aber wie beschrieben drauf.) Welche Winkelabweichung (in Grad) dürfen wir uns höchstens erlauben, damit die letzte Kugel tatsächlich in die Tasche rollt? Übrigens: Billardkugeln haben einen Durchmesser von 57,2 mm, während die Ecktaschen eine Breite von 11 cm aufweisen. Um tatsächlich in die Ecktasche zu gelangen, muss die Kugel in ihrer ganzen Breite hineinpassen (so wie in Abbildung 3) – eine Berührung

19

Mathematik ganz freizeitlich

Abbildung 3. Um tatsächlich in die Ecktasche zu gelangen, muss die Kugel in ihrer ganzen Breite hineinpassen.

der Taschen-Eckpunkte führt nicht zum Erfolg. Wir nehmen der Einfachheit halber und in Ignoranz der Realität an, dass die Öffnung der Ecktasche senkrecht zur Diagonale des Tisches liegt.

Antwortmöglichkeiten

1. 2. 3. 4. 5.

0,0003 0,001 0,003 0,01 0,03

6. 7. 8. 9. 10.

20

0,1 0,3 1 3 10

Molekülbillard

Lösung (Richtige Lösung:) Antwort 4) Wenn eine Kugel nicht genau entlang der Diagonale gestoßen wird, sondern in einem abweichenden Winkel α, so trifft sie die nächste Kugel nicht zentral, wodurch diese in einem Winkel β angestoßen wird. In der Abbildung 4 sind die Größen L = 50 cm und r = 2, 86 cm bekannt, α wird als gegeben vorausgesetzt. Dann gilt: d = t sin α

= ( L − s) sin α    = L − 4r2 − d2 sin α Formen wir diese Gleichung etwas um: L−

 d = 4r2 − d2 sin α

Quadrieren beider Seiten führt auf eine quadratische Gleichung für d, mit der relevanten Lösung  L − L2 − (1 + (sin α)2 )( L2 − 4r2 ) d= . (1) sin α + sin1 α







 

Abbildung 4. Stoß zweier Kugeln (Aufsicht)

21

 

Mathematik ganz freizeitlich 3.5

Bahnabstand 3. Kugel

3 2.5 2 1.5 1 0.5 0 0

0.005

0.01

0.015

0.02

0.025

0.03

Abbildung 5. Bahnabweichung der dritten Kugel in cm, abgetragen über der Winkelabweichung der ersten Kugel in Grad

Schließlich bestimmen wir sin β =

d d = √ , 2 s 4r − d2

also mittels (1) sin β in Abhängigkeit von sin α. So können wir aus dem Anfangswinkel α1 nacheinander die Winkelabweichungen α2 und α3 berechnen. Schließlich ist die Bahnabweichung der letzten Kugel beim Erreichen der Tasche 1 m sin α3 . Damit die Kugel tatsächlich in die Tasche fällt, darf die Bahnabweichung nicht mehr als 2,64 cm betragen (die Hälfte der Differenz von Taschenbreite und Kugeldurchmesser). Anhand der Abbildung 5 ist ersichtlich, dass die Winkelabweichung der ersten Kugel nur rund 0,025 Grad betragen darf.

22

Stein–Schere–Papier Boris Springborn

Wie gewinnt man im Spiel? Die Analyse von Strategien bei Gesellschaftsspielen ist ein Thema der mathematischen Spieltheorie. Mit ihren Methoden kann man aber nicht nur Spiele wie Schach oder Skat untersuchen, sondern auch verschiedenste Konfliktsituationen, bei denen das Schicksal jedes einzelnen Akteurs nicht nur vom eigenen Verhalten abhängt, sondern auch vom Verhalten der anderen, die ebenso wie er versuchen, ein für sie selbst möglichst positives Ergebnis herauszuschlagen. Die Spieltheorie hat großen Einfluss in den Wirtschaftswissenschaften. Auch in der Psychologie, Soziologie, Biologie und der Militärwissenschaft findet sie Anwendung. In der folgenden Aufgabe geht es aber tatsächlich um ein Spiel, und zwar um ein sehr einfaches, das jeder kennt. Trotzdem ist die Lösung nicht ganz einfach, und wer sie findet, hat schon die eine oder andere grundlegende Idee der Spieltheorie verstanden. Der Weihnachtsmann und der Osterhase spielen gern Stein– Schere–Papier (ohne „Brunnen“). Wer ein Spiel gewinnt, bekommt vom Verlierer eine Marzipankartoffel. Allerdings kann der Osterhase mit seinen Pfoten nur Stein und Papier, aber nicht Schere machen. Beide wissen das, reden aber nicht darüber. Der Weihnachtsmann ist also im Vorteil, weil er die Wahl zwischen Stein, Schere und Papier hat. Die Frage ist: Wie groß ist dieser Vorteil? Genauer: Wie viele Marzipankartoffeln macht der Weihnachtsmann im Durchschnitt pro Spiel plus, wenn beide optimal spielen? Antwortmöglichkeiten 1.

1 2

5.

2.

1

6.

3.

1 3 2 3

7.

4.

8.

1 4 3 4 1 6 5 6

9. 10.

23

1 9 2 9

Mathematik ganz freizeitlich

Lösung (Richtige Lösung: Antwort 3) Der Ausgang einer Spielrunde hängt nicht vom Ausgang der vorherigen Spielrunden ab; es macht also keinen Sinn, die Entscheidung für Stein, Schere oder Papier vom bisherigen Spielverlauf abhängig zu machen. Auch sonst gibt es keine äußeren Einflüsse, die zu berücksichtigen wären. Es bleibt folglich für jeden Spieler vernünftigerweise nichts anderes übrig, als sich in jeder Spielrunde zufällig für einen der möglichen Spielzüge zu entscheiden. Die Spieler, in diesem Fall Weihnachtsmann und Osterhase, können sich aber aussuchen, mit welchen Wahrscheinlichkeiten sie sich jeweils für Stein, Schere oder Papier bzw. für Stein oder Papier entscheiden. Aus so einer Wahrscheinlichkeitsverteilung besteht die Strategie eines Spielers. Tatsächlich sind, wie wir sehen werden, verschiedene Strategien unterschiedlich gut. Zunächst stellen wir fest, dass es für den Weihnachtsmann unsinnig ist, Stein zu spielen, weil er damit nicht gewinnen kann. Bezeichnen wir also die Wahrscheinlichkeit, dass der Weihnachts, und die Wahrscheinlichkeit, dass er mann Schere spielt, mit pW Schere W Papier spielt, mit pPapier . Der Osterhase spiele Stein und Papier mit O den Wahrscheinlichkeiten pO Stein und pPapier . Dann ist nach den Regeln der Wahrscheinlichkeitsrechnung der zu erwartende Gewinn (in Marzipankartoffeln) für den Weihnachtsmann O W O EW = − 1 · pW Schere pStein + 1 · pSchere pPapier O W O + 1 · pW Papier pStein + 0 · pPapier pPapier .

Der zu erwartende Gewinn für den Osterhasen ist EO = − EW , denn entweder geht es unentschieden aus, oder einer muss dem anderen eine Marzipankartoffel geben. Für die Wahrscheinlichkeiten gilt W O O pW Schere + pPapier = pStein + pPapier = 1.

24

Stein–Schere–Papier

Damit können wir die Wahrscheinlichkeiten pW und pO Stein aus Schere W der Gleichung für E durch Einsetzen eliminieren und erhalten O W O EW = − 1 + 2 pW Papier + 2 pPapier − 3 pPapier pPapier

oder, wenn wir pO Papier ausklammern, O W EW = − 1 + 2 pW Papier + pPapier (2 − 3 pPapier ).

Uns interessieren nun drei Fälle, nämlich, ob der Wert der Klammer größer als, gleich oder kleiner als 0 ist. Davon hängt nämlich ab, was die beste Gegenstrategie des Osterhasen ist. 2 W Fall 1. pW Papier < 3 . Dann ist 2 − 3 pPapier > 0; und die beste Gegenstrategie des Osterhasen (der ja den Gewinn des Weihnachtsmanns minimieren will) ist pO Papier = 0, also immer Stein zu spielen. Wenn der Osterhase optimal spielt, ist also

EW = − 1 + 2 pW Papier < Fall 2.

1 . 3

2 W pW Papier > 3 . Dann ist 2 − 3 pPapier < 0; und die beste Ge-

genstrategie des Osterhasen ist pO Papier = 1, also immer Papier zu spielen. Wenn der Osterhase optimal spielt, ist also W W EW = − 1 + 2 pW Papier + 2 − 3 pPapier = 1 − pPapier
0 gilt | xn | <  für alle bis auf endlich viele Folgenglieder xn . Die Schreibweise λ ∈ [0, 2[ ist gleichbedeutend mit 0 ≤ λ < 2, und x0 ∈] − 1, 1[ heißt −1 < x0 < 1. In den Antwortmöglichkeiten werden analoge Schreibweisen benutzt, zum Beispiel λ ∈ [0, 1] bedeutet 0 ≤ λ ≤ 1.

Antwortmöglichkeiten 1. 2. 3. 4. 5. 6. 7. 8. 9.

Die Eigenschaft (4) gilt für alle λ ∈ [0, 2[. Die Eigenschaft (4) gilt für kein λ ∈ [0, 2[. Die Eigenschaft (4) gilt nur für λ = 0. Die Eigenschaft (4) gilt für alle λ ∈ [0, 1[ und nur für diese λ. Die Eigenschaft (4) gilt für alle λ ∈ [0, 1] und nur für diese λ. Die Eigenschaft (4) gilt nur für λ = 1. Die Eigenschaft (4) gilt für alle λ ∈ [1, 2[ und nur für diese λ. Die Eigenschaft (4) gilt für alle λ ∈ ]1, 2[ und nur für diese λ. Die Eigenschaft (4) gilt für alle λ ∈ [0,5, 1,5] und nur für diese λ.

Ingenieure würden die Frage wie folgt stellen: Wie viel Energie muss mindestens in den Laser gepumpt werden, damit er nicht bei jedem Anfangszustand (der im Intervall ] − 1, 1[ der technisch vernünftigen Werte liegen soll) im Verlaufe der Zeit wieder ausgeht?

94

Wann geht der Laser an?

Lösung (Richtige Lösung: Antwort 5)

Ein geometrischer Lösungsweg Wir betrachten den Parameter λ = 0,5 und zeichnen den zugehörigen Graphen y = 0,5x − x3 . Als Startwert wählen wir x0 = −0, 9. Ausgehend vom Punkt ( x0 , x0 ) zeichnen wir eine vertikale Linie parallel zur y-Achse bis wir den Graphen in ( x0 , x1 ) schneiden. Den nächsten Zustand x2 erhalten wir, indem wir eine horizontale Linie ausgehend vom letzten Schnittpunkt ( x0 , x1 ) bis zur Geraden y = x (blau eingezeichnet) zeichnen und dann vom erreichten Schnittpunkt ( x1 , x1 ) aus wieder eine vertikale Linie bis zum

95

Mathematik komplett technologisch 












=1


=1.7

 
 
 
 














  
 
 
 




























Schnittpunkt ( x1 , x2 ) mit dem Graphen zeichnen, usw. Die Prozedur ist in der Graphik durch den grünen Linienzug dargestellt. Man erkennt, dass die Punkte ( xn , xn+1 ) gegen den Nullpunkt (0, 0) konvergieren. Falls man einen anderen Startwert x0 wählt, so ergibt sich ein ähnliches Bild, also gilt Eigenschaft (4) für λ = 0, 5. Man überlegt sich dann, dass für 0 ≤ λ ≤ 1 das geometrische Bild qualitativ nicht anders ist. Also gilt (4) für 0 ≤ λ ≤ 1. Erst für λ > 1 ändert sich die Situation. Man stellt fest, dass der Graph die y = x Achse in zwei weiteren Punkten schneidet (grüne Punkte). Die Schnittpunkte mit der y = x Achse werden unter der beschriebenen graphischen Iteration festgehalten und befinden sich für λ ∈ [0, 2[ im Einheitswürfel −1 < x < 1, −1 < y < 1, entsprechen also Zuständen im Intervall ]−1, 1[. Also gilt (4) nicht für 1 < λ < 2.

96

Wann geht der Laser an?

Ein analytischer Lösungsweg

√ Wenn λ ∈ ]1, 2[ ist, so ist x0 = λ − 1 ∈ ]−1, 1[ ein zugelassener Anfangswert. Zu diesem Anfangswert gehört die Lösung (3), und für die gilt nicht limn→∞ xn = 0. Mit anderen Worten: Alle λ ∈ ]1, 2[ haben die Eigenschaft (4) nicht. Wir zeigen nun, dass alle λ ∈ [0, 1] die Eigenschaft (4) besitzen. Es sei also λ ∈ [0, 1] und x0 ∈ ]−1, 1[. Dann gilt | x1 | = | x0 | · |λ − x02 | ≤ | x0 | < 1. Dabei haben wir benutzt, dass λ und x02 Zahlen zwischen Null und Eins sind, ihre Differenz also dem Betrag nach kleiner oder gleich Eins ist. Analog erhält man

| x2 | = | x1 | · |λ − x12 | ≤ | x1 | < 1 usw. Die Folge | x1 |, | x2 |, . . . ist also eine monoton fallende Folge nichtnegativer Zahlen. Folglich konvergiert sie gegen einen Grenzwert, nennen wir ihn y, welcher strikt kleiner als Eins ist. Wenn wir in der Gleichung     | xn+1 | = | xn | · λ − | xn |2  den Grenzübergang n → ∞ durchführen, erhalten wir     y = y λ − y2  . Diese Gleichung besitzt aber für λ ∈ [0, 1] und 0 ≤ y < 1 nur die Lösung y = 0. Daraus folgt 0 = y = limn→∞ | xn |, also limn→∞ xn = 0.

Ein Lösungsweg mit dem Taschenrechner Für λ ∈ ]1, 2[ beobachtet man durch sukzessive Berechnung mit dem Taschenrechner der Werte xn mit Hilfe von (1), dass für Start-

97

Mathematik komplett technologisch

werte √ x0 nahe Null die√xn von Null wegdriften und gegen die Grenzwerte λ − 1 oder − λ − 1 konvergieren. So kommt man zur Vermutung, dass (4) für λ > 1 nicht erfüllt ist. Wählt man hinreichend viele verschiedene Parameter 0 ≤ λ ≤ 1 und Startwerte x0 ∈ ]−1, 1[, so kann man sich davon überzeugen, dass stets die Werte xn gegen Null streben, d. h. dass die fünfte Antwort richtig ist.

98

Mathematik ganz zufällig

Der Forsch-Frosch Fred Volker Kaibel

Bewegt man sich auf der Suche nach Informationen zu einem bestimmten Thema immer neuen Links folgend durch das WorldWide-Web, so stellt man in der Regel nach einer gewissen Zeit fest, dass man auf manchen Seiten immer wieder gelandet ist. Diese Seiten stellen sich oft als wichtig heraus. Suchmaschinen wie Google machen sich dieses Phänomen zu Nutze, um die Wichtigkeit einzelner Web-Seiten zu bewerten. Dazu lassen sie auf einer beliebigen Web-Seite einen imaginären Surfer starten, der immer zufällig einen der auf seiner aktuell besuchten Seite vorgefundenen Links verfolgt. Der Surfer vollführt einen Random Walk im Netzwerk der Web-Seiten. Für jede Schrittzahl gibt es nun eine bestimmte Wahrscheinlichkeitsverteilung, die beschreibt, wo der Surfer sich nach genau dieser Schrittzahl mit welcher Wahrscheinlichkeit aufhält. Vor dem ersten Schritt ist das zum Beispiel mit Wahrscheinlichkeit Eins die Startseite. Verweist diese auf drei andere Seiten A, B und C, so ist der Surfer nach dem ersten Schritt mit Wahrscheinlichkeit 13 auf A, mit Wahrscheinlichkei 13 auf B und mit Wahrscheinlichkeit 13 auf C. Verweist A zum Beispiel auf A1 und A2 (und keine der Seiten B und C verweisen auf A1 oder A2 ), so ist der Surfer nach dem zweiten Schritt mit Wahrscheinlichkeit 16 auf A1 , mit Wahrscheinlichkeit 16 auf A2 , und mit irgendwelchen Wahrscheinlichkeiten, die sich zu 2 3 summieren, auf den Seiten, auf die B und C verweisen. Die Wahrscheinlichkeitsverteilung ändert sich in der Regel zunächst von Schritt zu Schritt sehr stark. Man kann jedoch beweisen, dass sie sich mit wachsender Schrittzahl immer mehr einer eindeutig bestimmten Grenzverteilung nähert (zumindest, wenn man in bestimmtem Sinne vorsichtig mit Situationen umgeht wie der, dass eine Web-Seite auf gar keine andere verweist). Die Verteilun-

101

Mathematik ganz zufällig

gen konvergieren gegen diese Grenzverteilung, und zwar unabhängig von der Startseite. In der Grenzverteilung hat jede Web-Seite eine Wahrscheinlichkeit. Diese entspricht sehr genau der relativen Besuchshäufigkeit dieser Seite, also dem Quotienten aus der Anzahl der Besuche der jeweiligen Seite und der Anzahl aller gemachten Seiten-Besuche, wenn man den Random Surfer sehr lange surfen lässt. Insofern lag es nahe, diese Grenzwahrscheinlichkeiten bzw. Besuchshäufigkeiten als ein Maß für die Wichtigkeit der jeweiligen Seite zu nehmen. Das taten Larry Page und Sergej Brin und bauten in ihre Suchmaschine Google diesen Page-Rank genannten Bewertungsmechanismus ein. Wie man die Grenzwahrscheinlichkeiten ermitteln kann, ohne einen imaginären Surfer zu bemühen, wird in der unten gestellten Aufgabe deutlich werden. Natürlich fließen in der Praxis von Suchmaschinen viele andere Kriterien mit in die Bewertung ein, vor allem auch solche, die den Suchbegriff berücksichtigen. Das Prinzip eines Random Walks spielt aber nicht nur bei Suchmaschinen eine wichtige Rolle, sondern beispielsweise auch in der theoretischen Physik, wo man so versucht, komplexe Systeme zu modellieren, die sich in vielen verschiedenen Zuständen befinden können und den tatsächlichen Zustand immer wieder unter Einfluss von Zufall wechseln. Die möglichen Zustände entsprechen dann den Web-Seiten, die Bewegung des Surfers durch das WorldWide-Web korrespondiert mit der zeitlichen Entwicklung (fortlaufender Wechsel des Zustands) des Systems. Hat man sich nun ein Bild davon gemacht, wie die Übergänge zwischen den verschiedenen Zuständen zufällig passieren, so steht man danach vor der Aufgabe, die Entwicklung des Systems über eine lange Zeit zu analysieren, also zum Beispiel herauszufinden, ob das System eine Grenzverteilung auf dem Zustandsraum hat, und sie gegebenenfalls zu ermitteln. Umgekehrt macht sich die moderne algorithmische Mathematik das Prinzip des Random Walks zu Nutze, um komplexe mathematische Objekte zufällig zu erzeugen. In diesem Fall hat man in der Regel eine vorgegebene Wunschverteilung auf den Objekten (die

102

Der Forsch-Frosch Fred

Der Forsch-Frosch-Fred im Seerosenteich (©2004 Jens Jordan)

jetzt die Rolle der Web-Seiten spielen) und möchte einen Random Walk entwerfen, dessen Grenzverteilung gerade die Wunschverteilung ist. Als Entwurfsparameter hat man dabei die Übergangswahrscheinlichkeiten zwischen Paaren von Objekten zu Verfügung. Man kann z. B. festlegen, dass von Objekt A aus mit Wahrscheinlichkeit 15 zu Objekt A1 und mit Wahrscheinlichkeit 45 zu Objekt A2 übergegangen werden soll. Hat man nun geeignete Übergangswahrscheinlichkeiten theoretisch konstruiert, so simuliert man mit einem Computer den Random Walk eine Zeit lang. Die mathematische Kunst besteht nun darin, herauszufinden, wie viele Schritte man den Computer simulieren lassen muss, damit die erzielte Wahrscheinlichkeitsverteilung auf den Objekten nah genug an der Grenzverteilung, und damit an der Wunschverteilung, ist. Mit solchen Methoden kann man zum Beispiel komplizierte mathematische Zählprobleme (approximativ) lösen, bei denen Objekte gezählt werden müssen, deren Anzahl so groß ist, dass man sie niemals alle erzeugen kann. Das dahinter stehende Prinzip, den Zufall intelligent in Algorithmen und Computerprogrammen zu nutzen, spielt eine wichtige Rolle in vielen Bereichen der aktuellen Algorithmenforschung.

103

Mathematik ganz zufällig

Um das Prinzip des Random Walks an einem konkreten Beispiel zu studieren, schauen wir uns den Forsch-Frosch Fred an. Fred ist Mathematiker. Um so wenig wie möglich von seiner hochgeistigen Tätigkeit abgelenkt zu werden, führt er ein etwas monotones Leben. Er tut nichts, als zwischen den 14 Seerosenblättern seines Teiches hin und her zu springen. Da die Natur Fred zwar mit einem großen Kopf, aber mit für einen Frosch eher dünnen Beinen ausgestattet hat, kommen für ihn nur die im Bild rot eingezeichneten Sprünge in Frage. Und weil er seine mathematischen Überlegungen nicht durch unwesentliche Gedanken unterbrechen möchte, springt er stets vom aktuellen Seerosenblatt gleich zufällig zu einem der möglichen Nachbarblätter. Der Forsch-Frosch Fred macht also im Wesentlichen das Gleiche wie der Random Surfer im WorldWide-Web, nur dass er nicht von Webseite zu Webseite klickt, sondern von Blatt zu Blatt springt. Ein solches Forsch-Frosch-Leben mit viel Bewegung und stets an der frischen Luft ist natürlich sehr gesund, so dass Fred sehr alt wird. An seinem 20. Geburtstag überlegt er, auf welchem Blatt er vermutlich am häufigsten gewesen sei. Einige Sprünge später ist ihm die Antwort klar – aber er ist ja auch Profi. Was meinst Du, wo er am häufigsten war? Freds erste Idee war, dass die 14 relativen Besuchshäufigkeiten sich zu Eins aufsummieren sollten. Seine zweite Idee war dann, für jedes der 14 Blätter eine Formel zu finden, nach welcher man (zumindest ungefähr) seine Besuchshäufigkeit mit Hilfe der Besuchshäufigkeiten seiner Nachbarblätter ausdrücken kann. Und er erinnerte sich, dass er einmal in einem Werk eines berühmten Mathematikers (Fred meinte sich zu erinnern, dass sein Name Froschbeinius gewesen war) gelesen hatte, dass solche Systeme von Gleichungen genau eine Lösung haben. Und die sollte dann ja wohl aus seinen Besuchshäufigkeiten bestehen.

104

Der Forsch-Frosch Fred

Antwortmöglichkeiten 1. 2. 3. 4. 5. 6. 7. 8. 9. 10.

Da, wo er gestartet ist. Im Zentrum: Blatt 7. Auf dem Blatt, auf das er im Bild zuspringt: Blatt 10. Wenn er rechts startet, auf Blatt 7, wenn er links startet auf Blatt 6. Wenn er rechts startet, auf Blatt 6, wenn links startet auf Blatt 7. Auf allen Blättern (ungefähr) gleich häufig. Auf den hinteren Blättern 1, 2, 13 und 14 (ungefähr) gleich häufig, weil man von dort schlecht weg kommt. Auf dem Dreieck der Blätter 4, 5, 6, weil man dort oft kreiselt. Auf Blatt 6, weil es das größte ist. Das kann man nicht vorhersagen.

105

Mathematik ganz zufällig

Lösung (Richtige Lösung: Antwort 3) Fred bezeichnete die Anzahl der Besuche der einzelnen Blätter mit H (1), H (2), . . . , H (14). Er ist in seinem Leben also H (7) mal auf Blatt 7 gewesen. Die Gesamtzahl aller seiner Blatt-Besuche war dann H = H (1) + H (2) + · · · + H (14) . Die relativen Besuchshäufigkeiten der einzelnen Blätter waren h (1) =

H (1) , H

h (2) =

H (2) , H

··· ,

h(14) =

H (14) . H

Wie Fred sofort erkannte, musste also H (1) H (2) H (14) + +···+ H H H H = =1 H

h(1) + h(2) + · · · + h(14) =

gelten. Wie konnte Fred jetzt z. B. die Anzahl H (7) der Besuche des Blatts 7 (zumindest ungefähr) mittels der Anzahlen H (6), H (8) und H (10) der Besuche seiner Nachbarblätter 6, 8 und 10 ausdrücken? Weil Blatt 6 drei Nachbarn hat, wird er wohl bei einem Drittel seiner Besuche des Blatts 6 von dort auf Blatt 7 gesprungen sein, dachte Fred. Ebenso wird er bei einem Drittel der Besuche des Blatts 8 von dort auf Blatt 7 gesprungen sein, und bei einem Viertel der Besuche des Blatts 10 wird er von dort auf Blatt 7 gehüpft sein. Also sollte H (7) =

1 1 1 H (6) + H (8) + H (10) 3 3 4

gelten. Fred teilte diese Gleichung durch H und erhielt H (7) 1 H (6) 1 H (8) 1 H (10) , = · + · + · H 3 H 3 H 4 H

106

Der Forsch-Frosch Fred

also wegen h(7) =

H (7) H

h (7) =

usw. 1 1 1 h(6) + h(8) + h(10) . 3 3 4

Das schien ihm plausibel, denn die Besuchshäufigkeit von Blatt 7 setzte sich zusammen aus einem Drittel der Besuchshäufigkeit von Blatt 6 (das drei Nachbarn hat), einem Drittel der Besuchshäufigkeit von Blatt 8 (das ebenfalls drei Nachbarn hat) und einem Viertel der Besuchshäufigkeit von Blatt 10 (das vier Nachbarn hat). Analog bestimmte Fred für jedes Blatt eine solche Gleichung, zum Beispiel 1 1 1 h (4) = h (3) + h (5) + h (6) 3 2 3 oder 1 h (1) = h (3) . 3 Insgesamt stellte Fred also 14 dieser Gleichungen auf, welche zusammen mit der Gleichung h(1) + h(2) + · · · + h(14) = 1 ein System von 15 Gleichungen ergaben, das von den Besuchshäufigkeiten h(1), h(2), . . . , h(14) erfüllt werden musste. Fred erinnerte sich nun an seine Studentenzeit, in der er gelesen hatte, dass Systeme von der Art dessen mit den 15 Gleichungen, welches er gerade aufgestellt hatte, genau eine Lösung haben. Er erinnerte sich auch, dass das nicht ganz einfach zu beweisen gewesen war. Wie auch immer, jetzt war ihm jedenfalls klar, dass er nur irgendwie Werte für die Variablen h(1), h(2), . . . , h(14) finden musste, die alle 15 Gleichungen erfüllten. Sein erster Gedanke war, dass er ja schon in der Froschschule lineare Gleichungssysteme mit zwei, drei oder auch vier Variablen gelöst hatte. Aber mit 14 Variablen schien ihm das doch etwas zu aufwändig, zumal er beim Weiterhüpfen ja auch nicht schreiben, sondern nur denken konnte. Fred dachte noch einmal an die Gleichung h (7) =

1 1 1 h(6) + h(8) + h(10) , 3 3 4

107

Mathematik ganz zufällig

die ausdrückte, wie häufig er auf Blatt 7 gewesen war. Auf der rechten Seite standen drei Summanden, weil Blatt 7 drei Nachbarn hatte. In der Summe wurden h(6) und h(8) mit 13 multipliziert, weil die Blätter 6 und 8 jeweils drei Nachbarn hatten, und h(10) wurde mit 1 4 multipliziert, weil Blatt 10 vier Nachbarblätter hatte. Also könnte man diese Gleichung doch ganz einfach erfüllen, wenn man h (7) = 3

(Anzahl Nachbarn von Blatt 7)

h (6) = 3

(Anzahl Nachbarn von Blatt 6)

h (8) = 3

(Anzahl Nachbarn von Blatt 8)

h(10) = 4

(Anzahl Nachbarn von Blatt 10)

wählen würde. Fred wurde ganz aufgeregt. Ja, so konnte es gehen. Wenn man für jedes Blatt n den Wert von h(n) auf die Anzahl der Nachbarn von Blatt n setzen würde, dann wären zumindest schon einmal die 14 Gleichungen erfüllt, denn die waren ja alle nach dem gleichen Prinzip wie die Gleichung für h(7) entstanden. Zu dumm nur, dass diese 14 Werte ganz bestimmt in der Summe nicht Eins ergaben, sondern irgendeine größere Zahl. Welche eigentlich? Diese Summe enstand ja, indem für jedes Blatt die Anzahl seiner Nachbarn aufaddiert wurde. Fred durchzuckte ein Gedanke: Aber dann musste doch genau das Doppelte der Anzahl aller Sprungmöglichkeiten in seinem Teich heraus kommen, denn jede Sprungmöglichkeit machte ja zwei Blätter zu Nachbarn voneinander. Fred zählte schnell die Sprungmöglichkeiten und kam auf 18 (die Anzahl der roten Verbindungslinien). Also summierten sich die 14 Werte, die zumindest schon einmal die 14 Gleichungen erfüllten, zu 36. Jetzt war Fred alles klar: Man brauchte diese Werte nur durch 36 zu teilen. Dann blieben die 14 Gleichungen erfüllt, weil ja bei jeder dieser Gleichungen beide Seiten durch 36 geteilt wurden, und sogar die 15. Gleichung war dann erfüllt, denn wenn die 14 alten Zahlen in der Summe 36 ergaben, dann musste die Summe der 14 durch 36 geteilten Zahlen natürlich Eins sein.

108

Der Forsch-Frosch Fred

Das war die Lösung: Die Besuchshäufigkeit des Blatts n war h(n) =

Anzahl der Nachbarn von Blatt n 36

für jedes n = 1, 2, . . . , 14. Die Besuchshäufigkeiten waren also 1 ) zu den Anzahlen der proportional (mit Proportionalitätsfaktor 36 Nachbarblätter. Fred quakte zufrieden: Dann war er also am häufigsten auf Blatt 10 gewesen, denn dieses Blatt hatte vier Nachbarn, während alle anderen Blätter höchstens drei Nachbarn hatten. Übrigens ist das Berechnen der Grenzverteilung im Web nicht so einfach wie im Seerosenteich. Das liegt daran, dass Fred immer, wenn er von einem Blatt auf ein anderes springen kann, auch wieder unmittelbar zurück springen kann. Im Web gibt es aber nicht von jeder Seite B, auf die ein Link von A verweist, auch unbedingt einen Link zurück zu A. Anders als im Seerosenteich ist die Grenzwahrscheinlichkeit einer Seite im Web daher nicht proportional zur Anzahl der Links, welche auf die Seite verweisen. Das ist auch gut so, denn sonst könnte man die Bewertung der Seiten durch Suchmaschinen allzu leicht hereinlegen, indem man viele künstliche Seiten mit Links auf eine Seite erzeugt, die man gerne weit oben bei den Suchergebnissen sehen möchte. Statt einfach Links zu zählen, müssen Betreiber von Suchmaschinen also in der Tat lineare Gleichungssysteme mit Computern und ausgefeilten Methoden der numerischen Linearen Algebra lösen.

109

Keller oder Dach zuerst? Nicole Megow

Komplexe Planungsaufgaben entstehen in vielen Bereichen wie z. B. in der Produktion und Logistik, der Bauplanung oder allgemein im Projektmanagement. Typischerweise werden umfangreiche Projekte in viele einzelne Teilaufgaben zerlegt, die dann zeitlich geplant werden. Das heißt, es wird genau bestimmt wann bzw. in welcher Reihenfolge Aufgaben mit welchen Ressourcen durchgeführt werden sollen. Bei der Planung müssen verschiedenste Reihenfolgeabhängigkeiten zwischen den Vorgängen berücksichtigt werden. Diese Abhängigkeiten können technischer Natur sein oder werden aus sicherheitsrelevanten oder wirtschaftlichen Gründen festgelegt. Betrachten wir als vereinfachtes Beispiel den Bau eines Hauses und einige grobe Arbeitsschritte die dabei durchgeführt werden. Es wird ein Fundament ausgehoben, der Rohbau wird errichtet, ein Dach wird aufgesetzt, Böden, Fenster, Elektrik werden eingebaut und vieles mehr. Zwischen all diesen Teilaufgaben bestehen Reihenfolgeabhängigkeiten. Einige Vorgänge können parallel bearbeitet werden (müssen sie aber nicht), andere wiederum müssen zwingend nacheinander ausgeführt werden. So kann natürlich weder mit der Dachkonstruktion noch mit dem Innenausbau begonnen werden, bevor das Fundament gegossen ist. Andererseits können die Fenster eingesetzt werden, während gleichzeitig die Elektrik verlegt wird. Große Projekte können aus hunderten oder tausenden einzelnen Vorgängen bestehen, die alle miteinander in Beziehung stehen. Sie müssen nun zeitlich genau geplant werden. Dies allein kann eine sehr herausfordernde und komplizierte Planungsaufgabe sein. In der Praxis kommt erschwerend hinzu, dass die wirkliche Dauer der einzelnen Arbeitsschritte oft nicht im Voraus bekannt ist. Sie unterliegt einer Unsicherheit die durch viele Faktoren bestimmt wird, die

111

Mathematik ganz zufällig

a

c

b

d Abbildung 1. Projektnetz

mit dem Arbeitsschritt selbst oder äußeren Einflüssen zusammenhängen. Überraschende Verzögerungen bei der Lieferung von Teilprodukten, unterschiedlich ausgebildete Arbeitskräfte, Verschleiß von Arbeitsmitteln, das Wetter und viele andere Faktoren können eine Rolle spielen. Aus statistischen Beobachtungen heraus können aber häufig Wahrscheinlichkeitsverteilungen für die Dauern der Vorgänge angegeben werden, auf deren Basis dann geplant wird. In der folgenden Aufgabe wird ein kleines, abstraktes Planungsproblem mit unsicheren Dauern beschrieben. Es sollen vier Arbeitsschritte a, b, c und d durchgeführt werden. Sie sind in dem abgebildeten Projektnetz (das als Graph bezeichnet wird) als Kreise (Knoten) dargestellt. Die Pfeile (Kanten) geben Reihenfolgebeziehungen an. So kann Arbeitsschritt c erst dann beginnen, wenn Arbeitsschritt a beendet ist, während Arbeitsschritt d auf die Fertigstellung der Arbeitsschritte a und b warten muss. Die Arbeitsschritte haben Bearbeitungsdauern, die vor der eigentlichen Ausführung nicht genau bekannt sind. Jeder Arbeitsschritt kann 1, 2 oder 3 Zeiteinheiten dauern. Jede dieser Dauern ist für jeden Arbeitsschritt gleich wahrscheinlich und unabhängig von den Dauern anderer Vorgänge. Eine mögliche Kombination von Dauern, z. B. (1, 3, 2, 2), für die Vorgänge a, b, c, d heißt Realisierung. Bei der Planung des Projektes möchte man vorab Information über die kürzeste zu erwartende Projektdauer ermitteln. Als kürzeste Projektdauer bezeichnen wir den frühesten Zeitpunkt, zu dem

112

Keller oder Dach zuerst?

alle Vorgänge beendet sein können. Das heißt, wir gehen davon aus, dass keine unnötigen Wartezeiten eingefügt werden. Folgende Fragen sollen beantwortet werden: 1. Wie groß ist die Wahrscheinlichkeit, dass die kürzeste Projektdauer (PD) nicht länger als 4 Zeiteinheiten ist? Tipp: Die Wahrscheinlichkeit für PD ≤ 4 ist die Anzahl der Realisierungen für die Dauern der Vorgänge a, b, c, d, die PD ≤ 4 erfüllen, dividiert durch die Anzahl aller möglichen Realisierungen. 2. Wie groß ist die Wahrscheinlichkeit, dass die kürzeste Projektdauer PD ≥ 5 ist? 3. Welche ist die kürzeste Projektdauer die sich auf Basis der mittleren Bearbeitungsdauern bestimmt?

Antwortmöglichkeiten 23 81 ,

29 81 ,

1.

Aufgabenteil 1:

2.

Aufgabenteil 1: 1, Aufgabenteil 2: 0, Aufgabenteil 3: 6

3.

Aufgabenteil 1:

4.

Aufgabenteil 1:

5.

Aufgabenteil 1:

6.

Aufgabenteil 1:

7.

Aufgabenteil 1:

8.

Aufgabenteil 1:

9.

Aufgabenteil 1:

10.

Aufgabenteil 1:

31 81 , 8 81 , 23 81 , 1 81 , 60 81 , 23 81 , 31 81 , 31 81 ,

Aufgabenteil 2:

Aufgabenteil 2: Aufgabenteil 2: Aufgabenteil 2: Aufgabenteil 2: Aufgabenteil 2: Aufgabenteil 2: Aufgabenteil 2: Aufgabenteil 2:

113

50 81 , 72 81 , 58 81 , 80 81 , 21 81 , 29 81 , 29 81 , 50 81 ,

Aufgabenteil 3: 3

Aufgabenteil 3: 4 Aufgabenteil 3: 3 Aufgabenteil 3: 4 Aufgabenteil 3: 2 Aufgabenteil 3: 6 Aufgabenteil 3: 5 Aufgabenteil 3: 4 Aufgabenteil 3: 6

Mathematik ganz zufällig

Lösung (Richtige Lösung: Antwort 3) Es gibt vier Vorgänge, die unabhängig voneinander jeweils drei verschiedene Dauern annehmen können. Insgesamt gibt es also 34 = 81 verschiedene Realisierungen. Aus den Reihenfolgebeziehungen im Graphen und den möglichen Realisierungen von Vorgangsdauern lassen sich die möglichen Gesamtprojektdauern 2, 3, . . . , 6 ableiten. Nun kann man einfach durch Auszählen der Häufigkeiten die Verteilung bestimmen. Dazu zählt man, wieviele Realisierungen eine bestimmte Projektdauer PD erzielen und teilt sie durch die Gesamtzahl der Realisierungen 81. Damit ergibt sich folgende Verteilung für die Projektdauer: PD = 2 mit Wahrscheinlichkeit PD = 3 mit Wahrscheinlichkeit PD = 4 mit Wahrscheinlichkeit PD = 5 mit Wahrscheinlichkeit PD = 6 mit Wahrscheinlichkeit

1 81 7 81 23 81 29 81 21 81

1 7 31 + 81 + 23 Also gilt PD ≤ 4 mit Wahrscheinlichkeit 81 81 = 81 = 37 % 50 und PD ≥ 5 mit Wahrscheinlichkeit 81 = 61,7 %. Das heißt, die Wahrscheinlichkeit, dass das Projekt länger als vier Zeiteinheiten dauert ist wesentlich höher als die Wahrscheinlichkeit, dass es genau vier oder weniger Zeiteinheiten dauert. Vergleichen wir dieses Ergebnis nun mit einer groben Schätzung auf Basis der mittleren Bearbeitungsdauern. Jeder Vorgang hat eine mittlere Bearbeitungsdauer von zwei Zeiteinheiten. Auf Basis dieser Dauern hätte das Gesamtprojekt eine Dauer von vier Zeiteinheiten, was dem frühestens Fertigstellungszeitpunkt der Vorgänge c und d

114

Keller oder Dach zuerst?

entspricht. Dies steht im deutlichen Gegensatz zu den exakten Berechnungen im vorigen Abschnitt, nach denen die Wahrscheinlichkeit für die Einhaltung der Projektdauer 4 gering ist. Dieses Beispiel zeigt, dass Gesamtdauern für Projekte mit (komplexen) Reihenfolgeabhängigkeiten, die auf Basis der Mittelwerte der einzelnen Dauern bestimmt werden, die wirklich zu erwartende Projektdauer sehr stark unterschätzen können. Dieser Zusammenhang ist in allgemeiner Form auch als Jensensche Ungleichung bekannt. Sie besagt, dass für konvexe Funktionen f : → und Zufallsvariablen X gilt, dass E [ f ( X ) ] ≥ f (E [ X ]). Hierbei sind E [ X ] bzw. E [ f ( X ) ] die Erwartungswerte von X bzw. f ( X ), also die mittleren zu erwartenden Werte bei oftmaligem Wiederholen. Der korrekte Erwartungswert der Projektdauer ist der Mittelwert über alle Projektdauern gewichtet mit deren Wahrscheinlichkeit, 1 7 29 21 d. h. in unserem Beispiel 2 81 + 3 81 + 4 23 81 + 5 81 + 6 81 ≈ 4, 8.

R

115

R

Viele Tests – viele Fehler? Karsten Tabelow

Bildgebende Verfahren haben sich in den letzten Jahren einen festen Platz in der Medizin erobert und die medizinische Forschung und Diagnostik revolutioniert. Sie ermöglichen Ärzten und Forschern einen Einblick in lebendes Gewebe. Mit der fortschreitenden technischen Entwicklung liefern die Verfahren immer höhere Auflösungen, schärfere Bilder und mehr Details. Bildgebende Verfahren sind ohne Mathematik undenkbar, von der Bildrekonstruktion aus den gemessenen Signalen, bis hin zur Auswertung der Bildinformation. Für die Analyse der großen Menge an Bilddatenpunkten (Voxel, volume element, im Gegensatz zum zweidimensionalen Pixel, picture element) werden häufig insbesondere Methoden der mathematischen Statistik benötigt. Zufällige Fehler in der Messung äußern sich als Bildrauschen, die Bilder wirken unscharf und gestört. Dadurch werden diagnostische Entscheidungen erschwert. Unter den bildgebenden Verfahren spielt die Magnetresonanztomographie (MRT) in den Neurowissenschaften eine herausragende Rolle. Ein Grund dafür ist ein guter Weichteilkontrast, welcher die Technik auch für die Untersuchung des menschlichen Gehirns interessant macht. Darüber hinaus arbeitet die MRT im Gegensatz zur bekannten und weit verbreiteten Computertomographie (CT) nicht mit schädlicher ionisierender Strahlung sondern mit Radiowellen in einem starken permanenten Magnetfeld. Mit der Magnetresonanztomographie eröffnet sich den Neurowissenschaftlern die Möglichkeit, dem Gehirn bei der Arbeit zuzuschauen. In schneller Abfolge, das heißt alle zwei bis drei Sekunden, können komplette dreidimensionale Bilder des Gehirns aufgezeichnet werden. Diese Technik wird als funktionelle Magnetresonanztomographie (fMRI) bezeichnet und kann dazu benutzt werden, Denkprozesse im Gehirn zu lokalisieren. Solche Prozesse bedeuten eine hohe Aktivität

117

Mathematik ganz zufällig

Abbildung 1. Simuliertes erwartetes Signal in einem Voxel, welcher während des dreimal wiederholten Stimulus aktiv war (rote Linie). Gezeigt sind außerdem die gemessenen Werte. Die Abweichungen entsprechen den zufälligen Fehlern, also dem Bildrauschen.

des Gehirns, welche mehr Sauerstoff benötigt. Dieser wird mit dem Blut in die entsprechenden Areale transportiert. Die resultierende lokale Änderung des gemessenen Signals durch diesen BOLD (Blood Oxygen Level Dependent)-Effekt kann als natürlicher Kontrast für die Bildgebung benutzt werden. Ein typisches fMRI-Experiment sieht so aus: Der Proband oder Patient wird für eine gewisse Zeit z. B. einem optischen oder akustischen Reiz ausgesetzt. Daran schließt sich eine entsprechende Ruhephase an. Dieser Zyklus wird einige Male wiederholt. Statt eines passiven Reizes können auch Aufgaben gelöst werden, selbst Rechnen oder das Erfassen von Textinhalten sind denkbar. In Voxeln, die während der Stimulation aktiv waren, kann durch den BOLD-Effekt ein ganz spezifisches Signal erwartet werden (siehe Abbildung 1). Dieses Signal ist jedoch, wie eingangs bereits erwähnt, durch zufällige Fehler überlagert. Daher ist es im Einzelfall schwer zu entscheiden, ob das gemessene Signal die erwartete Form hat oder nicht. Die mathematische Statistik stellt Signifikanztests bereit, um in einem Voxel diese Entscheidung zu treffen. Bei solchen Tests wird eine Schranke (Signifikanzniveau) α > 0 für die Wahrscheinlich-

118

Viele Tests – viele Fehler?

keit festgelegt, durch den Test das erwartete Signal zu finden, obwohl keines vorhanden ist. Dies sind sogenannte falsch positive Testergebnisse. Typische Werte für α sind 0,05 oder 0,01, denn dies wird als eine hinreichend kleine Wahrscheinlichkeit für solche Ergebnisse betrachtet. Die Aufgabe, unter den rund 100 000 Voxeln, die zum fMRI Datensatz gehören, die wenigen hundert aktivierten zu finden, führt auf ein multiples Testproblem, also dem gleichzeitigen Test in allen Voxeln. Wird als Signifikanzniveau des voxelweisen Tests zum Beispiel α = 0,05 gewählt, so ergibt dies allein etwa 5000 = 0,05 × 100 000 fälschlicherweise als aktiv klassifizierte Voxel. Wie soll auf diese Weise eine einigermaßen sichere Entscheidung getroffen werden, in welchen Voxeln tatsächlich eine Aktivierung vorliegt und welche Voxel nur durch die große Anzahl unabhängiger Signifikanztests als aktiv angezeigt werden? Eine Möglichkeit ist die Festlegung einer Schranke für die Wahrscheinlichkeit, bei Anwendung des voxelweisen Signifikanztests auf alle Voxel des Datensatzes kein falsch positives Ergebnis zu erhalten. Wie groß muss α gewählt werden, damit die Wahrscheinlichkeit, bei 100 000 Voxeln kein falsch positives Ergebnis zu erhalten 0,99 = 99 % ist? Hinweis: Es sollte gerundet werden!

Antwortmöglichkeiten

1.

0,05

6.

2.

0, 05 5000

0, 01 100 000

7.

3.

0, 05 100 000

0, 01 · 1000 100 000

8.

0,991000

4.

0,01

9.

0,995000

5.

0, 01 1000

10.

0, 99 100 000

119

Mathematik ganz zufällig

Lösung (Richtige Lösung: Antwort 6) Wie so oft führt die Untersuchung des komplementären Ereignisses schnell zum Ziel. Wenn für jeden einzelnen Test die Wahrscheinlichkeit ein falsch positives Ergebniss zu liefern α ist, so ist die Wahrscheinlichkeit, dass der Test kein falsch positives Ergebnis hat 1 − α. Wenn alle n = 100 000 Tests unabhängig sind, ist die Wahrscheinlichkeit dafür, dass keiner der Tests ein falsch positives Ergebnis liefert (1 − α ) n , also das n-fache Produkt der einzelnen Wahrscheinlichkeiten. Folglich ist die Wahrscheinlichkeit, dass mindestens ein Test (von n) falsch positiv ist 1 − (1 − α ) n . Diese Wahrscheinlichkeit soll laut Aufgabe nur 0,01 = 1 % betragen, damit ist aber α auf jeden Fall klein und wir erhalten nach Auswertung der Potenz durch die binomische Formel, durch Vernachlässigung aller Terme, die eine mindestens quadratische Potenz von α enthalten, 1 − (1 − α)n ≈ 1 − (1 − nα) = nα. Demnach muss α = 0,01/n = 0,0000001 = 0,00001 % sein!

120

Karamell und Schokolade optimal Andreas Eichhorn

In verschiedenen Situationen in Technik, Wirtschaft oder Politik ist man daran interessiert unter einer Anzahl von möglichen Entscheidungen die jeweils beste auszuwählen, also die optimale Entscheidung zu treffen, die den größtmöglichen Nutzen bringt. In den meisten Fällen sind Nutzen und Entscheidungsalternativen nicht exakt gegeben, Entscheidungen werden dann entweder sprachlichargumentativ ausgewählt und begründet oder gar aus dem Bauch heraus gefällt. In manchen Fällen ist es aber möglich, Entscheidungsalternativen und Nutzen in Zahlen und Formeln so auszudrücken, dass über diese Beschreibung im Prinzip die optimalen Entscheidungen und der maximale Nutzen festgelegt sind. Dabei ist zu beachten, dass bei mehreren (gleichzeitig oder hintereinander) zu treffenden Entscheidungen gewisse Abhängigkeiten zu berücksichtigen sind, bezüglich der möglichen Alternativen. Wenn beispielsweise die Umsetzung einer bestimmten (Teil-)Entscheidung mit bestimmten Kosten verbunden wäre, so stünde dieser Geldbetrag für andere Entscheidungen nicht mehr zur Verfügung. Das Gebiet mathematische Optimierung (oder auch Operations Research in der Ökonomie) befasst sich mit der mathematischen Umsetzung der Optimierung, also mit der Berechnung von optimalen Lösungen (für den Fall, dass die Ausgangssituation und der zu maximierende Nutzen mathematisch beschrieben werden können). Formal geht es also um die Maximierung (oder Minimierung) von mathematischen (Nutzen-)Funktionen, die von vielen Variablen abhängen, unter gewissen Nebenbedingungen (Restriktionen) an diese Variablen, z. B.: maximiere f ( x1 , x2 ) unter der Nebenbedingung, dass 0 ≤ x1 ≤ x2 ≤ a mit irgendeiner festen Zahl a > 0 gilt. Die Variablen x1 , x2 repräsentieren hier die (optimal zu wählenden) Entscheidungen. In den meisten Anwendungsfällen repräsen-

121

Mathematik ganz zufällig

tiert die Nutzenfunktion f einen finanziellen Nutzen (Gewinn oder Kosten), die Mathematik abstrahiert aber von der zu Grunde liegenden Interpretation. So können etwa dieselben Berechnungsmethoden auch für andere Optimierungsmodelle verwendet werden, in denen es beispielsweise darum geht nach einer Naturkatastrophe gewisse Güter so zu verteilen, dass eine maximale Anzahl von Menschenleben gerettet wird. In den allermeisten Anwendungen sind aber nicht alle Randbedingungen exakt bekannt. In manchen Fällen beschränken sich diese Unsicherheiten aber auf bestimmte Parameter (Daten), über die man vielleicht wenigstens statistische Informationen besitzt. In obigem Beispiel könnte beispielsweise die Zahl a ein solcher Parameter sein, dessen Wert man nicht exakt kennt, aber dessen Wahrscheinlichkeitsverteilung aufgrund von empirischen Beobachtungen aus der Vergangenheit bekannt ist. Meistens ist es in solchen Situationen nicht sinnvoll, x2 ≤ a für alle möglichen Werte von a zu fordern, sondern man fordert, dass die Wahrscheinlichkeit, dass x2 ≤ a beispielsweise mindestens 95 % beträgt. Die resultierende Aufgabe ist dann ein Optimierungsproblem mit Wahrscheinlichkeitsrestriktionen. In der Energieversorgung z. B. werden solche Optimierungsansätze auf Problemstellungen der folgender Art angewendet: Zu welchem Zeitpunkt muss man welches Kraftwerk an- oder abschalten, um den Strombedarf eines Versorgungsgebietes so zu decken, dass die Gesamtkosten minimal sind? Dabei werden die Stromproduktionsmengen der Kraftwerke zu verschiedenen Zeitpunkten als Entscheidungsvariablen modelliert. Da das Starten eines Kraftwerkes längere Zeit in Anspruch nimmt, ist etwa der Strombedarf eine Größe, die zum Entscheidungszeitpunkt nicht exakt bekannt ist. Die Einbeziehung der zusätzlichen Möglichkeit Strom und Derivate an der Strombörse zu Handeln macht dieses Anwendungsfeld zu einer interessanten Herausforderung an die Mathematik. Generell führt die Einbeziehung von Wahrscheinlichkeitstheorie und Statistik in die mathematische Optimierung auf das Gebiet der stochastischen Optimierung. Dieses ermöglicht es auch solche Entscheidungspro-

122

Karamell und Schokolade optimal

Abbildung 1. Stromkraftwerk

bleme mathematisch anzugehen, in denen einige Parameter „nur“ statistisch und nicht exakt gegeben sind. Auch die nun folgende Entscheidungssituation fällt in die Problemklasse der Optimierungsprobleme mit Wahrscheinlichkeitsrestriktionen. Die Zahlen dK und dS entsprechen den (nicht exakt gegebenen) Daten, bK und bS entsprechen den Entscheidungen. Ein Mathematiklehrer möchte einer Schulklasse mit 20 Schülern zu seinem Geburtstag als Überraschung Muffins aus seiner (nicht ganz billigen) Lieblingskonditorei spendieren. Er möchte zwei Sorten (Karamell- und Schokoladenmuffins) zur Verfügung stellen, da er weiß, dass Schüler sehr wählerisch sein können. Andererseits ist der Lehrer ein sparsamer Mensch und möchte seine Ausgaben minimal halten. Da die ganze Aktion eine Überraschung sein soll und die Schüler deshalb nicht direkt befragt werden können, fragt der Lehrer beim nächsten Elternabend die Eltern der Schüler, ob deren Kinder lieber Schoko- oder Karamellmuffins mögen. Er erhält überraschenderweise von allen Eltern dieselbe Antwort: „Mein Kind mag, glaube ich, lieber einen Karamellmuffin.“ Allerdings ist sich keiner der Eltern sicher. Der Lehrer weiß aber aus Erfahrung dass

123

Mathematik ganz zufällig

sich die Eltern bei solchen Fragen unabhängig voneinander jeweils mit einer Wahrscheinlichkeit von 0,4 (=40 %) irren. Als die Eltern jedoch von dem Plan des Lehrers hören sind sie ein wenig besorgt darüber, ob bei dieser Aktion alles korrekt und gerecht zugehen wird. Sie einigen sich schließlich mit dem Lehrer auf die folgenden Bedingungen: – Jeder Schüler bekommt genau einen Muffin. – Die Ausgabe der Muffins an die Schüler erfolgt alphabetisch nach Namen. Dabei können sich die Schüler ihren präferierten Muffin aussuchen solange noch beide Sorten vorhanden sind, andernfalls bekommen sie die Sorte die noch übrig ist. – Die Wahrscheinlichkeit, dass alle Schüler ihre bevorzugte Muffinsorte bekommen, muss mindestens 0,98 (=98 %) betragen (basierend auf der Irrtumswahrscheinlichkeit von 0,4). Des weiteren nehmen wir an, dass es keinen Schüler gibt, dem die Sorte egal ist, d. h. jeder Schüler hat eine eindeutige Präferenz. Von der Konditorei bekommt der Lehrer die folgenden Bedingungen: – Ein Karamellmuffin kostet 6 Euro pro Stück, ein Schokoladenmuffin jeweils 4 Euro. – Übriggebliebene Muffins können nicht zurückgegeben werden. Als nächstes muss der Lehrer nun also die Bestellung aufgeben, d. h. er muss sich für eine Anzahl bK von zu bestellenden Karamellmuffins und eine Anzahl bS von Schokomuffins entscheiden. Die Gesamtkosten 6 · bK + 4 · bS sollen dabei unter den gegebenen Bedingungen minimal sein. Mit dieser Aufgabe tut sich der Mathematiklehrer allerdings schwer. Er könnte natürlich, um die 98 %-Vorgabe zu erfüllen, einfach bK = bS = 20 wählen. Damit würden mit Sicherheit alle Schüler zufrieden gestellt, aber die Kosten dafür wären nicht minimal. Hilf ihm, indem Du die (unter diesen Bedingungen) optimalen Bestellmengen bK und bS berechnest! Bemerkungen. Der wirkliche Bedarf an Karamellmuffins dK und an Schokomuffins dS ist zum Bestellzeitpunkt nicht exakt bekannt. Berechne zunächst die Wahrscheinlichkeitsverteilung von dK , d. h. be-

124

Karamell und Schokolade optimal

rechne für i = 0, . . . , 20 die Werte P(dK = i ), wobei P die Wahrscheinlichkeit bezeichnet. Hinweis: Binomialverteilung (siehe Formelsammlung). Stelle eine Formel auf für die in dieser Aufgabe relevante Wahrscheinlichkeit P(bK ≥ dK und bS ≥ dS ), dass alle Schüler ihren Lieblingsmuffin erhalten können. Beachte dabei – Wahrscheinlichkeiten sich gegenseitig ausschließender Ereignisse können additiv zusammen gesetzt werden, z. B. P(dK = i ) + P(dK = i − 1) = P(dK = i oder dK = i − 1)

= P (i − 1 ≤ d K ≤ i ) für i = 1, . . . , 20. – Die Wahrscheinlichkeit aller möglichen Ereignisse beträgt immer 100 %, d. h. z. B. 20

∑ P(dK = i) = P(0 ≤ dK ≤ 20) = 1 .

i =0

– Es gilt immer dK = 20 − dS . Damit kannst Du nun für jede der 400 möglichen Kombinationen für bK , bS die relevante Wahrscheinlichkeit P(bK ≥ dK und bS ≥ dS ) berechnen. Allerdings muss man gar nicht alle Möglichkeiten auswerten. Starte z. B. mit der Kombination bK = bS = 20 und arbeite Dich dann geschickt schrittweise voran! Viel Spaß!

Antwortmöglichkeiten

1. 2. 3. 4. 5.

bK bK bK bK bK

= 20 und bS = 17 und bS = 12 und bS = 20 und bS = 20 und bS

=0 = 13 =8 = 10 =8

6. 7. 8. 9. 10.

125

bK bK bK bK bK

= 16 und bS = 18 und bS = 19 und bS = 16 und bS = 15 und bS

= 13 = 13 = 10 = 14 = 10

Mathematik ganz zufällig

Lösung (Richtige Lösung: Antwort 9) Für jeden der 20 Schüler beträgt die Wahrscheinlichkeit, dass er lieber einen Karamellmuffin möchte 0,6 = 60 %, unabhängig davon, was die anderen präferieren. Dies führt auf eine Binomialverteilung (äquivalentes Urnenmodell, siehe Formelsammlung), d. h. die Wahrscheinlichkeitsverteilung für den Bedarf an Karamellmuffins ist gegeben durch  P(dK = i ) =

 20 · 0,6i · 0,420−i i

für i = 0, . . . , 20. Dies sind Zahlenwerte, die man z. B. mit dem Taschenrechner ausrechnen kann: i

0

1

(20i )

1 1, 0995 · 10−08

20 3, 2985 · 10−07

P(dK = i )

2 190 4, 7004 · 10−06

3 1140 4, 2304 · 10−05

4 4845 2, 6969 · 10−04

... ... ...

(Die Binomialkoeffizienten (20i ) können dabei aus der Formelsammlung entnommen oder mit dem Taschenrechner oder auch über das Pascalsche Dreieck ausgerechnet werden.) Wegen dS = 20 − dK gilt für den Bedarf an Schokomuffins P(dS = i ) = P(dK = 20 − i ) und für die gesuchte Wahrscheinlichkeit ergibt sich P(bK ≥ dK und bS ≥ dS ) = P(bK ≥ dK und bS ≥ 20 − dK )

= P(20 − bS ≤ dK ≤ bK )

126

Karamell und Schokolade optimal

=

bK

∑

i =20−bS

P(dK = i )

 20 · 0,6i · 0,420−i ∑ i i =20−bS 19−bS   20 = 1− ∑ · 0,6i · 0,420−i i i =0   20 20 − ∑ · 0,6i · 0,420−i i i = b +1

=

bK



K

für gegebene Bestellmengen bK und bS . Dabei sei der Wert einer Summe ∑ gleich Null, falls der untere Index größer ist als der obere, 20 i 20−i . also zum Beispiel 0 = ∑20 i =21 ( i ) · 0.6 · 0.4 Nun können die relevanten Kombinationen von Bestellmengen bK und bS bestimmt werden, so dass P(bK ≥ dK und bS ≥ dS ) ≥ 0,98 = 98 %. Dabei kann man ausnutzen dass diese Wahrscheinlichkeit monoton wachsend in der Variablen bK und in der Variablen bS ist. Trivialerweise gilt P(20 ≥ dK und 20 ≥ dS ) = 1 > 0,98. Von dort aus kann man sich an die Lösung „herantasten“, indem man zum Beispiel zunächst bS so lange verringert bis man die zulässigen 98 %-Bereich verlässt. Dafür genügt es jeweils nur einen Wert aus obiger Tabelle zu subtrahieren. Vom letzten zulässigen Punkt für bK = 20 aus (bS = 13) kann man anschließend bK schrittweise verringern usw., mit obiger Formel kommt man damit auf folgende Werte für P(bK ≥ dK und bS ≥ dS ):

127

Mathematik ganz zufällig

bS 20 19 18 17 16 15 14 13 12 .. .

20 1, 00000000 0, 99999999 0, 99999966 0, 99999496 0, 99995266 0, 99968297 0, 99838848 0, 99353412 0, 97897107

bS 20 19 18 17 16 15 14 13 12 .. .

bK 19

18

0, 99349756

0, 99301008

17

16

0, 98992265

0, 98242731 0, 97757296

bK

15 0, 94904805 0, 94904804 0, 94904771 0, 94904301 0, 94900070 0, 94873102 0, 94743652

... ... ... ... ... ... ... ... ...

... ...

Da auch die Kosten 6 · bK + 4 · bS monoton wachsend in bK und in bS sind ist klar, dass nur die folgenden beiden Kombinationen optimal sein können (minimale Kosten): bK = 16 und bS = 14 bzw. bK = 17 und bS = 13. Einsetzen in die Kostenfunktion ergibt dass bK = 16 und bS = 14 die optimale Lösung ist, d. h. der Lehrer muss 16 Karamellmuffins und 14 Schokomuffins bestellen und (nur) 152 Euro dafür bezahlen.

128

Mathematik in Produktion und Logistik

Roboter und Zuckerstangen Heike Siebert

Bei Produktion und Logistik denkt man sofort an Fabriken, Lagerhallen und Gabelstapler und nicht unbedingt an Zellbiologie. Sieht man etwas genauer hin erscheint dieser Gedankensprung jedoch gar nicht mehr so unpassend. In einer lebenden Zelle laufen eine Vielzahl von Produktions-, Transport- und Regulationsprozessen ab. Soll etwa ein gerade verfügbarer Rohstoff abgebaut werden, muss vielleicht ein Signal ein Gen erreichen, das ein geeignetes Enzym kodiert. Die Aktivierung des Gens führt über mehrere Zwischenstationen zur Produktion des Enzyms, das schließlich noch dahin gelangen muss, wo es gebraucht wird. Ist der Bedarf gedeckt, muss wiederum die Enzymproduktion eingestellt werden. Die Frage, wie verschiedene Komponenten biologischer Systeme, z. B. Proteine, Gene, Stoffwechselprodukte, einander beeinflussen und somit die Funktion des Systems gewährleisten, ist Gegenstand der sogenannten Systembiologie. Die betrachteten Zusammenhänge sind oft sehr komplex und sie zu verstehen wird noch erschwert dadurch, dass oft nicht alle Komponenten und Vorgänge in einem System bekannt sind. Mathematische Methoden können helfen, die vorhandene Information systematisch zu erfassen und zu analysieren. In einem ersten Schritt kann man Komponenten und Interaktionen des Systems als einen gerichteten Graphen darstellen. Dieser repräsentiert die Struktur eines Systems, gibt aber noch keine Auskunft darüber, wie sich das System verhält. Dazu muss man beschreiben, nach welchen Regeln sich die Komponenten gegenseitig beeinflussen, z. B. welche Substanzen vorliegen müssen, damit eine bestimmte Reaktion ablaufen und eine neue Substanz erzeugt werden kann. Wenn man genaue Informationen aus Experimenten zur Verfügung hat, etwa wie sich die Konzentrationen von Sub-

131

Mathematik in Produktion und Logistik

stanzen verändern und wie die beteiligten Prozesse chemisch und physikalisch aussehen, kann man sehr genaue Modelle bauen. Dafür werden meistens Differentialgleichungssysteme verwendet. Hat man jedoch nur sehr grobe Informationen, so bietet es sich an, eine diskrete Funktion zur Beschreibung des Systems zu verwenden. Im einfachsten Fall nimmt man an, jede Komponente kann den Wert 0 oder 1 annehmen. So würde etwa einem Gen der Wert 0 zugeordnet werden, wenn es inaktiv ist. Der Wert wird auf 1 gesetzt, wenn es aktiviert wird. Für Stoffwechselprodukte kann der Wert 1 eine hohe, der Wert 0 eine niedrige Konzentration der Substanz bedeuten. Weist man jeder Komponente des Systems einen Wert zu, erhält man einen Vektor, der den Zustand des Systems beschreibt. Mittels einer Funktion kann man nun die Regeln, nach denen sich die Komponenten des Systems gegenseitig beeinflussen, beschreiben. So wird festgelegt wie sich der Zustand eines Systems ausgehend von einem Startzustand verändert. Durch wiederholtes Anwenden der Funktion können wir simulieren, wie das System sich über einen gewissen Zeitraum hinweg verhalten wird. Oft ist es von Interesse, ob das System bestimmte Aufgaben erfüllen kann, etwa ob ein bestimmtes Gen exprimiert wird. Simulation und Analyse des mathematischen Modells, also des Graphen und der Funktion, geben Hinweise darauf, ob die Vorstellung, die man vom Aufbau des Systems hat, mit den experimentellen Beobachtungen übereinstimmt. Oft liefern sie neue Ansatzpunkte für die Gestaltung von Experimenten im Labor, die zu einem besseren Verständnis des Systems führen können. Die Aufgabe, ein (vielleicht unvollständig beschriebenes) System zu modellieren und sein Verhalten zu analysieren, ist zentral für Mathematiker, die in der Systembiologie arbeiten. Die Werkzeuge und Methoden, die man dafür entwickelt, können aber wiederum sehr vielseitig eingesetzt werden, nicht zuletzt auch für Problemstellungen, die sich um Fabriken, Lagerhallen und Gabelstapler drehen. Heinrich Drögel ist erfolgreicher Unternehmer. Er macht sein Geld mit Zuckerstangen, die er beutelweise auf Jahrmärkten ver-

132

Roboter und Zuckerstangen

kauft. Er versucht immer auf der Höhe der Zeit zu sein, deswegen hat er sich für einfache Aufgaben robotische Hilfe beschafft. Die Roboter sollen Papiertüten mit Zuckerstangen befüllen. Die Roboter stehen dazu in einer Schlange hintereinander. Ganz vorne ist eine Tüte, die zu befüllen ist. Alle Roboter schauen Richtung Tüte, d. h. in die gleiche Richtung. Das Befüllen selbst funktioniert wie folgt: – Jede Minute führen die Roboter folgende Aktionen gleichzeitig aus: Wenn sie eine Zuckerstange in der Hand haben, geben sie sie an den Roboter vor ihnen in der Schlange weiter, der sie natürlich auch annimmt, oder, wenn sie ein Roboter vor der Tüte sind, stecken sie die Zuckerstange in die Tüte. – Jeder Roboter kann sowohl gleichzeitig eine Zuckerstange vom Hintermann annehmen als auch seine, die er in der Hand hält (also in der vorherigen Minute erhalten hat), weitergeben oder in die Tüte stecken. Von dieser Sorte sogenannter Transportroboter hat Heinrich Drögel 14 Stück erworben. Zusätzlich hat er sich noch zwei Multifunktionsroboter, Robbi und Tobbi, geleistet. Wenn diese beiden in Betrieb sind, produzieren sie jede Minute eine Zuckerstange und geben die eine Minute vorher produzierte Zuckerstange an den vor ihnen stehenden Roboter weiter. Wohlwollend beobachtet von Heinrich Drögel stehen die Roboter in zwei geordneten, jeweils von Robbi und Tobbi ausgehenden Reihen und befüllen Tüten, als plötzlich das Telefon klingelt. Drögel erwartet einen wichtigen Anruf, und so stürmt er rücksichtslos Richtung Telefon und wirbelt dabei alle Roboter durcheinander. Sie rappeln sich wieder auf, laufen verwirrt durcheinander und kommen schließlich in einer neuen Anordnung zur Ruhe. Robbi, Tobbi und 8 weitere Roboter stehen in einem Kreis, in dem alle Roboter in Uhrzeigerrichtungssinn blicken. Unter den Transportrobotern, die in dem Kreisbogen stehen, der von Robbi zu Tobbi führt, gibt es drei Roboter, die nicht nur einen Roboter vor sich zu stehen haben, sondern auch einen in Reichweite neben

133

Mathematik in Produktion und Logistik

R

T Abbildung 1. Schematische Darstellung des neuen Aufbaus

sich. D. h. hier zweigen insgesamt 3 Schlangen vom Kreis ab. Jede dieser 3 Schlangen endet vor einer leeren Tüte. Robbi und Tobbi haben bei dem Unfall ihre Produktion gestoppt, und fast alle Roboter haben ihre Zuckerstangen verloren, nur Tobbi und drei Transportroboter haben noch eine in der Hand. Diese drei Transportroboter stehen alle in dem Teil des Kreisbogens, der von Tobbi zu Robbi führt. Wie sich die verbleibenden Roboter, die nicht im Kreis stehen, auf die drei abzweigenden Schlangen aufteilen, ist unklar. Man weiß nur, dass alle wieder mitarbeiten. Abbildung 1 gibt einen Überblick über die prinzipielle neue Anordnung. wobei R für Robbi und T für Tobbi stehen. In dieser neuen Situation beginnen die Roboter wieder ihre Arbeit, d. h. nach jeder Minute sollten sie die oben beschriebenen Aktionen ausführen. Aber die neue Anordnung verwirrt einige Roboter und führt bei manchen zu einer Funktionsänderung. Jeder Roboter, der einen Roboter vor sich und einen neben sich stehen hat, ändert seine jede Minute stattfindende Weiterreichaktion, so er denn eine Zuckerstange zum Weiterreichen hat, folgendermaßen: Er bricht die Zuckerstange durch und reicht jedem der beiden eine Hälfte. Ein Teil einer Zuckerstange wird von allen Robotern wie eine ganze Zuckerstange behandelt.

134

Roboter und Zuckerstangen

Robbi und Tobbi sind begeistert, wenn ihnen eine Zuckerstange gereicht wird. Sie essen sie mit einem Biss auf und vergessen darüber in derselben Minute, in denen ihnen die Stange gereicht wird, eine neue Stange zu produzieren, reichen aber, falls sie eine Minute vorher eine produziert haben, diese trotzdem brav weiter. In der Minute nach jedem Schmaus produzieren sie wieder, es sei denn, sie bekommen erneut einen Stange gereicht. In der ersten Minute reicht Tobbi die Zuckerstange, die er nach dem Sturz noch in der Hand hat, weiter und produziert gleichzeitig eine neue. 32 Minuten nachdem die Roboter ihre Arbeit wieder aufgenommen haben, kommt Heinrich Drögel zurück und prüft, ob die Tüten fertig befüllt sind. In jeder Tüte sollen mindestens drei Zuckerteile sein, wobei Drögel es nicht so genau nimmt, ob ein Zuckerteil nun eine ganze oder nur ein Stück einer Zuckerstange ist. Wie viele der drei Tüten können fertig befüllt sein?

Antwortmöglichkeiten 1. 2. 3. 4. 5. 6. 7. 8. 9. 10.

Es sind alle Tüten fertig befüllt, egal wie die Roboter stehen. Es sind genau zwei oder genau drei Tüten fertig befüllt. Nur eine Tüte ist fertig befüllt, egal wie die Roboter stehen. Genau eine Tüte ist fertig befüllt oder genau drei Tüten sind fertig befüllt. Es sind alle oder keine der Tüten fertig befüllt. Genau eine Tüte oder genau zwei oder genau drei Tüten sind fertig befüllt. Es ist keine oder genau eine der Tüten fertig befüllt. Alle oder genau zwei oder keine der Tüten sind fertig befüllt. Es sind genau zwei Tüten fertig befüllt, egal wie die Roboter stehen. Es ist keine der Tüten fertig befüllt, egal wie die Roboter stehen.

135

Mathematik in Produktion und Logistik

Lösung (Richtige Lösung: Antwort 8) Zunächst besteht die Schwierigkeit darin, dass wir nicht genau wissen, wie sich die Roboter aufgestellt haben. Wir wissen, dass zehn Roboter einen Kreis bilden und die anderen sechs sich auf drei Schlangen aufteilen. Da die drei Schlangen von Transportrobotern in der Schlange von Robbi zu Tobbi abzweigen, stehen in dieser also mindestens drei Transportroboter. Weiter haben drei Transportroboter Zuckerstangen in der Hand und stehen in der Schlange zwischen Tobbi und Robbi. Sechs Transportroboter teilen sich auf drei Schlangen auf, also haben wir die möglichen Aufteilungen 1, 1, 4 oder 1, 2, 3 oder 2, 2, 2 auf die drei Schlangen. Die Zuckerstangen oder Zuckerstangenstücke, die die Tüten befüllen, werden alle von Robbi produziert, da die von Tobbi produzierten schließlich an Robbi weitergegeben werden und der sie aufisst. Wir müssen also herausfinden, ob und mit welcher Frequenz Robbi Zuckerstangen produziert und dann überlegen, wie lange es dauert bis die produzierten Stangen oder Stücke davon die Tüten erreichen. Wir nummerieren die Roboter, die im Kreis stehen von 1 bis 10 durch, wobei Tobbi die 1 bekommt. Nun basteln wir eine Funktion xi für jeden der Roboter, so dass xi (t) = 0 gilt, falls Roboter i in der t-ten Minute keine Stange weiterreicht, und xi (t) = 1, falls Roboter i in der t-ten Minute eine Stange weiterreicht. Für jeden Transportroboter j gilt x j (t + 1) = x j−1 (t) für t = 2, 3, . . . und der Wert x j (1) hängt davon ab, ob Roboter j in der Anfangsaufstellung eine Stange in der Hand hat oder nicht. Für Tobbi gilt x1 (t + 1) = 1 − x10 (t) für t = 2, 3, . . . und x1 (1) = 1 , und für Robbi, der eine Nummer 4 < r < 8 hat, gilt xr (t + 1) = 1 − xr−1 (t) für t > 1 und xr (1) = 0 ,

136

Roboter und Zuckerstangen

da beide nur produzieren, wenn ihr Vorgänger ihnen keine Zuckerstange reicht, und sie immer die eine Minute vorher produzierte Stange weiterreichen. Betrachten wir zuerst den Fall, dass zwischen Tobbi und Robbi nur die drei Transportroboter mit der Zuckerstange in der Hand stehen, d. h. Robbi hat die Nummer 5 und wir wissen   x1 (1), . . . , x10 (1) = (1, 1, 1, 1, 0, 0, 0, 0, 0, 0). Anwendung der oben bestimmten Funktionsregeln ergibt   x1 (2), . . . , x10 (2) = (1, 1, 1, 1, 0, 0, 0, 0, 0, 0), d. h. die Situation in Bezug auf das Stangenweitergeben ändert sich nicht. Tatsächlich ändert sich der Vektor und insbesondere der Wert x5 (t) = 0, der beschreibt, ob Robbi eine Stange weitergeben kann, nie. Unser Anfangswert ist ein Fixpunkt. Es bleiben also alle drei Tüten leer, egal wie lange Drögel zum Telefonieren braucht. Damit können nur die Lösungsvorschläge 5, 7, 8 und 10 richtig sein. Als nächstes überlegen wir, welche Anordnung zu einem Befüllen der Tüten führt und für welche unter diesen Anordnungen das Befüllen am langsamsten vonstatten geht. Wir nehmen nun an, dass mindestens einer der Roboter in der Schlange von Tobbi zu Robbi anfangs keine Stange hat. Wir überlegen uns zunächst, dass Robbi alle zehn Minuten so viele Zuckerstangen produziert wie Transportroboter ohne Zuckerstange in der Schlange von Tobbi zu Robbi in der Anfangsaufstellung stehen. Der Ablauf in 10 Minuten sieht wie folgt aus: xr (1) = 0, x r (2 ) = 1 − x r −1 (1 ), x r (3 ) = 1 − x r −2 (1 ), .. . x r ( k + 1) = 1 − x2 (1), xr ( k + 2) = 1 − x1 (1),

137

Mathematik in Produktion und Logistik

wobei k die Anzahl der Transportroboter ist, die in der Schlange von Tobbi zu Robbi stehen. Da x1 (t + 1) = 1 − x10 (t), erhalten wir weiter:   xr (k + 3) = 1 − 1 − x10 (1) = x10 (1),   x r ( k + 4) = 1 − 1 − x9 (1) = x9 (1), .. .

  x r ( k + 2 + l ) = 1 − 1 − x r +1 (1 ) = x r +1 (1 ), wobei l die Anzahl der Transportroboter in der Schlange von Robbi zu Tobbi ist, also k + 2 + l = 10. Wir wissen, dass xi (1) = 0 für r < i ≤ 10 . Nur die Roboter i mit 1 < i < r und xi (1) = 0 führen dazu, dass Robbi in den ersten 10 Minuten eine Stange weitergibt. Wenn wir jetzt noch einen Schritt weitergehen, sehen wir, dass xr (11) = xr (1). Auf die gleiche Art können wir zeigen, dass xi (1) = xi (11) für alle Roboter im Kreis, und noch genauer xi (1) = xi (1 + m · 10) für m = 1, 2, . . . Also, produziert Robbi alle zehn Minuten so viele Zuckerstangen wie Transportroboter ohne Zuckerstange in der Schlange von Tobbi zu Robbi in der Anfangsaufstellung stehen. Jetzt können wir noch ausrechnen, wie lange es im schlimmsten Fall dauert, eine Tüte zu befüllen. Die Zuckerstangenproduktion von Robbi geht am langsamsten, wenn nur ein Roboter ohne Zuckerstange in der Schlange von Tobbi zu ihm steht. Also stehen insgesamt vier Roboter in dieser Schlange. Je weiter der Roboter ohne Stange von Robbi entfernt steht, desto länger dauert es, bis Robbi

138

Roboter und Zuckerstangen

mit der Produktion beginnt. Deshalb nehmen wir an, er steht direkt vor Tobbi, d. h. er hat die Nummer 2. Wenn Robbi eine Zuckerstange produziert, muss diese, oder Stücke davon, ja noch weiter gereicht werden. Je mehr Roboter also zwischen Robbi und einer zu befüllenden Tüte stehen, desto länger dauert es bis diese gefüllt ist. Da vier Roboter in der Schlange von Tobbi zu Robbi stehen, stehen auch vier in der Schlange von Robbi zu Tobbi. Um den längsten möglichen Weg von Robbi zu einer Tüte zu bekommen, muss also die längste mögliche Schlange (wie wir oben gesehen haben, hat diese die Länge 4) von dem letzten Roboter in der Schlange von Robbi zu Tobbi (Nummer 10) abzweigen. Wir nummerieren diese Roboter 11, 12, 13 und 14. Insgesamt stehen dann 8 Roboter zwischen Robbi und dem Strumpf am Ende dieser Schlange. In diesem Szenario produziert Robbi in der vierten Minute eine Stange, da der Roboter hinter ihm in der vierten Minute keine Stange weiterreicht. Die Stange reicht Robbi in der fünften Minute weiter, d. h. x6 (5) = 1. Die Stange oder Teile davon werden jede Minute weitergereicht, d.h. x10 (9) = 1 und schließlich x14 (13) = 1. Das bedeutet, dass der Roboter mit Nummer 14 in der 13. Minute das erste Stangenstück in die Tüte steckt. Nun haben wir schon gezeigt, dass sich jede Situation alle 10 Minuten wiederholt. Also wird das zweite Stangenstück in der 23. und das dritte in der 33. Minute in die Tüte gesteckt. Heinrich Drögel unterbricht aber nach 32 Minuten, also sind erst zwei Stücke im Sack. Da alle anderen Wege von Robbi zu den verbleibenden zwei Tüten kürzer sind, sind diese fertig befüllt. In dieser Situation haben wir also genau zwei fertige Tüten. Für jede andere Möglichkeit einer Anfangsaufstellung der Roboter – wir nehmen immer noch an, dass mindestens ein Roboter ohne Stange in der Schlange von Tobbi zu Robbi steht – gilt, dass es weniger als 13 Minuten dauert, bis jede Tüte ein Stangenstück enthält. Da sich jede Situation alle zehn Minuten wiederholt, dauert es also immer weniger als 33 Minuten bis jede Tüte fertig gefüllt ist. Damit ist Antwort 8 richtig.

139

Die Welt des Herrn Kuhn Daniela Kern

Eines Morgens erwachte Herr Kuhn fröstelnd und staunte darüber, dass es in seiner Wohnung eiskalt war. Dennoch quälte er sich aus seiner kuscheligen Bettdecke heraus und schlurfte ins Bad. „Hoffentlich wird wenigstens das Wasser warm“, dachte er sich, als er den Wasserhahn betätigte – aber es kam nicht nur kein warmes Wasser, außer einem unheilvollen Gluckser kam gar nichts aus der Leitung. „Dann werde ich wohl mal den Klempner anrufen“, sprach er sich leise in den Bart und griff zu seinem Handy – doch das Netz war tot! Herr Kuhn begann nun, sich ernsthaft Sorgen zu machen, „Oje, was ist denn heute nur los? Ist irgendetwas Schlimmes passiert?“ Um einen besseren Überblick über die Lage zu bekommen und sich austauschen zu können, brannte er nun förmlich darauf, rauszugehen und zur Arbeit zu fahren. An anderen Tagen, die er frisch geduscht und mit Kaffee und Marmeladen-Brot begann, war er selten so motiviert. So ging er also nun mit leerem Magen aus dem Haus. Hätte er den Versuch unternommen, sein tägliches Marmeladenbrot zuzubereiten, und dafür den Kühlschrank geöffnet, um das Marmeladenglas herauszunehmen, wäre ihm aufgefallen, dass auch die Stromversorgung Störungen unterworfen war, unschön zu erkennen an den ersten grünen, felligen Inseln auf seinem Lieblingskäse. Draußen auf der Straße liefen viele Menschen umher und auch Autos fuhren herum, die Zivilisation war also doch noch nicht ganz verloren. Allerdings auch hier stimmte etwas nicht: an den Kreuzungen gab es wildes Gehupe und Geschrei, da die Ampelanlage der weit weniger befahrenen Ost-West-Achse längere Grünphasen gewährten als der vom Berufsverkehr gebeutelten Nord-Süd-Straße. Zusätzlich verstopften Busse mit sehr unterschiedlich starken Fahrgastzahlen die Durchfahrt, während an manchen Bushaltestellen empörte Fahrgäste offensichtlich schon sehr lange auf „ihren“ Bus warteten. Glücklicherweise hatte Herr Kuhn es nicht weit zu seiner Arbeitsstätte und darum ging er nun einfach zu Fuß und schlängelte

141

Mathematik in Produktion und Logistik

sich durch die Engstellen. In seinem Büro angekommen, befragte er die Kollegen, ob sie eine Erklärung für die Vorkommnisse hatten. Der Mathematiker Albert klärte auf, dass die Versorgungsnetze für Wasser, Strom etc. nicht lahmgelegt, sondern lediglich überfordert waren, da die optimierten Steuerungspläne gegen alte Pläne ausgetauscht worden waren. Ebenso verhielt es sich bei den Busfahrplänen und der Ampelsteuerung. „Die Ursache für das Verwenden der nicht-optimierten Pläne ist noch völlig ungeklärt, vielleicht haben sich ein paar unbezahlte Praktikanten einen Streich erlaubt. Ab morgen soll der Betrieb aber wieder normal laufen.“ Da auch in den Büros alles sehr langsam und schleppend lief, ging Herr Kuhn an diesem Tag bereits Mittags nach Hause. Dort angekommen legte er sich einfach gleich ins Bett, um den Rest dieses Tages einfach zu verschlafen, was ihm in dieser Situation die beste Lösung erschien. Herr Kuhn tut sich schwer, wenn nicht alles reibungslos klappt. Dabei ist es eigentlich ein Wunder, dass unsere komplizierten Versorgungsstrukturen doch normalerweise ziemlich gut funktionieren. Bieten neue Technologien, globalisierte Märkte und gutvernetzte Transportwege zwar großes Potential für Fortschritt und Wohlstandsmehrung, so bedarf es aber auch großen Analyse- und Planungsaufwands, um diese Strukturen auch tatsächlich gewinnbringend zu nutzen. Um dies zu gewährleisten, wird unter anderem die mathematische Optimierung bemüht. Komplizierte Probleme mit vielen Nebenbedingungen, wie z. B. das Aufstellen eines guten Busfahrplans, die Planung der Energie-Erzeugung in einem Kraftwerk, oder die Logistik an einem Verladehafen sind kaum ohne die Hilfe einer systematischen Herangehensweise zu meistern. Doch nicht nur in Fragen der Infrastruktur sind mathematische Optimierungsmethoden gut zu gebrauchen. Auch in der Entwicklung oder Verbesserung von Produkten und modernen Materialien, im Finanzwesen und in unzähligen anderen Bereichen wird viel Mathematik und Optimierung eingesetzt. Bei der mathematischen Optimierung handelt es sich aber nicht um eine einheitliche Theorie, da die Bedingungen der verschiedenen Anwendungen sehr unterschiedlich sind.

142

Die Welt des Herrn Kuhn

Abbildung 1. Moderne Produktion: Kooperierende Roboter bei der Arbeit (INVISION-Simulation, WIAS Berlin)

Durch das Umsetzen physikalischer Gesetzmäßigkeiten in mathematische Formeln und das Finden von Lösungsstrategien für die entstehenden komplexen Gleichungssysteme lassen sich Prozesse in Natur, Technik und Produktion annähernd abbilden. Auf diese Weise kann man diese Prozesse zum Gegenstand mathematischer Optimierung machen. Mögliche Fragestellungen lauten zum Beispiel: – Wie härte ich Stahl so, dass das Material möglichst wenig Schaden erleidet und sich mit Eigenschaften wie Form und Belastbarkeit gut in einer Gesamt-Apparatur verarbeiten lässt? – Welche Bahn muss ein Schweiss-Roboter in der Automobil-Herstellung fahren, so dass keine fehlerhaften Schweissnähte entstehen, aber die Fertigung dennoch zügig vonstattengehen kann? Bei diesen Anwendungen hat man es mit Bedingungen in Form partieller Differentialgleichungen zu tun. Die Lösung solcher Gleichungen stellt für sich bereits eine Herausforderung dar, häufig kann man eine Lösung nur näherungsweise mit dem Computer ermitteln und auch dies ist manchmal schwierig oder sogar unmöglich. In der Verkehrsoptimierung hingegen behandelt man unter anderem Probleme mit einer Ganzzahligkeitsbedingung, die große Hürden aufwirft, da die Standardmethoden der Analysis wie das

143

Mathematik in Produktion und Logistik

Ausnutzen von Aussagen über die Ableitungen nicht unmittelbar eingesetzt werden können. Für das Lösen der auftretenden Gleichungen müssen raffinierte Algorithmen eingesetzt werden. Bei Situationen hingegen, bei denen viele verschiedene menschliche Interessengruppen agieren, z. B. auf dem Finanz- oder Energiemarkt, hat man es oft mit stochastischen Unwägbarkeiten zu tun und muss darum Methoden der Wahrscheinlichkeitstheorie in die Optimierung einbinden. Man könnte die Liste der Problemarten noch fortsetzen, den meisten Optimierungsaufgaben ist aber gemeinsam, dass ein Wert (die Auswertung einer „Zielfunktion“ bezüglich gewisser Prozess-Variablen) unter Nebenbedingungen minimiert oder maximiert werden soll. Unter den Problemklassen der Optimierung mit ihren jeweiligen Lösungsmethoden gehört die der Linearen Optimierung zu den am besten erforschten. Zudem ist sie der Intuition noch sehr gut zugänglich. Man begegnet ihr in vielen Bereichen, z. B. in der Produktionsplanung, beim Routing in Telekommunikations- und Verkehrsnetzen und in der Spieltheorie. Da man linearen Optimierungsproblemen einerseits häufig begegnet, sie sich andererseits aber auch relativ einfach lösen lassen, soll im Folgenden eine solche Aufgabe untersucht werden: Eine kleine Saftfabrik produziert Orangen- und Apfelsaft. Der Orangensaft bringt 0,30 Euro Gewinn pro Flasche, der Apfelsaft 0,20 Euro. Die Obstlieferanten können Orangen für maximal 300 Flaschen Orangensaft und Äpfel für maximal 700 Flaschen Apfelsaft pro Tag liefern. Die Produktionskapazität bei Beschränkung auf eine Saftsorte beträgt 500 Flaschen Orangensaft oder 1000 Flaschen Apfelsaft pro Tag (d. h. in der Zeit, die gebraucht wird, 500 Flaschen Orangensaft herzustellen, können 1000 Flaschen Apfelsaft produziert werden; in der gegebenen Zeit aber höchstens 500 Flaschen Orangensaft beziehungsweise höchstens 1000 Flaschen Apfelsaft, würde sich die Fabrik auf eine Sorte beschränken). Beide Säfte werden in die gleichen Flaschen abgefüllt (lediglich anders etikettiert), insgesamt stehen pro Tag 800 dieser Flaschen zur Verfügung. Der Safthersteller möchte natürlich seinen Gewinn maximieren –

144

Die Welt des Herrn Kuhn

welche Produktionsstrategie sollte er wählen? (Nicht zu vergessen: natürlich kann der Safthersteller keine negativen Mengen produzieren.) Eigentlich ist es noch sinnvoll, eine Ganzzahligkeitsbedingung zu fordern (z. B. keine halben Flaschen), da dies dann aber zur schwierigeren Klasse der ganzzahligen Optimierung führen würde, möge darüber hinweggegangen werden. Zusatzfrage: kann er seinen Gewinn vergrößern, wenn er statt in Flaschen in Tetra-Paks abfüllt, von denen er unbegrenzt viele einsetzen kann?

Antwortmöglichkeiten Die gewinnbringendste der zulässigen Produktionsstrategien ist die Herstellung von . . . 1. 350 Flaschen Orangensaft. 2. 700 Flaschen Apfelsaft, kein Orangensaft. 3. 800 Flaschen Orangensaft, kein Apfelsaft. 4. Es gibt zwei gewinn-optimale Möglichkeiten, nämlich die Herstellung von 700 Flaschen Apfelsaft und 100 Flaschen Orangensaft oder 300 Flaschen Orangensaft und 400 Flaschen Apfelsaft. 5. Es gibt unbegrenzt viele Möglichkeiten, den optimalen Gewinn von 18 Euro zu erwirtschaften. 6. 320 Flaschen Orangensaft und 480 Flaschen Apfelsaft bei einem Gewinn von 19,20 Euro. 7. 320 Flaschen Orangensaft und 480 Flaschen Apfelsaft bei einem Gewinn von 20,80 Euro. 8. 200 Flaschen Orangensaft und 600 Flaschen Apfelsaft. 9. Die Kleinstfabrik kann einen optimalen Gewinn von 19 Euro pro Tag erwirtschaften. 10. Bei Verwenden von Tetra-Paks besteht die optimale Lösung darin, 300 mit Orangensaft und 400 mit Apfelsaft zu befüllen, was einen Gewinn von 17 Euro einbringt.

145

Mathematik in Produktion und Logistik

Lösung (Richtige Lösung: Antwort 8) Es gibt verschiedene Möglichkeiten, den Aufgabentyp zu lösen, hier wird die Lösung an einer Graphik (Abbildung 2) veranschaulicht. An der x-Achse ist die Anzahl von Orangensaftflaschen, an der y-Achse die der Apfelsaftflaschen aufgetragen. Da die Anzahl der Saftflaschen nicht negativ sein kann, betrachten wir nur den ersten Quadranten, also nur den Bereich des Koordinatensystems, in dem x ≥ 0 und y ≥ 0 gilt. Die in der Aufgabenstellung formulierten Beschränkungen sind in der Abbildung eingezeichnet und entsprechend beschriftet. Die Beschränkung „zur Verfügung stehende Orangen“ beispielsweise wirkt nur auf die Produktion des Orangensafts und definiert somit einen Abschnitt auf der x-Achse. Links der Linie ist die Beschränkung erfüllt, rechts davon nicht mehr. Analog verhält es sich mit der Beschränkung „zur Verfügung stehender Äpfel“, hier wird entsprechend ein Abschnitt auf der y-Achse spezifiziert. Die Beschränkung „Kapazität“ betrifft die Produktion beider Saftsorten. Würde man sich auf eine Sorte beschränken, könnte man 1000 Flaschen Apfelsaft herstellen, entsprechend beginnt die Linie bei ( x, y) = (0, 1000) (kein Orangensaft, 1000 Flaschen Apfelsaft). Umgekehrt kann man 500 Flaschen Orangensaft produzieren, wenn man auf Apfelsaft verzichtet. Also geht die Linie auch durch den Punkt ( x, y) = (500, 0). Es besteht ein proportionaler Zusammmenhang zwischen den jeweiligen Produktionskapazitäten der beiden Saftsorten – für die Herstellung einer Flasche Orangensaft wird soviel Zeit wie für die zweier Flaschen Apfelsaft benötigt, die Punkte (0, 1000) und (500, 0) werden somit durch eine Linie verbunden. Ähnlich verhält es sich mit den Flaschen. Es stehen 800 Flaschen zur Verfügung, also ist die Anzahl der Saftflaschen durch 800 beschränkt, x + y ≤ 800. Auf der mit „Flaschen“ beschrifteten Linie gilt genau x + y = 800. Links der Linie ist die Bedingung erfüllt, rechts davon nicht.

146

Die Welt des Herrn Kuhn

Abbildung 2. x: Orangen, y: Äpfel

Die Gesamtheit der Beschränkungen definiert den zulässigen Bereich, also die Werte ( x, y), die sich auch tatsächlich unter den gegebenen Beschränkungen (wie z. B. die limitierte Anzahl des jeweiligen Obsts) realisieren lassen. Der zulässige Bereich für die Originalaufgabe ist gelb eingefärbt; verzichtet man auf die FlaschenBeschränkung, kommt zu dem gelben noch der cyanblaue (hellblaue) Bereich dazu. Der optimale Gewinn wird bei einem Paar ( x, y) dieser zulässigen Produktionszahlen angenommen. Neben den Beschränkungslinien sind in der Abbildung 2 noch zwei Niveaulinien eingezeichnet. (Diese sind mit kleinen senkrecht stehenden Pfeilen versehen, deren Bedeutung weiter unten erläutert wird.) Entlang einer solchen Niveaulinie nimmt der Gewinn als Funktion f ( x, y) (der erzielte Gewinn bei Herstellung von x Flaschen Orangensaft und y Flaschen Apfelsaft) konstant den gleichen Wert an. So geht z. B. die links unten eingezeichnete Niveaulinie durch ( x, y) = (0, 300) und

147

Mathematik in Produktion und Logistik

( x, y) = (200, 0). In diesen beiden Punkten und auch auf allen anderen Punkten dieser Linie gilt f ( x, y) = 600, der Gewinn beträgt dort auf allen Punkten der Linie also 600 Euro. Auf der Niveaulinie oben rechts, die durch die Punkte ( x, y) = (0, 900) und (600, 0) geht, beträgt der Gewinn 1800 Euro. Man könnte noch beliebig viele weitere Niveaulinien einzeichnen, zu jedem Gewinn-Betrag eine. Alle diese Niveaulinien wären parallel zu den beiden eingezeichneten. Die kleinen Pfeile an den beiden exemplarischen Niveaulinien deuten die Richtung der Gewinnerhöhung: in Pfeilrichtung wird der Gewinn immer größer. Zieht man nun ein Lineal in Pfeilrichtung (bzw. parallel zu den eingezeichneten Niveaulinien) über das Bild, dann entspricht die Linealkante also zu jedem Zeitpunkt des Darüberziehens selber einer solchen Niveaulinie, entlang derer der Wert der Gewinnfunktion gleichbleibend (konstant) ist. Fügt man nun noch die Informationen zusammen, dass der Gewinn in Pfeilrichtung steigt und dass die Produktionszahlen, also ( x, y), im zulässigen (den Beschränkungen genügenden) Bereich liegen muss, erhält man, dass wir dann den höchsten erreichbaren Gewinn haben, wenn wir das Lineal solange in Pfeilrichtung über das Bild schieben, bis die Linealkante noch den zulässigen Bereich berührt, aber bereits auf seinem Rand liegt. Die Niveaulinie oben rechts entspricht genau dem Beschriebenen: sie berührt den zulässigen Bereich gerade noch und liegt am äußersten Punkt in Pfeilrichtung. Der Gewinn entlang dieser Niveaulinie beträgt 18 Euro, insbesondere auch in dem zulässigen Punkt, der auf dem Rand des zulässigen Bereich liegt und durch den die Nivaulinie gezogen ist. Dieser Punkt hat die Koordinaten (200, 600). Der maximale Gewin wird also bei Produktion von 200 Flaschen Orangensaft und 600 Flaschen Apfelsaft erreicht und beträgt 18 Euro. Ließe man die Flaschen-Beschränkung weg, könnte man „das Lineal“ noch weiter in Pfeilrichtung in den cyanblauen Bereich ziehen und gelangte zum Punkt (300, 400), wo der Gewinn – da wir uns in Pfeilrichtung bewegen – noch höher ist als 18 Euro, nämlich 18,50 Euro.

148

Die Welt des Herrn Kuhn

Eine alternative Vorgehensweise Man kann beweisen (oder sich wie oben an den Niveaulinien anschaulich klarmachen), dass der maximale Gewinn an einer Ecke des zulässigen Bereichs realisiert wird. (Manchmal auch an einer ganzen Kante, also sogar an 2 Ecken und den unendlich vielen Punkten dazwischen, wenn man auch nicht-ganzzahlige Mengenangaben zulässt. Die Forderung nach Ganzzahligkeit ist in der Aufgabe aber sowieso explizit ausgeschlossen, denn sonst wäre auch der oben beschriebene Lösungsweg nicht korrekt. Dass die optimale Lösung ( x, y) = (200, 600) ganzzahlig herauskommt, ist „eingefädelter Zufall“, d. h. durch gute Wahl der Zahlen in der Aufgabenstellung herbeigeführt.) Da die optimale Lösung also an einer Ecke gefunden werden kann, muss man nur die jeweils erzielten Gewinne an den Ecken vergleichen. Der höchstmögliche Gewinn unter den Ecken ist auch gleichzeitig der höchste der ganzen Aufgabe. Die an den Ecken erzielten Gewinne sind im Folgenden aufgelistet. Auch hier sieht man, dass es am gewinnträchtigsten ist, 600 Flaschen Apfelsaft und 200 Flaschen Orangensaft zu produzieren. Ecke Nr. 1 2 3 4 5

x Anz. Orangensaft

y Anzahl Apfelsaft

300 300 200 100 0

0 400 600 700 700

Gewinn in Euro 9 17 18 17 14

Den höchsten Gewinn erzielt man bei Ecke 3, nämlich 18 Euro. Lässt man die durch die Flaschen gegebene Beschränkung weg, entfallen Ecken 3 und 4, statt dessen erhält man noch eine Ecke X: Ecke Nr. X

x Anz. Orangensaft

y Anzahl Apfelsaft

150

700

149

Gewinn in Euro 18,50

Mathematik in Produktion und Logistik

Tatsächlich erhält man ohne die Flaschen-Beschränkung einen höheren Gewinn, dieser beträgt aber 18,50 Euro und nicht 17 Euro wie im Lösungsvorschlag.

150

Arvin, Berit und die Lastwagen Falk Ebert und Anita Liebenau

Die Aufgabe hat ihren mathematischen Hintergrund in einer Problemstellung, die sich Modellreduktion nennt. Dabei geht es darum, große mathematische Probleme so umzuformulieren, dass sie mit möglichst wenig Unbekannten auskommen. Das hat den Vorteil, dass diese Aufgaben für einen Computer schneller lösbar sind und weniger Speicherplatz verbrauchen. Unter Umständen nimmt man für so einen Gewinn an Geschwindigkeit beim Lösen der Aufgaben auch kleine Fehler in Kauf – allerdings nur, solange man weiß, wie groß die Fehler maximal werden können. Die Methode findet Anwendung in einer Vielzahl von alltäglichen Problemstellungen. Die bekanntesten darunter sind wahrscheinlich Bild-, Ton- und Videokompression. Aber auch beim automatischen Beladen von Transportern, beispielsweise, möchte man möglichst wenig verschiedene Roboter einsetzen. Man versucht dafür, das Modell für das Beladen zu reduzieren, und so mit möglichst wenig Unbekannten = Robotern auszukommen. Ein Spielzeuglieferant bereitet sich auf das Weihnachtsgeschäft vor. Alle Geschenke sind produziert, die Lastwagen vollgetankt. Nun müssen nur noch die Lastwagen mit den Geschenken beladen werden, dann können die Geschäfte mit den Waren beliefert werden. Acht Lastwagen gilt es mit Spielzeugautos, Bällen, Puppen, Baukästen, Springseilen und Kuscheltieren zu beladen. Tabelle 1 gibt die gewünschte Bepackung der acht Lastwagen an. Beispielsweise sollen also auf Lastwagen 1 fünf Autos, zwei Bälle, vier Puppen, fünf Baukästen, fünf Springseile und drei Kuscheltiere liegen. Nun gibt es beliebig viele Roboter, die diese Lastwagen bepacken können. Allerdings sind in diesem Jahr viele neue Waren zu produzieren, wofür man gern einige der Roboter einsetzen möchte.

151

Mathematik in Produktion und Logistik Tabelle 1. Die gewünschte Bepackung der acht Lastwagen

Auto Ball Puppe Baukasten Springseil Kuscheltier

– – – – –

–

L1

L2

L3

L4

L5

L6

L7

L8

5 2 4 5 5 3

4 4 5 4 4 4

2 2 3 2 2 2

4 4 4 4 3 4

2 8 4 2 2 6

5 2 4 5 5 3

2 2 1 2 2 2

5 2 4 5 6 3

Für die Roboter wird ein Arbeitsplan festgelegt: Ein Roboter bewegt sich immer von einem Lastwagen ins Lager oder vom Lager zu einem Lastwagen. Das Lager hat mehr als genug Waren jeden Typs vorrätig. Ein Roboter kann beliebig oft hin und her laufen und beschwert sich niemals darüber. Die Reihenfolge, in der die Roboter an den Lastwagen ankommen, ist prinzipiell egal. Ein Roboter kann sich ohne Waren beliebig zwischen Lager und allen Lastwagen bewegen, ein Warentransport besteht aber immer aus einem Hin- und einem Rückweg. Dabei ist egal, ob er im Lager oder an einem Lastwagen startet. In letzterem Fall kommt er auch wieder an dem Lastwagen an, an dem er gestartet ist. Jedem einzelnen Roboter kann man ein bestimmtes Muster, Waren zu transportieren, beibringen. Dieses Muster beinhaltet, wieviele Waren jedes Typs er von seinem Startpunkt mitnimmt und zum Zielpunkt schafft. Das heißt, er nimmt eine feste Anzahl jedes Warentyps von seinem Startpunkt mit und deponiert sie am Ziel und er bringt eine feste Anzahl jedes Warentyps von seinem Zielpunkt wieder zum Startpunkt zurück. Alle Anzahlen können auch null sein.

Beispiel. Roboter Arvin trägt stets zwei (Spielzeug-)Autos und eine Puppe, sonst nichts. Egal wie oft er vom Lager zu einem Lastwagen läuft, auf diesem Lastwagen sind dann stets doppelt so viele Autos

152

Arvin, Berit und die Lastwagen

wie Puppen. Wenn man eine gleiche Anzahl dieser beiden Waren auf einem Lastwagen benötigt, reicht Arvin also nicht aus. Kommt jetzt Roboter Berit dazu, kann dieser den Roboter Arvin eventuell korrigieren. Berit trägt stets ein Auto hin und eine Puppe zurück, egal von wo nach wo. Wenn jetzt auf einem Lastwagen drei Autos und drei Puppen liegen sollen, so reicht es, Arvin zweimal vom Lager zum Lastwagen laufen zu lassen (vier Autos, zwei Puppen) und Berit einmal vom Lastwagen zum Lager. Berit nimmt vom Lastwagen ein Auto weg, schafft es ins Lager und holt von dort eine Puppe und legt sie auf den Lastwagen. Mit diesen beiden Robotern kann man den Lastwagen also korrekt beladen, mit nur einem der beiden nicht. Diese beiden können auch beim Beladen der anderen Lastwagen helfen, eventuell braucht man aber noch mehr Roboter, um alle Lastwagen korrekt beladen zu können. Teil 1: Man möchte so wenig Roboter wie möglich einsetzen. Wie viele Roboter benötigt man mindestens, um die acht Lastwagen korrekt zu bepacken? Teil 2: Lässt man bei der Gesamtbeladung kleine Abweichungen zu (d. h. auf jedem Lastwagen darf genau eine Ware zu wenig oder zu viel sein), wie viele Roboter benötigt man dann mindestens für die Beladung? Antwortmöglichkeiten 1. 2. 3. 4. 5. 6. 7. 8. 9. 10.

korrekt 5, mit Abweichung 3 korrekt 7, mit Abweichung 6 korrekt 4, mit Abweichung 3 korrekt 6, mit Abweichung 7 korrekt 4, mit Abweichung 4 korrekt 5, mit Abweichung 4 korrekt 5, mit Abweichung 2 korrekt 6, mit Abweichung 3 korrekt 4, mit Abweichung 2 korrekt 6, mit Abweichung 4

153

Mathematik in Produktion und Logistik

Lösung (Richtige Lösung: Antwort 9) Diese Aufgabe kann als praktische Anwendung der Vektorrechnung benutzt werden, ohne dabei über geometrische Darstellungen zu argumentieren.

Zunächst sollte man sich darüber klar werden, dass die Trageleistung eines Roboters durch einen Vektor veranschaulicht werden kann. Jeder dieser Vektoren enthält sechs Einträge - von Auto, Ball, Puppe, Baukasten, Springseil bis Kuscheltier. Diese Einträge sind ganze Zahlen. Ein positiver Eintrag bedeutet, dass eine Ware in der angegebenen Menge vom Lager zum Lastwagen gebracht wird und ein negativer Eintrag sagt aus, dass die entsprechende Ware vom Lastwagen ins Lager geschafft wird. Eine Multiplikation des Vektors mit einer positiven ganzen Zahl bedeutet, dass der Roboter mehrere solche Lieferungen durchführt, und die Multiplikation mit einer negativen Zahl sagt aus, dass die Laufrichtung zwischen Lager und Lastwagen umgekehrt wird und dann entsprechend mehrere Lieferungen erfolgen. Eine Multiplikation mit null führt dazu, dass nichts transportiert wird. In analoger Weise kann auch die Beladung eines Lastwagen als Vektor geschrieben werden. Formaler ausgedrückt: Sei V die Menge aller möglichen Tragemuster. Seien a, b und c die Tragemuster dreier Roboter und α, β und γ die jeweiligen Häufigkeiten, mit denen die Transporte durchgeführt werden. Demnach ist α · a + β · b die Menge an Waren, die nach α Läufen des Typs a und β Läufen des Typs b auf einem Lastwagen liegen. Für einen Vektorraum gilt: 1. Abgeschlossenheit: Für beliebige a und b aus V und α, β aus Z gilt: α · a + β · b ∈ V. Das, was mehrere Roboter in vielen Transporten zu einem Lastwagen gebracht haben, hätte auch einer auf einmal hinschaffen können.

154

Arvin, Berit und die Lastwagen

2. Assoziativität: Für beliebige a, b, c ∈ V gilt a + (b + c) = ( a + b) + c. Hier kann man sich die einzelnen Warentypen anschauen, zum Beispiel a Ball + (bBall + c Ball ) = ( a Ball + bBall ) + c Ball und erkennt das bekannte Assoziativitätsgesetz der Addition von ganzen Zahlen. 3. Neutrales Element: Es gibt ein Element 0 ∈ V, so dass a + 0 = a. Diese 0 bedeutet einfach, dass nichts transportiert wird. 4. Inverses Element: Zu jedem a ∈ V gibt es ein − a, so dass a + (− a) = 0. Wenn a ein beliebiges Transportmuster ist, bei dem feste Anzahlen von Waren vom Lager zum Lastwagen gebracht werden, dann ist − a einfach das Muster, mit dem die gleichen Anzahlen vom Lastwagen zurück ins Lager geschafft werden. 5. Kommutativität: Wie bereits in der Beschreibung ausgeführt wurde, ist die Reihenfolge der Beladung prinzipiell egal, also gilt a + b = b + a für a, b ∈ V. 6. Eins-Element: Es gibt eine 1 ∈ Z, so dass für jedes a ∈ V gilt: 1 · a = a. Dies ist die gleiche Eins, die aus dem Rechnen mit ganzen Zahlen bekannt ist. Ein einmaliger Gang eines Roboters führt nunmal dazu, dass seine Ladung auch nur einmal transportiert wird. 7. Assozativität und Distributivgesetze: Die übrigen drei Gesetze α · ( β · a) = (α · β) · a, sowie α · ( a + b) = α · a + α · b und (α + β) · a = α · a + β · a können entweder wieder komponentenweise erklärt werden, oder anschaulich durch Gruppierungen von Mehrfachtransporten zu jeweils einem Lauf. Was nach dem Prüfen der ganzen Vektorraumaxiome feststeht ist, dass V ein Vektorraum über der Grundmenge (dem Körper) der ganzen Zahlen ist. Jedes Transportmuster besteht aus 6 Einträgen, die beliebig gewählt werden können. Demnach handelt es sich um einen Vektorraum der Dimension 6. Wie aus dem Rechnen mit Vektoren in 2D und 3D bekannt sein sollte, benötigt man zur Darstellung eines beliebigen Vektors aus diesen Vektorräumen jeweils 2 bzw. 3 sogenannte Basisvektoren. In unserem 6-dimensionalen Raum heißt das, dass man für jede beliebige Lastwagenbeladung mit sechs Robotern auskommt, die eventuell mehrfach laufen müs-

155

Mathematik in Produktion und Logistik

sen. Am einfachsten könnte man sie als ⎡ ⎢ ⎢ ⎢ ⎢ a=⎢ ⎢ ⎢ ⎣

1 0 0 0 0 0

⎤ ⎥ ⎥ ⎥ ⎥ ⎥, ⎥ ⎥ ⎦

⎡ ⎢ ⎢ ⎢ ⎢ b=⎢ ⎢ ⎢ ⎣

0 1 0 0 0 0

⎤ ⎥ ⎥ ⎥ ⎥ ⎥,..., ⎥ ⎥ ⎦

⎡ ⎢ ⎢ ⎢ ⎢ f =⎢ ⎢ ⎢ ⎣

0 0 0 0 0 1

⎤ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎦

wählen. Also ist für jeden Warentyp genau ein Roboter zuständig. Diese Wahl von Vektoren entspricht den Einheitsvektoren. Mit diesen Vektoren ist es also möglich, den gesamten Vektorraum V aufzuspannen. Dies ist allerdings nicht mit beliebigen 6 Vektoren möglich sondern wir benötigen auch noch deren lineare Unabhängigkeit. Mathematisch heißt das, wenn sich ein Vektor c beispielsweise als α · a + β · b schreiben lässt, dann ist er von diesen Vektoren a und b linear abhängig. Für die Roboter heißt das: Wenn sich die Transportleistung eines Roboters durch kombinierte Transporte anderer Roboter erreichen lässt, dann ist er überflüssig. Eine Möglichkeit, die lineare Unabhängigkeit von Vektoren a bis f zu prüfen, stellt die folgende Bedingung dar: Die folgende Gleichung ⎡ ⎢ ⎢ ⎢ ⎢ x1 · a + x2 · b + x3 · c + x4 · d + x5 · e + x6 · f = ⎢ ⎢ ⎢ ⎣

0 0 0 0 0 0

⎤ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎦

darf nur für x1 = x2 = . . . = x6 = 0 wahr sein. Genaugenommen handelt es sich bei dieser Gleichung um ein Gleichungssystem mit

156

Arvin, Berit und die Lastwagen

6 Unbekannten. Wir bezeichnen die Einträge von a als ⎡ ⎤ aAuto ⎢ a ⎥ ⎢ Ball ⎥ ⎢ ⎥ ⎢ a ⎥ a = ⎢ Puppe ⎥ ⎢ aKasten ⎥ ⎢ ⎥ ⎣ aSeil ⎦ aTier und für die Vektoren b bis f analog. Dann sieht das Gleichungssystem in Form eines Tableaus wie folgt aus: aAuto aBall aPuppe aKasten aSeil aTier

bAuto bBall bPuppe bKasten bSeil bTier

cAuto cBall cPuppe cKasten cSeil cTier

dAuto dBall dPuppe dKasten dSeil dTier

eAuto eBall ePuppe eKasten eSeil eTier

f Auto f Ball f Puppe f Kasten f Seil f Tier

0 0 0 0 0 0

Bei einem Gleichungssystem dieser Größe macht es keinen Sinn, über eine Determinante die eindeutige Lösbarkeit zu prüfen. Statt dessen wenden wir den Gauß-Algorithmus an und bringen das System auf Dreiecksform. Im Fall der Einheitsvektoren ist das schnell geschehen: 1 0 0 0 0 0

0 1 0 0 0 0

0 0 1 0 0 0

0 0 0 1 0 0

0 0 0 0 1 0

0 0 0 0 0 1

0 0 0 0 0 0

Durch zeilenweises Lösen dieses Gleichungssystems ergibt sich also rechnerisch die Bedingung x1 = x2 = . . . = x6 = 0 und damit auch die lineare Unabhängikeit. Betrachten wir jetzt wieder die ursprüngliche Aufgabe des Lastwagenbeladens.

157

Mathematik in Produktion und Logistik

Angenommen, für jeden Lastwagen L1 bis L8 ist genau ein Roboter zuständig, der genau einmal läuft und den Lastwagen komplett belädt. Das würde bedeuten, dass acht Roboter nötig sind. Ein kurzer Blick verrät, dass L1 und L6 identisch beladen sind, also ist der 6. Roboter schonmal durch den für L1 zuständigen ersetzbar. Wir wissen bereits, dass der Vektorraum der beladenen Lastwagen die Dimension 6 hat und damit mit 6 Basisvektoren komplett aufgespannt werden kann. Nun muss man noch prüfen, ob die Lastwagen-Vektoren auch mit weniger Basisvektoren darstellbar sind. Wir prüfen also, ob sich die Trageleistung einzelner Roboter durch Kombinationen anderer darstellen lässt. Dazu stellen wir wieder das Gleichungssystem zur Überprüfung der linearen Unabhängigkeit auf: ⎡ ⎤ 0 ⎢0⎥ ⎢ ⎥ ⎢ ⎥ ⎢0⎥ L1 x1 + L2 x2 + L3 x3 + L4 x4 + L5 x5 + L6 x6 + L7 x7 + L8 x8 = ⎢ ⎥ ⎢0⎥ ⎢ ⎥ ⎣0⎦ 0 Als Tableau dargestellt: 5 4 2 4 2 5 2 5 2 4 2 4 8 2 2 2 4 5 3 4 4 4 1 4 5 4 2 4 2 5 2 5 5 4 2 3 2 5 2 6 3 4 2 4 6 3 2 3

0 0 0 0 0 0

(1)

Eine Rückinterpretation auf Lastwagen hieße: Auf welche Art und Weise ist es möglich, einen Lastwagen so zu beladen, dass er leer ist. Wenn dies nur dadurch möglich ist, dass kein Roboter irgendetwas transportiert, dann sind die Tragemuster der Roboter linear unabhängig. Jetzt kann man versuchen, dieses System ,per Hand‘ auf Dreiecksform zu bringen, allerdings stellen graphikfähige Taschenrech-

158

Arvin, Berit und die Lastwagen

ner eine sinnvolle und zuverlässige Alternative dar. Auf den meisten Geräten wird eine Funktion rref() angeboten, welche die Treppennormalform oder auch Zeilenstufenform einer Matrix mit Hilfe des Gauß-Algorithmus berechnet. Damit erhält man für das Gleichungssystem (1) die folgende Form: 1 0 0 0 0 0

0 1 0 0 0 0

0 0 1 0 0 0

0 0 0 1 0 0

−2 6 −6 0 0 0

1 0 0 0 0 0

0 2 −3 0 0 0

1 2 −2 −1 0 0

0 0 0 0 0 0

Es ist an diesem Gleichungssystem erkennbar, dass nur 4 relevante Gleichungen verbleiben. Die letzten beiden Zeilen stellen nur triviale Aussagen dar. Der interessante Punkt liegt jetzt darin, die übrigen Gleichungen zu interpretieren. Nach x1 bis x4 umgestellt lauten sie: x1 = 2x5 − x6 − x8

(2a)

x2 = −6x5 − 2x7 − 2x8

(2b)

x3 = 6x5 + 3x7 + 2x8

(2c)

x4 = x8

(2d)

Die Werte für x5 bis x8 sind beliebig wählbar. Dies widerspricht natürlich der Forderung, dass für lineare Unabhängigkeit das Gleichungssystem nur jeweils 0 als Lösung hat. Gleichzeitig lässt sich aber folgendes erkennen: Wenn beispielsweise L6 einmal beladen wird, also x6 = 1, dann folgt aus der Gleichung (2a), dass x1 = −1. Im folgenden Text wird mit Ri der Roboter bezeichnet, der den Lastwagen Li mit einmal Laufen belädt. Der Gleichung (2a) kann man dann entnehmen, dass wenn der Roboter R6 den Lastwagen L6 belädt, dieser von dem Roboter R1 komplett wieder entladen werden kann. Da die Bewegungsrichtung eines Roboters beliebig ist, hätte L6 von vornherein auch durch den Roboter R1 beladen werden können. Dieser Zusammenhang sollte schon vorher aufgefallen sein. Et-

159

Mathematik in Produktion und Logistik

was interessanter wird es für x7 = 1 und x5 = x6 = x8 = 0. Dann ergibt sich in den Gleichungen (2b, 2c) x2 = −2 und x3 = 3. Dies bedeutet, wenn Lastwagen L7 einmal beladen wird und anschließend noch 3 mal die Beladung von L3 hinzukommt, dann kann dies nach zwei Läufen des Roboters R2 wieder abtransportiert werden. Analog hätte der Lastwagen L7 also auch nur mit den Robotern R2 und R3 beladen werden können. In den Gleichungen (2a-2d) erkennt man also, dass die Beladungen L5 bis L8 komplett durch die Roboter R1 bis R4 dargestellt werden können. Dementsprechend sind die Roboter R5 bis R8 ersetzbar und alle Lastwagen können mit den Robotern R1 bis R4 beladen werden. Problem I ist damit gelöst. Es werden 4 Roboter benötigt und es kann sogar angegeben werden, was sie jeweils zu tragen haben. Die Lösung von Teil 2 ist etwas schwieriger. Durch ein wenig Knobeln kann man erkennen, dass die Vektoren L1 bis L8 sich auch als Linearkombination der Form ⎡ ⎤ ⎡ ⎤ ⎡ ⎤ ⎡ ⎤ 1 1 0 0 ⎢1⎥ ⎢ −2⎥ ⎢0⎥ ⎢0⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢1⎥ ⎢ 0 ⎥ ⎢1⎥ ⎢0⎥ L i = x1 ⎢ ⎥ + x2 ⎢ ⎥ + x3 ⎢ ⎥ + x4 ⎢ ⎥ ⎢1⎥ ⎢ 1 ⎥ ⎢0⎥ ⎢0⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎣1⎦ ⎣ 1 ⎦ ⎣0⎦ ⎣1⎦ 1 0 0 −1 darstellen lässt, wobei x3 und x4 nur −1, 0, 1 sein können. Von den letzten beiden Robotern wird jeweils nur eine Ware (Puppe oder Seil) transportiert und sie sind auch nur mit maximal einem Lauf an der Beladung beteiligt. Streicht man die Transporte dieser beiden Roboter, dann kann auch stets nur eine Puppe bzw. ein Springseil zuviel oder zuwenig aufgeladen werden. Eine vollständige aber leicht fehlerhafte Beladung ist also durch die ersten beiden Roboter gewährleistet.

160

Lagenwechsel minimieren – oder das Bohren von Löchern in Leiterplatten Martin Grötschel, Thorsten Koch und Nam D˜ ung Hoàng

Diese Aufgabe behandelt ein Problem, das beim Entwurf von Leiterplatten auftritt. Die Aufgabe ist rein kombinatorischer Natur, man benötigt keine Kenntnisse der Elektromechanik. Einfache Leiterplatten haben zwei Seiten (auch Lagen genannt), auf die Strom leitende Bahnen (genannt Leiterbahnen) aufgebracht werden können. Wir nennen diese Lagen obere und untere Lage. Abbildung 1 zeigt eine unbestückte Leiterplatte und ihren „Schatten“, der die Löcher in der Leiterplatte sichtbar macht.

Abbildung 1. Unbestückte Leiterplatte

161

Mathematik in Produktion und Logistik

Abbildung 2. Leiterbahnen

Diese Löcher (auch Vias genannt) dienen entweder dem Anschluss von Bauteilen oder dazu, eine Leiterbahn auf der oberen Lage mit einer Leiterbahn auf der unteren Lage zu verbinden. Eine Leiterbahn kann also mit Hilfe eines Vias die Lage wechseln. Die Leiterbahnen stellt man in Konstruktionszeichnungen durch Linien dar. Diese Linien können Knicke haben und sich auch verzweigen. Abbildung 2 zeigt sieben Leiterbahnen, die als verschiedenfarbige Linien dargestellt sind. Die Leiterbahnen in unserem Beispiel führen zum nördlichen oder südlichen Rand und verlaufen (noch) alle auf der oberen Lage. Zwei Leiterbahnen dürfen sich jedoch nicht überschneiden, denn jede Überkreuzung führt zu einem Kurzschluss. Überkreuzungen werden dadurch vermieden, dass eine der beiden Leiterbahnen irgendwo vor der Kreuzung die Seite der Platte wechselt. Das geschieht dadurch, dass ein Loch (Via) durch die Platte gebohrt wird und so eine der beiden sich kreuzenden Bahnen auf der oberen und die andere auf der unteren Lage geführt wird. Abbildung 3 zeigt Leiterbahnen, die sowohl auf der Oberseite, als auch auf der Unterseite der Leiterplatte verlaufen. Die Unterscheidung von Ober- und Unterseite einer Leiterplatte machen wir durch unterschiedliche Linienarten deutlich: Leiterbahnen mit

162

Lagenwechsel minimieren

Abbildung 3. Leiterbahnen auf Ober- und Unterseite einer Leiterplatte

komplett ausgefüllten Linien gehen auf der Oberseite der Leiterplatte entlang (hier Leiterbahn 1) und Leiterbahnen mit umrandeten Linien verlaufen auf der Unterseite der Leiterplatte (hier Leiterbahnen 2 und 3). Wie man die Leiterbahnen der Leiterplatte aus Abbildung 2 den beiden Lagen zuweisen kann, zeigt Abbildung 4. Dies ist eine häufig in der Industrie genutzte sogenannte „Standardlösung“. Alle horizontalen Linien werden auf der Unterseite und alle vertikalen Linien auf der Oberseite der Leiterplatte geführt.

Abbildung 4. Standardlösung

163

Mathematik in Produktion und Logistik

Abbildung 5. Lösung mit nur vier Löchern

Das bedeutet, dass in jeden Knick einer Leiterbahn ein Loch gebohrt wird, um an dieser Stelle die Seite der Leiterplatte zu wechseln. Man muss übrigens nicht unbedingt in einen Knick bohren. In unserem Beispiel dürfen Leiterbahnen auf der Leiterplatte sowohl oberhalb als auch unterhalb beginnen, sie können oberhalb oder unterhalb aufhören. Hierfür gibt es keine Vorschriften. Das muss bei einer realen Leiterplatte jedoch nicht so sein. Hier kann es vorkommen, dass eine Bahn auf der oberen Lage beginnen und unten enden muss oder umgekehrt. Die Bohrlöcher sind mit roten Kreisen markiert. In unserem Beispiel müssen wir, wenn wir die Standardlösung der Industrie verwenden wollen, zwölf Löcher bohren, um die Lagenwechsel (Seitenwechsel) vorzunehmen. Es geht aber viel besser. Wie Abbildung 5 zeigt, kommt man mit nur vier Löchern statt zwölf aus und erreicht so eine erhebliche Aufwandsersparnis. In Abbildung 6 sind 10 Leiterbahnen zu sehen. Diese sind nummeriert und farblich gekennzeichnet. Alle Leiterbahnen führen zu den Rändern der Leiterplatte. Man beachte, dass es Leiterbahnen mit 2, 3 und 4 Endpunkten gibt. Bestimmen Sie eine bestmögliche kurzschlussfreie Realisierung des Leiterbahnengeflechts aus Abbildung 6.

164

Lagenwechsel minimieren

Abbildung 6. Leiterbahngeflecht

Mit anderen Worten, bestimmen Sie die minimale Anzahl der Lagenwechsel (Bohrungen durch die Leiterplatte, so dass die Leiterbahnen ohne Kurzschluss aufgebracht werden können). Noch genauer, bestimmen Sie Punkte auf den Leiterbahnen, an denen ein Loch gebohrt werden soll, damit die Leiterbahn die Lage wechseln kann, und zwar so, dass je zwei kreuzende Leiterbahnen auf unterschiedlichen Lagen sind und dass die Anzahl der zu bohrenden Löcher so gering wie möglich ist.

Antwortmöglichkeiten 1. 2. 3. 4. 5.

9 oder weniger Bohrungen 10 Bohrungen 11 Bohrungen 12 Bohrungen 13 Bohrungen

6. 7. 8. 9. 10.

165

14 Bohrungen 15 Bohrungen 16 Bohrungen 17 Bohrungen 18 Bohrungen

Mathematik in Produktion und Logistik

Bemerkungen. Betrachten wir die Leiterbahn 1. Von dem mit 1 gekennzeichneten Punkt am linken Rand (Westen) führt eine gerade rot gefärbte Linie zu dem mit 1 markierten Punkt am rechten Rand (Osten). Zwischen den Leiterbahnen 2 und 7 zweigt von der roten horizontalen Linie eine rote Linie nach Süden ab. Wenn man in den Verzweigungspunkt ein Loch bohrt, so hat man verschiedene Lagenzuweisungen zur Auswahl: Man kann die nach Westen laufende rote Linie oben auf der Leiterplatte, die nach Osten laufende unten führen oder umgekehrt; gleichzeitig hat man die Freiheit, die nach Süden laufende rote Linie oben oder unten zu führen. Verzweigungspunkte bieten also Gestaltungsmöglichkeiten. In Abbildung 1 haben Sie eine unbestückte Leiterplatte und ihren Schatten auf einem weißen Blatt Papier gesehen, so dass die Löcher, die in eine solche Leiterplatte gebohrt werden müssen, gut sichtbar sind. Die beiden Seiten einer bestückten Leiterplatte sehen Sie in Abbildung 7. Einige Löcher haben die „Beinchen“ von Bauteilen aufgenommen, andere dienen dazu, den Strom einer Leiterbahn von der einen auf die andere Seite der Leiterplatte zu führen. Alle Löcher sind nun mit Lötzinn (oder anderem stromleitenden Material) gefüllt. Das Bohren der Löcher ist zeitaufwendig und führt nicht selten zu Beschädigungen der Platte. Schlecht verlötete Löcher beeinträchtigen die Funktionsfähigkeit der Leiterplatte. Ein Ziel beim Entwurf

Abbildung 7. Zwei Seiten einer bestückten Leiterplatte

166

Lagenwechsel minimieren

von Leiterplatten ist daher, die Anzahl der zu bohrenden Löcher so klein wie möglich zu halten. Diese Aufgabe ist eine (ein wenig vereinfachte) Version des Leiterplattenbohrproblems. Dieses Bohrproblem nennt man im Jargon des Leiterplatten-und VLSI-Designs Via-Minimierung, weil es gilt, die Anzahl der Vias (Löcher, Durchkontaktierungen) so klein wie möglich zu halten.

167

Mathematik in Produktion und Logistik

Lösung (Richtige Lösung: Antwort 1) Abbildung 8 zeigt eine mögliche Lösung der Aufgabe mit acht Vias. Es gibt verschiedene Lösungen mit acht zu bohrenden Löchern. Mit sieben oder weniger Löchern kann man keine kreuzungsfreie Verdrahtung des Leiterbahnengeflechts aus Abbildung 6 erreichen. Das Via-Minimierungsproblem ist im Sinne der Komplexitätstheorie N P -schwer. Dies bedeutet, dass es im Allgemeinen (falls die noch offene Vermutung P = N P richtig ist) nicht möglich ist, einen kurzen Beweis für die Optimalität einer zulässigen Lösung dieses Problems zu führen. In speziellen Anwendungsbeispielen kann das jedoch gelingen. Wie macht man so etwas? In einem ersten Schritt versucht man, durch (systematisches und überlegtes) Ausprobieren eine gute Lösung zu finden. Im Falle unserer Aufgabe möchte man eine kurzschlussfreie Realisierung der Leiterbahnen aus Abbildung 6 bestimmen, die möglichst wenige Bohrungen benötigt. Hat man k Bohrlöcher gefunden und glaubt, dass es nicht mit weniger geht, dann muss man eine untere Schranke für die Anzahl der Bohrlöcher bestimmen. Besagt die untere Schranke, dass mindestens k Bohrungen benötigt werden, so hat man einen Beweis für die Optimalität der Zahl k gefunden. Die Bestimmung einer guten unteren Schranke ist in der Regel schwierig. In unserem Falle hat Daniel Glöckner, ein Teilnehmer am Adventskalenderwettbewerb 2007, eine Lösung mit 8 Bohrlöchern gefunden und einen Beweis dafür angegeben, dass es nicht mit weniger Bohrungen geht. Sein Beweis verläuft wie folgt (Originalzitat aus der eingesandten Lösung): Bei der Lösung des Problems ist es von Vorteil, eine untere Schranke für die Anzahl der Bohrungen zu haben. Betrachtet man das Netz genauer, so erkennt man eine Situation, in der man um eine Bohrung nicht herumkommt. Dies ist genau an den Stellen der Fall, wo ein freier Fleck von einer ungeraden Anzahl unterschiedlicher Leiterbahnstücke umschlossen ist. Im Folgenden bezeichne Segment ein Stück einer Leiterbahn, das

168

Lagenwechsel minimieren

Abbildung 8. Optimallösung

von Kreuzungen mit anderen Leiterbahnen oder Lagenwechseln durch Bohrungen begrenzt wird. Ein Kreis bezeichne eine (minimale) Menge von Segmenten, die lückenlos einen freien Fleck der Leiterplatte umschließen. Ein guter Kreis habe eine gerade, ein schlechter Kreis eine ungerade Anzahl Segmente. Nur wenn ein Kreis ein guter Kreis ist, ist es möglich, die Segmente abwechselnd der oberen bzw. unteren Lage zuzuordnen, ohne beim Schließen des Kreises das letzte Segment auf der gleichen Lage zu haben, wie das angrenzende erste Segment. Folglich hat jede Lösung des Problems nur gute Kreise. Ein schlechter Kreis lässt sich nur durch eine Bohrung auf einem seiner Segmente in einen guten Kreis umwandeln. In dem gegebenen Leiterbahnennetz gibt es 9 schlechte Kreise (markiert in der Abbildung durch ein X). Der große schlechte Kreis bei H8 teilt sich drei seiner Segmente mit anderen schlechten Kreisen (D8, F6, I10). Diese drei Segmente sind die einzigen, an denen zwei schlechte Kreise aneinanderstoßen. Da hier die Möglichkeit besteht, zwei schlechte Kreise mit nur einer Bohrung gleichzeitig umzuwandeln, kann für den Kreis

169

Mathematik in Produktion und Logistik

Abbildung 9. Schlechte Kreise, nach Daniel Glöckner

H8 keine Bohrung gezählt werden, so dass man eine unter Schranke von nur 8 Bohrungen erhält. Wenn man optimistisch ist und davon ausgeht, dass diese untere Schranke erreicht werden kann, wird man nun die 24 möglichen Positionen für Bohrungen (bunte Punkte in der Abbildung) auf den Segmenten der 8 kleinen schlechten Kreise genauer unter die Lupe nehmen. 10 dieser Positionen (gelb) bilden Paare (C2-B3, E1-A5, D3-C4, E6-D7, G7-E9), wo an beiden Stellen gleichzeitig eine Bohrung gesetzt werden müsste, um nicht einen neuen schlechten Kreis zu schaffen. Bei 9 anderen Positionen (rot) gibt es nicht die Möglichkeit durch eine andere geplante Bohrung einen neuen schlechten Kreis zu verhindern. Daraus folgt, dass bei D13, E12, F5, I11, K5, K10, L7, M12 und N13 nicht gebohrt werden darf. Hieraus folgt wiederum, dass 4 der Kreise nur durch Bohrungen bei C11, G9, M6 und O11 (grün) umgewandelt werden können. Die verbleibende Position C8 (grau) kommt nicht in Frage, da bei diesem Kreis eine der gepaarten Positionen gewählt werden muss, um den Kreis bei F6 umwandeln zu können. Wie man nach einigem Überprüfen feststellt, sind alle 6 durch die Paare gegebenen Möglichkeiten (mal zwei wenn man noch die Lagen tauscht) Lösungen des Problems. Also wurde die untere Schranke erreicht.

170

Lagenwechsel minimieren

Der Beweis der unteren Schranke 8 durch Daniel Glöckner ist durchaus knifflig. Für große Leiterplatten ist eine derartige Argumentation selten (einigermaßen nachvollziehbar) möglich. Hierzu muss die aufwändige Maschinerie der ganzzahligen Optimierung eingesetzt werden. Variationen. Bei realen Leiterplatten sind Hunderte oder gar Tausende von Löchern zu bohren. Neben den bereits erwähnten Vorgaben, dass Leiterbahnen auf vorher festgelegten Lagen enden müssen, kann es sein, dass das Bohren von Löchern in bestimmten Zonen nicht erlaubt ist. Bohrlöcher z. B. benötigen mehr Platz als Leiterbahnen, und wenn zwei Leiterbahnen sehr eng nebeneinander geführt werden, kann es passieren, dass eine Bohrung in eine der beiden Bahnen, die andere Leiterbahn berührt (das führt zu einem Kurzschluss, und man hat Ausschuss produziert). In der Leiterplatte aus Abbildung 6 könnte es zum Beispiel sein, dass die vom südli-

Abbildung 10. Lösung, wenn nur an Verzweigungen gebohrt werden darf.

171

Mathematik in Produktion und Logistik

chen Rand nach oben verlaufenden Leiterbahnen 6 und 3 so eng nebeneinander liegen, dass die in der Optimallösung aus Abbildung 8 vorkommende Bohrung in Leiterbahn 5 (die zwischen den Bahnen 6 und 3 liegt) zu einem Kurzschluss führt. Die Frage ist dann, ob es eine andere Optimallösung gibt, die ohne eine solche Bohrung auskommt. Man kann nun nachweisen, dass beim Ausschluss einer Bohrung in Leiterbahn 5 zwischen den Leiterbahnen 6 und 3 mindestens neun Bohrlöcher erforderlich sind. Mit neun Bohrungen kommt man übrigens auch aus, wenn man fordert, dass nur an „Knicken“ bzw. „Verzweigungen“ gebohrt werden darf. Eine solche Lösung ist in Abbildung 10 zu sehen.

172

Mathematik gegen Bankrott

Die Paketversicherung von MathPost Peggy Daume

Angesichts der fundamentalen Bedeutung des Versicherungsgedankens für die menschliche Existenz kann das Versicherungswesen auf eine lange Geschichte zurückblicken. Dabei lassen sich zwei Grundformen von Versicherungen unterscheiden, die sich gegenseitig beeinflusst und gegenüber anderen Formen durchgesetzt haben. Gefahrengemeinschaften. Erste Vorstufen zur Versicherung entstanden bereits in der Antike, als sich einzelne Interessengruppen (z. B. Bauern), die in gleicher Art von einem bestimmten schadensbringenden Ereignis (z. B. Ernteausfall) bedroht waren, zu so genannten Gefahrengemeinschaften zusammenschlossen. Jedes Mitglied der Gemeinschaft entrichtete einen Beitrag in die Gemeinschaftskasse, aus der die entstandenen Schäden reguliert wurden. Die Höhe des Beitrages wurde entweder im Voraus, unter der Annahme des zu erwartenden Schadens, oder im Nachhinein, auf Grund des tatsächlich eingetretenen Schadens, bestimmt. Als urtümlichste Gefahrengemeinschaft ist die Familie anzusehen, in der sich die einzelnen Familienmitglieder zur gegenseitigen Hilfe verpflichteten. Genossenschaftliche und freiwillige Zusammenschlüsse, wie sie aus dem Altertum überliefert sind, kommen der Versicherungsidee aber näher. So initiierten beispielsweise die ärmeren Bevölkerungsschichten im kaiserlichen Rom die „collegia tenuiorum“ als Kassen zur Bestreitung von würdigen und kostspieligen Bestattungszeremonien. Etwa zeitgleich wurden in Ägypten kultische Unterstützungseinrichtungen für Hinterbliebene und in Israel Brautausstattungsvereine gegründet. Ende des 19. Jahrhundert griff der preußisch-deutsche Staat mit dem Aufbau einer gesetzlichen Sozialversicherung, wie sie auch

175

Mathematik gegen Bankrott

heute noch existiert, in das Versicherungswesen ein. Derzeit ist die Sozialversicherung als systematischste Form der Bildung einer, wenn auch staatlich erzwungenen, Gefahrengemeinschaft anzusehen. Versicherungen als kaufmännisches Rechtsgeschäft. Die ersten echten Versicherungsverträge wurden im 14. Jahrhundert abgeschlossen. In den so genannten See-Versicherungsverträgen wurde das Risiko eines schadensbringenden Ereignisses erstmalig auf eine Person übertragen: Ein Geschäftsmann (= Versicherungsunternehmer) verpflichtete sich gegen Zahlung einer Versicherungsprämie, Seeleuten (= Versicherungsnehmer) einen fest vereinbarten Betrag zu bezahlen, falls ihre Schiffe bzw. Waren durch Piraten oder Unwetter verloren gingen. Ein zweiter Ursprung eines geschäftsmäßigen Versicherungswesens ist in den Leibrentenverträgen des frühen Mittelalters zu sehen: Der Versicherungsnehmer erkaufte sich von einem Geschäftspartner, z. B. durch Übertragung seines Grundstücks, das Anrecht auf eine später zu erfolgende, regelmäßige und bis zum Lebensende dauernde Zahlung von Rentenbeträgen. Mit Beginn des 18. Jahrhunderts setzte die Entwicklung einer professionell betriebenen privaten Lebensversicherung ein, nachdem u. a. durch Pascal, Leibniz und Bernoulli die wahrscheinlichkeitstheoretischen Grundlagen des Versicherungswesens gelegt wurden. Seit dieser Zeit wird das Risiko eines schadensbringenden Ereignisses mittels Stochastik kalkuliert und die Prämie auf Grundlage mathematischer Überlegungen bestimmt, da Versicherungsgeschäfte notwendigerweise ein zufälliges Element enthalten. Im Falle von Kfz-Versicherungen beispielsweise steckt der Zufall in der Unfallwahrscheinlichkeit, im Zusammenhang mit Lebensversicherungen in der restlichen zufälligen Lebensdauer des Versicherungsnehmers. Insbesondere das Versicherungswesen rund um die Lebensversicherungen hat stark von der Entwicklung der Wahrscheinlichkeitstheorie profitiert. Mittlerweile gibt es kaum etwas, das man nicht versichern kann. Neben den allseits bekannten Versicherungen wie Lebens-

176

Die Paketversicherung von MathPost

versicherung, Haftpflichtversicherung, Krankenversicherung oder Kfz-Versicherung gibt es sehr ungewöhnliche Versicherungen: Wer beispielsweise Angst davor hat, von einem Außerirdischen entführt zu werden, sollte eine entsprechende Police abschließen. Wenn der Versicherungsnehmer tatsächlich entführt wird und dies glaubhaft nachweisen kann, ist sich dieser eines hohen Schmerzensgeldes sicher. Fußballfans erleben schon schwere Momente, wenn ihr Lieblingsverein aus der ersten Bundesliga absteigt. Vielleicht hilft dann ein kleiner finanzieller Ausgleich. Kein Problem – wenn rechtzeitig eine entsprechende Versicherung abgeschlossen wurde. Das Versicherungswesen wird also immer individueller: Maßgeschneiderte Versicherungen – wie sie u. a. Unternehmen abschließen – helfen in jeder Problemsituation. So profitiert beispielsweise auch das Familienunternehmen MathPost von der auf seine betriebliche Situation abgestimmten Paketversicherung. Schauen wir uns diese im Folgenden näher an1 . Das Familienunternehmen MathPost ist ein kleines, seit einem Jahr existierendes Unternehmen, das Pakete mit besonders wertvollen Inhalten verfrachtet. In diesem Unternehmen sind viele fleißige Mitarbeiter beschäftigt, die alle sorgfältig und umsichtig arbeiten. Dennoch kommt es schon einmal vor, dass ein Paket auf dem Weg zum Kunden verloren oder etwas beim Verladen der Pakete zu Bruch geht. Im ersten Jahr des Unternehmens gab es immer wieder enttäuschte Gesichter, wenn etwa der Paketempfänger voller Vorfreude das Paket öffnete und feststellen musste, dass die heiß erwartete Digitalkamera leider kaputt war, weil das Paket offensichtlich einem Postboten aus den Händen geglitten war. Doch der Geschäftsführer Max Math hat aus den Erfahrungen des ersten Jahres gelernt. Traurige Kunden möchte er ab sofort ver-

1. Auf die gleiche Art, wie in der folgenden Aufgabe die Versicherungsprämie für eine Paketversicherung bestimmt wird, werden in der Realität Prämien für Lebensversicherungen berechnet.

177

Mathematik gegen Bankrott

meiden. Aus diesem Grund denkt er über die Möglichkeit nach, eine spezielle Paketversicherung für die beförderten Pakete abzuschließen. Dafür hat Max Math folgenden Einfall: Geht der Inhalt eines Pakets entzwei oder das Paket gar verloren, wird dem Kunden ein Gutschein ausgestellt. Als kleines „Schmerzensgeld“ soll der Gutschein mit einer Summe, die 10 % über dem ursprünglichen Wert des Pakets liegt, versehen werden. Das auf dem Gutschein stehende Geld möchte der Geschäftsführer im Schadensfall von einer Versicherung ausbezahlt bekommen. Mit dieser Idee wendet er sich an das Versicherungsunternehmen GlüKu. Das Risiko, das die Versicherung durch die Paketversicherung eingeht, lässt sie sich natürlich mit einem Beitrag, der so genannnten Versicherungsprämie, bezahlen. Doch wie berechnet die Versicherung die Versicherungsprämie? Max Math lässt sich dies von einem Mathematiker des Versicherungsunternehmens erklären: Zur Berechnung der Versicherungsprämie müssen wir alle möglichen Leistungen betrachten, die von uns und von Ihnen erbracht werden. Klar sollte zunächst sein, dass Sie für die Paketversicherung für jedes Paket einmalig eine Prämie zahlen. Die Prämie für ein Paket wird sofort beim Abschluss der Versicherung fällig. Für die Leistung, die wir als Versicherung erbringen, gibt es zwei mögliche Szenarien: – Das Paket geht nicht verloren und kommt unversehrt beim Kunden an. Dann erbringen wir keine Leistung. – Das Paket geht auf dem Weg zum Kunden verloren oder der Paketinhalt wird beschädigt. Dann zahlen wir genau einen Monat nach Vertragsabschluss die Versicherungssumme. Unsere Leistung ist also vom zufälligen Verschwinden der Pakete oder Zerbrechen derer Inhalte abhängig. Wir halten es daher für fair, wenn Sie als Versicherungsprämie gerade so viel bezahlen, wie wir an Leistung durchschnittlich zahlen. Das bedeutet: Ist X die Versicherungssumme (= Betrag, den Sie nach Eintreten des Schadensfall ausbezahlt bekommen), berechnen wir die Versicherungsprämie P mit der folgenden Formel P = pV · X + pK · X. Dabei ist pV die Wahrscheinlichkeit dafür, dass ein Paket auf dem Weg zum Kunden verloren geht und pK die Wahrscheinlichkeit dafür, dass

178

Die Paketversicherung von MathPost

der Paketinhalt zerbricht. Hinter der Formel steckt im Übrigen die Erwartung, dass wir eine Unmenge von Versicherungen dieser Art verkaufen und sich die Schadensfälle mit den Nichtschadensfällen ausgleichen, so dass wir im Durchschnitt weder einen Verlust noch einen Gewinn machen. Um aber die durchschnittliche Leistung berechnen zu können, brauchen wir Aussagen darüber, mit welcher Wahrscheinlichkeit ein Paket verloren geht oder dessen Inhalt zerbricht. Ohne diese können wir Ihnen leider keine Versicherung anbieten.

Glücklicherweise hat der umsichtige Max Math genauestens darüber Buch geführt. Von allen Paketen, die sein Unternehmen im ersten Jahr beförderte, sind 1,3 % aller Pakete auf dem Postweg verloren gegangen. Bei 3,19 % aller ausgelieferten Pakete gab es Beschwerden von Kunden, weil der Inhalt leider beschädigt wurde. Da das Unternehmen MathPost sehr viele Pakete befördert, können diese beobachteten Werte auch als entsprechende Wahrscheinlichkeiten interpretiert werden. Max Math kann also auf Grund seiner guten Buchführung der Versicherung alle notwendigen Daten zur Bestimmung der Versicherungsprämie liefern. Max Math denkt einen Moment über den Vorschlag der Versicherung nach. Eigentlich ist er mit dem Angebot zufrieden, allerdings ist er der Meinung, dass die Versicherung ein kleines Detail übersehen hat. Max Math soll die Versicherungsprämie bereits zum Zeitpunkt des Versicherungsabschlusses zahlen, wird aber im Schadensfall erst einen Monat später das Geld für die zerstörten oder verschwundenen Pakete erhalten. Er denkt, dass dies unfair ist, da die Versicherung noch einen Monat lang Zinsen erhält (Jahreszinssatz 3 % bei monatlicher Verzinsung mit Zinseszins und linearer Verzinsung, d. h. bei einem Jahreszinssatz von i % beträgt der Monatszinssatz 12i %) und erst dann die Versicherungssumme zahlen muss. Diesen Vorteil auf Seiten der Versicherung möchte Max Math bei der Berechnung der Versicherungsprämie berücksichtigt wissen und schlägt daher vor, dass durch so genanntes Abzinsen auf den Zeitpunkt des Vertragsabschlusses die Leistungen der Versicherung und des Unternehmens MathPost vergleichbar gemacht werden.

179

Mathematik gegen Bankrott

Wie groß ist die Differenz (bzw. der Betrag der Differenz) zwischen den zwei vorgeschlagenen Versicherungsprämien, wenn das Versicherungsunternehmen ein Paket im Wert von 5000,00 Euro versichern möchte?

Antwortmöglichkeiten

1.

1,00 Euro

6.

0,54 Euro

2.

0,65 Euro

7.

0,90 Euro

3.

1,03 Euro

8.

0,91 Euro

4.

0,40 Euro

9.

0,72 Euro

5.

0,61 Euro

10.

0,62 Euro

180

Die Paketversicherung von MathPost

Lösung (Richtige Lösung: Antwort 10) Da die Versicherung ein Paket im Wert von 5 000,00 Euro versichern möchte, beträgt die Versicherungssumme zuzüglich der 10 % Schmerzensgeld 5500,00 Euro. Zunächst wird die von dem Versicherungsunternehmen vorgeschlagene Prämie PV gemäß der Formel PV = pV · X + pK · X bestimmt. Dabei ist pV = 1, 3 % die Wahrscheinlichkeit dafür, dass ein Paket verloren geht und pK = 3, 19 % die Wahrscheinlichkeit dafür, dass der Paketinhalt zerbricht. Mit den gegebenen Wahrscheinlichkeiten ergibt sich für PV : PV = (0, 013 + 0, 0319) · 5 500, 00 Euro = 246, 95 Euro. Die Versicherungsprämie nach dem Vorschlag des Versicherungsunternehmens beträgt also 246,95 Euro. Nun betrachten wir den Vorschlag von Max Math. Aus einem 3 jährlichen Zinssatz von 3 % folgt ein Monatszinssatz von 12 % = 0, 25 %. Durch so genanntes Abzinsen der oben berechneten Prämie erhalten wir unsere neue Versicherungsprämie PM , die berücksichtigt, dass die Versicherung mit dem Geld noch einen Monat arbeiten kann. Es gilt: 1 · ( pV · X + p K · X ) 1, 0025 1 · 246, 95 Euro = 246, 33 Euro = 1, 0025

PM =

Die Versicherungsprämie nach Vorschlag von Max Math beträgt folglich 246,33 Euro. Damit beträgt die Differenz zwischen beiden Prämien 0,62 Euro. Dies erscheint auf dem ersten Blick eine kleine Summe zu sein.

181

Mathematik gegen Bankrott

Wenn man jedoch bedenkt, dass Max Math sehr viele Verträge bei der Versicherung abschließen wird und die meisten Versicherungen nicht nur einen Monat, sondern viele Jahre laufen, dann lässt sich mit dem Vorschlag von Max Math schon viel Geld sparen. Und tatsächlich sind Versicherungen dazu verpflichtet, ihren Zinsvorteil an die Versicherten weiterzugeben und die Prämien auf den Zeitpunkt des Vertragsabschlusses abzuzinsen.

182

Ein Kredit für Weihnachtsbaumkugeln Sina Tutsch

Eine Mathematikerin aus dem DFG-Forschungszentrum Matheon arbeitet an Methoden zur dreidimensionalen Visualisierung. Sie hat die Geschäftsidee, Weihnachtsbaumkugeln mit bewegten Hologrammen herzustellen, die sich individuell gestalten lassen, und plant eine Existenzgründung. Aus einem öffentlichen Förderprogramm erhält sie ein günstiges Darlehen in Höhe von 50 000 Euro. Für die Startphase ihres Unternehmens benötigt sie jedoch den vierfachen Betrag. Ihre Hausbank bietet ihr einen Kredit über 150 000 Euro mit einer Laufzeit von 5 Jahren zu den folgenden Konditionen an: Die Bank leiht der Mathematikerin die 150 000 Euro, und nach 5 Jahren zahlt diese den Betrag plus Zinsen zurück, also 150 000 · (1 + r )5 Euro, wobei r den jährlichen Zinssatz bezeichnet. Hat sie mit den Hologramm-Weihnachtsbaumkugeln Erfolg, so kann sie nach 5 Jahren ihre Schulden tilgen, und die Bank würde durch die Zinsen einen Gewinn in Höhe von 150 000 · (1 + r )5 − 150 000 Euro machen. Die Bank zieht aber auch ein zweites Szenario in Betracht, nämlich den Ausfall der Schuldnerin, also das Scheitern des Projekts. In diesem Fall hätte die Bank einen Totalverlust von 150 000 Euro. Anhand des vorliegendes Businessplans und ihrer Erfahrungen mit ähnlichen Existenzgründungen schätzt die Bank die Wahrscheinlichkeit p für einen Ausfall auf 28 %. Sie wählt den Zinssatz r so, dass der erwartete Gewinn   150 000 · (1 + r )5 − 1 · (1 − p) − 150 000 · p so hoch wie bei einer risikofreien Anlage der 150 000 Euro mit einem Zinssatz r  von 2 % ist. Nun muss die Mathematikerin entscheiden, ob sie den Kredit unter diesen Bedingungen aufnehmen

183

Mathematik gegen Bankrott

möchte. Sie will den Vertrag nur unterschreiben, falls der Zinssatz r nicht höher als 10 % ist. Angenommen, es kommt tatsächlich zur Vergabe des Kredits. Dann bildet die Bank eine Rücklage für den Fall, dass die junge Unternehmerin mit ihrer Firma Bankrott geht und ihre Schulden nicht zurückzahlen kann. Das Geld wird risikofrei mit Zinssatz r  angelegt. Welcher Betrag R ist als Rücklage ausreichend? Dazu beurteilt die Bank das Ausfallrisiko erneut, diesmal unter strengeren Kriterien im Sinne eines Stress-Tests. Sie setzt also eine höhere Ausfallwahrscheinlichkeit p˜ an. Mit dieser pessimistischen Schätzung sinkt natürlich auch der erwartete Gewinn. Das heißt, es steigt der erwartete Verlust, definiert als negativer erwarteter Gewinn. Die Bank wählt nun die Rücklage R so, dass sie in fünf Jahren diesen höheren erwarteten Verlust abdeckt. Das bedeutet, dass R die folgende Ungleichung erfüllt:   −150 000 · (1 + r )5 − 1 · (1 − p˜ ) + 150 000 · p˜ ≤ R · (1 + r  )5 Akzeptiert die Mathematikerin die Konditionen des Kreditvertrags? Wenn ja, auf welcher pessimistischen Schätzung für die Ausfallwahrscheinlichkeit p˜ würde eine Rücklage in Höhe von mindestens 10 860 Euro beruhen?

Antwortmöglichkeiten 1. 2. 3. 4. 5. 6. 7. 8. 9. 10.

Sie lehnt die Konditionen ab. Sie akzeptiert, und p˜ wurde auf circa 31 % angesetzt. Sie akzeptiert, und p˜ wurde auf circa 35 % angesetzt. Sie akzeptiert, und p˜ wurde auf circa 40 % angesetzt. Sie akzeptiert, und p˜ wurde auf circa 43 % angesetzt. Sie akzeptiert, und p˜ wurde auf circa 45 % angesetzt. Sie akzeptiert, und p˜ wurde auf circa 49 % angesetzt. Sie akzeptiert, und p˜ wurde auf circa 53 % angesetzt. Sie akzeptiert, und p˜ wurde auf circa 58 % angesetzt. Sie akzeptiert, und p˜ wurde auf circa 59 % angesetzt.

184

Ein Kredit für Weihnachtsbaumkugeln

Lösung (Richtige Lösung: Antwort 4) Zunächst muss man den Zinssatz r berechnen. Der erwartete Gewinn unter p mit Zinssatz r soll gleich dem Gewinn einer risikofreien Anlage mit Zinssatz r  sein. Das bedeutet:   150 000 · (1 + r )5 − 1 · (1 − p) − 150 000 · p

  = 150 000 · (1 + r  )5 − 1 .

Durch Umstellen der Gleichung erhält man: 1 + r −1 r=  5 1− p 1 + 0, 02 = √ − 1 ≈ 9 %. 5 1 − 0, 28 Das heißt, die Mathematikerin unterschreibt den Kreditvertrag. ˜ bei dem die Bank eine Danach bestimmt man den Wert für p, Rücklage in Höhe von mindestens 10 860 Euro bilden müsste. Also löst p˜ die folgende Gleichung:   −150 000 · (1 + r )5 − 1 · (1 − p˜ ) + 150 000 · p˜ = 10 860 · (1 + r  )5 Einsetzen von r und Zusammenfassen der Terme ergibt:   (1 + r  )5 · (1 − p˜ ) 150 000 · 1 − = 10 860 · (1 + r  )5 (1 − p ) Diese Gleichheit gilt genau dann, wenn p˜ ungefähr 40% ist.   (1 − p ) 10 860 · (1 + r  )5 · p˜ = 1 − 1 − 150 000 (1 + r  )5   (1 − 0, 28) 10 860 · (1 + 0, 02)5 = 1− 1− · 150 000 (1 + 0, 02)5

≈ 40 %

185

Optionsbewertung John Schoenmakers

Seitdem es auf dieser Welt Geld gibt, wird damit gerechnet. Mathematik und Geld sind von daher eng miteinander verknüpft. Dabei sind die Anforderungen an die Rechenkünste gestiegen: Das Einmaleins reicht längst nicht mehr aus, schon gar nicht, wenn es um die Bewertung von Portfolios und komplizierten Finanzkonstrukten (Derivaten) geht. Mathematiker helfen der Finanzindustrie und arbeiten eng mit Banken und Versicherungen zusammen. Sie entwickeln Modelle und Programme, mit denen sich mittels mathematischer Verfahren Risiken und Absicherungsstrategien kompliziert strukturierter Finanzprodukte besser einschätzen lassen. Ein relativ einfaches Finanzprodukt ist das Termingeschäft, bei dem man sich festlegt an einem gewissen Zeitpunkt in der Zukunft eine Aktie oder ein anderes Gut gegen einen jetzt vereinbarten Preis zu kaufen oder zu verkaufen. In der Regel wird der künftige Preis (auch Termin- oder Forward-Preis genannt) gleich dem jetzigen Preis, zuzüglich der bis dahin anfallenden Zinsen zum aktuellen Zinssatz, gesetzt. So entstehen bei diesem Geschäft keine weiteren Vertragskosten. Etwas kompliziertere Produkte sind die so genannten Call- und Put-Optionen. Der Besitzer eines solchen Produktes darf, muss aber nicht wie im Falle eines Termingeschäfts, das Gut oder die Aktie zu dem jetzt festgelegten (Basis-) Preis kaufen (Call-Option) oder verkaufen (Put-Option). In der Zeit zwischen Abschluss der Option und Datum der Vertragsausübung (Kauf/Verkaufsmöglichkeit der Aktie) kann die Aktie fallen oder steigen. Ein Beispiel: Man schließt eine Call-Option am 10. 2. 2008 für eine Aktie ab. Diese sieht vor, dass man die Aktie am 10. 2. 2009 für 200 Euro kaufen darf. Die 200 Euro werden als Basispreis bezeich-

187

Mathematik gegen Bankrott

net. Die Aktie hat heute einen Wert von 190 Euro. Der Wert der Aktie und der vereinbarte Basispreis müssen nicht identisch sein. Am 10. 2. 2009 steht die Aktie bei 260 Euro, ist also im Wert gestiegen. Wir lösen die Call-Option ein und können die 260 Euro teure Aktie für 200 Euro kaufen. Wäre die Aktie am 10. 2. 2009 weniger als 200 Euro wert, würde man die Aktie nicht kaufen und die Option verfallen lassen. Weil man mit einer Option ein Recht auf Kauf oder Verkauf erwirbt, jedoch nicht verpflichtet ist sie auch einzulösen, wird die Ausübung des Vertrages immer einen Gewinn oder besser gesagt keinen Verlust liefern. Dieses Recht hat natürlich seinen Preis. Fischer Black und Myron Scholes gelang es 1973 solche Optionen in einem halbwegs realistischen Preisentwicklungsmodell (geometrische Brownsche Bewegung) auf Grund von Arbitrageprinzipien zu bewerten. Für diese Entdeckung wurde 1996 an Scholes und Robert Merton der Nobelpreis verliehen (Black war 1995 verstorben). Black, Scholes und Merton wiesen nach, dass im Rahmen des unterliegenden Preismodels, es genau einen fairen Options-Preis gebe. Alle anderen Preise würden unbeschränkt risikolose Gewinne (Arbitrage) ermöglichen und sind von daher ökonomisch nicht relevant. In der folgenden Aufgabe werden die Ideen von Black, Scholes und Merton zur Bewertung einer Call-Option vereinfacht dargestellt. Wir betrachten folgendes stilisierte Aktien-Zins-Modell: Eine Aktie hat heute einen Wert von 100 Euro. Mit 50-prozentiger Wahrscheinlichkeit steigt der Wert der Aktie in einem Jahr auf 205 Euro, sonst fällt er auf 55 Euro (also auch mit 50-prozentiger Wahrscheinlichkeit). Festverzinslich angelegtes Geld wird mit 10 % jährlich verzinst, und man darf auch gegen Zahlung von 10 % Zinsen ,negativ‘ anlegen, d. h. leihen. Ein Investor will ohne Einsatz von eigenem Geld am Markt eine Call-Option mit einem Basispreis von 105 Euro und einer Laufzeit von 1 Jahr verkaufen. Der Käufer dieser Option erwirbt das Recht, aber nicht die Pflicht, die Aktie in einem Jahr für 105 Euro zu kaufen. Wenn der Wert der Aktie, wie oben angegeben, steigt, wird er die Option nutzen und somit de facto um

188

Optionsbewertung

205 − 105 = 100 Euro reicher sein, aber falls ihr Wert fällt, wird er die Option verfallen lassen. Die Aufgabe lautet: Ermittle, welchen Preis der Investor fairerweise für den Verkauf dieser Option verlangen kann. Unter einem fairen Preis versteht man hier, dass der Investor bei jeder Kursentwicklung die Optionsauszahlung replizieren kann, wenn die Option fällig wird, ohne dass er dabei Verlust erleidet, aber auch ohne dass er dabei Gewinn erzielt. Hinweis: Lege heute ein Portfolio (Bestand an Wertpapieren) aus Aktien (dies können auch nur Bruchstücke einer Aktie sein) und einer risikolosen festverzinslichen Anlage auf dem Bankkonto an. Gestalte den Wert P dieses Portfolios so, dass ,egal, was passiert‘, nach einem Jahr genau die Auszahlungsverpflichtung gegenüber dem Optionshalter abgedeckt ist. Der heutige Wert dieses Portfolios ist dann der sogenannte „arbitragefreie“ Preis der Call-Option. Wie muss P gewählt werden?

Antwortmöglichkeiten

1. 2. 3. 4. 5.

66,66 Euro 55,50 Euro 50,00 Euro 45,45 Euro 43,33 Euro

6. 7. 8. 9. 10.

189

40,00 Euro 36,66 Euro 33,33 Euro 30,00 Euro 25,66 Euro

Mathematik gegen Bankrott

Lösung (Richtige Lösung: Antwort 8) Der Investor legt sich ein Portfolio P an, welches aus Aktienanteilen θ und Geld auf einem Bankkonto ψ zusammengesetzt ist. Die Aktien haben heute einen Wert von 100 Euro, somit beträgt der Anfangswert P des Portfolios PAnfang = 100 Euro · θ + ψ Euro. Nun müssen θ und ψ so gewählt werden, dass die Wertentwicklung des Portfolios der Wertentwicklung der Option entspricht, d. h. ist der Wert der Aktie nach einem Jahr gestiegen, so ist der Wert der Option gleich 100 Euro (Differenz aus aktuellem Aktienwert von 205 Euro und Basispreis der Option von 105 Euro). Ist nach einem Jahr die Aktie gefallen, so ist der Wert der Option gleich Null (sie wird nicht eingelöst). Wenn das Portfolio diesen Werten entspricht, kann der Investor in den jeweiligen Szenarien entweder 100 Euro oder 0 Euro an den Optionshalter auszahlen. Daraus ergeben sich folgenden Forderungen: Pgestiegen = 205 Euro · θ + 1, 1 · ψ Euro = 100 Euro Pgefallen = 55 Euro · θ + 1, 1 · ψ Euro = 0 Euro Dieses Gleichungssystem können wir nach den Unbekannten auflösen: 2 100 Euro θ= , ψ=− 3 3 Also muss der Investor 100 3 Euro Kredit bei der Bank aufnehmen und 2 Anteile Aktien kaufen. Der Wert des Portfolios am Anfang der 3 Laufzeit beträgt also: 2 100 Euro = 33, 33 Euro − 3 3 Diesen Wert kann er von dem Optionskäufer verlangen. Somit ist die richtige Antwortmöglichkeit Nummer 8. Doch wie funktioniert dieses faire Geschäft nun wirklich? PAnfang = 100 Euro ·

190

Optionsbewertung

Zu Beginn des Optionsgeschäftes benötigt der Investor laut Rechnung 23 Aktienanteile. Die Kaufsumme ( 23 · 100 Euro = 66, 66 Euro) finanziert er zur Hälfte aus dem Preis für die Option, zur anderen Hälfte über einen Kredit. 1. Der Kurs der Aktie sei gestiegen. Der Optionskäufer wird also sein Kaufrecht ausüben und den Basispreis von 105 Euro an den Investor zahlen. Um dem Inhaber der Option eine Aktie geben zu können, benötigt der Investor nochmals ein Drittel einer Aktie zum jetzt aktuellen Preis. Dafür muss er bezahlen: 13 · 205 Euro = 68, 33 Euro. Somit hat der Investor insgesamt folgende Kosten: 1 Aktienanteil + Tilgung verzinster Kredit 3 100 1 Euro · 1,1 = 105 Euro · 205 Euro + 3 3

Kaufpreis von

Seine Einnahmen, durch den Verkauf der Option, belaufen sich auch auf 105 Euro und somit gibt es weder Gewinn noch Verlust für den Investor. 2. Der Kurs der Aktie sei gefallen. Der Optionskäufer wird also sein Kaufrecht nicht ausüben. Der Investor verkauft seine Aktienanteile zum aktuellen Preis (von 55 Euro pro Anteil) und tilgt seinen verzinsten Kredit: aktueller Aktienwert − verzinster Kredit 2 100 Euro · 1,1 = 0 Euro = · 55 Euro − 3 3 Der Investor erzielt/erleidet also auch hier weder Gewinn noch Verlust – der Preis ist also „fair“. Bemerkung. Die abdiskontierte ,erwartete‘ Optionsauszahlung beträgt: 1 100 · = 45,45 Euro. 2 1,1 Antwort 4 wäre also kein korrekter Preis!

191

Mathematik gegen Bankrott

Der Investor könnte z. B. 45,45 Euro − 33,33 Euro risikolos anlegen und erzielte damit einen Gewinn, weil alles andere genauso wie oben dargestellt abliefe.

192

Mathematik im menschlichen Körper

Das morgendliche Brückenritual Oliver Sander

Es wäre für Mediziner sehr interessant zu wissen, was für Kräfte genau in den menschlichen Knien wirken. Klar ist, dass sie recht groß sein müssen. Das Gewicht eines erwachsenen Mannes beträgt ca. 80 kg. Wenn davon je die Hälfte auf einem Bein ruht hat man schon mindestens 400 Newton pro Knie, beim Laufen, Springen, oder Treppensteigen noch viel mehr. Man will es aber noch viel genauer wissen. Die Kondylen, das sind die Kontaktflächen in den Knien, sind nicht eben. Es gibt dort Unregelmäßigkeiten, und die Kräfte konzentrieren sich dort. An einzelnen Stellen können die Kräfte dann noch viel höher sein. Die genaue Verteilung dieser Kräfte hat verschiedene medizinische Folgen. So sind z. B. die Kondylen mit einer dünnen Knorpelschicht bedeckt, die als Schmiere im Gelenk dient. Sind jetzt die Kräfte an einer Stelle zu hoch, so wird diese Knorpelschicht langsam abgerieben. Das Stadium fortgeschrittenen Abriebs bezeichnet man als Arthrose, eine Krankheit, die für den Patienten sehr schmerzhaft ist. Wüsste man die Kräfte im Knie, könnte man Arthrose in manchen Fällen vorhersehen. Ein anderes Gebiet, auf dem die Kräfte im Knie eine wichtige Rolle spielen, sind Knieprothesen. Diese werden teilweise in den Knochen geschraubt. In der Nähe der Schrauben merkt der Knochen manchmal, dass ein Großteil der Last jetzt von der metallenen Schraube übernommen wird, und bildet sich zurück. Als Resultat fängt die Prothese an zu wackeln. Eine genaue Kenntnis der Kräfte im Knie würde helfen, Prothesen zu entwickeln, bei denen dieser Effekt möglichst wenig auftritt. Leider kann man diese Kräfte kaum messen. Einem lebenden Menschen einen Drucksensor einzubauen ist sehr aufwändig und deshalb nur in ganz wenigen Fällen gemacht worden. Stattdessen

195

Mathematik im menschlichen Körper

Abbildung 1. Ein Knochen als verformbarer Körper. Die durchgezogene Linie zeigt den Knochen im spannungsfreien Zustand. Wird er belasted, so verformt er sich (gestrichelte Linie).

eilt die Mathematik zur Hilfe. Wenn man die Kräfte schon nicht messen kann, vielleicht kann man sie stattdessen ausrechnen? Das Teilgebiet der Mathematik, das sich mit der Mechanik verformbarer Körper beschäftigt, heißt Kontinuumsmechanik. Eine Verformung wird dort durch eine Funktion beschrieben, die jedem Punkt im unverformten Körper eine Position im verformten Körper zuweist. Allerdings entsprechen nicht allen solchen Funktionen Verformungen, die in der Realität vorkommen. Die, die das tun, zeichnen sich dadurch aus, dass sie Lösung bestimmter partieller Differentialgleichungen sind. Um die Verformungen und Kräfte eines elastischen Körpers auszurechnen muss man also die dazugehörige partielle Differentialgleichung lösen. Damit beschäftigt sich die Numerik. Auch das Knie ist ein verformbarer Körper, allerdings stehen die Dinge hier noch etwas komplizierter. Denn ein Knie besteht ja aus vielen unterschiedlichen Bestandteilen, die sich alle unterschiedlich verhalten. So ist z. B. Knochen hart und spröde, Muskelgewebe dagegen eher weich. Bänder und Sehnen sind sehr stark gegenüber Zugbelastung, Knorpel und die Menisken federn Stöße ab. Jeder ein-

196

Das morgendliche Brückenritual

zelne dieser Bestandteile kann durch eine partielle Differentialgleichung beschrieben werden. Möchte man aber das ganze Knie mit all seinen unterschiedlichen Materialien auf einmal beschreiben, so erhält man eine Gleichung, die extrem schwierig zu lösen ist. An dieser Stelle hilft eine Methode, die Gebietszerlegung genannt wird. Anstatt eine große Gleichung zu behandeln, die schwierig zu lösen ist, nimmt man die Einzelgleichungen für die einzelnen Gebiete und löst jede davon mehrfach. Angenommen, das Knie besteht aus drei Teilen A, B, und C, die sich alle drei wechselseitig berühren. Man löst die Gleichung für A, und danach die von B. Da A und B aneinanderstoßen hängt die Lösung von B natürlich von der Lösung von A ab. Als drittes löst man die Gleichung von C, und benutzt dabei, was man vorher für A und B ausgerechnet hat. Jetzt ist man einmal durch, aber was man für A ausgerechnet hat kann nicht die richtige Lösung sein. Denn die hängt ja von C ab, C wurde aber erst nach A ausgerechnet. Andererseits ist das, was man jetzt für A, B und C hat, vielleicht besser als vorher, und daher kommt die Idee, jetzt alle drei Gleichungen nochmal zu lösen, aber die Ergebnisse aus der vorherigen Runde zu verwenden. Vielleicht ist das Ergebnis dann noch besser. In der folgenden Aufgabe ist das wiederholte Lösen der Teilprobleme durch das abwechselnde Einstellen der beiden Brücken dargestellt. Die Staatsgrenze zwischen Dirichland und Neumannien liegt in einer tiefen Schlucht. Genaugenommen liegt sie a Meter von der dirichländischen Schluchtseite und b Meter von der neumannischen Schluchtseite entfernt. Die Schlucht ist also a + b Meter breit. Obendrein ist die neumannische Seite c Meter höher als die dirichländische. Die einzige Möglichkeit die Grenze zu überschreiten bilden zwei Zugbrücken, eine dirichländische und eine neumannische. Diese sind nicht nur schwenkbar, sondern können auch in der Länge verstellt werden. Im Prinzip können sie beliebig lang werden. Aus politischen Gründen darf allerdings kein Land seine Brücke soweit verlängern, dass sie über die Staatsgrenze hinausragt. Deswegen ist

197

Mathematik im menschlichen Körper

c a

Neumannien

b

Dirichland

c a

b

Neumannien

Dirichland

Abbildung 2. Oben: Mögliche Ausgangssituation; unten: Gesuchte Lösung

Kooperation notwendig. Damit der Grenzübergang passierbar ist, müssen beide Zugbrücken so eingestellt werden, dass sie sich an der exakten Staatsgrenze treffen und eine gerade Linie bilden. Da die Brücken nachts hochgezogen werden, muss die richtige Position jeden Morgen neu eingestellt werden. Dazu bedient man sich eines jahrtausendealten, ehrwürdigen Rituals. Schritt 1. Die beiden Brücken werden in eine beliebige, nichtsenkrechte Position gezogen und so verlängert, dass sie bis zur Staatsgrenze reichen (wir gehen davon aus dass weder die eine noch die andere Brücke zufällig sofort die korrekte Position einnimmt). Schritt 2. Die dirichländische Brücke wird so eingestellt, dass sie die neumannische an der Grenzlinie trifft.

198

Das morgendliche Brückenritual

c a

Neumannien

b

Dirichland

c a

b

Neumannien

Dirichland

Abbildung 3. Oben: Mögliche Brückenpositionen nach Schritt 2; unten: Brücken nach Schritt 3

Schritt 3. Die neumannische Brücke wird so eingestellt, dass sie die gleiche Steigung hat wie die dirichländische und wird dann wieder bis zur Grenze verlängert. Schritt 4. Falls die zwei Brücken jetzt eine gerade Linie bilden, wird das Ritual abgebrochen. Schritt 5. Ansonsten zurück zu 2 Funktioniert dieses Ritual überhaupt?

199

Mathematik im menschlichen Körper

Antwortmöglichkeiten 1. Ja, das Verfahren wird nach höchstens 96 Schritten mit der richtigen Lösung beendet. 2. Ja, das Verfahren wird nach mindestens 96 Schritten mit der richtigen Lösung beendet. 3. Das Verfahren wird nie beendet, aber die Position der Brücken wird immer besser. 4. Das Verfahren wird nie beendet und die Position der Brücken wird nicht besser. 5. Das Verfahren bricht nie ab, aber falls a > b, so wird die Position der Brücken immer besser. 6. Das Verfahren bricht nie ab, aber falls c > a + b, so wird die Position der Brücken immer besser. 7. Das Verfahren wird mit der korrekten Lösung beendet, falls der Höhenunterschied zwischen den Brückenenden am Anfang nicht mehr als c beträgt. 8. Das Ritual bricht nie ab, aber die Position der Brücken wird immer besser, falls der Höhenunterschied zwischen den Brückenenden am Anfang mehr als c + a + b beträgt. 9. Falls für die Brückenlänge  der korrekten Lösung genau 2 = ( a + b)2 + c2 gilt, wird das Verfahren beendet. 10. Das Verfahren wird nie beendet, aber die Lösung wird immer besser, wenn beide Brücken am Anfang eine Ausgangslage haben, die nicht waagerecht ist.

200

Das morgendliche Brückenritual

Lösung (Richtige Lösung: Antwort 5) Als erstes sollte man sich klar machen, dass das Verfahren nie abbricht. Das sieht man so: Angenommen der Zyklus ist ein paarmal durchlaufen worden, und nach Schritt 3 ist auf einmal die korrekte Lösung erreicht. Das bedeutet, dass vor dem letzten Schritt 3 die Brücke auf der dirichländischen Seite schon die korrekte Steigung gehabt haben muss. Überhaupt muss sie die korrekte Position gehabt haben. Da sich deren Position aber an der Position der neumannischen Seite der Brücke orientiert, folgt, dass diese wiederum vorher auch schon die richtige Stellung hatte. Damit sind wir jetzt einmal im Kreis gelaufen und kommen zu dem Schluss, dass, falls das Brückenpaar auf einmal die korrekte Stellung einnimmt, es die gleiche Stellung schon einen Zyklus vorher eingenommen haben muss. Da diese Schlussfolgerung natürlich auch für den vorherigen Zyklus gilt, folgt, dass beide Brücken schon immer die richtige Position hatten. Das aber widerspricht unserer Annahme, dass die Brücken am Morgen nicht in der richtigen Position waren. Dass numerische Verfahren unendlich lange laufen ist nichts Ungewöhnliches. Es gibt in der numerischen Mathematik nur sehr wenige Algorithmen, die ein Problem in einer endlichen Anzahl von Schritten lösen. Man nennt solche Algorithmen direkt. Unglücklicherweise sind sie meistens sehr langsam. Deshalb werden in der Praxis die iterativen Verfahren fast immer bevorzugt. Man verzichtet dabei auf den Anspruch, die exakte Lösung des Problems zu erhalten. Das ist häufig nicht schlimm, da man sowieso keine exakte Lösung des Anwendungsproblems erwarten kann. Dies hat unterschiedliche Gründe, wie z. B. vereinfachende Annahmen in der mathematischen Formulierung des Problems oder auch banale Rundungsfehler, die sich auch auf modernen Rechnern nur mit extremem Aufwand vermeiden lassen. Stattdessen begnügt man sich damit, in einer gewissen Anzahl von Iterationen nah an die exakte Lösung heranzukommen.

201

Mathematik im menschlichen Körper

r c a

Neumannien

b

Dirichland

r c a

b

Abbildung 4. Zur Definition des Fehlers r. Unten die schematische Darstellung

S β rk b’ α’

C a’ α

B

c

rk+1 β’ S’

A

a

b

Abbildung 5. Hilfszeichung zum Beweis dass rk+1 =

b a

· rk

So funktioniert auch das in der Aufgabe beschriebene ,Ritual‘ (Mathematiker nennen es das Dirichlet-Neumann-Verfahren). Um zu

202

Das morgendliche Brückenritual

zeigen dass die Lösung ,immer besser‘ wird, falls a > b ist, müssen wir uns als erstes ein Maß für den Fehler einer Brückenposition ausdenken. Ein mögliches Maß ist das folgende: Nach jedem Schritt 2 liegen die beiden Brückenenden aneinander. Als r bezeichnen wir jetzt den vertikalen, positiven Abstand von dem Punkt, wo sie zusammenstoßen, zu dem Punkt, an dem sie in der exakten Lösung zusammenstoßen würden. Offensichtlich ist r ein gutes Fehlermaß, denn r ist immer positiv und genau dann Null, wenn die Lösung erreicht ist. Überhaupt kann man eine Brückenposition als umso ,besser‘ bezeichnen, je kleiner r ist. Man nehme jetzt an, dass die in der Aufgabe beschriebene Schleife k mal durchlaufen worden ist. Den Fehler nach dem k-ten Durchlauf nennen wir rk . Entsprechend heißt der Fehler nach dem k + 1-ten Durchlauf rk+1 . Wir werden jetzt zeigen, dass immer r k +1 =

b ·r a k

gilt. Dann ist klar, dass r genau dann immer kleiner wird, wenn a > b, bzw. b/a < 1 ist. Man betrachte also die Abbildung 5. Dort ist AS die dirichländische Brücke nach Schritt k, und BS ist die neumannische Brücke nach Schritt k. AS ist die dirichländische Brücke nach Schritt k + 1 und BS die neumannische Brücke nach Schritt k + 1. Da die neumannische Brücke immer so eingestellt wird, dass sie die gleiche Steigung wie die dirichländische hat folgt, dass die Strecken AS und S B parallel sind. Damit muss der Winkel α gleich dem Winkel α sein, und β gleich β . Die Dreiecke ACS und BCS sind also ähnlich, d. h. man kann das eine durch Verschiebungen, Drehungen, Spiegelungen und Größenänderungen in das andere verwandeln. Daraus folgt, dass die Strecken S C und CB im gleichen Verhältnis zueinander stehen wie die Strecken SC und CA. Es gilt also r r k +1 = k b a bzw. b r k +1 =  · r k . a

203

Mathematik im menschlichen Körper

Durch den Strahlensatz weiß man aber, dass kommt man wie gewünscht r k +1 =

b ·r . a k

204

b a

=

b a,

und so be-

Die Schokoladen-Diät Matthias Ehrhardt

Schlankheitskuren sind einerseits ein soziales Phänomen, aber auch ein großer Zweig der Nahrungsmittelindustrie. Die Industrie bietet dabei verschiedene Produkte an, wie Diätlebensmittel, Nahrungsergänzungsmittel, Sportkleidung und -ausrüstung, Übungsvideos und -bücher, usw. Allerdings ist es bekanntermaßen sehr schwer, das einmal erreichte Wunschgewicht auch langfristig zu halten. Häufig tritt dabei der so genannte Jojo-Effekt auf, so dass man schließlich nach der Diät mehr wiegt als vorher. Hier möchten wir ein mathematisches Modell für Diäten entwickeln und das langfristige Verhalten der Lösung (d. h. des Körpergewichts) studieren. Modellierung. Die Funktion G (t) bezeichne das Gewicht des Menschens zur Zeit t. Sie erfüllt die Differentialgleichung (kurz: DGL)   (1) G  (t) = E(t) − A(t) − S G (t) , t ≥ 0, wobei E(t) ≥ 0 die Essensaufnahme-Funktion (in Kalorien pro Zeit), A(t) ≥ 0 ein Maß für die körperliche Aktivität ist und   S G (t) ≥ 0 den Stoffwechsel modelliert, der vom Gewicht G (t) abhängt. Mit G  (t) bezeichnet man die Ableitung der Funktion G (t). Sie gibt an, wie steil oder flach die Kurve G (t) an einem Punkt t ist – geometrisch entspricht sie der Tangentensteigung in diesem Punkt. Als erstes Modell kann man die folgende Funktion wählen   3 (2) S G (t) = σG (t) 4 , wobei σ > 0 ein reeller Parameter ist. Nun ist die einfachste Diät-Strategie die Essensaufnahme (z. B. Schokolade) und die Essensverbrennung (beispielsweise beim Lösen

205

Mathematik im menschlichen Körper

mathematischer Probleme) über einen überschaubares Zeitintervall als konstant anzusehen, d. h. zu mitteln. Wir legen dieses Zeitintervall auf einen Tag fest und setzen die konstante Essensrate (Kalorien/Tag) als E¯ und analog die konstante Kalorien-Verbrennungsrate als A¯ an, d. h.

[ E(t) − A(t)]Tag = E¯ − A¯ = λ,

(3)

wobei der Parameter λ im allgemeinen positiv ist: λ > 0. Einsetzen von Gleichung (2) und (3) in (1) liefert nun die Gleichung 3

G  (t) = λ − σG (t) 4 ,

t ≥ 0,

(4)

Dies ist eine nichtlineare Differentialgleichung 1. Ordnung, die von 2 Parametern λ und σ abhängt. Gleichung (4) hat keine elementare explizite Lösung, aber auch ohne Kenntnis einer solchen Lösung kann man wichtige Erkenntnisse gewinnen. Bei einer Diät ist man am Langzeitverhalten der Lösungen von (4) interessiert; dieses wird bestimmt durch die zeitlich konstanten Lösungen G¯ (t) von (4), für die gilt G¯  (t) = 0. Frage 1. Was ist die konstante Lösung G¯ von (4) (für festes λ und σ)? Weiterhin ist wichtig, wie stabil sich die Gewichtsfunktion G (t) dicht an G¯ verhält, d. h. wie wirken sich kleine Schwankungen g(t) des Körpergewichts aus. Dazu machen wir den so genannten Störungsansatz G (t) = G¯ + g(t),

¯ | g(0)| 0 anhand von (4) abgelesen werden: Frage 3. Wie ist das Vorzeichen der Ableitung von G links/rechts ¯ von G? Zusatzfrage.

Was bedeutet das eigentlich?

Bemerkung. Ein komplexeres Modell ist durch die Stoffwechselfunktion   S G (t) =

σ1 G (t) , 1 + σ2 G (t)1−α

0 < α < 1,

mit positiven Parametern σ1 , σ2 gegeben. Beide Modelle sind konsistent mit bekannten Daten über Diäten.

207

Mathematik im menschlichen Körper

Antwortmöglichkeiten 1.

G¯ =

 4 λ σ

G  (t) =

2.

3.

4.

5.

6.

7.

8.

3



, lim g(t) = 0, t→∞

¯ > 0, G > G,

¯ < 0, 0 < G < G;  4 3 G¯ = λσ , lim g(t) = 0,  t→∞ ¯ < 0, G > G, G  (t) = ¯ > 0, 0 < G < G;  4 3 G¯ = λσ , lim g(t) existiert nicht,  t→∞ ¯ > 0, G > G, G  (t) = ¯ < 0, 0 < G < G;  4 3 G¯ = λσ , lim g(t) = ∞,  t→∞ ¯ < 0, G > G, G  (t) = ¯ > 0, 0 < G < G; σ3 G¯ = λ 4 , lim g(t) = 0,  t→∞ ¯ > 0, G > G, G  (t) = ¯ < 0, 0 < G < G; 3   Fixpunkt G¯ = λσ 4 , lim g(t) = 0, t→∞  ¯ < 0, G > G, G  (t) = ¯ > 0, 0 < G < G; σ3 G¯ = λ 4 , lim g(t) existiert nicht,  t→∞ ¯ > 0, G > G, G  (t) = ¯ < 0, 0 < G < G; 3   G¯ = λσ 4 , lim g(t) = ∞, t→∞

208

Die Schokoladen-Diät

 G  (t) =

9. 10.

¯ < 0, G > G,

¯ > 0, 0 < G < G; Teilprobleme sind lösbar, aber nicht eindeutig; Mindestens ein Teilproblem ist nicht lösbar.

209

Mathematik im menschlichen Körper

Lösung (Richtige Lösung: Antwort 2) Lösung 1: Konstante Lösung G¯ von (4). Konstante Lösung bedeutet G  (t) = 0 setzen in (4), d. h. G¯ ist die Lösung von 3 0 = λ − σ G¯ 4

und somit ergibt sich G¯ =

 4 λ 3 . σ

Lösung 2: Grenzwert von g(t) für t → ∞. tialgleichung 1. Ordnung (6) g (t) = − Rg,

(7) Aus der linearen Differen-

R > 0,

(6)

folgt wegen des Vorzeichens von R, dass lim g(t) = 0 gilt. t→∞

¯ Lösung 3: Vorzeichen der Ableitung von G links/rechts von G. kennt unmittelbar an (4):  ¯ < 0, G > G, G (t) = ¯ > 0, 0 < G < G.

Man er-

Somit kann man folgern, dass alle Lösungen mit zunehmender Zeit monoton die konstante Lösung G¯ erreichen, d.h. ¯ lim G (t) = G,

t→∞

G (0) > 0.

Abbildung 1 zeigt typische Lösungen von (4) und illustriert die Rolle ¯ von G. Für jeden einzelnen Menschen ist σ > 0 konstant und die DiätStrategie ist in diesem mathematischen Modell durch die Wahl eines (positiven) Wertes für λ bestimmt. Jeder Wert von λ bestimmt ein finales Körpergewicht G¯ gegeben durch (7).

210

Die Schokoladen-Diät G(t)

_

_ G

+

t

Abbildung 1. Typische Lösungen von (4)

Da der Wert von G¯ als Funktion von λ schneller wächst als eine lineare Funktion (eine Gerade), zeigt das Modell, dass signifikante Änderungen in der Diät-Strategie zu sehr großen Änderungen im finalen Körpergewicht G¯ führen. Nehmen wir einmal an, das Individuum strebt nach einem Gewichtsverlust. Ferner sei G¯ A das Anfangsgewicht und G¯ E das angestrebte Endgewicht: G¯ A > G¯ E . Aus Gleichung (7) können wir schließen, dass daher der Diät-Parameter λ wie folgt reduziert werden muss: 3

3

λ A = σ G¯ A4 > λ E = σ G¯ E4 Abbildung 2 illustriert einen typischen Gewichtsverlust. Zum Zeitpunkt t = t0 beginnt die Diät und das Körpergewicht G (t) sinkt monoton auf den angestrebten Wert G¯ E . Natürlich kann der Wert von λ durch verschiedene Kombinationen von E¯ und A¯ erreicht werden, vgl. Gleichung (3). Der Fall λ ≤ 0. Normalerweise ist, wie in der Aufgabe angenommen, der Parameter der Diät-Strategie λ > 0. Der Fall λ ≤ 0 ist

211

Mathematik im menschlichen Körper G(t) _ GA

_ GE

t

t0

Abbildung 2. Ein typischer Gewichtsverlust

’pathologisch’: alle Lösungen von (4) streben dann zu Null lim G (t) = 0,

t→∞

λ ≤ 0,

d. h. dieser Fall korrespondiert zum Hungertod: E¯ = 0 und A¯ ≥ 0. Für eine reale Person gilt stets G (t) ≥ 0. Wenn nun zu einem Zeitpunkt t = t1 G (t1 ) = 0 ist, so setzen wir sinnvollerweise G (t) = 0 für alle Zeiten t ≥ t1 .

1. R.E. Mickens, D.N. Brewley und M.L. Russel, A Model of Dieting, SIAM Rev. 40 (1998), Seiten 667–672. 2. R.L. Leibel, M. Rosenbaum und J. Hirsch, Changes in energy expenditure resulting from altered body weight, The New England Journal of Medicine 332 (1995), Seiten 621–628. 3. T.A. McMahon und J.T. Bonner, On Size and Life, Scientific American Library, New York, 1985, Seiten 64–66.

212

Von Bakterien und Antibiotika Alexander Bockmayr und Abdelhalim Larhlimi

In jedem Lebewesen spielt der Stoffwechsel oder Metabolismus eine zentrale Rolle. Dabei werden verschiedene Stoffe aus der Umgebung aufgenommen, innerhalb des Organismus umgewandelt und schließlich in veränderter Form wieder abgegeben. Auf diese Weise gewinnt die Zelle die Energie und stellt die Bausteine her, die für die Aufrechterhaltung der biologischen Funktionen benötigt werden. Die Erforschung des Stoffwechsels hat eine Vielzahl von Anwendungen. In der Biotechnologie etwa versucht man, die Stoffwechselprozesse von Bakterien so zu beeinflussen, dass die Erzeugung bestimmter Stoffe (z. B. Antibiotika) verbessert wird. In der Medizin hängen zahlreiche Krankheiten mit Störungen des Stoffwechsels zusammen. Auch hier kommt es darauf an, Stoffwechselvorgänge besser zu verstehen und wenn nötig darauf einzuwirken. Der Stoffwechsel in einer Zelle bildet ein komplexes Netzwerk, an dem Tausende von Stoffen und Reaktionen beteiligt sein können. Mathematisch kann das Zusammenwirken der verschiedenen biochemischen Reaktionen, mit denen Substrate in Produkte umgewandelt werden, in Form eines metabolischen Netzes dargestellt werden. Ein kleines Beispiel davon findet sich in Abbildung 1. Zunächst sind da verschiedene Ausgangsstoffe S1 , S2 , S3 , S4 , von denen man annimmt, dass sie in beliebiger Menge zur Verfügung stehen. In einer Reihe von Reaktionen, die durch die Pfeile 1, . . . , 13 dargestellt sind, können daraus Zwischenprodukte A, B, . . . , H hergestellt werden, aus denen dann die Endprodukte P1 , P2 entstehen. Bei der Untersuchung metabolischer Netze interessiert man sich für die Frage, auf welche Weise ein bestimmter Stoff hergestellt werden kann. Oft gibt es dafür nicht nur eine, sondern verschiedene Möglichkeiten. Um sich einen Überblick zu verschaffen, was in ei-

213

Mathematik im menschlichen Körper

S1

1

A 2

S2

5

B

D

P1

10

E 8

11

C

4

G

7 6

S3

3

12

9

H

P2

F 13

S4 Abbildung 1. Metabolisches Netwerk

nem Netzwerk alles passieren kann, sucht man nach den minimalen Reaktionswegen zur Herstellung eines oder mehrerer Endprodukte. Unter einem Reaktionsweg versteht man dabei eine nichtleere Menge von Reaktionen (die nicht unbedingt in der ablaufenden Reihenfolge aufgelistet sind) mit den folgenden Eigenschaften: 1. Ein Zwischenprodukt kann nur verwendet werden, wenn es zuvor hergestellt wurde. Ein Beispiel: Bei den Reaktionen 2 und 8, die jeweils zwei Zwischenprodukte verwenden, müssen diese beide vorhanden sein. 2. Ein Zwischenprodukt darf nur hergestellt werden, wenn es in einer nachfolgenden Reaktion auch verbraucht wird. Die Reaktion 10 spielt eine Sonderrolle. Innerhalb eines Reaktionsweges kann sie in die eine oder die andere Richtung durchlaufen werden, nicht aber in beide Richtungen gleichzeitig. Ein Reaktionsweg heißt minimal, wenn man nicht eine oder mehrere Reaktionen auslassen kann, ohne die Bedingung 1 oder 2

214

Von Bakterien und Antibiotika

zu verletzen. Ein Beispiel für einen minimalen Reaktionsweg ist die Menge {1, 2, 3, 4, 5}. Frage a. Wie viele minimale Reaktionswege gibt es? Manchmal möchte man in einem metabolischen Netz die Erzeugung bestimmter Stoffe verhindern, z. B. wenn diese bei der Entstehung von Krankheiten eine Rolle spielen. Man versucht dann, Stellen innerhalb des Netzwerkes zu identifizieren, die sich als Ziel einer medikamentösen Therapie eignen. Dazu sucht man minimale Mengen von Reaktionen, deren Blockade die Entstehung des unerwünschten Stoffes (auch über mögliche Umwege) definitiv ausschließt. In unserem Beispiel könnte dies das Endprodukt P2 sein. Ein naheliegendes Vorgehen wäre, direkt die Reaktion 9 zu unterbinden, was aber nicht immer möglich ist. Wenn die Reaktion 9 selbst nicht blockiert werden kann, müssen mindestens zwei andere Reaktionen blockiert werden, um die Herstellung des Endprodukts P2 zu verhindern, z. B. {8, 10}. Frage b.

Wie viele solche zweielementige Blockademengen gibt es?

Antwortmöglichkeiten 1. 2. 3. 4. 5.

Es gibt 8 minimale Reaktionswege und 10 zweielementige Blockademengen. Es gibt 8 minimale Reaktionswege und 12 zweielementige Blockademengen. Es gibt 10 minimale Reaktionswege und 8 zweielementige Blockademengen. Es gibt 10 minimale Reaktionswege und 10 zweielementige Blockademengen. Es gibt 10 minimale Reaktionswege und 12 zweielementige Blockademengen.

215

Mathematik im menschlichen Körper

6. 7. 8. 9. 10.

Es gibt 10 minimale Reaktionswege und 14 zweielementige Blockademengen. Es gibt 12 minimale Reaktionswege und 8 zweielementige Blockademengen. Es gibt 12 minimale Reaktionswege und 10 zweielementige Blockademengen. Es gibt 12 minimale Reaktionswege und 12 zweielementige Blockademengen. Es gibt 14 minimale Reaktionswege und 10 zweielementige Blockademengen.

216

Von Bakterien und Antibiotika

Lösung (Richtige Lösung: Antwort 8) Es gibt 12 minimale Reaktionswege und 10 zweielementige Blockademengen. Um die minimalen Reaktionswege zu bestimmen, halten wir folgende Eigenschaften unseres Netzwerkes fest: 1. Die Reaktionen 1, 2 und 3 können nur gemeinsam oder gar nicht ablaufen. 2. Die Reaktionen 7 und 8 können nur gemeinsam oder gar nicht ablaufen. 3. Für jeden minimalen Reaktionsweg gilt: a. Wenn Reaktion 12 beteiligt ist, dann auch die Reaktionen 7 und 8, nicht aber Reaktion 13. b. Wenn Reaktion 6 beteiligt ist, dann auch Reaktion 11, nicht aber Reaktion 5. c. Ist Reaktion 10 an der Umwandlung von G in H beteiligt, dann auch die Reaktionen 1, 2 und 3. d. Ist Reaktion 10 an der Umwandlung von H in G beteiligt, dann auch die Reaktionen 7 und 8. 4. Jeder minimale Reaktionsweg führt zur Herstellung mindestens eines der beiden Endprodukte. Auf diese Beobachtungen gestützt suchen wir zuerst die minimalen Reaktionswege, die zur Herstellung von Endprodukt P1 führen (d. h. Reaktion 4 beinhalten). Dann bestimmen wir die minimalen Reaktionswege, die zur Herstellung von Endprodukt P2 führen (d. h. Reaktion 9 beinhalten). Abbildung 2 veranschaulicht die Gesamtheit der möglichen minimalen Reaktionswege, indem es die Abhängigkeiten zwischen den Reaktionen darstellt (wenn zum Beispiel Reaktion 4 beteiligt ist, dann auch entweder 1, 2, 3 oder 7, 8, 10 usw.). Wenn wir nun die einzelnen Wege aus Abbildung 2 von links beginnend auflisten, erhalten wir folgende minimale Reaktionswege (in Mengenschreibweise, also nach Zahlen aufsteigend sortiert

217

Mathematik im menschlichen Körper 9

4

5

1,2,3 ,10

7,8 ,10

1,2,3

6,11

11,12

5

6,11

13

12

5

7,8

6,11

13

5

11,12

6,11

13

12

13

Abbildung 2. Minimale Reaktionswege

und nicht in der Reihenfolge der Reaktionen): 1. 2. 3. 4. 5. 6.

{1, 2, 3, 4, 5} {1, 2, 3, 4, 6, 11} {4, 5, 7, 8, 10, 11, 12} {4, 5, 7, 8, 10, 13} {4, 6, 7, 8, 10, 11, 12} {4, 6, 7, 8, 10, 11, 13}

7. 8. 9. 10. 11. 12.

{1, 2, 3, 5, 9, 10} {1, 2, 3, 6, 9, 10, 11} {5, 7, 8, 9, 11, 12} {5, 7, 8, 9, 13} {6, 7, 8, 9, 11, 12} {6, 7, 8, 9, 11, 13}

Die zweielementigen Blockademengen können aus Abbildung 2 wie folgt bestimmt werden: Wir müssen sicherstellen, dass durch Blockade von nur zwei (von Reaktion 9 verschiedenen) Reaktionen alle Reaktionswege zur Herstellung von Endprodukt P2 verhindert werden. Dies ist entweder durch Blockade einer Reaktion aus der Menge {1, 2, 3, 10} zusammen mit einer Reaktion aus der Menge {7, 8} möglich, oder durch eine Blockade von Reaktion 5 zusammen mit einer Reaktion aus der Menge {6, 11}. Insgesamt ergeben sich 4 · 2 + 1 · 2 = 10 Möglichkeiten, nämlich: 1. 2. 3. 4. 5.

{1, 7} {1, 8} {2, 7} {2, 8} {3, 7}

6. 7. 8. 9. 10.

218

{3, 8} {10, 7} {10, 8} {5, 6} {5, 11}

Das DNA-Puzzle Stefan Kirchner

Im Jahre 1953 wurde von James Watson und Francis Crick erstmalig der strukturelle Aufbau der sogenannten DNA (Desoxyribonukleinsäure) beschrieben, welche das Erbgut jedes Lebewesens enthält. Der wesentliche Teil des Erbguts wird dabei durch eine sehr lange Folge der vier Basen Adenin (A), Cytosin (C), Guanin (G) und Thymin (T) codiert. Seit einigen Jahren ist es möglich, die Folge der vier Basen zu einer gegebenen DNA zu bestimmen. Biologen bezeichnen diesen Vorgang als Sequenzierung. Die DNA oder auch Teile einer DNA sind aus verschiedenen Gründen von Interesse. Auf einigen Abschnitten sind zum Beispiel Gene codiert, deren genaue Sequenz für ein besseres Verständnis und eine gezielte Behandlung einiger Erbkrankheiten von entscheidender Bedeutung ist. Andere Abschnitte der DNA sind insbesondere für den genetischen Fingerabdruck relevant. Dieser hat in den letzten Jahren die Kriminalistik revolutioniert und ermöglichte die Aufklärung vieler schwerer Straftaten. Für die Sequenzierung der DNA finden sogenannte Sequenziermaschinen Verwendung, die in der Lage sind, DNA-Stränge mit einigen hundert Basen zu lesen. Dies ist jedoch viel zu wenig, um die komplette DNA in einem Schritt zu lesen. Die DNA eines Menschen beispielsweise besteht aus etwa drei Milliarden Basen und auch die DNA eines der Lieblingsobjekte der Molekularbiologen, der Taufliegenart Drosophila melanogaster, besteht immerhin noch aus 120 Millionen Basen. Dennoch gelang im Rahmen des Humangenomprojekts Anfang dieses Jahrtausends die vollständige Sequenzierung des menschlichen Erbguts. Die Forscher verwendeten dabei ein Mitte der 90er Jahre entwickeltes Verfahren, das Shotgun-Sequenzierung genannt

219

Mathematik im menschlichen Körper ACTGGTACAGTGGATGTGTAAGCGAAGCGCGAGTGAAGCCA ACTGGTACAGTGGATGTGTAAGCGAAGCGCGAGTGAAGCCA ACTGGTACAGTGGATGTGTAAGCGAAGCGCGAGTGAAGCCA ACTGGTACAGTGGATGTGTAAGCGAAGCGCGAGTGAAGCCA ACTGGTACAGTGGATGTGTAAGCGAAGCGCGAGTGAAGCCA

Abbildung 1. Vervielfältigung der DNA ACTGGTACAGTGGATGTGT

AAGCGAAGCGC

ACTGGTACAG

GTAAGCGA

ACTGGTA ACTGG ACTGGT

TGGATGT

CAGTGGAT

GTGTAAGCGAAGC

TACAGTGGATGT

GTAAGCGAA

ACAGTG

GATGTGTAA

GAGT

GAAGCCA

AGCGCGAGTGAAGCCA GCGAGTGAAGCCA

GCGCGAGTGAAGCCA

GCGAAGCGCG

AGTGAAGCCA

Abbildung 2. Zerhacken in DNA-Fragmente

wird und inzwischen ein Standardverfahren in der DNA-Sequenzierung geworden ist. Dieses Verfahren wird im Folgenden vereinfacht beschrieben. In einem ersten Schritt wird die DNA vervielfältigt (siehe Abbildung 1). Anschließend werden die DNA-Stränge mittels Ultraschall an zufälligen Stellen zerhackt (siehe Abbildung 2). Die dabei enstehenden Teile der DNA, im Folgenden DNA-Fragmente genannt, sind dann so kurz, dass sie von den Sequenziermaschinen gelesen werden können. Dabei mischen sich die Fragmente. In einem letzten Schritt wird die Ursprungs-DNA aus diesen Fragmenten mit Hilfe von Computern unter Verwendung ausgefeilter Algorithmen rekonstruiert (siehe Abbildung 3). Im Folgenden betrachten wir den letzten Schritt etwas genauer. Bei der Rekonstruktion der Fragmente zu der Ursprungs-DNA macht man sich zunutze, dass die Anfangssequenz (sog. Präfix) eines Fragments mit der Endsequenz (sog. Suffix) eines anderen Fragments übereinstimmt. Ist die gemeinsame Übereinstimmung hinreichend lang, so ist die Wahrscheinlichkeit recht groß, dass der Präfix und der Suffix die gleiche Stelle der Ursprungs-DNA reprä-

220

Das DNA-Puzzle GAGT

ACTGGTACAG ACTGGT

TACAGTGGATGT GCGAAGCGCG AAGCGAAGCGC

TGGATGT

ACAGTG

GTAAGCGA

GATGTGTAA

AGCGCGAGTGAAGCCA

GTGTAAGCGAAGC GAAGCCA

GCGCGAGTGAAGCCA

AGTGAAGCCA ACTGGTA

GTAAGCGAA

GTAAGCGAA

ACTGG CAGTGGAT

GCGAGTGAAGCCA

ACTGGTACAGTGGATGTGT

??? ACTGGTACAGTGGATGTGTAAGCGAAGCGCGAGTGAAGCCA

Abbildung 3. Durchmischung und Rekonstruktion

sentieren und aus jeweils zwei verschiedenen Kopien der DNA stammen. Mit Hilfe der Wahrscheinlichkeitsrechnung kann dann folgendes Resultat gezeigt werden: Werden hinreichend viele Kopien angefertigt und sind im Durchschnitt die Fragmente nicht zu kurz – aber auch nicht zu lang, so dass sie von den Sequenziermaschinen komplett gelesen werden können – dann ist die Annahme gerechtfertigt, dass gerade das kürzeste Wort, das alle Fragmente als Teilwörter enthält, die Ursprungs-DNA ist. Das Zusammenfügen der Fragmente wird dabei mit Hilfe von Computern erledigt. Bei mehreren Millionen Fragmenten ist eine Berechnung per Hand auch nicht mehr möglich. Die folgenden beiden Aufgaben haben daher auch nur illustrierenden Charakter, da ein realistisches Beispiel den Rahmen dieses Buches sprengen würde. Zunächst kann jedoch das Zusammenfügen der Fragmente auch abstrakt formuliert werden, ohne dass man dabei etwas über die DNA wissen müsste. Das ist eine generelle Stärke der Mathematik, dass sie losgelöst von Anwendungen das eigentliche Problem bearbeiten kann. Es sei eine endliche Menge von Wörtern gegeben. Bestimme ein kürzestes Wort, das jedes gegebene Wort als Teilwort enthält. Betrachte das folgende Beispiel, bei dem die folgenden vier Wörter (Fragmente) von der Sequenziermaschine gelesen wurden.

221

Mathematik im menschlichen Körper

1. 2. 3. 4.

TACAGC CAGCG CGTAC ACGT

Gesucht ist nun ein kürzestes Wort, das jedes dieser vier Wörter als Teilwort enthält. Mit ein wenig Überlegen erhält man als Lösung das Wort ACGTACAGCG: ACGTACAGCG 4. ACGT 3. CGTAC 1. TACAGC 2. CAGCG Nach diesem Beispiel wird nun ein kürzestes Wort gesucht, das die folgenden sieben Wörter enthält. GTGA

CGG

CGAC

GGTG

TGAC

GTGTG

Antwortmöglichkeiten 1. 2. 3. 4. 5. 6. 7. 8. 9. 10.

Das kürzeste Wort besteht aus 10 Buchstaben. Das kürzeste Wort besteht aus 11 Buchstaben. Das kürzeste Wort besteht aus 12 Buchstaben. Das kürzeste Wort besteht aus 13 Buchstaben. Das kürzeste Wort besteht aus 14 Buchstaben. Das kürzeste Wort besteht aus 15 Buchstaben. Das kürzeste Wort besteht aus 16 Buchstaben. Das kürzeste Wort besteht aus 17 Buchstaben. Das kürzeste Wort besteht aus 18 Buchstaben. Das kürzeste Wort besteht aus 19 Buchstaben.

222

ACGG

Das DNA-Puzzle

Lösung (Richtige Lösung: Antwort 3) Das kürzeste Wort ist CGACGGTGTGAC und besteht aus 12 Buchstaben. CGACGGTGTGAC CGAC ACGG CGG GGTG GTGTG GTGA TGAC Die korrekte Antwort lautet daher 12. Wie kann das Problem aber allgemein gelöst werden? Zunächst können alle Wörter aus der Aufgabenstellung entfernt werden, die als Teilwort in einem anderen Wort vorkommen. In diesem Beispiel ist CGG das einzige Wort, das als Teilwort in einem anderen Wort (ACGG) vorkommt. Der nächste Schritt besteht darin zu erkennen, dass gegenüber dem einfachen Aneinanderhängen zweier Wörter die Länge sich verkürzen lässt, wenn ein Endstück von einem Wort genau das Anfangsstück von einem anderen Wort ist. Die maximale Länge eines solchen End- bzw. Anfangstückes wird als Überlappungslänge bezeichnet. Diese gibt an, wie viele Buchstaben eingespart werden. In Abbildung 4 ist der dazugehörige Überlappungsgraph abgebildet, wobei der Übersicht halber nur Verbindungen (sog. Kanten) eingezeichnet sind, die eine Überlappungslänge von mindestens 1 haben. Die Aufgabe wird mit Hilfe des Überlappungsgraphen relativ einfach, wenn in einem kürzesten Wort zusätzlich die gegebenen Wörter in einer zuvor festgelegten Reihenfolge σ vorkommen sollen. Man geht im Überlappungsgraphen in der gegebenen Reihenfolge σ von Wort zu Wort entlang und addiert die jeweiligen Überlappungs-

223

Mathematik im menschlichen Körper CGAC

2

ACGG

1 2

1

GTGTG

2 1 3

GGTG

2

3 2

TGAC

1

3 3

GTGA

Abbildung 4. Der Überlappungsgraph von der gegebenen Instanz

längen. Die Summe Sσ ist dann genau die Anzahl Buchstaben, die man durch das Ineinanderschieben gegenüber dem einfachen Aneinanderhängen einspart. Das kürzeste Wort bezüglich der gegebenen Reihenfolge σ hat dann eine Gesamtlänge von Länge des Wortes bei einfachem Aneinanderhängen − Sσ . Der Minuend ist konstant (in der Aufgabe ist er 25), aber der Subtrahend ist abhängig von der Reihenfolge σ, in der die einzelnen Wörter vorkommen. Damit die Länge des Gesamtwortes minimiert wird, muß also Sσ maximiert werden. Mit ein wenig systematischem Suchen erkennt man, dass die Reihenfolge σ, die Sσ maximiert, durch die hervorgehobenen Kanten in Abbildung 4 bestimmt wird. Bei dieser Reihenfolge werden 13 Buchstaben gespart (Sσ = 2 + 2 + 3 + 3 + 3 = 13), somit ist 25 − 13 = 12 die Gesamtlänge eines kürzesten Wortes, das die vorgegebenen Wörter enthält. Geht es noch besser als 12? Nein! Am einfachsten erkennt man das, wenn die Aufgabe ohne GGTG und GTGA gestellt wird. Betrachte nun den Überlappungsgraphen ohne diese beiden Wörter, d. h. entferne die beiden Wörter samt ihrer angrenzenden Kanten. Dann existieren keine Kanten mehr mit Überlappungslänge drei, es gibt

224

Das DNA-Puzzle

nur noch drei Kanten mit Überlappungslänge zwei ((CGAC, ACGG), (TGAC, ACGG) und (GTGTG, TGAC)). Prinzipiell wäre damit maximal eine Einsparung von 3 · 2 = 6 Buchstaben erreichbar. Da diese drei Kanten jedoch keinen Pfad bilden, sind maximal fünf Buchstaben einsparbar, was über den Pfad CGAC → ACGG → GTGTG → TGAC tatsächlich auch erreicht wird. Dieser Pfad führt dann, bei dieser eingeschränkten Aufgabe, zum optimalen Lösungswort CGACGGTGTGAC bestehend aus zwölf Buchstaben. Andererseits ist dieses Wort auch eine gültige Lösung für unser Ausgangsproblem mit den zusätzlichen Wörtern GGTG und GTGA. Da zusätzliche Wörter in dieser Aufgabe die Länge des Lösungswortes nicht verkürzen können, sind im Ursprungsproblem daher mindestens zwölf Buchstaben nötig.

225

Die kalte Zunge Sören Bartels und Rüdiger Müller

Gefühlte Temperaturen. Ist ein Null Grad Celsius kalter Metallstab eigentlich kälter als ein Holzstab mit der selben Temperatur? Rein physikalisch gesehen natürlich nicht, aber wenn wir beide Stäbe anfassen, kommt uns der Metallstab deutlich kälter vor. Und wer kennt nicht die Szene aus dem Film Dumm und Dümmer in der Harry mit seiner Zunge am Metallrahmen des Skilifts hängen bleibt. Würde das auch passieren, wenn man an einem eiskalten Stück Holz lecken würde? Wohl kaum, doch woran liegt das eigentlich? Unterschiedliche Materialien haben verschiedene Fähigkeiten, Wärme zu übertragen und zu leiten. So transportiert Metall die von der Zunge ausgehende Wärme sehr schnell weiter und verändert seine Temperatur kaum, während die Zunge abkühlt. Holz hingegen leitet Wärme fast gar nicht und daher wird der Teil, der von der Zunge berührt wird, aufgewärmt. Industrielle Anwendungen. Ein gutes Verständnis von der Ausbreitung von Wärme ist nicht nur beim Skilaufen wichtig. Bei Katalysatoren von Autos und bei Computerchips treten sehr hohe Temperaturen auf und könnten diese Bauteile zerstören. Um dies zu verhindern, führt man am Computer Simulationen durch, die einem verraten, ob ein Chip den auftretenden Temperaturen standhalten kann. Dadurch kann man es in der Entwicklung vermeiden, kostspielige Prototypen zu produzieren und für die Produktion verhindern, zu teure temperaturbeständige Materialien zu verwenden. Mathematische Beschreibung. Um ein physikalisches Experiment am Computer durchführen zu können, muss man zunächst einige mathematische Gleichungen herleiten, die das Verhalten der Temperatur beschreiben. Der Begriff der Temperatur für sich ist sehr kom-

227

Mathematik im menschlichen Körper

Abbildung 1. Die Änderung der Wärmemenge in jedem kleinen Würfel wird durch die Bilanz des ein- und austretenden Wärmeflusses bestimmt.

pliziert aber dennoch lässt sich mit einfachen Argumenten eine praxistaugliche mathematische Beschreibung formulieren. Betrachten wir einen kleinen Würfel innerhalb des Metallstabs, so entspricht die zeitliche Veränderung der Gesamtwärme, die in diesem Würfel enthalten ist, genau der Wärmemenge, die über die Seiten des Würfels hinein- beziehungsweise hinausfließt. Wenn wir uns jetzt noch klarmachen, dass Wärme immer von Regionen hoher Temperaturen in solche niedrigerer Temperaturen fließt, so ist die mathematische Beschreibung des physikalischen Vorgangs nahezu komplett. Gibt die Funktion f (t, x ) die Temperatur im Stab an, so führt unsere Argumentation auf die Gleichung f  (t, x ) = κ · f  (t, x ) .

(1)

Hier ist f (t, x ) eine Funktion, die von der Zeit t und dem Ort x abhängt, während κ eine Konstante ist, die die Temperaturleitfähigkeit eines Materials angibt. Die Funktion f  (t, x ) ist die Ableitung von f (t, x ) nach der Zeit t, wenn wir x als Konstante betrachten. Ist zum Beispiel f (t, x ) = t3 cos( x ) + x2 sin(2t),

228

Die kalte Zunge

so ist f  (t, x ) = 3t2 cos( x ) + 2x2 cos(2t) . Die auf der rechten Seite unserer Gleichung stehende Funktion f  (t, x ) ist die bekannte zweite Ableitung von f (t, x ) nach x, also im Beispiel f  (t, x ) = −t3 sin( x ) + 2x sin(2t) und f  (t, x ) = −t3 cos( x ) + 2 sin(2t) . Anfangs- und Randbedingungen. Wir müssen noch festlegen, wie die Wärme zu Beginn des Experiments im Stab verteilt ist und was am Rand passiert, also ob der Stab beispielsweise isoliert ist oder ob an einer Stelle eine Wärmequelle, wie etwa eine Zunge, den Stab berührt. Die Anfangstemperatur wird durch eine nur von x abhängige Funktion f 0 ( x ) vorgegeben, das heißt wir fordern zum Zeitpunkt t = 0, dass (2) f (0, x ) = f 0 ( x ) gilt. Wollen wir beschreiben, dass der Stab an den Enden, die sich bei x = 0 und x = 1 befinden, immer auf Null Grad gehalten wird, so stellen wir zusätzlich die Bedingung, dass f (t, 0) = 0

und

f (t, 1) = 0

(3)

für alle positiven Zeiten t gelten. Man kann zeigen, dass die Gleichungen (1), (2) und (3) eine gute Beschreibung der tatsächlich auftretenden Temperatur liefern. Doch wie kann man die unbekannte Funktion f (t, x ) bestimmen? Mit Zettel und Bleistift ist dies in aller Regel nicht möglich und daher müssen wir den Computer zur Hilfe heranziehen. Lösungsmethode für den Computer. Ein Rechner kann uns auf einem festgelegten Raster von Punkten gute Näherungswerte der Lösung liefern. Wir wählen dazu für die x-Variable im gleichen Abstand Δx

229

Mathematik im menschlichen Körper

f

f’

Δx x j−1

xj

x j−1

xj

x j+1

Δx

x j+1

Abbildung 2. Näherungen für f  ( x j−1 ) und f  ( x j ) (links) und daraus resultierende Näherung für f  ( x j ) (rechts)

voneinander J + 1 Punkte x j = j · Δx, wobei j = 0, 1, 2, . . . , J, und setzen dort f j0 := f (0, x j ) = f 0 ( x j ) . Anstatt der Ableitung f  können wir damit nur noch Differenzenquotienten berechnen, die der Steigung im Steigungsdreieck entsprechen, also   1 f (t, x j+1 ) − f (t, x j ) , f  (t, x j ) ≈ Δx wie in Abbildung 2 skizziert. Für die zweite Ableitung wenden wir wiederum einen Differenzenquotienten an, nur diesmal rückwärts    1 f  (t, x j ) ≈ Δx f (t, x j ) − f  (t, x j−1 )   ≈ (Δx1 )2 − f (t, x j−1 ) + 2 f (t, x j ) − f (t, x j+1 ) . Auch für die Zeitvariable t wählen wir Punkte tn = n · Δt, mit n = 0, 1, 2, . . . , N, und bestimmen für n ≥ 1 den Differenzenquotienten f  ( t n +1 , x ) ≈

1 Δt

( f (tn+1 , x ) − f (tn , x )) .

Setzen wir die Näherungen in unsere Gleichung (1) ein, so erhalten wir die rekursive Berechnungsvorschrift f jn+1 = s · ( f jn−1 + f jn+1 ) + (1 − 2s) · f jn ,

(4)

wobei wir zur Vereinfachung der Schreibweise die Vereinbarungen Δt f jn := f (tn , x j ) und s := κ Δx 2 getroffen haben. Die Formel (4) gestattet uns, die Temperatur an den inneren Punkten des Metallstabs

230

Die kalte Zunge

zu berechnen. Um die Temperatur auch an den Randpunkten zu erhalten, verwenden wir die Randbedingungen und setzen f 0n = 0

und

f Jn = 0 .

1 . Zum Zeitpunkt t0 = 0 sei er Für den Metallstab gelte κ = 100 in der Mitte durch die Zunge aufgewärmt und befinde sich überall sonst noch auf der Umgebungstemperatur von 0 Grad Celsius. Ab welchem Zeitpunkt t∗ ist der Stab überall auf weniger als 10 Grad Celsius abgekühlt? Für eine einfache Abschätzung wählen Sie J + 1 1 = 11 Gitterpunkte im Ort, also Δx = 10 , sowie Δt = 14 und setzen 0 0 f 5 = 36 und f j = 0 für j = 0, 1, . . . , 4 und j = 6, 7, . . . , 10. Wie groß ist zu diesem Zeitpunkt t∗ die Temperatur f ∗ am Ort x = 0,2? Hinweis: Der Umfang der Aufgabe ist soweit begrenzt, dass eine Rechnung von Hand möglich ist. Tragen Sie die Werte f jn für n = 0, 1, . . . und j = 0, 1, . . . , 10 in eine Tabelle ein.

Antwortmöglichkeiten Der Zeitpunkt t∗ und die Temperatur f ∗ am Ort x = 0.2 zum Zeitpunkt t∗ sind: 1. t∗ = 14 , f ∗ = 0,1875 t∗ = 14 ,

f ∗ = 1,6666667

3.

t∗ =

f∗ = 0

4.

t∗ =

5.

t∗ =

6.

t∗ =

7.

t∗ = 1 ,

f ∗ = 0,140625

8.

t∗ = 1 ,

f ∗ = 1,125

9.

t∗ =

10.

t∗ =

5 4, 5 4,

2.

1 2, 1 2, 3 4, 3 4,

f ∗ = 3,9375 f ∗ = 1,7578125 f ∗ = −2

f ∗ = 2,1484375 f ∗ = 4,125

231

Mathematik im menschlichen Körper

Weiterführende Aspekte. Die Komplexität und Schwierigkeit der Aufgabe nimmt zu, wenn nicht mehr eine einzelne Variable ausreicht, um die Ortsverteilung der Temperatur im Raum zu beschreiben. Als eine Verallgemeinerung von Gleichung (4) schreiben wir dann beispielsweise ∂ f (t, x, y) = κ ∂t



∂2 ∂2 f (t, x, y) + 2 f (t, x, y) 2 ∂x ∂y

 ,

wobei die (partiellen) Ableitungen jetzt für jede Variable in der Form ∂  ∂x f anstelle von f geschrieben werden. Der Wärmetransport ist, wie viele Vorgänge in der Natur, durch das Prinzip der Energieminimierung bestimmt. Das führt dazu, dass ohne Einfluss von außen ein energieoptimaler Ausgleichszustand eingenommen wird. In einem solchen Zustand findet von sich aus keine zeitliche Verände∂ rung mehr statt, wodurch die Ableitung ∂t f (t, x, y) den Wert Null annehmen muss. Oft ist man nur an Ausgleichszuständen interessiert und hat dann ein Problem der Form 0=

∂2 ∂2 f ( x, y) + 2 f ( x, y) , 2 ∂x ∂y

mit geeigneten Bedingungen auf dem Rand des betrachteten Gebietes zu lösen. Für Probleme dieser Art hat sich die Finite-ElementeMethode (FEM) bewährt, die inzwischen auch als ein Standardwerkzeug in der computerunterstützten Konstruktion (CAD) etabliert ist. Ein Beispielproblem im Kontext der Wärmeleitung könnte folgendermaßen lauten: In einem mit Wasser gefüllten Kreisring mit innerem Radius r = 5 m und äußerem Radius R = 10 m sei die Wassertemperatur an den Rändern auf 10 beziehungsweise 30 Grad Celsius festgehalten. Wo muss man seine Runden schwimmen, um immer im angenehmen 20 Grad Celsius warmen Wasser zu sein? (Hinweis: Es ist nicht bei r∗ = 7,5m!) Eine FEM-Simulation zeigt, dass der Radius, an dem die Wassertemperatur 20 Grad Celsius beträgt, etwa durch r∗ = 7,0711m gegeben ist. Dies liegt daran, dass der äußere Rand mit der höheren Temperatur aufgrund seiner grö-

232

Die kalte Zunge

Abbildung 3. Die Finite-Elemente-Methode liefert mit Hilfe einer Dreieckszerlegung eine Lösungsfläche, von deren Höhenlinien eine die gesuchte Bahn ergibt.

ßeren Länge einen stärkeren Einfluss auf die Wassertemperatur im Becken hat. Limitationen des Verfahrens. Wer im Approximationsschema (4) andere Werte für Δx und Δt ausprobiert, kann feststellen, dass der Parameter s auf keinen Fall größer als 12 gewählt werden darf, um sinnvolle Näherungslösungen zu erhalten. Dadurch ist eine Beziehung zwischen den möglichen Abständen der Punkte im Ort und in der Zeit gegeben: es muss immer Δx2 ≥ 2κΔt gelten. Versuchen wir sukzessive bessere Lösungen zu berechnen, indem wir jeweils die Ortsschrittweite halbieren, so muss jedesmal die Zeitschrittweite geviertelt werden. Die Punkte, die von einem bestimmten Anfangswert beeinflusst werden, können wir in einem Kegel liegend darstellen. So stellen wir fest, dass mit jeder feiner aufgelösten Rechnung der zugehörige Kegel aufgeweitet wird, bis er im Grenzfall für Δx → 0 den ganzen oberen Halbraum einnimmt. Durch die Gleichung (1) wird somit ein unendlich schneller Transport von Informationen beschrieben, was physikalisch kaum sinnvoll erscheint. Dies liegt an unserer sehr einfachen Beschreibung des Wärmeleitungsprozesses. Es lässt sich aber auch zeigen, dass der Einfluss der Temperatur eines Punktes auf die an anderen Punkten sehr rasch mit wachsendem Abstand abnimmt.

233

Mathematik im menschlichen Körper

Lösung (Richtige Lösung: Antwort 8) Die Werte f jn für n ≥ 1 und j = 1, 2, . . . , 9 ergeben sich aus der

n = 0 für alle Vorschrift (4) mit s = 14 , während f 0n = 0 und f 10 n ≥ 1 gilt. Beispielsweise erhalten wir für n = 0 und j = 5, dass

f 51 =

 1 1 · (0 + 0) + 1 − 2 · 36 = 18, 4 4

da gemäß Anfangsbedingung f 40 = 0, f 60 = 0 und f 50 = 36 gilt. Geht man so schrittweise vor, erhält man alle Werte f jn und kann diese übersichtlich in einer Tabelle anordnen (aufgrund der Symmetrie des Problems gilt stets f 6n = f 4n , f 7n = f 3n , f 8n = f 2n , f 9n = f 1n und n = f n ): f 10 0 j=0

j=1

j=2

j=3

j=4

j=5

n=0

0

0

0

0

0

36

n=1

0

0

0

0

9

18

9 4 54 16 252 64 1080 256 4455 1024

36 4 135 16 504 64 1890 256 7128 1024

54 4 180 16 630 64 2268 256 8316 1024

f jn

n=2

0

0

0

n=3

0

0

n=4

0

n=5

0

n=6

0

9 64 9 256 585 1024

9 16 72 64 405 256 1980 1024

Man kann die Lösung auch zu jedem Zeitpunkt graphisch darstellen, indem man die einzelnen Funktionswerte mit Linien verbindet, siehe Abbildung 4. Eine genaue Überprüfung der Tabelle zeigt, dass Antwortmöglichkeit 8 die richtige Lösung ist, das heißt t∗ = 1, f ∗ = 1,125.

234

Die kalte Zunge 40 35 30

t=0

f(0,x)

25 20 15 10 5 0 0

0.2

0.4

0.6

0.8

1

0.6

0.8

1

0.6

0.8

1

0.6

0.8

1

x 40 35 30

t=1/2

f(1/2,x)

25 20 15 10 5 0 0

0.2

0.4 x

40 35 30

t=1

f(1,x)

25 20 15 10 5 0 0

0.2

0.4 x

40 35 30

t=3/2

f(3/2,x)

25 20 15 10 5 0 0

0.2

0.4 x

Abbildung 4. Mit dem angegebenen Schema berechnete Näherungslösung f (t, x ) zu verschiedenen Zeitpunkten

235

Mathematik auf die Schnelle

Knoten John M. Sullivan

In einer großen Fabrik werden Geschenkpapiere, Schnüre und Gummibänder hergestellt. Die Gummibänder werden zum Verpacken von besonderen Überraschungen benötigt und sind auf himmlische Weise in sich verschlungen. Leider ist in der Gummibandproduktionsmaschine ein Defekt aufgetreten: Nur zwei von fünf Gummibändern wurden wie gewünscht produziert, die anderen drei sind zu kompliziert geraten. Welche der fünf Bilder zeigen die Gummibänder, die gleich verschlungen sind? (Achtung: Beim Hinlegen kann es passieren, dass zwei gleich verschlungene Gummibänder jeweils ein anderes Bild abgeben!)

1

2

4

3

5

239

Mathematik auf die Schnelle

Antwortmöglichkeiten

1. 2. 3. 4. 5.

1 und 2 sind gleich. 1 und 3 sind gleich. 1 und 4 sind gleich. 1 und 5 sind gleich. 2 und 3 sind gleich.

6. 7. 8. 9. 10.

2 und 4 sind gleich. 2 und 5 sind gleich. 3 und 4 sind gleich. 3 und 5 sind gleich. 4 und 5 sind gleich.

In der Mathematik versteht man unter einem Knoten eine geschlossene Schleife im Raum, wie aus Bindfaden. Zwei Knoten werden als gleich betrachtet, wenn man sie ineinander deformieren kann, ohne den Faden zu zerschneiden. Das Ziel der Knotentheorie ist, alle möglichen Knoten zu klassifizieren. Für dieses Problem interessieren sich seit einiger Zeit auch Biophysiker, die über DNSMoleküle forschen. Wenn bei der Zellteilung die Doppelhelix der DNS kopiert wird, würden sich beide Stränge schrecklich verknoten, wenn es nicht Enzyme gäbe, die es möglich machen, dass sich ein Strang durch den anderen bewegt.

240

Knoten

Lösung (Richtige Lösung: Antwort 6) Abbildungen 2 und 4 zeigen den gleichen Knoten. Knoten zu entwirren zählt zu den schwierigen Problemen der Mathematik: Bislang ist kein effizientes Verfahren bekannt, um zu entscheiden, ob zwei beliebige, gegebene Knoten identisch sind oder nicht. In vielen Fällen ist es jedoch möglich, einen Knoten (die Darstellung eines Knotens) zu vereinfachen, indem man z. B. eine Schleife des Knotens über eine andere hinweg bewegt. Das Bild eines Knotens wird dabei „einfacher“, wenn es gelingt, die Anzahl der Überkreuzungen zu verringern. Alle gezeichneten Knoten haben acht Überkreuzungen. Zieht man bei den Knoten 2 und 4 die Schlaufe rechts unten etwas enger, so verringert sich die Zahl der Überkreuzungen auf sechs. Entwirrt man die Knoten 2 und 4 weiter, so kommt man schließlich auf drei Überkreuzungen und kann sich einfach davon überzeugen, dass es sich um den gleichen Knoten handelt. Dieser Knoten mit drei Kreuzungen ist der kleinste nichttriviale Knoten und wird Kleeblattschlinge oder auch Überhandknoten genannt. (Der Knoten 1 lässt sich entsprechend auf vier Kreuzungen reduzieren und Knoten 5 auf sechs Kreuzungen. Hingegen lässt sich Knoten 3 nicht vereinfachen. Achtung: Bei manchen Knoten muss man erst Überkreuzungen hinzufügen, bevor man sie anschließend vereinfachen kann! Genau das macht die Sache so schwierig . . . )

241

Dachkunst Ulrich Reitebuch und Christian Schulz

Der Baron, Herr von und zu Dreieck, braucht ein neues Dach für seinen Pferdestall. Nach Absprache mit dem Architekten hat er sich für das in Abbildung 1 dargestellte sternförmige Design entschieden. Beim Entwerfen hat der Baron mehrmals betont, dass die Positionen der roten und grünen Punkte feststehen. Aufgabe des Architekten ist es nun noch, die Höhe des blauen Punktes in der Mitte zu bestimmen. Herr von und zu Dreieck möchte möglichst wenig Material zum Dachbau verwenden, d. h. der blaue Punkt soll so gewählt werden, dass die Gesamtfläche des Daches minimal wird. Die Koordinaten der Punkte sind folgendermaßen gegeben: – rote Punkte (±1, ±1, 0) – grüne Punkte (± 12 , 0, 1) und (0, ± 12 , 1) – blauer Punkt (0, 0, z) Bestimme die minimale Fläche A des Daches.

Antwortmöglichkeiten 1.

A=1

2.

A=2 2 √ A = 32 3 √ A = 65 5 √ 8 A = 11 6

3. 4. 5.

√

6. 7. 8. 9. 10.

A = 1, 8 √ A= 7 √ A = 17 √ A = 87 6 √ 10 A = 11 9

Bei der Aufgabe handelt es sich um ein Randwertproblem, d. h. die Werte einer Funktion sind auf dem Rand eines Gebietes vorgegeben und sollen ins Innere fortgesetzt werden. In diesem Beispiel entspricht die Funktion der Höhe des Daches. Durch die Fortsetzung

243

Mathematik auf die Schnelle

Abbildung 1. Entwurf des Daches: Perspektivische Ansicht (oben) und Draufsicht (unten)

dieser Randwerte ins Innere soll eine Fläche mit minimalem Flächeninhalt entstehen – eine Minimalfläche. Populäre Beispiele für solche Flächen sind Seifenhäute. Bei der Lösung solcher Probleme im Computer muss das Gebiet diskretisiert, d. h. zerlegt, werden. Hier wird eine Gebietszerlegung durch acht Dreiecke verwendet. Die z Koordinate des gesuchten Punktes für diese recht grobe Triangulierung liegt höher als die der Randpunkte. Es entsteht eine Fläche mit einer Spitze im Inneren, im Gegensatz zu einer Seifenhaut die sich glatt – spitzenfrei – zwischen diesen Punkten aufspannen würde. Dieser mögliche Gegensatz zwischen einer diskreten und

244

Dachkunst

kontinuierlichen Lösung wird auch als Verletzung des Maximumprinizips bezeichnet. Durch eine geeignete Verfeinerung, d. h. eine Zerlegung in mehr Dreiecke, würde die Lösung immer besser das Verhalten einer Seifenhaut beschreiben. Zusätzlich müssten aber auch die Positionen von immer mehr Punkten bestimmt werden, d. h. der Rechenaufwand nimmt zu.

245

Mathematik auf die Schnelle

Lösung (Richtige Lösung: Antwort 4) Die Fläche eines Dreiecks (begrenzt durch einen roten, grünen und blauen Punkt) sei gegeben durch A . Es gilt also für die Gesamtfläche des Daches ADach (z) = 8A (z). Hier bezeichnet z die Höhe des mittleren Punktes. Die Fläche A (z) eines Dreiecks kann durch das Kreuzprodukt oder durch die Heronformel ermittelt werden. Dies liefert einen Wurzelausdruck mit quadratischem Term als Radikanden für ADach (z). Differenzieren und Nullsetzen der Ableitung liefert den Extremalwert für z. Nochmaliges Ableiten bestätigt dann den Minimalcharakter der Lösung. ⎛

⎞ ⎛ 1 ⎞ 0 2 (blau zu grün) v = ⎝ 0 ⎠ − ⎝ 0 ⎠ = ⎝ 0 ⎠ z 1 1−z 1 2

⎞

⎛

⎛

⎞ ⎛ ⎞ ⎛ ⎞ 1 0 1 (blau zu rot) w = ⎝ 1 ⎠ − ⎝ 0 ⎠ = ⎝ 1 ⎠ 0 z −z ⎛

⎞ z−1 n(z) = v × w = ⎝ 1 − 21 z ⎠ 1 2

A (z) =

1 1 n(z) = 2 2

1 1 ( z − 1)2 + (1 − z )2 + ( )2 2 2

dA (z) dADach (z) 10z − 12 6 =8 = √ = 0, für z = 2 dz dz 5 5z − 12z + 9 6 6 6√ ADach ( ) = √ = 5 5 5 5

246

Dachkunst

Die Lösung ist auch ohne Differenzieren berechenbar. Der Ausdruck für ADach (z) enthält einen Wurzelausdruck mit einem quadratischen Term als Radikanden. Dieser quadratische Term beschreibt eine nach oben geöffnete Parabel. Das Minimum befindet sich im Scheitelpunkt der Parabel. Der Scheitelpunkt kann durch quadratische Ergänzung bestimmt werden.

247

102009? Serhiy Yanchuk und Leonhard Lücken

Der Weihnachtsmann hat im Jahr 1 a1 = 7 Millionen Geschenke vorbereitet. Im nächsten Jahr bereitete er a2 = 15 Millionen Geschenke vor. Im dritten Jahr war die Zahl der Geschenke a3 = aa2 Millionen. 1 Diese Iterationsformel gelte ganz allgemein: a k +1 =

ak a k −1

, k = 2, 3, 4, . . .

Wie viele Millionen Geschenke wird der Weihnachtsmann nun im Jahr k = 102009 = 100 · · · 000 (eine Zahl mit 2009 Nullen) vorbereiten?

Antwortmöglichkeiten 1.

2009 Millionen

6.

7 15

2.

15 Millionen

7.

7 Millionen

15 7

Millionen

8.

102009 Millionen

2 Millionen

9.

1 15

Million

10.

1+ 5 2

3. 4. 5.

√ 1 7

Millionen

Million

√

Millionen

Die Aufgabe ist ein Beispiel eines dynamischen Systems. Dynamische Systeme finden vielfältige Anwendungen auf Prozesse im Alltag und erlauben Einblicke in viele Bereiche der Mathematik, Physik, Biologie usw.

249

Mathematik auf die Schnelle

Lösung (Richtige Lösung: Antwort 5) Die ersten acht Jahren sind einfach zu berechnen. Es ergibt sich (Angaben jeweils in Millionen): a1 = 7 a2 = 15 a3 = a4 = a5 = a6 =

15 7 1 7 1 15 7 15

a7 = 7 a8 = 15 Wir bemerken, dass die zwei Größen a1 = 7 und a2 = 15 sich nach sechs Schritten wiederholen. Die Iterationsformel ak+1 = ak /ak−1 zeigt, dass die Zahl der Geschenke ak+1 nur von der Zahl der Geschenke in zwei vorherigen Jahren abhängt. Deshalb wird sich die Folge unendlich oft mit Periode 6 wiederholen. (Man sagt, dass die Zeitreihe periodisch ist.) Die Anzahl der Geschenke kann deshalb nur a1 , a2 , a3 , a4 , a5 oder a6 sein. Um festzustellen, wie viel Millionen Geschenke im Jahr 102009 vorbereitet werden, müssen wir alle Perioden von der Zahl 102009 subtrahieren. D. h. Y = 102009 − X, wobei X die größte Zahl unter 102009 ist, die durch 6 teilbar ist, ohne dass ein Restwert bleibt. Y ist dann der Restwert, der sich nach der Teilung von 102009 durch 6 ergibt (man sagt, Y ist gleich 102009 „modulo“ 6). Diese Aufspaltung können wir folgendermaßen machen: 4 = 102009 − 9 · · · 99996

250

102009 ?

In der Tat, die Zahl 9 · · · 99996 ist sowohl durch 2 als auch durch 3 teilbar. Deshalb ist 9 · · · 99996 durch 6 teilbar. Deshalb wird die Zahl der Geschenke im Jahr 102009 dieselbe Zahl sein wie im Jahr 4, nämlich 17 Million Geschenke: a102009 = a4 =

251

1 7

Stichwortverzeichnis

ADAC, 59 Aktie, 187 Aktien-Zins-Modell, 188 Algorithmus, 53 Datenstrom, 54 Gauß, 159 Greedy, 8, 67 numerischer, 9 Streaming, 54 Apfelsaft, 144 Approximationsschema, 233 Berlin-Marathon, 55 Billard, 19 binäres lineares Programm, 73 Binomialverteilung, 125, 126 Blockademenge, 215 Chip, 227 Dachbau, 243 Datenstrom-Algorithmus, 54 Diät, 205 Differentialgleichung, 37, 205 gewöhnliche, 39 lineare, 207 nichtlineare, 206 partielle, 196 Differenzenquotient, 230 Dirichlet-Neumann-Verfahren, 202 diskrete Funktion, 132 Diskretisierung, 40

DNA, 219 Dualdarstellung, 88 dynamisches System, 249 Einheitsvektoren, 156 Entscheidungsproblem, 122 Erwartungswert, 115 Existenzgründung, 183 falsch positiv, 119 Festplatte, 53 Finite-Elemente-Methode, 232 Folge, 97 Folgenglieder, 94 Frosch, 104 gültige Lösung, 62 Gauß-Algorithmus, 159 Gaußsches Eliminationsverfahren, 13 Gebietszerlegung, 197 Gegenstrategie, 25 Gene, 219 Geschenke, 249 Gleichungssystem, 57 lineares, 9, 84, 107, 156, 190 Google, 101 Graph, 72, 112 graphische Iteration, 96 Greedy-Algorithmus, 8, 67 Grenzverteilung, 101 Grenzwahrscheinlichkeit, 102

253

Stichwortverzeichnis

Grenzwert, 97, 207 Gummibänder, 239 Handy, 77 Heronformel, 246 Iterationsformel, 250 iterative Verfahren, 201 Jensensche Ungleichung, 115 Katalysator, 227 Kleeblattschlinge, 241 Knapsack-Problem, 3 Knie, 195 Knoten, 240 komplementäres Ereignis, 120 Komplexitätstheorie, 168 Kontinuumsmechanik, 196 Kostenfunktion, 128 Kraftwerk, 122 Kredit, 183 Kreuzprodukt, 246 Laser, 93 Lastwagen, 151 Leiterplatten, 161 lineare Unabhängigkeit, 156 Liniennetz, 41 logische Verknüpfungen, 87 Magnetresonanztomographie, 117 Matching, 50, 72 Mauseloch, 29 Medikamente, 17 metabolisches Netz, 213 Metabolismus, 213 Mindestfahrzeugbedarf, 44 minimaler Reaktionsweg, 215

Minimalfläche, 244 Mobilfunknetz, 77 Modellreduktion, 151 Moleküle, 17 MP3-Player, 5 Muffins, 123 Näherungsverfahren, 31 Nobelpreis, 188 N P -Probleme, 5 N P -schwer, 168 Numerik, 37, 196 numerisch instabil, 10 numerische Simulation, 18 numerischer Algorithmus, 9 Nutzenfunktion, 122 Operations Research, 121 optimaler Gewinn, 147 Optimalwert, 62 Optimierung, 142 ganzzahlige lineare, 45 kombinatorische, 50 lineare, 144 stochastische, 122 Optimierungsproblem, 60, 72, 122 Option, 188 Call, 187 Put, 187 Orangensaft, 144 Osterhase, 23 Page-Rank, 102 Pakete, 177 Panne, 59 partielle Ableitungen, 232 Planungsaufgaben, 111 Planungsprobleme, 41

254

Stichwortverzeichnis

Portfolio, 189 Postbote, 177 Projektmanagement, 111 quadratische Gleichung, 58 Randbedingungen, 231 Random Walk, 101 Randwertproblem, 243 Reaktionsweg, 214 Regionalverkehr, 41 Reihenentwicklung, 206 Relaxierung, 60 Roboter, 133, 151 Saftfabrik, 144 Schaltungen, 88 schlecht konditioniertes Problem, 10, 18 Schranke obere, 60 untere, 60, 68, 168 Sequenzierung, 219 Shotgun-Sequenzierung, 219 Signal-zu-Störsignal-Verhältnis, 78 Signifikanztest, 118 Spieltheorie, 23 Spielzeug, 11 Störungsansatz, 206 Standardlösung, 163 Stein–Schere–Papier, 23 Stoffwechsel, 213 Strategie, 24 Streaming-Algorithmus, 54 Subset-Sum-Problem, 3 Systembiologie, 131 Teilwort, 221 Telefongesellschaft, 53

Telefonieren, 77 Temperatur, 227 Testproblem, multiples, 119 Tilgung, 191 Übergangswahrscheinlichkeit, 103 Überhandknoten, 241 Überlappungsgraph, 223 Umlaufzeit, 44 UMTS, 77 Vektorraum, 154 Versicherungen, 175 Versicherungsprämie, 178 Versicherungssumme, 181 Via-Minimierung, 167 Wärmeleitung, 232 Wahrscheinlichkeitsrestriktionen, 122 Wahrscheinlichkeitsverteilung, 24, 101, 122, 126 Warenhaus, 11 Weihnachtsbaumkugeln, 183 Weihnachtsmann, 23, 249 World-Wide-Web, 101 Wort, 221 Zellbiologie, 131 Zinsen, 179, 183 Zuckerstangen, 132 Zugbrücke, 197 Zugriffszeit, 54 Zunge, 227 Zuordnungsproblem, 47 lineares, 71, 74 Zuse Z1, 87 Zustandsraum, 102

255

Die Autorinnen und Autoren

Sören Bartels ist Mathematiker an der Rheinischen FriedrichWilhelms-Universität Bonn und dort Mitglied des Exzellenzclusters Hausdorff-Zentrum für Mathematik sowie des DFGSonderforschungsbereichs 611. Von 2005 bis 2007 leitete er die Matheon-Nachwuchsgruppe Numerische Analysis an der Humboldt-Universität zu Berlin. Katja Biermann ist Mathematikerin an der Technischen Universität Berlin und vermittelt in Schülerprojekten die spannenden und faszinierenden Aspekte der Mathematik. Von 2005–2008 betreute sie den Digitalen Adventskalender des DFG-Forschungszentrums Matheon. Aktuell arbeitet sie im Roberta-Projekt und bringt Schülerinnen und Schülern Naturwissenschaft mittels Lego-Mindstrom Robotern nahe. Alexander Bockmayr ist Professor für Mathematik in den Lebenswissenschaften an der Freien Universität Berlin und am DFG-Forschungszentrum Matheon. Im Mittelpunkt seiner Arbeit steht die mathematische Modellierung biologischer Prozesse auf molekularer Ebene. Peggy Daume ist Haupt- und Realschullehrerin mit den Fächern Mathematik und Chemie. Nach ihren ersten Staatsexamen an der Humboldt-Universität zu Berlin füllte sie das Matheon-Projekt „Current mathematics at schools“ mit Inhalten der Finanzmathematik. Peter Deuflhard lehrt Numerische Mathematik an der Freien Universität Berlin und ist Gründer des Zuse-Instituts Berlin (ZIB). Er ist Autor mehrerer Lehrbücher. Die gestellte Aufgabe stammt aus dem Gebiet der numerischen Lösung von Differentialspielen, vermeidet aber diesen Begriff explizit.

257

Die Autorinnen und Autoren

Falk Ebert arbeitet an der Technischen Universität Berlin und beschäftigt sich dort mit riesigen Gleichungssystemen für elektrische Schaltkreise. Außerdem versucht er, in Vorträgen und Seminaren Schülerinnen und Schülern angewandte Mathematik auf einfache Art und Weise näherzubringen. Aus dem Versuch, einem Schüler das Thema Modellreduktion zu veranschaulichen, entstand die vorliegende Aufgabe. Matthias Ehrhardt ist Technomathematiker und setzt sich seit vielen Jahren dafür ein, Mathematik für Schülerinnen und Schüler zugänglicher zu gestalten. In seinem Projekt „MATEMA – MAThematik Erlebt iM Alltag“ (http://www. matema.de/) hat er eine Reihe von Vorträgen speziell für Schüler entwickelt, die die Bedeutung der angewandten Mathematik anhand von modernen Beispielen erläutert. Er ist Privatdozent an der Technischen Universität Berlin und wissenschaftlicher Mitarbeiter am Weierstraß-Institut für Angewandte Analysis und Stochastik. Andreas Eichhorn ist Mathematiker und derzeit bei dem Unternehmen VERBUND – Austrian Power Trading AG in Wien tätig. Er berechnet dort unter anderem optimale Einsatzstrategien für große Wasserkraftwerke. Zuvor forschte er im Rahmen des Matheon mehrere Jahre lang an der HumboldtUniversität zu Berlin über mathematische Optimierung unter Unsicherheit und Risiko. Andreas Eisenblätter ist Geschäftsführer einer Firma, die mit Methoden aus der Mathematik Telekommunikationsnetze plant und optimiert. In dem DFG-Forschungszentrum Matheon erforschte er Methoden zur Optimierung von UMTSMobilfunknetzen. Hans-Florian Geerdes hat an der TU Berlin angewandte Mathematik und Telekommunikation studiert. In Projekten am Matheon und am Zuse-Institut Berlin hat er erforscht, wie man Mobilfunknetze gut plant und betreibt. Heute arbeitet er als Unternehmensberater.

258

Die Autorinnen und Autoren

Martin Grötschel ist Mathematikprofessor an der TU Berlin und Vizepräsident des Zuse-Instituts Berlin; er war von 2002 bis 2008 Sprecher des Matheon. Derzeit ist er Generalsekretär der International Mathematical Union (IMU). Er beschäftigt sich mit Diskreter Mathematik, Optimierung und Operations Research und arbeitet mit vielen Industriefirmen beim Einsatz von mathematischen Methoden zur Verbesserung ihrer Prozesse zusammen.

Nam-D˜ ung Hoàng ist seit 2006 als Doktorand an der Technischen Universität Berlin und am Zuse-Institut Berlin. Er beschäftigt sich mit Diskreter Mathematik, Optimierung und Operations Research.

Stefan Hougardy ist Professor für Diskrete Mathematik am Forschungsinstitut für Diskrete Mathematik der Universität Bonn. Dort beschäftigt er sich mit mathematischen Fragestellungen, die beim Chip-Design auftreten. Von 2002–2007 war er Projektleiter in einem Matheon-Projekt, das Methoden der kombinatorischen Optimierung einsetzte, um die Entwicklung neuer Medikamente zu unterstützen.

Volker Kaibel ist seit 2007 Professor für Mathematische Optimierung an der Otto-von-Guericke Universität Magdeburg. Zuvor war er mehrere Jahre im DFG-Forschungszentrum Matheon aktiv.

Daniela Kern arbeitet als Mathematikerin am WeierstraßInstitut für Angewandte Analysis und Stochastik in Berlin. Dort befasst sie sich mit mathematischen Methoden zur optimalen Wärmebehandlung von Stahl mit dem Ziel, dass Bauteile gewünschte Härte aufweisen und sich nicht verziehen.

259

Die Autorinnen und Autoren

Stefan Kirchner studierte Informatik an der HumboldtUniversität zu Berlin und war dort als wissenschaftlicher Mitarbeiter tätig. Er promovierte im Bereich Algorithmen und war von 2004–2006 Mitglied am Matheon.

Thorsten Koch ist Mitarbeiter im Bereich Optimierung am Konrad-Zuse-Zentrum Berlin und seit 2001 Mitglied des Matheon. Er hat hier an Projekten zur Planung von Mobilfunknetzen, Verifikation von integrierten Schaltkreisen und zur Mathematikausbildung gearbeitet. 2004 promovierte er an der TU Berlin mit einer Arbeit über die Modellierung und Optimierung von Industrieproblemen.

René Lamour ist Mathematiker am Lehrstuhl für Numerische Mathematik des Institutes für Mathematik der HumboldtUniversität zu Berlin. Neben seinem Interesse an AlgebroDifferentialgleichungen versucht er bei allen sich bietenden Anlässen wie dem Tag der Mathematik, der Langen Nacht der Wissenschaften oder anderen schon bei Schülern Interesse für das Spannende an der Mathematik zu wecken.

Abdelhalim Larhlimi promovierte mit einer Arbeit zur mathematischen „Analyse metabolischer Netzwerke“ an der Freien Universität Berlin und ist nun wissenschaftlicher Mitarbeiter am Max-Planck-Institut für molekulare Pflanzenphysiologie in Golm.

Mark Lichtner promovierte 2006 an der Humboldt-Universität zu Berlin. Seit 2006 ist er Wissenschaftlicher Mitarbeiter am Weierstraß-Institut Berlin. Dort beschäftigt er sich mit der Simulation und theoretisch-experimentellen Analyse von Hochleistungsdiodenlasern sowie mit mathematischen Grundlagenfragen.

260

Die Autorinnen und Autoren

Christian Liebchen ist Netzplaner bei der DB Schenker Rail Deutschland AG, dem Schienengüterverkehrsdienstleister der Deutschen Bahn AG. Im Rahmen seiner Promotion an der TU Berlin war er noch mit dem Personenverkehr befasst. Dort gelang es ihm, den ersten mathematisch optimierten Fahrplan zu berechnen, der in Betrieb genommen wurde.

Anita Liebenau hat einige Aufgaben im Rahmen eines Praktikums am Matheon mit entwickelt, nachdem sie selbst Jahre lang als Schülerin mitgekniffelt hat. Zur Zeit studiert sie in Darmstadt Mathematik und verbringt ihr Auslandsjahr in Großbritannien.

Andreas Loos fühlt sich in der Schnittmenge von Mathematik und Journalismus wohl. Er hat bereits an einer ganzen Reihe von Büchern und Ausstellungen mitgearbeitet und viele Artikel über naturwissenschaftliche, mathematische (und ganz andere) Themen geschrieben. Als Mathematiker forscht er derzeit an der Universität Magdeburg.

Leonhard Lücken ist Student an der Humboldt Universität zu Berlin und Mitglied der Junior Research Group „Dynamics and synchronization of complex systems“. Sein aktuelles Projekt ist die Suche einer Formel zur Bestimmung der genauen Anzahl der Geschenke, die er und Serhiy Yanchuk in diesem Jahr bekommen werden. Drücken wir ihm die Daumen, dass er rechtzeitig die Lösung findet!

Brigitte Lutz-Westphal ist Professorin für Mathematikdidaktik an der Freien Universität Berlin und setzt sich seit vielen Jahren dafür ein, dass Mathematik zugänglicher und verständlicher wird. Sie macht Themen der modernen angewandten Mathematik für Unterricht und Lehreraus- und -fortbildung zugänglich. In den ersten Jahren des MatheonAdventskalenders war sie aktiv an Konzeption und Organisation beteiligt.

261

Die Autorinnen und Autoren

Nicole Megow ist Mathematikerin am Max-Planck-Institut für Informatik in Saarbrücken. Sie beschäftigt sich mit Methoden zur Lösung von Optimierungsproblemen wie sie in der Logistik, im Projekmanagement oder auch bei der Prozessplanung für Hochleistungsrechner auftreten. Insbesondere erforscht sie, wie man trotz unvollständiger Informationen gute Lösungen erzielt.

Volker Mehrmann ist Professor für Numerische Mathematik an der Technischen Universität Berlin und Sprecher des DFG Forschungszentrums Matheon, Mathematik für Schlüsseltechnologien in Berlin.

Rüdiger Müller betreibt Bruchrechnung der speziellen Art. Um Materialversagen von Werkstücken vorzubeugen, arbeitet er am WIAS Berlin an der mathematischen Modellierung und Berechnung von Schädigungsvorgängen in Metallverbindungen mit Hilfe der Methode der Finiten Elemente.

Jörg Rambau leitet seit Dezember 2004 den Lehrstuhl für Wirtschaftsmathematik an der Universität Bayreuth. Er ist Gründungsmitglied des Matheon und hat am Zuse-Institut Berlin zusammen mit Sven Oliver Krumke (jetzt TU Kaiserslautern) den Optimierungsalgorithmus für die Einsatzplanung der Gelben Engel entwickelt.

Lutz Recke ist Hochschuldozent an der Humboldt-Universität zu Berlin und bildet dort zukünftige Mathematiker und Physiker aus. Seit 2002 untersucht er im Rahmen des DFGForschungszentrums Matheon das dynamische Verhalten von Halbleiterlasern.

262

Die Autorinnen und Autoren

Ulrich Reitebuch ist technischer Mitarbeiter in der Arbeitsgruppe Geometry Processing an der Freien Universität Berlin. Neben der Betreuung technischer Geräte und der notwendigen Computer-Administration unterstützt er die wissenschaftlichen Mitarbeiter bei ihren aktuellen Forschungstätigkeiten. Oliver Sander ist Mathematiker an der Freien Universität Berlin. Er versucht, die Kräfte in Kniegelenken zu berechnen, damit Prothesen später länger halten. Außerdem ist er einer der Entwickler von Dune, einem großen Softwarepaket für die numerische Mathematik. Anton Schiela ist Mathematiker am Konrad-Zuse-Zentrum für Informationstechnik in Berlin. Dort hat er viel mit Differentialgleichungen und auch mit Optimierung zu tun. In seiner Jugend hatte er immer wieder die Möglichkeit, die Hauskatze der Familie beim Jagen zu beobachten. John Schoenmakers promovierte an der Universität Delft (Niederlande) über theoretische Wahrscheinlichkeit im Bereich der stochastischen Prozesse. Nach der Promotion beschäftigte er sich mit Themen der angewandten Wahrscheinlichkeit mit dem Schwerpunkt Finanzen. Seit 1998 ist er stellvertretender Leiter der Arbeitsgruppe „Stochastische Algorithmen und Nichtparametrische Statistik“ und Leiter der Forschungsrichtung „Entwicklung und Analyse von Finanzmodellen“ am WeierstraßInstitut Berlin. Christian Schulz ist wissenschaftlicher Mitarbeiter an der Freien Universität Berlin in der Arbeitsgruppe Geometry Processing. Er beschäftigt sich mit der Segmentierung von Oberflächen, d. h. der Zerlegung von Geometrien in „gute“ Bereiche. Da „gut“ bzw. geeignet im Allgemeinen vom Betrachter und Anwendungsgebiet abhängen, ist das Ziel dieser Forschung, wahrgenommene in mathematisch fassbare Oberflächeneigenschaften zu übersetzen.

263

Die Autorinnen und Autoren

Heike Siebert hat Mathematik mit Nebenfach Biologie in Kiel studiert und dort 2004 ihre Promotion in Mathematik abgeschlossen. Seit 2005 genießt sie die Möglichkeit, Mathematik für biologische Fragestellungen in der Gruppe „Mathematik in den Lebenswissenschaften“ an der Freien Universität Berlin zu entwickeln.

Boris Springborn forscht an der Technischen Universität Berlin auf dem Gebiet der Geometrie. Die Aufgabe Stein–Schere– Papier entstand einmal beim Mittagessen, als es aus irgendeinem Grund darum ging, den Unterschied zwischen einem Nullsummenspiel und einem fairen Spiel zu erklären.

John M. Sullivan ist seit 2003 Professor für Mathematik an der Technischen Universität Berlin. Seine Forschung im Gebiet der Geometrie beschäftigt sich mit der geometrischen Knotentheorie, der mathematischen Visualisierung und der diskreten Differentialgeometrie.

Karsten Tabelow ist Physiker am Weierstraß-Institut für angewandte Analysis und Stochastik (WIAS) in Berlin und arbeitet seit einigen Jahren auf dem Gebiet der medizinischen Bildverarbeitung. Besonders das Schärfen von verrauschten Aufnahmen aller Art hat es ihm angetan. Davon profitiert nicht nur die eigene Fotosammlung.

Caren Tischendorf ist Mathematikprofessorin an der Universität zu Köln und arbeitet eng mit europäischen Halbleiterfirmen (Infineon, NXP) auf dem Gebiet der Simulation integrierter Schaltungen zusammen. Sie gehört zu den Initiatoren des Kölner Mathematik-Turniers, bei dem Schüler in kleinen Teams mathematische Probleme lösen und in Strategiespielen gegeneinander antreten.

264

Die Autorinnen und Autoren

Sina Tutsch ist Mathematikerin und hat an der HumboldtUniversität zu Berlin im Rahmen eines Projekts des DFGForschungszentrums Matheon im Bereich der Finanzmathematik promoviert. Danach wechselte sie zur Allianz Global Corporate & Specialty AG nach München und bewertet seitdem als Aktuarin das Industriegeschäft der Allianz.

Martin Weiser ist Mathematiker am Zuse-Institut Berlin, stellvertretender Leiter der Abteilung Numerische Analysis und Modellierung und Leiter der Arbeitsgruppe „Computational Medicine“. Er setzt sich mit vielen Vorträgen dafür ein, Schülerinnen und Schülern die Anwendungsbreite und praktische Bedeutung der Mathematik zu vermitteln.

Serhiy Yanchuk ist seit 2008 Nachwuchsgruppenleiter am Institut für Mathematik der Humboldt Universität zu Berlin. Vor 2008 war er als wissenschaftlicher Mitarbeiter am Weierstraß-Institut für Angewandte Analysis und Stochastik in Berlin beschäftigt. Seine Forschungsinteressen sind Dynamische Systeme und deren Verhalten, Synchronisationseffekte und Anwendungen in Physik und Biologie.

Mariano Zelke hat in Berlin Informatik studiert und seine Doktorarbeit über Algorithmen zum Verarbeiten von großen Datenströmen geschrieben. Jetzt ist er wissenschaftlicher Mitarbeiter an der Goethe-Universität in Frankfurt am Main.

265