Date post: | 06-Apr-2015 |
Category: |
Documents |
Upload: | caecilia-zehr |
View: | 104 times |
Download: | 1 times |
MATHEMATISCHE MODELLIERUNG AM BEISPIEL VERSCHIEDENER FALLSTUDIEN
Seminar Angewandte Mathematik für LAK
Professor Schmitt
Maria Hutsteiner, Kerstin Kranz
ÜBERBLICK
Was ist Modellierung?
Fallbeispiele:
1. Müllabfuhr – Optimierungsproblem
2. Rettungshubschrauber – Standortbestimmung
Zusammenfassung
MODELLIERUNG
Reales Problem Mathematisches Problem
Reale Lösung Mathematische Lösung
Modellbildung
Analyse
Simulation
Interpretation
Überprüfung
MÜLL MÜLL MÜLL
Stadtreinigungen entsorgten 2007: Hamburg: ~754000 t, 587 kg pro Einwohner,
2066 t täglich Österreich: ~430 kg pro Einwohner
Optimale Route: Spart Treibstoff, Zeit Geld
Mei Go Guan „Chinesisches- Postboten-Problem“
ROUTENPLANUNG -MÜLLABFUHR
Optimierungskriterien: Sackgasse Einbahnstraße jede Straße mind. einmal abfahren Anfangspunkt = Endpunkt
MODELLIERUNG- GRAPHENTHEORIE
aus Straßennetz Graph erstellen Graph: Ein Graph besteht aus einer Menge
von Knoten, Kanten und einer Zuordnung, die jeder Kante ein Knotenpaar zuweist (Knoten sind Endpunkte der Kante)
Grad: Anzahl der Kantenenden an einen Knoten
MODELLIERUNG- GRAPHENTHEORIE
Straßen gerade Kanten Kreuzungen, Ende Sackgasse Knoten
Kantengewichte (verschiedene Parameter wie z.B. Weglänge, Durchfahrtszeit usw.)
EULERGRAPHEN- EULERTOUREN
Eulerweg: Ein Weg, der durch jede Kante eines zusammenhängenden Graphen genau einmal führt, heißt Eulerweg
Eulergraph: Ein Graph, der eine Eulertour enthält, heißt Eulergraph
Eulertour: Eulerweg mit gleichem Start-und Zielpunkt
Algorithmen: Zwiebelschalen- Algorithmus (Hierholzer-Algorithmus) Fleurys Algorithmus
ZWIEBELSCHALEN-ALGORITHMUS
1. Schritt: Wähle einen Startknoten
2. Schritt: Gehe auf unmarkierten Kanten und markiere diese Falls alle markiert Schritt 3 Falls nicht, suche neuen Startknoten, wiederhole
Schritt 2
3. Schritt: Gehe entlang des ersten Kreises bis er einen weiteren berührt; gehe weiter auf dem neuen bis dieser wieder einen weiteren berührt usw.
Gehe den zuletzt begonnenen zu Ende, dann den vorhergehenden, usw. bis alle Kanten besucht wurden
FLEURYS- ALGORITHMUS
Brücke: Kante in einem Graphen, bei deren Wegnahme der Graph in zwei Komponenten zerfallen würde
1. Schritt: beginne mit beliebiger Kante
2. Schritt: wähle nächste Kante so, dass sie im Restgraphen keine Brücke bildet
…
grün = Brücke
UNGERADE KNOTEN
Knoten besitz ungeraden Grad Bsp. 2 ungerade Knotengrade
Mehr als 2 ungerade Knotengrade: Anzahl gerade: wie oben Anzahl ungerade: ????
UNGERADE KNOTEN
Satz: In jedem Graphen ist die Anzahl der Knoten mit ungeradem Grad gerade.
Satz: Die Summe aller Knotengrade eines Graphen = doppelte Anzahl der Kanten,
(da jede Kante die Summe aller Knotengrade genau um 2 erhöht (Anfangs- und Endknoten))
aus jedem Graph lässt sich Eulergraph entwickeln
THE PERFECT MATCH
Matching: Teilgraph, in dem alle Knoten höchstens Grad 1 haben
Minimal: Summe der Kantengewichte ≤ Summe der Kantengewichte bei jedem anderen Matching, das diese Knoten verbindet
Perfektes Matching: nur Knoten vom Grad 1, alle Knoten sind zu Paaren verbunden
STANDORTWAHL FÜR RETTUNGSHUBSCHRAUBER
AUSGANGSPROBLEM: Ein Rettungshubschrauber soll mehrere
Einsatzgebiete optimal versorgen.
Was heißt „optimal“?
BEISPIEL: gleichmäßig schnelle Versorgung der Unfallopfer
BSP.: Gleichmäßig schnelle Versorgung
Vereinfachte Modellannahmen: Modellieren Einsatzgebiete sowie
Hubschrauberstandort als Punkte in der Ebene Flugzeit zw. A und B – proportional zur Länge der
geraden Strecke zw. A und B Es wird nur die Zeit bis zur Erstversorgung des
Unfallopfers berücksichtigt Unfallhäufigkeit ebenfalls nicht berücksichtigt
BSP.: Gleichmäßig schnelle Versorgung
Wenn wir annehmen, dass M Einsatzorte Ex1(a11 | a12), Ex2(a21 | a22),..., ExM(aM1 | aM2) zu beachten sind und X(x1 | x2) irgendein Standort für den Hubschrauber ist, so ist für m = 1,…, M
die Euklidische Entfernung zwischen dem m-ten Standort Exm(am1 | am2) und X
BSP.: Gleichmäßig schnelle Versorgung
CENTER ZIELFUNKTION
CENTER STANDORTPROBLEM
2 4 6 8 10-4 -2
2
4
6
8
10
Ex1(3,5 | 6)
Ex2(-1,5 | 10)
X(1 | 8)
ZWEI EINSATZORTE:
Mittelpunkt der Strecke zw. den beiden Einsatzorten
Außerhalb der beiden Kreisscheiben ist die Entfernung sowohl von Ex1 als auch von Ex2 größer als r*.
In der (gelben) Kreisscheibe um Ex1 mit Radius r* hat jeder Punkt X außer X* eine Entfernung von Ex2, die größer als r* ist. Analog hat jeder Punkt X außer X* in der (grünen) Kreisscheibe um Ex2 mit Radius r* eine Entfernung von Ex1, die größer als r* ist.
21 43
4
2
1
3
5
Ex1(1 | 2) Ex2(5 | 2)X*(3 | 2)
r* r*
2 4 6 8 10-4 -2
-2
2
4
6
8
10
X(3 | 4)
Ex1(-2 | 2)
Ex3(-5 | -1)
Ex2(5 | 9)
DREI EINSATZORTE – FALL1:(Spitzwinkeliges Dreieck)
Umkreismittelpunkt
Der einzige Punkt mit Euklidischer Entfernung kleiner oder gleich r* zu allen drei existierenden Standorten ist X*.
Ex2(2 | 6)
Ex1(2 | -2)
42
86
4
2
6
-2
10
Ex3(8 | 0)
X*(4 | 2)
2 4 6-4 -2
-2
2
4
6
XU(-2 | -4)
Ex2(1 | 3)
-8 -6
-4
-6
XM(0 | 1)
Ex1(-5 | 3)
Ex3(5 | -1)
FALL2:(Stumpfwink. Dreieck)
FALL2:(Stumpfwink. Dreieck)
Seien Ex1 und Ex2 die Endpunkte der längsten Seite und X* der Mittelpunkt dieser Seite.Dann gilt für jeden Standort X, der von X* verschieden ist:
FALL 3 (?) – rechtwinkeliges Dreieck
SATZ:
MEHR ALS DREI EINSATZORTE:
Lösung durch Probieren?
2 4 6 8 10
2
4
6
8
10
Ex1(0 | 0)
Ex2(9 | -2)
X1(4 | 5)
12
14
-2
Ex3(7 | 13)
Ex4(4 | 15)
100
2 4 6 8 10
2
4
6
8
10
Ex1(0 | 0)
Ex2(9 | -2)
12
14
-2
Ex3(7 | 13)
Ex4(4 | 15)
X2(5 | 4)
122
2 4 6 8 10
2
4
6
8
10
Ex1(0 | 0)
Ex2(9 | -2)
12
14
-2
Ex3(7 | 13)
Ex4(4 | 15)
X3(5 | 5)
101
2 4 6 8 10
2
4
6
8
10
Ex1(0 | 0)
Ex2(9 | -2)
X1(4 | 5)
12
14
-2
Ex3(7 | 13)
Ex4(4 | 15)
100
MEHR ALS DREI EINSATZORTE:
Zurückführung auf das Problem mit zwei oder drei Einsatzorten
Für alle Paare und Tripel in der Menge Ex mache das folgende:
Schritt 1: Bestimme den optimalen Center Standort X‘ und den optimalen Zielfunktionswert r‘ für das Center Standortproblem mit zwei bzw. drei Einsatzorten.
Schritt 2: Bestimme den Kreis mit Radius r‘ um X‘. Falls die entsprechende Kreisscheibe alle Punkte in Ex enthält, ist X‘=X* und r‘=r* (X*... Optimaler Center Standort, r*... Optimaler Center Zielfunktionswert)
3 6 9 12 15
3
6
9
12
15
Ex1(-12 | 4)
Ex2(14 | 7)
18-6
-3
Ex3(18 | -6)
Ex4(-9 | -5)
-3
-6
-9
-9-12X*(3 | -1)
r* ≈ 15,8
3 6 9 12 15
3
6
9
12
15
Ex1(-12 | 4)
Ex2(14 | 7)
18-6
-3
Ex3(18 | -6)
Ex4(-9 | -5)
-3
-6
-9
-9-12
3 6 9 12 15
3
6
9
12
15
Ex1(-12 | 4)
Ex2(14 | 7)
18-6
-3
Ex3(18 | -6)
Ex4(-9 | -5)
-3
-6
-9
-9-12
3 6 9 12 15
3
6
9
12
15
Ex1(-12 | 4)
Ex2(14 | 7)
18-6
-3
Ex3(18 | -6)
Ex4(-9 | -5)
-3
-6
-9
-9-12
3 6 9 12 15
3
6
9
12
15
Ex1(-12 | 4)
Ex2(14 | 7)
18-6
-3
Ex3(18 | -6)
Ex4(-9 | -5)
-3
-6
-9
-9-12
3 6 9 12 15
3
6
9
12
15
Ex1(-12 | 4)
Ex2(14 | 7)
18-6
-3
Ex3(18 | -6)
Ex4(-9 | -5)
-3
-6
-9
-9-12
3 6 9 12 15
3
6
9
12
15
Ex1(-12 | 4)
Ex2(14 | 7)
18-6
-3
Ex3(18 | -6)
Ex4(-9 | -5)
-3
-6
-9
-9-12
3 6 9 12 15
3
6
9
12
15
Ex1(-12 | 4)
Ex2(14 | 7)
18-6
-3
Ex3(18 | -6)
Ex4(-9 | -5)
-3
-6
-9
-9-12
> 90°
3 6 9 12 15
3
6
9
12
15
Ex1(-12 | 4)
Ex2(14 | 7)
18-6
-3
Ex3(18 | -6)
Ex4(-9 | -5)
-3
-6
-9
-9-12
3 6 9 12 15
3
6
9
12
15
Ex1(-12 | 4)
Ex2(14 | 7)
18-6
-3
Ex3(18 | -6)
Ex4(-9 | -5)
-3
-6
-9
-9-12
> 90°
3 6 9 12 15
3
6
9
12
15
Ex1(-12 | 4)
Ex2(14 | 7)
18-6
-3
Ex3(18 | -6)
Ex4(-9 | -5)
-3
-6
-9
-9-12
3 6 9 12 15
3
6
9
12
15
Ex1(-12 | 4)
Ex2(14 | 7)
18-6
-3
Ex3(18 | -6)
Ex4(-9 | -5)
-3
-6
-9
-9-12X*(3 | -1)
r* ≈ 15,8
Optimierung bei Kenntnis der Unfallhäufigkeit
EIN HUBSCHRAUBER – ZWEI EINSATZORTE
1) Intuitive Lösungsfindung
w1, w2 ... Unfallhäufigkeiten in Ex1 u. Ex2
Bsp.: w1< w2 , etwa w1=1, w2=2
- Hubschrauber wird näher an Ex2 heranrücken
Ex1Ex2
1 21 2 1 2
1 2 1 2
1 2*
3 3
w wX Ex Ex Ex Ex
w w w w
Schwerpunkt
Optimierung bei Kenntnis der Unfallhäufigkeit
EIN HUBSCHRAUBER – ZWEI EINSATZORTE
2) Zielfunktion und Optimierung
Optimierung bei Kenntnis der Unfallhäufigkeit
EIN HUBSCHRAUBER – ZWEI EINSATZORTE
2) Zielfunktion und Optimierung
2 21 1 2 2( ) : ( , ) ( , )F X w d Ex X w d Ex X
Optimierung bei Kenntnis der Unfallhäufigkeit
EIN HUBSCHRAUBER – ZWEI EINSATZORTE
2) Zielfunktion und Optimierung
Minimierung der Zielfunktion führt zur Lösung:
2 21 1 2 2( ) : ( , ) ( , )F X w d Ex X w d Ex X
1 21 2
1 2 1 2
*w w
X Ex Exw w w w
Schwerpunkt
Optimierung bei Kenntnis der Unfallhäufigkeit
EIN HUBSCHRAUBER – N EINSATZORTE
Zielfunktion:
Bedingung:
Lösung:
2
1
( ) : ( , )N
i ii
F Q wd P Q
1
( ) 2 ( ) 0N
i ii
gradF Q w P Q
1
1
N
i iiN
ii
w PQ
w
n Hubschrauber – m Einsatzorte
LÖSUNGSALGORITHMUS:
Wähle n verschiedene Einsatzorte als Hubschrauberstandorte zufällig aus.
Ordne jeden Einsatzort einem ihm nächstgelegenen Hubschrauberstandort zu.
Verlege jeden Hubschrauber in den optimalen Standort der ihm zugeordneten Einsatzorte. Bewegt sich dabei kein Hubschrauber mehr, halte an, andernfalls gehe zu 2.
n Hubschrauber – m Einsatzorte - BEISPIEL
ZUSAMMENFASSUNG
Optimierung des Weges in vielen Bereichen anwendbar (Busrouten, Speditionen, Postboten, Museen)
Ortlieb et. al. Mathematische Modellierung. Vieweg und Teuber, Wiesbaden, 2007.
Hamacher, E. Korn, R. Korn, Schwarze. Mathe und Ökonomie. Universum Verlag, Wiesbaden, 2004.
Gritzmann, Brandenberg. Das Geheimnis des kürzesten Weges. 3. Auflage, Verlag Springer, Berlin, Heidelberg, 2005.