Seite 1 Wirtschaftsmathematik in Kaiserslautern - eine Einführung Prof. Dr. Horst W. Hamacher...

Seite 1

Wirtschaftsmathematikin Kaiserslautern

-eine Einführung

Prof. Dr. Horst W. Hamacher

Fachbereich Mathematik, Universität Kaiserslautern

Seite 2

Was ist Wirtschaft?

• Da, wo man seine Cola, sein Bier ... trinkt, und ...

oder

• Bezeichnung für alle Aktivitäten und Einrichtungen, die der Produktion, Distribution und Konsumtion von Gütern und Dienstleistungen dienen. Das Ziel dieser Aktivitäten besteht nach der gängigen Volkswirtschaftslehre ganz allgemein darin, über knappe Mittel (RessourcenHWH) so zu verfügen, dass sich die menschlichen Bedürfnisse befriedigen lassen. "Wirtschaft", Microsoft® Encarta® 99 Enzyklopädie. © 1993-1998

Seite 3

Was ist Mathematik?

• Das, was man in der Schule lernt.

• Untersuchung der Beziehungen zwischen Mengen, Größen und Eigenschaften sowie der logischen Operationen, aus denen unbekannte Mengen, Größen und Eigenschaften hergeleitet werden können. "Mathematik", Microsoft® Encarta® 99 Enzyklopädie. © 1993-1998

Seite 4

Was ist Wirtschaftsmathematik?

• Einsatz von mathematischen Methoden zur Lösung von wirtschaftlichen Problemen

• Beispiele:Problem Ressource Mathematische Methoden

– Lagerhaltung Platz, Zeit Simulation, Stochastik psb

– Nahverkehr Zeit, Umwelt Graphentheorie, Flußprobleme ÖV

– Krebsbestrahlung Gesundheit Multikriterielle Optimierung Krebs

– Notfallplanung Leben Standorttheorie Tirol

– Transporte Platz, Geld Ganzzahlige Optimierung IP

• Wie studiert man Wirtschaftsmathematik in Kaiserslautern KL

andere Mathe

Seite 5

Was ist Wirtschaftsmathematik?

• Einsatz von mathematischen Methoden zur Lösung von wirtschaftlichen Problemen

• Beispiele:Problem Ressource Mathematische Methoden

– Lagerhaltung Platz, Zeit Simulation, Stochastik psb

– Nahverkehr Zeit, Umwelt Graphentheorie, Flußprobleme ÖV

– Krebsbestrahlung Gesundheit Multikriterielle Optimierung Krebs

– Notfallplanung Leben Standorttheorie Tirol

– Transporte Platz, Geld Ganzzahlige Optimierung IP

• Wie studiert man Wirtschaftsmathematik in Kaiserslautern KL

Seite 6

Wie studiert man Wirtschaftsmathematik in KL?

O p tim ie ru n g

S toch as tik

A llg em ein e M ath em atik

M ath em atik In fo rm atik W irtsch a ftsw issen sch a ften

W irtschaftsm athem atik

60% 20% 20%

zurück

Seite 7

Notfall-rettung durchHubschrauber

E1

E2

zurück

Seite 8

Mittelpunkt zwischen E1 und E2:

zurück

Seite 9

Notfall-rettung durchHubschrauber

zurück

Seite 10

Mittelsenkrechte zwischen E1 und E2:

zurück

Seite 11

E3

E2

E1

MS13

MS12

MS23

Der beste Standort eines Hubschraubers für 3 Einsatzorte :

zurück

Seite 12

E3

E2

E1

zurück

Seite 13

Standorttheorie

VerboteneGebiete

BarrierenMulti-

kriteriellWege,Kreise

Distanz-maße

Industrie-anlagen

Notfall-anlagen

Roboter BuslinienKrebs-

therapie GIS

Standortanwendungen

SAP IBM Kommunen Verkehrsverbünde DKFZ Arcview Markant Krankenhäuser ptv

Library of Location Algorithms

zurück

LOLA

Seite 14

Parallellager- und Materialflußplanung

Parallellager mit Durchfluß von 500-1000 Transporteinheiten (TE) pro Stunde

, Pirmasens, Germany

zurück

Seite 15

Erwartete Anzahl aktiver Stockwerke

Annahme: n = Anzahl der Stockwerke

m = Anzahl von Lagerplätzen/Stockwerk

nT= Anzahl der TEen (unabhängig, gleichförmig verteilt, nT>n)

Enn

k

k

i

m k i

n

nm

nki

i

k

k

n

occT T

( )( )

100

1

Rechentest:

Man kann nur 70% bis 90% aktiver Stockwerke erwarten (in der Praxis)

zurück

Seite 16

Optimierungsbeispiel: Hubrahmen -1-

Von den n! vielen möglichen Permutationen können

(m+1)!(m+1)n-m-1

realisiert werden

Ziel: Gleichmäßige Verteilung auf Ebenen Gleichmäßige Auslastung der Kommissionierplätze

zurück

Seite 17

TE i auf Ebene j

min,

c xiji j

ij

are feasible permutation

x i

x j

x i j

x i j

ijj

iji

ij

ij

1

1

0 1

{ | , }

{ , } ,

s.t.

xij 1 Kosten der Plazierung von TE i auf Ebene j z.B. #TE derselben Farbe

Optimierungsbeispiel: Hubrahmen -2-

zurück

Seite 18

Die zulässigen Permuationen entsprechen zulässigen

Matchings in einem bipartiten Graphen

TUs:

Layers:

Optimierungsbeispiel: Hubrahmen -3-

zurück

Seite 19

Systemoptimierung durch (dynamische) Netzwerkflußprobleme

Hubrahmen Materialflußnetzwerk

zurück

Seite 20

Zone k - Haltestelle iZuordnung

IP Model für Wabenproblem

Minimiere Abweichung von alten Tarifen:

h h d pik jl ij kli j k l

| |, , ,

h i

h i k

p d

ikk

ik

kl ij

1

0 1{ , } ,

,

s.t.

neuer (k,l) Wabentarif

alter (i,j) Entfernungstarif

•NP-schweres Problem

•einfach, falls Zonen gegeben sind

•Zonen können unzusammenhängend sein.

zurück

Seite 21

Bestrahlungstherapie

Applikation von hochenergetischer Strahlung zur

– Tumorkontrolle

– Tumorzerstörung

zurück

Seite 22

Problemstellung

Dosisanforderungen:

Zielvolumen: 50 Gray (minimal)

Risiken: 30 Gray (maximal)

20 Gray (maximal)

15 Gray (maximal)

zurück

Seite 23

InverseTherapieplanung

Berechnung der physikalischen Setup-Parameter aus den Dosisvorgaben

zurück

Seite 24

3-stufige Vorgehensweise

Wahl der Einstrahlgeometrie

Bestimmung der Intensitätsprofile

Phase I:

Phase II:

multikriterielles Problem

Standortproblem

zurück

Durchführung der Bestrahlung

Phase III:

Ganzzahliges Problem

Seite 25

Phase I: Einstrahlgeometrie

• Wahl von N Einstrahlrichtungen

• Wahl eines Isozentrums

Isozentrisches Modell:

zurück

Seite 26

Phase II: Intensitätsprofile

Ansatz

– Diskretisierung

– Approximation der

Dosisverteilung

zurück

Seite 27

K-kriterielles Problem

• K Organe von Interesse ( Ziel, Risiken )

• „maximale Dosisabweichung“

tk = tk( x ) für Intensität x 0 ( Organ k=1,..,K )

• „K-kriterielle lineare Optimierungsaufgabe“

t1 Min, t2 Min, .. , tK Min

( es existiert i. A. keine „Nullösung“ )

zurück

Seite 28

Ergebnisdatenbank

Generierung einer Datenbank mit– Setup-Parametern

– Visualiserungen• Isodosen• DVHs

– t-Vektoren

– Nachbarschaftsstruktur

– intelligenter Online-Suchhilfe

zurück

Isodosen:

Seite 29

Durchführung:Multileaf Collimator

Idee: Benutze dünne Metall“blätter“, hoch genug um die Bestrahlung abzublocken

0.5-1cm

5-7cm

zurück

Seite 30

Linke Blätter Rechte Blätter

zurück

Seite 31

Patientenblick

Quelle: Mitsubishi

zurück

Seite 32

Multileaf Collimators: Mechanik

zurück

Seite 33

Multileaf Collimator Ein Beispiel

+

Maximale Größe des Bestrahlungsfeldes

1 2 1 00 0

Setup für 1. Zeiteinheit

1 1 0 00 0

Setup für 2. Zeiteinheit

0 1 1 00 0

eine Zeile der Intensitätsmatrix

eine Zeile der ersten Reliefmatrix

eine Zeile der zweiten Reliefmatrix

zurück

Seite 34

Verschiedene Aufteilung in Reliefmatrizen

10

00*5

01

00*3

00

10*3

00

01*5

53

35

Beam-on Zeit: 16Setups : 4

Beam-on Zeit: 5Setups: 2

10

01*2

11

11*3

53

35

zurück

Seite 35

Mathematische Modellierung:Ganzzahlige Optimierung

sonst 0

wirdbestrahlt zur Zeit t i Kanalin j Spalte die falls 1

otherwise 0

steht zur Zeit t j Spalte von links i Kanalin Blatt rechte das falls 1

sonst 0

steht zur Zeit t j Spalte von links i Kanalin Blatt linke das falls 1

ijt

ijt

ijt

y

R

L

...

210 5 6 7

Kanal izur Zeit t:

Lijt=2 Rijt=6

Spaltennr. j

yijt = 0 0 1 1 1 0 0

...

zurück

Seite 36

Ganzzahlige Variable beschreiben MLC:

T tRowiR

T tRowiL

Ncells

j

ijt

Ncells

j

ijt

, 1 (1b)

, 1 (1a)

1

1

1

1

In jedem Kanal und zu jeder Zeit gibt es ein linkes und einrechtes Blatt:

zurück

Seite 37

Ganzzahlige Variable beschreiben MLC:

Kollisionen zwischen benachbarten Blätterpaaren werdenausgeschlossen:

|| 1:}1,,1{

,, * * (2) 1

1

1

1

Rowkiiik

T tRowiRjLjNcells

j

kjt

Ncells

j

ijt

zurück

Seite 38

Ganzzahlige Optimierung: Formulierung I

T tCol j,Rowi LR y (7b)

T tCol j,Rowi RL y (7a)

T tRowi 0 y (6b)

T tRowi 0 y (6a)

T tCol j,Rowi R yy (5)

T tCol j,Rowi L yy (4)

Col j,Rowi I y (3)

Row kiiik

T t,Rowi Rj Lj (2)

T tColi R (1b)

T t,Rowi L (1a) s.t.

szeitBehandlung

tjitjiijt

ijtijtijt

ti

tNcellsi

ijtijttji

ijttjiijt

ij

Ntime

t

ijt

Ncells

1j

kjt

Ncells

1j

ijt

Ncells

1j

ijt

Ncells

1j

ijt

,

,

,

,

,

,

||1:}1,,1{

,**

,1

1

min

,1,,1,

,0,

,1,

,1,

,1,

1

11

1

1

zurück

Seite 39

Beispiel: Transport von Gefahrengütern

• Wieviel Einheiten eines Gutes 1 bzw. 2 kann man transportieren, wenn

pro Einheit: Gut 1 Gut 2

Profit: 2 7 (Mill. Euro)

Kapazität: 1 4 (Platzeinheiten)

Gefahrenwert: 9 -4 ( -10 bis +10 Skala)(additiv)

Dabei Gesamtkapazität: 14

Gefahrenhöchstwert: 36

zurück

Seite 40

Mathematisches ModellGanzzahliges, Lineares Programm

Maximiere 2x1 + 7x2

unter den

Nebenbedingungen 1x1 + 4x2 < 4

9x1 - 4x2 < 36

Vorzeichenbedingungen x1,x2 > 0

Ganzzahligkeitsbedingungen x1,x2 ganzzahlig

pro Einheit: Gut 1 Gut 2 GesamtProfit: 2 7 (Mill. ECUs)Kapazität: 1 4 (Platzeinheiten) 4wissensch. Wert: -9 4 ( -10 bis +10 Skala) 36

zurück

Seite 41

9x1- 4x2 < 36

x1+ 4x2 < 14

Zielfunktion:2x1 + 7x2 = 0

21 43

3

2

1

x1

x2

Maximiere 2x1 + 7x2

unter den

Nebenbedingungen 1x1 + 4x2 < 4

9x1 - 4x2 < 36

Vorzeichenbedingungen x1,x2 > 0

Ganzzahligkeitsbedingungen x1,x2 ganzzahlig

Zielfunktionswert:2x1 + 7x2 =8

Zielfunktionswert:2x1 + 7x2 =25,75

Optimallösung ohne Ganzzahligkeit:x1

*=5, x2*=2.25

zurück

Lösung der Relaxation

Seite 42

21 1 43

3

2

1

x1*=5, x2

*=2.25

x1

x2

x2* > 3

x2* < 2

Partition des Problems in zwei Teilprobleme

zurück

9x1- 4x2 < 36

x1+ 4x2 < 14

Seite 43

21 1 43

3

2

1

Zielfunktion:2x1 + 7x2

x1

x2

Gomory Schnitt117x1 + 108x2 < 788

zurück

9x1- 4x2 < 36

x1+ 4x2 < 14

Seite 44

21 1 43

3

2

1

Zielfunktion:2x1 + 7x2

x1

x2

Ziel: Finde eine Beschreibung der konvexen Hülle der ganzzahligen Lösungen

Zielfunktion:2x1 + 7x2 =25

zurück

9x1- 4x4 < 36

x1+ 4x4 < 14

Seite 45

THE END

zurück